Sets

• Sequence cannot matter

• No multiplicity (things can only appear once)

Cardinality: The number of elements in the set

Notation

• “Roster Notation” : use a pattern that expands to the entire set {1, 2, 3, …}

• $|A|$ : Cardinality AKA number of elements

• “Set Builder Notation” : Prototype : Condition {$n$ : $n\in \mathbb{N}\&n\le 5$}

• A is a subset of B: $A\subset B$, Or including equality (They are the same set): $A\subseteq B$

Intervals

[a,b] = {x:x \in R and a⇐x⇐b}

(a,b) = {x:x \in R and a⇐x⇐b}

Special Sets

• $\mathbb{N}$ : All natural numbers {1, 2, 3, …}

• $\mathbb{Z}$ : All integers {…, -2, -1, 0, 1, 2, …}

• $\mathbb{Q}$ : Rational Numbers {$\frac{a}{b}$ : $a\in \mathbb{Z},b\in \mathbb{N}$} (Incomplete)

• $\mathbb{R}$ : Real numbers

• $0$ : Empty set {}

• Sets that contain other sets: {1, 2, {1, 2}}

Power Set

The set consisting of all possible combinations of all elements of a set.

$\mathcal{P}(A)=\{S:S\le A\}$

“The set of all subsets of A”

$|\mathcal{P}(A)|=2^{|A|}$

Operations

Cartesian Product

$A\times B=\{(a,b):a\in A,b\in B\}$

Set of all the possible ordered pairs.

$|A\times B|=|A|\times |B|$

${\mathbb{R}}^2=\mathbb{R}\times \mathbb{R}$

Compliments

$\mathbb{U}$ : Universal set. Contains “Everything”, but taken to mean whatever is relevant based on context.

$\bar{A}=\{x:x\in U-A\}$

De Morgans’ Laws

$\overline{A\cap B}=\overline{A}\cup \overline{B}$

$\overline{A\cup B}=\overline{A}\cap \overline{B}$

$\neg (x\in N.g(x))\to \exists x\in N.\neg g(x)$

$\forall x\in \mathbb{N}g(x)$: For all x in N, g(x)

$\exists x\in S.P(x)$: There exists an x in S such that p(x)