Sets

A set is an unordered colleciton of distinct objects. The objects in a set are elements or members.

Fields like the Natural numbers, Integers or Real numbers are all sets defined like {0,1,2, ...}.

Operations

• Union. A ∪ B = {x : x in A or x in B}
• Intersection. A ∩ B = {x : x in A and x in B}
• Difference. A \ B = {x : x in A and ¬ in B}
• Can be extended to multiple sets (like large sum notation ∑)
• Cardinality |A| is the size of A, number of elements.
• Subset. A ⊆ B = { for all x in A, x in B}

Two sets are disjoint if they share no elements, or whose intersection is the empty set ø. A family of sets is pairwise disjoint if for any two sets A and B are disjoint.

Notation

For sets A and B, A x B is a cartesian product, with the identity |A x B| = |A||B| (actually like a product of sets). Can be extended to say B^A to mean the set of all functions that map from A->B: { f: A -> B }

So the total number of possible functions is |B| possibilities |A| times for each element a in A. So |B^A| = |B|^|A|

R^2 is the two dimensional space (from linear algebra), or the set of all tuples of real numbers. This can be re-written as R^{0,1}. That is, the set of functions that map 0 or 1 to two Real numbers respectively. (3.14, -5) could be represented as f(0) = 3.14, f(1) = -5, f in R^2.

Set of All Subsets

The power set of A is the set of all subsets, denoted by 2^A. It can be thought of as {0,1}^A, the set of all functions that map an element a in A to either 1 or 0. That is, for every element a in A, we can either include it or exclude it, giving us 2 possiblities per element and 2^|A| subsets in total. Useful as a filter: f(a) = { 1 if a is allowed by f, 0 if not } where 2^A is the set of all subsets of A. This also works nicely with cardinality: |2^A| = 2^|A|