Set

An unordered collection of elements

Notation

Let $A,B$ be sets.

Symbol Name	Notation
Cardinality	$|A|$
Cartesian Product	$A\times B$
Complement	$A^{\prime }$ or $A^C$
Empty Set	$\{\}$ or $\varnothing$
	$A=B$
	$A\cap B$
	$x\in A$
Power Set	$\mathcal{P}(A)$
Subset	$A\subset B$
Superset	$A\supset B$
	$B-A$ or $B\text{textbackslash}A$
Set	$\{\dots \}$
Subset	$A\subseteq B$
Superset	$A\supseteq B$
Symmetric Difference	$A\oplus B$ or $A\Delta B$
	$A\cup B$
Universe	$\mathbb{U}$ or U

Operators

Binary

Equality

Let $A,B$ be sets

$$\begin{array}{c}A=B\\ ⟺\\ \forall x(x\in A⟺x\in B)\\ ⟺\\ A\subseteq B\wedge B\subseteq A\end{array}$$

Intersection

$$A\cap B=\{x|x\in A\wedge x\in B\}$$

Union

$$A\cup B=\{x|x\in A\vee x\in B\}$$

Relative Complement

$$A-B=\{x|x\in A\wedge x\notin B\}$$

Symmetric Difference

Symmetric Difference

$$\begin{array}{rl}A\oplus B& \\ & =(A\cup B)-(A\cap B)\\ & =(A-B)\cup (B-A)\\ & =\{x|(x\in A\vee x\in B)\wedge x\ne (A\cap B)\}\end{array}$$Link to original

Cartesian Product

Cartesian Product

$$A\times B=\{(a,b)|a\in A\wedge b\in B\}$$Link to original

Membership

Object $x$ is an element of the set of $A$

$$x\in A$$

Unary

Cardinality

Cardinality

The quantity of unique elements in a Set.

$$|A|=\text{\# unique elements in }A$$Link to original

Complement

Complement

$$A^{\prime }=\mathbb{U}-A=\{x\in \mathbb{U}|x\notin A\}$$Link to original

Power Set

Power Set

The powerset of the Set $A$, $\mathcal{P}(A)$, is the set of all subsets of $A$

$$\mathcal{P}(A)=\{S|S\subseteq A\}$$Link to original

Countability

Countable

A property of a Set related to its Cardinality.

Countable

• Finite sets are countable
• The set of Positive Integers / Natural Numbers is countable
• Any infinite set with same cardinality as $\mathbb{N}$ is countable
• For countable infinite $S$, $|S|={\aleph }_0$ (aleph-null)

Hilbert’s Grand Hotel

Finite hotel: if all rooms occupied, new guest requires eviction.

Hilbert’s Grand Hotel: countably infinite rooms, all occupied — a new guest can still be accommodated (shift $n\to n+1$), showing $|\mathbb{N}|=|\mathbb{N}\cup \{x\}|$ without eviction.

Cantor’s Diagonalization

Technique proving $\mathbb{Q}$ is countable (diagonal enumeration), and $(0,1)\subset \mathbb{R}$ is uncountable — hence $\mathbb{R}$ is uncountable.

Uncountable

$\mathbb{R}$ is uncountable. Hint: show $(0,1)$ uncountable via diagonal argument, so any superset is uncountable.

Equality and Comparison

Two sets $A,B$ have same cardinality iff $\exists$ bijection $f:A\to B$ ($|A|=|B|$). If $\exists$ Injective $f:A\to B$ then $|A|\le |B|$; if injective but no bijection then $|A|<|B|$.

Link to original