Set Theory

The study of Sets, which are collections of distinct objects.

Fundamentals

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\vee x\in B\}$$

Union

$$A\cup B=\{x|x\in A\wedge 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

Link to original

Subset

A part of a Set; Set A is a subset of B.

Definition

A set $A$ is a subset of $B$ if all elements of A are also elements of B.

$$A\subseteq B⟺\forall x(x\in A⟹x\in B)$$

Proper Subset

$$A\subset B\equiv A\subseteq B\wedge A\ne B$$Link to original

Superset

A Set encompassing/extending another set; Set B is a subset of A.

• A superset is the converse of a Subset. They are defined the same way, but the operands are swapped.
• Exclusively using subsets is favored

Definition

$$B\supseteq A⟺\forall x(x\in A⟹x\in B)$$

Proper Superset

$$B\supset A\equiv B\subseteq A\wedge B\ne A$$Link to original

Set Builder Notation

$$S=\{O|A\wedge B\wedge \dots \}$$

A set with some Object such that $A,B$ etc are true. e.g.

$$\{(x,y)|y=x^2\wedge x\in 2\mathbb{N}\wedge y\in \mathbb{N}\}$$Link to original

Composition

The act of combining the application of multiple Functions into one function.

• Age is a function that maps People to Integers
• GreaterThan18 is a function that maps Integers to Booleans
• GreaterThan18 $\circ$ Age is the Composition of the above functions that maps People to Booleans
  • It is equivalent to applying Age, then applying GreaterThan18
  • It can be thought of as: GreaterThan18 follows Age
  • GreaterThan18 $\circ$ Age = Age(GreaterThan18(…))
• id is the Identity Morphism, which is depicted above to map People to People
  • It exists for all sets, but is omitted for the others

Link to original

Universe

The Universe, Universal Set, or Universe of Discourse, denoted by $\mathbb{U}$ is the Set that contains all the entities one wishes to consider in a given situation.

• denoted mainly by $\mathbb{U}$ but also sometimes by $U,\mathcal{U}$
• ${\mathbb{U}}^{\prime }=\varnothing \wedge {\varnothing }^{\prime }=\mathbb{U}$

Link to original

Venn Diagram

In Set Theory, a Venn Diagram is a diagram that visually demonstrates the relationship between Sets, their overlap, and their relation to the Universe of Discourse

Link to original

Principle of Inclusion-Exclusion

$$\begin{array}{rl}|A_1\cup A_2\cup \cdots \cup A_n|& =\\ \sum _{i=1}^n|A_i|& -\\ \sum _{1\le i<j\le n}|A_i\cap A_j|& +\\ \sum _{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|& -\\ \dots & \\ & \\ +(-1{)}^{n+1}|A_1\cap A_2\cap \cdots \cap A_n|& \end{array}$$

For 2 sets, for example $|A\cup B|=|A|+|B|-|A\cap B|$

For 3 sets, for example $\mid A\cup B\cup C\mid =\mid A\mid +\mid B\mid +\mid C\mid -\mid A\cap B\mid -\mid B\cap C\mid -\mid C\cap A\mid +\mid A\cap B\cap C\mid$ Note that we add $|A\cap B\cap C|$

Link to original

Numbers

Number

An element of a Division Ring, used for measuring, counting, quantifying, etc.

Set Name	Symbol	Description	Examples
Natural Number	$\mathbb{N}$	Counting numbers	$1,2,3,42$
Whole Number	$\mathbb{W}$ or ${\mathbb{N}}_0$	Nonzero Integers	$0,1,2,3,42$
Integer	$\mathbb{Z}$	Natural numbers, their negatives, and zero.	$-5,0,12$
Rational Number	$\mathbb{Q}$	Any number expressible as a fraction $\frac{p}{q}$.	$0.75,\frac{1}{3},-4$
Irrational Number	${\mathbb{Q}}^{\prime }$	Numbers that cannot be fractions (non-repeating decimals).	$\pi ,e,\sqrt{2}$
Real Number	$\mathbb{R}$	All points on the continuous number line ($\mathbb{Q}\cup {\mathbb{Q}}^{\prime }$).	$1.5,\pi ,-22$
Imaginary Number	$\mathbb{I}$	$\mathbb{R}\cdot i$	$1.5i,\pi i,-22i$
Complex Number	$\mathbb{C}$	$a+bi,a,b\in \mathbb{R}$	$2+3i,5,-i$
Quaternion	$\mathbb{H}$	$a+bi+cj+dk,a,b,c,d\in \mathbb{R}$	$1+5i+2j+3k$
Octonion	$\mathbb{O}$	$a+bi+cj+dk+el$ + fm+gn+ho$$a,b,c,d,e,f,g,h \in \mathbb{R}	Takes up too much space

Link to original

Functions

Function

A Mathematical Object that takes a set as an input, and outputs a set

• A mapping between sets
• Maps a Domain to a Codomain
• $f:A\to B$ is the function from $A$ to $B$ where $A$ and $B$ are Sets.
  • $f:A\to B⟺f\subseteq A\times B\wedge \{(a,b)|\forall a\in A,\exists !b\in B((a,b)\in f)\}$

Link to original

Domain

The Set of all inputs to a Function

Link to original

Codomain

The Set of all outputs of a Function

Link to original

Injective

If there is at most one location in the Codomain for every location in the Domain

Link to original

Surjective

If there is a location in the Codomain for every location in the Domain

Link to original

Bijective

If there is exactly one location in the Codomain for every location in the Domain for the Transformation

Link to original