Sets

Based on 21-127 Concepts of Mathematics

• Informal: a set is a collection of objects called elements
• More formal: a set is a collections of objects from the universe of discourse called $\mathscr{U}$, which is supposedly the set of all mathematical objects but not itself.
  • Note quantifiers in Pure Math - Logic refers to $\mathscr{U}$ by default. So for example $\exists x, p(x) \equiv \exists x \in \mathscr{U}, p(x)$.
• Ways to specify a set
  • Implied set - list some elements, hopefully readers learn the pattern. eg.
    • $B = {2,3,5,7,11,13,…}$
  • Set builder notation - specify set using property. ex.
    • $C = {x | x>2}$
    • $D = {x | n \text{ is a prime number}}$

• $\mathbb{N}$ = set of natural numbers (includes 0)
• $\mathbb{Z}$ = set of integers (from german word)
• $\mathbb{Q}$ = set of rational numbers (from italian word) = ${x|x=\frac{a}{b} \text{ for some } a, b \in \mathbb{Z} \text{ with } b \neq 0}$
• $\mathbb{R}$ = set of real numbers
• $\mathbb{C}$ = set of complex numbers

Fun fact: the truth value of $\pi^{\pi}\in \mathbb{R}$ is unknown yet.

Let $a, b \in \mathbb{R}$ with $a < b$, then:

• $(a, b)$ = ${x \in \mathbb{R} \mid a<x<b}$ - open interval
• $[a, b]$ = ${ x \in \mathbb{R} \mid a \leq x \leq b}$ closed interval

Variants on notation

• mixing ${$ and $($ works.
• using infinity works
• but don’t do $[-\infty, \infty]$

• $x \in A$ indicates $x$ is an element of the set $A$
• $x \notin A$ indicates $x$ is not an element of the set $A$

• A set $X$ is non-empty or inhabited iff $\exists x, x \in X$. Otherwise, a set is empty and we write $X = \varnothing$.
• There exists a unique empty set.

Given sets $A$ and $B$, $A$ is a subset of $B$ if $\forall a \in A, a \in B$. We write $A \subseteq B$.

It follows that $\varnothing$ is a subset of all sets because every element of the empty set is vacuously in another other set.

The power set of set $X$ denoted by $\mathscr{P}(X)$ is the set of all subsets of $X$. That is, $\forall U, (U \in \mathscr{P}(X) \Leftrightarrow U \subseteq X)$.

Axiom: sets $A$ and $B$ are equal iff they are subset of each other viz. $(A = B) \Leftrightarrow (A \subseteq B \wedge B \subseteq A)$.

Let’s say we have sets $X$ and $Y$.

• The intersection $X \cap Y = {a \mid a \in X \wedge a \in Y}$.
• The union $X \cup Y = {a \mid a \in X \vee a \in Y}$.
• The relative complement of $X$ in $Y$ is $X \setminus Y = {a \mid a \in X \wedge a \notin Y}$.

Let $I$ be a set. Let $X_{i}$ be a set for all $i \in I$.

• $\displaystyle \bigcap_{i \in I} X_i =\left{a \mid \forall i \in I, a \in X_i\right}$. Essentially it’s the set of things all sets have in common.
• $\displaystyle \bigcup_{i \in I} X_i =\left{a \mid \exists i \in I, a \in X_i\right}$. Essentially it’s the set of things that are in at least one of the sets.

Other notations:

• $\displaystyle \bigcap_{i = 1}^{\infty} X_i$
• $\displaystyle \bigcup_{i = 1}^{\infty} X_i$

Let’s say we have sets $X$ and $Y$.

The cartesian product $X \times Y={p \mid p=(x, y)$ for some $X \in X$ and $y \in Y}$ viz. the set of all ordered pairs of $x$ and $y$ with $x \in X$ and $y \in Y$.

The $k$-fold cartesian product $X^k = { t \mid t = (x_{1}, x_{2}, \dots, x_{k})$ for some elements $x_{1}, x_{2}, \dots, x_{k} \in X}$.

A set can be divided into disjoint chunks. One definition of partition says that given set $X$ and $\mathscr{S} \subseteq \mathscr{P}(X)$, we consider $\mathscr{S}$ to be a partition of $X$ if:

• Every set in $\mathscr{S}$ is non-empty i.e. $\forall U \in \mathscr{S}, U \neq \varnothing$.
• Every element is in one and only one chunk. i.e. $\forall x \in X, (\exists! U \in \mathscr{S}, x \in U)$.

The consequences is that the intersection of any two chunks is empty, and that all the chunks in $\mathscr{S}$ union to our big set $X$.

Note that in Pure Math - Counting, we use finite partition, in which we are allowed to have empty partitions.