Finite Sets

Question 1

What are relations aka, in a database?

Answer 1

Tables

Question 2

Relations are finite sets of tuples. What are three consequences of them being finite sets?

Answer 2

• Order Independent
• No duplicates
• All tuples have the same type

Question 3

Define “extensionality” as it applies to sets.

Answer 3

If two sets have the same elements; they are, by definition, the same set.

Question 4

What are the two principles of sets?

Answer 4

No duplicates - at most one instance of an element in a given set

Order Independant - order does not contribute to the identity of a set

Question 5

How do we write “u is an element of the set v” in notation?

Answer 5

u ∈ v

Question 6

What is the union of two sets?

Answer 6

A set of elements in A and B, i.e. every element from each set

Question 7

What is the intersection of two sets?

Answer 7

Elements that are in both sets A and B.

Question 8

What is the difference of two sets?

Answer 8

The elements that are in set A but not set B

Question 9

How do you write the empty set of type T?

Answer 9

ØT

Question 10

When is A a subset of B?

Answer 10

When all elements in A are also elements in B

Question 11

What is separation in sets, and how do we write it?

Answer 11

A way of picking out subsets

{x ∈ *A *• *P[x] *}

That is, those elements in A that satisfy the predicate P[x].

E.g: {x ∈ A • x>3}

means the set of elements in A that are greater than 3

Very much like predicates in C#

Question 12

What is the powerset of a set, how do we notate it, and what is it’s type?

Answer 12

Set of all subsets of a set

P(S)* *where S is a set.

The type is Set(Set(T)) where T is the type of the elements in the set being powersetted.

E.g. S = {0, 1}

P(S) = { ØN, {0}, {1}, {0, 1} }