97. Sets

Definition: Set

A set is a collection of objects called elements or numbers

Definition: Empty Set $\varnothing$

Set with no elements

Notation

• $𝑎\in 𝑆$: a is an element of S
• $𝑎\notin 𝑆$: a is not an element of S
• $\forall$: for all
• $\exists$: there exists
• $\Rightarrow$: implies
• $\iff$: if and only if

Definition:

1. if $𝐴\subset 𝐵$ if $𝑎\in 𝐴\Rightarrow 𝑎\in 𝐵$

2. $𝐴=𝐵$ if

   $$𝐴\subset 𝐵\wedge 𝐵\subset 𝐴$$
3. $𝐴⊊𝐵$ if $𝐴\subset 𝐵\wedge 𝐴\ne 𝐵$

Set Building Notation

All $𝑥$ satisfying property $𝑃\left(𝑥\right)$

$\left\{𝑥\in 𝐴,𝑃\left(𝑥\right)\right\}$ or $\left\{𝑥,𝑃\left(𝑋\right)\right\}$

Examples

1. $\mathbb{N}=\left\{1,2,3,\dots \right\}$
2. $\mathbb{Z}=\left\{0,1,-1,2,-2,\dots \right\}$
3. $\mathbb{Q}=\left\{\frac{𝑚}{𝑛}:𝑚,𝑛\in \mathbb{Z}𝑛\ne 0\right\}$
4. Odd numbers: $\left\{2𝑚-1:𝑚\in \mathbb{N}\right\}$

Definition

1. Union: $𝐴\cup 𝐵=\left\{𝑥:𝑥\in 𝐴\vee 𝑥\in 𝐵\right\}$
2. Intersection: $𝐴\cap 𝐵.=\left\{𝑧:𝑥\in 𝐴\wedge 𝑥\in 𝐵\right\}$
3. Difference: $𝐴\backslash 𝐵=\left\{𝑥:𝑥\in 𝐴\wedge 𝑥\notin 𝐵\right\}$
4. Complement: ${𝐴}^{𝐶}=\left\{𝑥:𝑥\notin 𝐴\right\}$
5. Disjount: $𝐴\cap 𝐵=\varnothing$

De Morgan

If A, B, C are sets, then:

1. ${\left(𝐵\cup 𝐶\right)}^{𝐶}={𝐵}^{𝐶}\cap {𝐶}^{𝐶}$
2. ${\left(𝐵\cap 𝐶\right)}^{𝐶}={𝐵}^{𝐶}\cup {𝐶}^{𝐶}$
3. $𝐴\backslash \left(𝐵\cup 𝐶\right)=\left(𝐴\backslash 𝐵\right)\cap \left(𝐴\backslash 𝐶\right)$
4. $𝐴\backslash \left(𝐵\cap 𝐶\right)=\left(𝐴\backslash 𝐵\right)\cup \left(𝐴\backslash 𝐶\right)$

Proof

Let B, C be sets.

We want to prove that:

Since to prove the equality of two sets we need to show that Equation 1 holds:

We need to show that:

and

WTS Equation 2:

Let

Then

Thus, ${\left(𝐵\cup 𝐶\right)}^{𝐶}\subset {𝐵}^{𝐶}\cap {𝐶}^{𝐶}$

WTS Equation 3:

Let

Then

Thus, ${𝐵}^{𝐶}\cap {𝐶}^{𝐶}\subset {\left(𝐵\cup 𝐶\right)}^{𝐶}$

Thus, ${𝐵}^{𝐶}\cap {𝐶}^{𝐶}={\left(𝐵\cup 𝐶\right)}^{𝐶}$

Theorem: Induction

$\mathbb{N}=\left\{1,2,3,\dots \right\}$ has an ordering

Axiom: Well ordering property

If $𝑆\subset \mathbb{N}$ and $𝑆\ne \varnothing$ then $𝑆$ has a least element: i.e., $\exists 𝑥\in 𝑆𝑠.𝑡.𝑥\le 𝑦\forall 𝑦\in 𝑆$

Let $𝑃\left(𝑛\right)$ be a statement depending on $𝑛\in \mathbb{N}$. Assume:

1. (Base Case) $𝑃\left(1\right)$ is True
2. (Induction Step) If $𝑃\left(𝑚\right)$ is True, then $𝑃\left(𝑚+1\right)$ is True

Then $𝑃\left(𝑛\right)$ is true for all $𝑛\in \mathbb{N}$

Proof

Let $𝑆=\left\{𝑛\in \mathbb{N}:𝑃\left(𝑛\right)\text{is not True}\right\}$

WTS: $𝑆=\varnothing$

We will prove this by contradiction

(Assume the negation of the statement $𝑆\ne \varnothing$ and derive a false statement. Rules of logic say that $𝑆\ne \varnothing$ is false.)

Suppose $𝑆\ne \varnothing$, by the well ordering property (WOP) of $\mathbb{N}$, $𝑆$ has a least element $𝑥\in 𝑆$. Since $𝑃\left(1\right)$ is True (assumption), $1\notin 𝑆\to \Rightarrow 𝑥\ne 1$, this particular $𝑥>1$. Since $𝑥$ is the least element of $𝑆$ and $𝑥-1<𝑥$, $𝑥-1\notin 𝑆$. Thus, by the definition of $𝑆$, $𝑃\left(𝑥-1\right)$ is True. By the second property of induction (Induction Step) $\Rightarrow 𝑃\left(𝑋\right)$ is True $\Rightarrow 𝑥\notin 𝑆$.

From $𝑆\ne \varnothing$, we conclude $\exists 𝑥\in \mathbb{N}$, $𝑥\in 𝑆$ and $𝑥\notin 𝑆$. Contradiction.

Thus, $𝑆=\varnothing$

Using Induction

We want to prove $\forall 𝑛\in \mathbb{N},𝑃\left(𝑛\right)$ is True, we need to do 2 things:

1. Prove base case $𝑃\left(1\right)$
2. Prove, if $𝑃\left(𝑚\right)$ is True, $𝑃\left(𝑚+1\right)$ is True

Theorem

$𝑃\left(𝑛\right)$

$\forall 𝑐\ne 1,\forall 𝑛\in \mathbb{N}$,

Proof

Prove Equation 4 by induction: 1) (Basic Case)

2) (Induction Step)

We want to prove Equation 4 holds for $𝑛=𝑚+1$

We have:

Thus, Equation 4 holds for $𝑛=𝑚+1$. So by induction, Equation 4 holds for all $𝑛\in \mathbb{N}$

Theorem

If $𝑐\ge -1$, then $\forall 𝑛\in \mathbb{N}$,

Proof (By Induction)

1) (Base Case)

So, Equation 5