## 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|