1.1: Sets

• 1.1.1: Extensionality

  When we consider sets, we don’t care about the order of their elements, or how many times they are specified.

• 1.1.2: Subsets and Power Sets

  If every element of a set $A$ is also an element of $B$, then we say that $A$ is a subset of $B$. The set consisting of all subsets of a set $A$ is called the power set of $A$.

• 1.1.3: Some Important Sets

  Important sets include the natural ($\mathbb{N}$), integer ($\mathbb{Z}$), rational ($\mathbb{Q}$), and real ($\mathbb{R}$) numbers, but also strings ($X^*$) and infinite sequences ($X^\omega$) of objects.

• 1.1.4: Unions and Intersections

  The union of two sets $A$ and $B$, written $A \cup B$, is the set of all things which are elements of $A$, $B$, or both. The intersection $A \cap B$ of two sets is the set of elements they have in common.

• 1.1.5: Pairs, Tuples, Cartesian Products

  It follows from extensionality that sets have no order to their elements. So if we want to represent order, we use ordered pairs $\langle x, y \rangle$.

• 1.1.6: Russell’s Paradox

  Some properties do not define sets. If they all did, then we would run into outright contradictions. The most famous example of this is Russell’s Paradox.

• 1.1.7: Summary