Sets and Their Properties

Power Sets

• A power set (2^S) is the set of all subsets of a given set (S).
• Example: The power set of {a, b} is {{}, {a}, {b}, {a, b}}.
• The empty set's power set is {{}}.
• The size of the power set (|2^S|) is 2^|S|, where |S| is the size of set S.

Partitions

• A partition of a set (S) is a collection of non-overlapping subsets that together cover the entire set.
• Each element in S must be in exactly one subset of the partition.
• The empty set (∅) is not part of a partition.
• S can be partitioned into subsets. e.g. {{a,c}, {b,d,e}, {f}} is a partition of {a,b,c,d,e,f}.
• A set can be partitioned into itself {{a,b,c,d,e,f}} is a partition of {a,b,c,d,e,f}.
• A set can be partitioned into sub-sets {{a,b,c}, {d,e,f}} is a partition of {a,b,c,d,e,f}.

Ordered Pairs

• An ordered pair (x, y) is a pair where the order of the elements matters.
• (x, y) ≠ (y, x) if x ≠ y.

Cartesian Product

• The Cartesian product (A x B) of two sets A and B is the set of all ordered pairs (x, y) where x is in A and y is in B.
• Example: {a} x {b, c} = {(a, b), (a, c)}.
• The Cartesian product can also be extended to more than two sets—for example, A x B x C results in ordered triples.
• Example: {a} x {b, c} x {d} = {(a, b, d), (a, c, d)}.
• The Cartesian product is often presented using nested parentheses (e.g., (A x B) x C); however, often the outer parentheses can be omitted for clarity and readabilty.