Set Theory and Induction

Basic Set Theory Definitions

  • What does $x ∈ A$ mean?

    • $x$ is an element of set $A$.

  • What does $x ∉ A$ mean?

    • $x$ is not an element of set $A$.

  • Define the empty set.

    • The empty set $ ext{∅}$ contains no elements.

  • Is $ ext{{∅}} = ext{{ extnormal{{{∅}}}}}$?

    • No. $ ext{{{∅}}}$ has one element (the empty set), whereas $ ext{∅}$ has zero elements.

  • Define subset.

    • $A ⊆ B$ means every element of $A$ is also in $B$.

  • How do you prove $A ⊆ B$?

    • Assume $x ∈ A$, show $x ∈ B$. Therefore $A ⊆ B$.

  • When are two sets equal?

    • $A = B$ if and only if $A ⊆ B$ and $B ⊆ A$.

Set Operations

  • Define union.

    • $A ∪ B = {x : x ∈ A \text{ or } x ∈ B}$.

  • Define intersection.

    • $A ∩ B = {x : x ∈ A \text{ and } x ∈ B}$.

  • When are two sets disjoint?

    • When $A ∩ B = ext{∅}$.

  • Define set difference.

    • $A \ B = {x : x ∈ A \text{ and } x ∉ B}$.

  • Define complement.

    • $A^{ ext{ᶜ}} = U \ A$, where $U$ is the universe of discourse.

  • State De Morgan’s Laws.

    • $(A ∪ B)^{ ext{ᶜ}} = A^{ ext{ᶜ}} ∩ B^{ ext{ᶜ}}$

    • $(A ∩ B)^{ ext{ᶜ}} = A^{ ext{ᶜ}} ∪ B^{ ext{ᶜ}}$.

  • Define power set.

    • $𝒫(X)$ is the set of all subsets of $X$.

  • How many elements are in $𝒫(X)$ if $|X| = n$?

    • $|𝒫(X)| = 2^{n}$.

  • Define Cartesian product.

    • $A × B = {(a,b) : a ∈ A \text{ and } b ∈ B}$.

  • What happens if $A$ or $B$ is empty in a Cartesian product?

    • $A × B = ext{∅}$.

Principles of Mathematical Induction

  • State the base case in induction.

    • The first value of $n$ where $P(n)$ is proven true.

  • What is the inductive hypothesis?

    • The assumption that $P(k)$ is true for an arbitrary $k$.

  • What is the inductive step?

    • Show $P(k) → P(k+1)$ using the inductive hypothesis.

  • Final sentence of induction.

    • Thus, by induction, $P(n)$ holds for all $n ≥ n₀$.

  • What is strong induction?

    • In strong induction, you assume $P(n₀),…,P(k)$ to prove $P(k+1)$.

  • When do we use strong induction?

    • When the proof depends on multiple previous values, not only $k-1$.

  • Induction mistake: what must ALWAYS be proved first?

    • The base case.

Examples of Induction

  • How do you show where the inductive hypothesis is used?

    • Explicitly cite it: "By the inductive hypothesis, …".

  • Induction example: sum of first $n$ integers.

    • $1 + 2 + … + n = \frac{n(n+1)}{2}$.

  • Induction example: $2^{n} ≥ n + 1$ (for $n ≥ 0$).

    • Use induction: base $n=0$, then multiply both sides of inductive hypothesis by $2$.

  • Strong induction example: every integer $≥ 2$ factors into primes.

    • Base case: 2 is prime; composite case uses factors less than $n$.

  • Why does $|𝒫(X)| = 2^{n}$?

    • Each element has 2 choices: in or out → $2 × 2 × … × 2$ (repeated $n$ times).

  • How to prove $(A ∩ B)^{ ext{ᶜ}} = A^{ ext{ᶜ}} ∪ B^{ ext{ᶜ}}$?

    • Element chase using “not (P and Q)”.

  • Proof template for $A = B$.

    • Show $A ⊆ B$ and $B ⊆ A$.

  • Subset proof template.

    • Let $x ∈ A$. Show $x ∈ B$. Conclude that $A ⊆ B.