Class Description

Textbook: The Tools of Mathematical Reasoning

Real Numbers, Rational Numbers, and Integers

• $\mathrm{\forall }$ = “for all”, “for each”
• $\mathrm{\exists }$ = “for some”, “there exists”
• $\mathbb{R}$ = Set of all Real Numbers

Properties of the Real Numbers

1. $\mathrm{\forall }x,y,z\in \mathbb{R}(x+y)+z=x+(y+z)$
2. $\mathrm{\forall }x\in \mathbb{R}x+y=y+x$
3. $\mathrm{\exists }0\in \mathbb{R}\text{ such that }\mathrm{\forall }x\in \mathbb{R},x+0=x$
4. $\mathrm{\forall }x\in \mathbb{R}\mathrm{\exists }(-x)\in \mathbb{R}x+(-x)=0$
5. $\mathrm{\forall }x,y,z\in \mathbb{R}(xy)z=x(yz)$ Associative
6. $\mathrm{\forall }x,y\in \mathbb{R},xy=yx$ Commutative
7. $\mathrm{\exists }1\in \mathbb{R}$ such that $\mathrm{\forall }x\in \mathbb{R},x\cdot 1=x$
8. For any nonzero real number x, $\mathrm{\exists }\frac{1}{x}\in \mathbb{R}$ such that $x\cdot \frac{1}{x}=1$
9. $\mathrm{\forall }x,y,z\in \mathbb{R},x(y+z)=xy+xz$
10. $\mathrm{\forall }x,y,z\in \mathbb{R}(y+z)x=yx+zx$
11. The sum or product of any two real numbers is also a real number.

Proposition 1

Proposition

Let $x\in \mathbb{R}$, then $x\cdot 0=0$

Proof

By property 3, $0+0=0$.
Multiply both sides by x to get $x\cdot (0+0)=x\cdot 0$
$$x\cdot 0+x\cdot 0=x\cdot 0$$

Property 4 $\mathrm{\exists }-(x\cdot 0)$ such that $x\cdot 0+-(x\cdot 0)=0$
$$(x\cdot 0+x\cdot 0)+-(x\cdot 0)=(x\cdot 0)+-(x\cdot 0)$$
$$x\cdot 0+(x\cdot 0+(-x\cdot 0))=0$$
$$x\cdot 0+0=0$$
$$x\cdot 0=0$$

Proposition 2

Proposition

Let $a,b\in \mathbb{R}$. Assume that $ab=0$. Then $a=0$ or $b=0$

Proof

Either $a=0$ or $a\ne 0$

If $a=0$, then there is nothing to prove. So we shall suppose $a\ne 0$, and try to prove $b=0$

$$ab=0\text{ and }a\ne 0$$
By property 8 there is a real number $\frac{1}{a}$ so that $\frac{1}{a}=1$
$$\frac{1}{a}(ab)=\frac{1}{a}\cdot 0$$
$$(\frac{1}{a}\cdot a)b=\frac{1}{a}\cdot 0$$
$$1\cdot b=0$$
Hence $b=0$. So $a=0$ or $b=0$.

Set of Integers

$\mathbb{R}$ has a subset called the set of integers, denoted by $\mathbb{Z}$
$$\mathbb{Z}=\{0,\pm 1,\pm 2,\pm 3,\pm 4,\pm 5\dots \}$$

• $\mathbb{Z}$ is closed under addition and multiplication
• If $x\in \mathbb{Z}$, and $y\in \mathbb{Z}$, then $x+y\in \mathbb{Z}$ and $xy\in \mathbb{Z}$

Abbreviations

In $\mathbb{R}$, we can abbreviate $a\cdot \frac{1}{b}$ by $\frac{a}{b}$ if $b\ne 0$. $a+(-b)$ by $a-b$.

Set of Rational Numbers

$$\mathbb{Q}=\{\frac{a}{b}:a,b,\in \mathbb{Z}\text{ and }b\ne 0\}$$

• $\mathbb{Q}$ is a subset of $\mathbb{R}$

Question

• Suppose $x,y\in \mathbb{Q}$. Is it true that $x+y\in \mathbb{Q}$?

Answer

Since $x\in \mathbb{Q}$, there are integers $a$ and $b$ ($b\ne 0$) so that $x=\frac{a}{b}$. Similarly there are integers $c$ and $d$ ($d\ne 0$) so that $y=\frac{c}{d}$.
$$\frac{x}{y}=\frac{a}{b}+\frac{c}{d}=\frac{ad}{bd}+\frac{bc}{bd}$$
$$=\frac{ad+bc}{bd}$$

• $b\ne 0$ and $d\ne 0$, so by Prop 2, $bd\ne 0$.

• $b\in \mathbb{Z}\text{ and }d\in \mathbb{Z}$, so $bd\in \mathbb{Z}$ by closure.

• $a\in \mathbb{Z}$ and $d\in \mathbb{Z}$, so $ad\in \mathbb{Z}$ by closure.

• $b\in \mathbb{Z}$ and $c\in \mathbb{Z}$, so $bc\in \mathbb{Z}$ by closure.

• One more use of closure shows that $ad+bc\in \mathbb{Z}$

• Hence $x+y$ is the ratio of two integers, with non-zero denominator.

• Thus $x+y\in \mathbb{Q}$. QED

• Let $x,y\in \mathbb{Q}$. Is it true that $xy\in \mathbb{Q}$? Answer: Yes.

6.1: Division Algorithm and Well Ordering Principle

Let $\mathbb{N}=\{0,1,2,3,4,\dots \}$

Well Ordering Principle

Every nonempty subset of sequence of non-negative integers has a least element. Example: $\mathbb{N}$ has a least element.

Division Algorithm

Statement

Let $a\in \mathbb{Z},b\in \mathbb{Z}$ and let $b>0$

There is a unique pair of integers $q$ and $r$ such that $a=bq+r,0\le r<b$

q is the quotient and r is the remainder

Proof

Existence

First we need to prove that $q$ and $r$ exist such that $a=bq+r0\le r<b$. After that we’ll prove that there is only one pair $q$ and $r$ that is unique for a certain $a$ and $b$.

Define a set, $S$, as follows

$$S=\{a-bk:k\in \mathbb{Z},a-bk\in \mathbb{N}\}$$

In order to use the Well Ordering Principle (WOP), we need to show that $S\ne \mathrm{\varnothing }$.

$$\mathrm{\exists }k:k<\frac{a}{b},k\in \mathbb{Z}$$
There is at least one integer less than $\frac{a}{b}$ since $b>0$. If $a<b$, then the least integer would be 0.

$$k<\frac{a}{b}⟹a-bk>a-b\left(\frac{a}{b}\right)$$
$$a-bk>a-a$$
$$a-bk>0$$

Since $k\in \mathbb{Z}$ and $a,b\in \mathbb{Z}$, by closure, $a-bk\in \mathbb{Z}$. Since $a-bk>0$, $a-bk\in S$. Since $S\subseteq \mathbb{N}$, by the WOP, $S$ has a least element.

Now we need to prove that $0\le r<b$.

Let $r$ denote the least element of $S$. Then since $r\in S,\mathrm{\exists }q\in \mathbb{Z}:r=a-bq$

Since $r\in S$, we know that $r\in \mathbb{N}=\{0,1,2,3,\dots \}$, so $r\ge 0$.

Now we just need to prove the second part of the inequality, $r<b$. Use a Proof by contradiction and assume the opposite: $r\ge b$.

$$r\ge b⟹r-b\ge 0$$
$$⟹(a-bq)-b\ge 0$$
$$⟹r-b=a-b(q+1)\ge 0$$

If $r-b\ge 0$, then $r-b\in S$. If that were true, $r-b$ would be the least element in S, since $b\in \mathbb{Z},b>0$ and $r\ge 0$. This is a contradiction since $r$ is the least element in $S$, and not $r-b$.

Thus $0\le r<b$.

Uniqueness

Prove that $r$ and $q$ are unique solutions to $a=bq+r$.

Define $r^{\prime }$ and $q^{\prime }$
$$r^{\prime }=b{q}^{\prime }+t,0\le r^{\prime }<b$$
Our goal is to show that $r^{\prime }=r$ and $q^{\prime }=q$.

$$bq+r=a=b{q}^{\prime }+r^{\prime }$$
$$r-r^{\prime }=b(q^{\prime }-q)$$

This means that $b|(r-r^{\prime })$, so b is a multiple of $r-r^{\prime }$.

Also since $0\le r^{\prime }<b$ and $0\le r<b$, $-b<r-r^{\prime }<b$.
$$-b<r-r^{\prime }<b$$
$$-b<b(q^{\prime }-q)<b$$
$$-1<q^{\prime }-q<1$$
Since $q^{\prime }-q\in \mathbb{Z}$, $q^{\prime }-q=0$. So $q^{\prime }=q$.
$$bq+r=b{q}^{\prime }+r^{\prime }$$
$$r=r^{\prime }$$

Using the Division Algorithm

The Division Algorithm can reduce proofs about integers to finitely many cases.

We say that $a|b$, a divides b, if b is a multiple of a. $$\mathrm{\exists }q:b=aq+0,q\in \mathbb{Z}$$

Example

Prove that the square of any integer can be expressed in one of the following forms: $4k+1$ or $4k+0$

$$n\in \mathbb{Z},n=(4q+r),r\in \{0,1,2,3\}$$

Case r = 0

$$n^2=(4q+0{)}^2=16q^2$$
$$n^2=4(4q^2)$$
$$n^2=4k+0,k=4q^2\in \mathbb{Z}\text{ by closure}$$

Case r = 1

$$n^2=(4q+1{)}^2=16q^2+8q+1$$
$$n^2=4(4q^2+2q)+1$$
$$n^2=4k+1,k=4q^2+2q\in \mathbb{Z}\text{ by closure}$$

Case r = 2

$$n^2=(4q+2{)}^2=16q^2+16q+4$$
$$n^2=4(4q^2+4q+1)+0$$
$$n^2=4k+0,k=4q^2+4q+1\in \mathbb{Z}\text{ by closure}$$

Case r = 3

$$n^2=(4q+3{)}^2=16q^2+24q+9$$
$$n^2=16q^2+24q+2(4)+1$$
$$n^2=4(4q^2+6q+2)+1$$
$$n^2=4k+1,k=4q^2+6q+2\in \mathbb{Z}\text{ by closure}$$

Thus since $n^2=4k+1$ or $n^2=4k+0$ for all values of r, we have proven that the square of any integer can be expressed in just those forms.

1.1: Language of Proofs

Proposition

• Proposition: Sentence which has exactly one truth value
  • Not a proposition:
    • $4\cdot 5$ (no verb in sentence)
    • $18|n$ (The truth of falsity depends on the value of $n$)
• Predicate: A sentence whose truth value depends on values assigned to free variables
• Propositions can be combined with logical operators like AND, OR, NOT, IF, THEN, IFF

Implication

$$P⟹Q$$

• P implies Q

• If P then Q

• P is sufficient for Q

• P only if Q

• Q when P

• Q if P

• P is called the hypothesis of the implication

• Q is called the conclusion

$$\overline{)\begin{array}{ccc}p& q& p⟹q\\ T& T& T\\ T& F& F\\ F& T& T\\ F& F& T\end{array}}$$
$$p⟹q\equiv \mathrm{\neg }p\vee q$$

• Converse: $Q⟹P$

• Contrapositive: $\mathrm{\neg }Q⟹\mathrm{\neg }P$

  • Has the same truth table as the regular $P⟹Q$

• Example

  • Theorem:
    $$\text{If }\sum _{n=1}^{\mathrm{\infty }}{a}_n\text{ converges, then }\underset{n\to \mathrm{\infty }}{lim}{a}_n=0$$

  • Contrapositive of Theorem:
    $$\text{If }\underset{n\to \mathrm{\infty }}{lim}{a}_n\ne 0\text{, then }\sum _{n=1}^{\mathrm{\infty }}{a}_n\text{ diverges (Divergence Test)}$$

  • Converse:
    $$\text{If }\underset{n\to \mathrm{\infty }}{lim}{a}_n=0\text{, then }\sum _{n=1}^{\mathrm{\infty }}{a}_n\text{ converges (Not True)}$$

DeMorgan’s Laws & Formulas

Let $P$ and $Q$ be propositions

1. $\mathrm{\neg }(P\vee Q)$ is logically equivalent to $(\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)$
2. $\mathrm{\neg }(P\wedge Q)$ is logically equivalent to $(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$

Proof of 1.
$$\overline{)\begin{array}{cccc}p& q& p\vee q& \mathrm{\neg }(p\vee q)\\ T& T& T& \mathbf{F}\\ T& F& T& \mathbf{F}\\ F& T& T& \mathbf{F}\\ F& F& F& \mathbf{T}\end{array}}$$

$$\overline{)\begin{array}{ccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (\mathrm{\neg }p)\wedge (\mathrm{\neg }q)\\ T& T& F& F& \mathbf{F}\\ T& F& F& T& \mathbf{F}\\ F& T& T& F& \mathbf{F}\\ F& F& T& T& \mathbf{T}\end{array}}$$

Quantifiers

• Universal Quantifier: $\mathrm{\forall }$ = “for any”, “for all”, or “for each”
• Existential Quantifier: $\mathrm{\exists }$ = “there exists”, “for some”
  • $\mathrm{\exists }!$ = “there is a unique” or “there is exactly one”
• Examples
  1. Some positive integers are both perfect squares and perfect cubes
  • $\mathrm{\exists }x\in {\mathbb{Z}}^{+}|(\mathrm{\exists }y\in \mathbb{Z}|x=y^2)\wedge (\mathrm{\exists }w\in \mathbb{Z}|x=w^3)$

Negating Quantifiers

$$\mathrm{\neg }(\mathrm{\forall }xP(x))⟺\mathrm{\exists }x\mathrm{\neg }P(x)$$
$$\mathrm{\neg }(\mathrm{\exists }xP(x))⟺\mathrm{\forall }x\mathrm{\neg }P(x)$$
$$\mathrm{\neg }(\mathrm{\exists }xP(x))⟺\nexists xP(x)$$

Example

$$\mathrm{\forall }x\in \mathbb{R}\mathrm{\exists }k\in \mathbb{R}(x>0\wedge x=k^2)$$
The negation of the above would be
$$\mathrm{\neg }(\mathrm{\forall }x\in \mathbb{R}\mathrm{\exists }k\in \mathbb{R}(x>0\wedge x=k^2))$$
$$\mathrm{\exists }x\in \mathbb{R}\mathrm{\neg }(\mathrm{\exists }k\in \mathbb{R}(x>0\wedge x=k^2))$$
$$\mathrm{\exists }x\in \mathbb{R}\mathrm{\forall }k\in \mathbb{R}\mathrm{\neg }(x>0\wedge x=k^2))$$
Use Demorgan’s laws
$$\mathrm{\exists }x\in \mathbb{R}\mathrm{\forall }k\in \mathbb{R}\mathrm{\neg }(x>0)\vee \mathrm{\neg }(x=k^2)$$

Since $P⟹Q\equiv \mathrm{\neg }P\vee Q$
$$\mathrm{\exists }x\in \mathbb{R}\mathrm{\forall }k\in \mathbb{R}(x>0⟹x\ne k^2)$$

1.2: Direct Proofs

We can assume $P$ to be true and show that $Q$ is true.

2.1: More on Direct Proofs

Basic Properties of Real Numbers

For all real numbers $a$, $b$, and $c$

1. Closure under addition and multiplication: $a+b\in \mathbb{R},ab\in \mathbb{R}$
2. Associative Properties: $(a+b)+c=a+(b+c)$ and $(ab)c=a(bc)$
3. Commutative Properties: $a+b=b+a$ and $ab=ba$
4. Distributive Properties: $a(b+c)=ab+ac$
5. Identities: $0\ne 1,a+0=a,a\cdot 1=a,a\cdot 0=0$
6. Additive Inverses: $\mathrm{\exists }!-a=-1\cdot a:a+(-a)=0$
7. Subtraction: $b-a$ is defined to equal $b+(-a)$
8. Multiplicative Inverses: $a\ne 0⟹\mathrm{\exists }!a^{-1}=\frac{1}{a}:a\cdot a^{-1}=a\cdot \frac{1}{a}=1$
9. Division: $a\ne 0⟹\frac{b}{a}=b\cdot \frac{1}{a}$

Additional Axioms for Real Numbers

1. $\mathrm{\forall }a,b\in \mathbb{R}$ exactly one of $a<b$, $a=b$, or $a>b$ is true
2. $\mathrm{\forall }a,b,c\in \mathbb{R}(A<b)⟹(a+c<b+c)$
3. $\mathrm{\forall }a,b,c\in \mathbb{R}(a<b\wedge c>0)⟹ac<bc$
4. $\mathrm{\forall }a,b,c\in \mathbb{R}(a<b\wedge c<0)⟹ac>bc$
5. $\mathrm{\forall }a,b,c\in \mathbb{R}(a<b\wedge b<c)⟹a<c$ (Transitive)

Counterexamples

The negation of $\mathrm{\forall }x\in S,P(x)$ is $\mathrm{\exists }x\in S,\mathrm{\neg }P(x)$.
To disprove $\mathrm{\forall }x\in S,P(x)$, we need only find one example of an x for which P(x) is false.

Prime Numbers

Definition: $n\in {\mathbb{Z}}^{+}$ is prime the following is true:
$$n\ne 1\wedge (x\in {\mathbb{Z}}^{+}\wedge x|n)⟹(x=1\vee x=n)$$

Double Implications

• To prove $P⟺Q$, you need to prove both $P⟹Q$ and $Q⟹P$

Uniqueness

To prove a property is unique for a certain object, assume that there are two objects with this property $x$ and $y$ and show that they are the same.

Example

Prove the following statement:
$$\mathrm{\exists }x\in \mathbb{R}\mathrm{\forall }y\in \mathbb{R}x+y=y+x=y$$
We will prove that this additive property is unique to just one number.

1. Let $a\in \mathbb{R}$ be such that $a+w=w+a=w,\mathrm{\forall }w\in \mathbb{R}$
2. Let $b\in \mathbb{R}$ be such that $b+w=w+b=w,\mathrm{\forall }w\in \mathbb{R}$

• $a+b=b$ by line 1
• $a+b=a$ by line 2
• Thus we can conclude that $a=b$ and that only one unique number has the additive property we were interested in

2.2: Indirect Proofs

Note: $\therefore$ means therefore and $\because$ means because

Proof by Contradiction

To prove statement $P$ is to assume $\mathrm{\neg }P$ and then derive a statement of the form $Q\wedge (\mathrm{\neg }Q)$. If $\mathrm{\neg }P$ implies a falsehood, then $\mathrm{\neg }(\mathrm{\neg }P)$, which means $P$ itself is true.

Proof by Contrapositive

$$\mathrm{\neg }Q⟹\mathrm{\neg }P⟺P⟹Q$$

2.3: Two Important Theorems

Theorem: $\sqrt{2}$ is irrational

Let $\sqrt{2}$ denote the positive real number $y$ satisfying $y^2=2$.

Suppose BWOC (By way of contradiction),
$$\sqrt{2}\in \mathbb{Q}⟹\mathrm{\exists }a,b\in \mathbb{N}:\sqrt{2}=\frac{a}{b}$$

If we cancel common factors so no integer divides both $a$ and $b$ except $\pm 1$, we can say $\sqrt{2}=\frac{p}{q}$, where $p,q\in \mathbb{Z}$ and they share no common factors.

$$2=\frac{p^2}{q^2}⟹2q^2=p^2$$
$$2|p^2⟹2|p,p=2t,t\in \mathbb{Z}$$
$p$ is even since $p^2$ is even.

$$2q^2=(2t{)}^2$$
$$2q^2=4t^2$$
$$q^2=2t^2⟹2|q^2⟹2|q$$

$2|p\wedge 2|q$, contradicting our choice of $p$ and $q$ sharing no common factors.

Thus $\sqrt{2}\notin \mathbb{Q}$

Greatest Common Divisor (GCD)

Let $a,b\in \mathbb{Z}$ and $a\ne 0\wedge b\ne 0$.
$$S=\{x\in \mathbb{Z}:x|a\wedge x|b\}$$
$S$ is the set of common integer divisors of $a$ and $b$

$$\mathrm{\forall }a,b\in \mathbb{Z}:1\in S⟹S\ne \mathrm{\varnothing }$$
If $|k|>max(a,b)$, then $k\nmid a\wedge k\nmid b$, so $k\notin S$
So $S$ is finite and $S$ has a maximum element.

Define GCD as the following:
$$gcd(a,b)=max(S)$$

If $a=b=0$, we define $gcd(0,0)=0$

Bézout’s Lemma

Lemma: Let $a,b\in \mathbb{Z}$. Then $\mathrm{\exists }m,n\in \mathbb{Z}:gcd(a,b)=am+bn$

Proof

Case 1
$$a=b=0$$
$$gcd(0,0)=0=a\cdot 0+b\cdot 0$$
Case 2
$$a=0\wedge b\ne 0$$
$$gcd(0,b)=|b|$$
Case 3
$$a\ne 0\wedge b=0$$

• Same as Case 2

Case 4
$$T=\{x\in \mathbb{N}:\mathrm{\exists }u,v\in \mathbb{Z}:x=au+bv\}$$
$$a^2+b^2=a(a)+b(b)>0$$
$$a^2+b^2\in \mathbb{T}$$
$$T\ne \mathrm{\varnothing }\wedge T\in \mathbb{N}⟹d=min(T)$$

• By the Well Ordering Principle (WOP), the set $T$ has a minimum element.

• Now we show that $d|a$
  $$a=dq+rq,r\in \mathbb{Z},0\le r<d$$
  $$d\in T⟹\mathrm{\exists }s,t\in \mathbb{Z}:d=as+bt$$

• If $r\ne 0$, then $r\in \mathbb{N}$ and $r=a-dq=a-(as+bt)q=a(1-qs)+b(-tq)$, so that $r\in T$

• But $r<d$, so this would contradict that $d=min(T)$, since $r<d$. Hence $r=0$ must be true and $d|a$. Similarly $d|b$

• We’ve shown that $d|a\wedge d|b$. Now we show that $d$ is the greatest of the common divisors of $a$ and $b$. Let $c$ be another common divisor of $b$ and $a$
  $$c\in \mathbb{Z}:c|a\wedge c|b$$
  $$\mathrm{\exists }w,z\in \mathbb{Z}:q=cz,b=cw$$
  $$d=as+bt=(cz)s+(cw)t$$

• Since $d>0$, this means $c\le d$ since $c$ is a divisor of $d$. So $d$ is the greatest common divisor of $a$ and $b$

Euclid’s Lemma

Let $a,b\in \mathbb{Z}$ and let $p$ be a prime number. If $p|ab$, then $p|a\vee p|b$

Proof

If $p|a$, then we are done, so suppose $p\nmid a$ and try to show $p|b$.
If $p\ne a$ and $p$ is prime, then $gcd(a,p)=1$
By Bézout’s Theorem, $\mathrm{\exists }m,n\in \mathbb{Z}$ so that $am+pn=1$
$$\mathrm{\exists }x\in \mathbb{Z}:px=ab$$
$$b(am+pn)=1b$$
$$(ba)m+pnb=b$$
$$(px)m+pnb=b$$
$$p(xm+nb)=b$$
$xm+nb\in \mathbb{Z}$, so $p|b$, as desired.

2.4: Statements Including Mixed Quantifiers

$\mathrm{\forall }\mathrm{\exists }$

To prove a statement of the form $\mathrm{\forall }x\in S\mathrm{\exists }y\in TP(x,y)$, we let $x$ be an arbitrary element of S, and we try to find $y\in T$ for which $P(x,y)$ is true.

Example

Let ${\mathbb{R}}^{+}$ = set of positive real numbers.
Prove that $\mathrm{\forall }ϵ\in {\mathbb{R}}^{+}\mathrm{\exists }\delta \in {\mathbb{R}}^{+}$ such that $|4x-12|<ϵ$, whenever $0<|x-3|<\delta$.

Proof

Let $ϵ\in {\mathbb{R}}^{+}$ be given.
Choose $\delta =\frac{ϵ}{4}$. Now, if $0<|x-3|<\frac{ϵ}{4}$, then $|4x-12|=4|x-3|<4\cdot \frac{ϵ}{4}=ϵ$
So that $|4x-12<ϵ$ as desired.

$\mathrm{\exists }\mathrm{\forall }$

To prove a statement of the form $\mathrm{\exists }x\in S\mathrm{\forall }y\in TP(x,y)$, we carefully choose $x\in S$ and try to show that $\mathrm{\forall }y\in T$, $P(x,y)$ holds.

Example

Prove that $\mathrm{\exists }x\in \mathbb{Z}$ such that $\mathrm{\forall }y\in \mathbb{R},xy\in \mathbb{Z}$.

Proof

Put $x=0\in \mathbb{Z}$, $\mathrm{\forall }y\in \mathbb{R},x\cdot y=0\cdot y=0\in \mathbb{Z}$, as desired.

Changing the order of mixed quantifiers changes the meaning of the statement.

Epsilon Delta Definition of Limit

We say $\underset{x\to c}{lim}f(x)=L$ if $\mathrm{\forall }ϵ\in {\mathbb{R}}^{+}\mathrm{\exists }\delta \in {\mathbb{R}}^{+}$ such that $(0<|x-c|<\delta )⟹(|f(x)-L|)<ϵ$

Triangle Inequality

$$\mathrm{\forall }x,y\in \mathbb{R},|x+y|\le |x|+|y|$$

Proposition

Suppose $\underset{x\to c}{lim}f(x)=L$ and $\underset{x\to c}{lim}g(x)=M=L$, then $\underset{x\to c}{lim}(f(x)+g(x))=\underset{x\to c}{lim}f(x)+\underset{x\to c}{lim}g(x)$

Proof

We want $\mathrm{\forall }ϵ\in {\mathbb{R}}^{+}\mathrm{\exists }\delta \in {\mathbb{R}}^{+}$, so that $(f+g)(x)-(L+M)<ϵ$ whenever $0<|x-c<\delta$. We let $ϵ\in {\mathbb{R}}^{+}$ be given.

Since $\underset{x\to c}{lim}f(x)=L$, $\mathrm{\exists }\delta \in \mathbb{R}$, so that $f(x)-L<\frac{ϵ}{2}$ whenever $0<|x-c|<{\delta }_1$
Since $\underset{x\to c}{lim}f(x)=M$, $\mathrm{\exists }\delta \in \mathbb{R}$, so that $f(x)-M<\frac{ϵ}{2}$ whenever $0<|x-c|<{\delta }_2$

Let $\delta =min({\delta }_1,{\delta }_2$
$$\mid (f(x)+g(x))-(L+M)\mid =|f(x)+g(x)-L-M|$$
$$|(f(x)-L)+(g(x)-M)|\le |f(x)-L|+|g(x)-M|<\frac{ϵ}{2}+\frac{ϵ}{2}=ϵ$$

3.1: Mathematical Induction

Weak Induction Law

Suppose $S\subseteq \mathbb{N}$ has the following 2 properties

1. $1\in S$
2. $n\in S⟹n+1\in S$

Then $S=\mathbb{N}$

Proof

Let $T$ = set of positive integers NOT in $S$
Suppose BWOC, that $T\ne \mathrm{\varnothing }$
$T\subseteq \mathbb{N}$, so by the Well-Ordering Principle, $T$ has a least element, $m$.
By 1. $m\ne 1$, so $m>1$. Then $m-1\in \mathbb{N}$
$m-1<m$, and $m$ is the least element of $T$, so $m-1\in S$
By 2. $(m-1)+1\in S$, i.e. $m\in S$, but this contradicts our choice of $m$.
So we must have that $T$ is empty, and $S=\mathbb{N}$

Example 1

• Prove that the following is true:
  $$\sum _{i=1}^n\frac{n(n+1)}{2}\mathrm{\forall }n\in \mathbb{N}$$

• Base Case: $n=1$
  $$\sum _{n=1}^{1}i=1=\frac{1\cdot (1+1)}{2}=\frac{2}{2}=1$$

  so the result is true when n = 1

• Inductive Hypothesis: Suppose that $\sum _{i=1}^{m}i=\frac{m(m+1)}{2}$ for some $m\in \mathbb{N}$

  • We will prove that $\sum _{i=1}^{m+1}i=\frac{(m+1)((m+1)+1)}{2}=\frac{(m+1)(m+2)}{2}$

  $$\sum _{i=1}^{m+1}=\left(\sum _{i=1}^{m}i\right)+(m+1)=\frac{m(m+1)}{2}+(m+1)=\frac{(m+1)(m+2)}{2}$$

  • So by induction $\sum _{i=1}^{n}i=\frac{n(n+1)}{2}\mathrm{\forall }n\in \mathbb{N}$

Example 2

• Prove that for all integers $n$ with $n\ge 4$, we have $2^n<n!$

• We proceed by induction

• Base Case: $n=4$
  $$2^4=16$$
  $$4!=1\cdot 2\cdot 3\cdot 4=24$$

• Inductive Hypothesis: Suppose that $2^m<m!$ for some integer $m\ge 4$.

• We show that $2^{m+1}<(m+1)!$
  $$2^{m+1}=2^m\cdot 2^1<m!\cdot 2\underset{\text{since }m\ge 4\text{, so }2<m+1}{\underbrace{<}}m!\cdot (m+1)=(m+1)!$$

• So by induction, $2^n<n!$ for all integers $n\ge 4$

Strong Induction Law

Let $S$ be a subset of $\mathbb{N}$, and suppose $S$ has the following true properties:

1. $1\in S$
2. $(\{1,2,3,4\dots n\}\subseteq S)⟹n+1\in S$
   Then $S=\mathbb{N}$

Proof

Let $T=\{k\in \mathbb{N}:\{1,2,3,4\dots k\}\subseteq S\}$
(If $k\in T$, then $k\in S$, i.e. $T\subseteq S$)
$1\in S$, so $\{1\}\subseteq S$, and so $1\in T$
Now if $k\in T$, then $\{1,2,3\dots k\}\subseteq S$
So by 2. $k+1\in S$
But then $\{1,2,3\dots k,(k+1)\}\in S$, so $k+1\in T$
So $1\in T$ and $(k\in T)⟹(k+1\in T)$. So by Weak Induction, $T=\mathbb{N}$. It follows that $S=\mathbb{N}$

The difference between Weak Induction and Strong Induction is that Weak Induction only assumes $P(n)$ to be true and then shows that $P(n+1)$. However, Strong Induction has a “stronger” assumption by assuming that $P$ is true for all elements before $n$. Strong Induction assumes that $P(1),P(2),\dots P(n)$ are all true. Then Strong Induction shows that $P(n+1)$ is true based on this assumption.

Proposition

Let $n\in \mathbb{N},n\ne 1$. Then $n$ is a product of prime numbers.

Proof

• Base Case: $n=2$
  $2$ is prime, so $2$ is its own prime factorization.

• Inductive Hypothesis: Suppose the numbers $2,3,4,5,6\dots m$ are all products of primes. We must show that $m+1$ is also a product of primes.

• Since $m+1>1$ either $m+1$ is prime or $m+1$ is composite.

• If $m+1$ is prime, it is its own prime factorization.

• Else $m+1$ is composite.
  $$\mathrm{\exists }a,b\in \mathbb{N}s.t.m+1=ab$$
  $$a\in \{2,3,4,\dots m\}$$
  $$b\in \{2,3,4,\dots m\}$$

• By IH (Inductive Hypothesis), $a=\prod _{i=1}^s{p}_i$ and $b=\prod _{j=1}^t{q}_j$ where each $p_i$ and $q_j$ is prime.
  $$m+1=ab=\left(\prod _{i=1}^s{p}_i\right)\left(\prod _{j=1}^t{q}_j\right)$$

This is an example of where strong induction is useful and not weak.

4.1: The Language of Sets

• A Set is a collection of objects
  • Order doesn’t matter
  • No duplicate elements
• $x\in A$ means $X$ is an element of $A$
• $\text{\#}A$ is the cardinality (# of elements)

Set Builder Notation

$$\{varabie:condition\}$$
$$\{x\in A|P(x)\}$$

Subset

If $A$ and $B$ are sets, we write $A\subseteq B$ if $\mathrm{\forall }x\in A,x\in B$

$$A\subseteq B\wedge B\subseteq A\equiv A=B$$

$A⊈B$ means $\mathrm{\exists }x\in As.t.x\notin B$

If we want to prove $A\subseteq B$, then we can use the following skeleton:
Let $x\in A$

Then check that $x$ also satisfies the membership criteria of $B$
Hence $x\in B$

Example

1. Let $A=\{x\in \mathbb{Z}:\mathrm{\exists }a\in \mathbb{Z}$ so that $x=a^2\}$
   Let $B=\{x\in \mathbb{Z}:x\equiv 0(\mathrm{mod}4)\vee x\equiv 1(\mathrm{mod}4)\}$
   Prove $A\subseteq B$
   Let $x\in A$. Then $x\in \mathbb{Z}$, and $\mathrm{\exists }a\in \mathbb{Z}$ so that $x=a^2$.
   By the division algorithm, we can write $a=4q+r,q\in \mathbb{Z},r\in \{0,1,2,3\}$
   If $r=0$, then $x=a^2={\left(4q\right)}^2=4(4q^2)+0$, so $x$ leaves remainder $0$ on division by $4$
   If $r=1$, then $x=a^2={(4q+1)}^2=4(4q^2+2q)+1$, so $x$ leaves remainder $1$ on division by $4$
   If $r=2$, then $x=a^2={(4q+2)}^2=4(4q^2+4q+1)$, so $x$ leaves remainder $0$ on division by $4$
   If $r=3$, then $x=a^2={(4q+3)}^2=4(4q^2+6q+2)+1$, so $x$ leaves remainder $1$ on division by $4$

   In each case $x{\equiv }_0(\mathrm{mod}4)\vee x\equiv 1(\mathrm{mod}4)$. Thus $x\in B$, and it follows that $A\subseteq B$

2. Let $A=\{x\in \mathbb{Z}:\mathrm{\exists }a\in \mathbb{Z}$ so that $x=a^2\}$
   Let $B=\{x\in \mathbb{Z}:x\equiv 0(\mathrm{mod}4)\vee x\equiv 1(\mathrm{mod}4)\}$
   Prove $B⊈A$

   Consider $32\in \mathbb{Z}$
   $32=4(8)+0$, so $32\equiv 0(\mathrm{mod}4)$, and we see that $32\in B$
   $5^2=25<32$, and $6^2=36>32$, so $5<\sqrt{32}<6$, and $32⊈A$

   3. Let $A$ and $B$ be sets. $A=B$, if $(A\subseteq B)\wedge \{B\subseteq A\}$
      Equivalent to $x\in A⟺x\in B$
      Let $C=\{x\in \mathbb{Z}:\text{x is odd}\}$
      Let $D=\{x\in \mathbb{Z}:x\equiv 1(\mathrm{mod}4)\vee x\equiv 3(\mathrm{mod}4)\}$
      Prove $C=D$

   x \in \mathbb{Z}, $and$\exists x = 2q + 1$.Provethat$x = 4t + 1 \lor x = 4+3$.SupposebyBWC,supposethat$x$doesnotleaveremainder3or1.Intheend,$x$isfoundtobeeven,whichisacontradictionsince$x$ is supposed to be odd.

   Prove the converse:

• Let $x\in D$. Then $\mathrm{\forall }\mathbb{Z}$ and $x\equiv 1(\mathrm{mod}4)\vee x\equiv 3(\mathrm{mod}4)$
• If $x\equiv 1(\mathrm{mod}4)$, then $x=4t+1$, for some $t\in 2$
• $x$ is still odd
• If $x\equiv 3(\mathrm{mod}4)$ and $x=4t+3$, for some $t\in \mathbb{Z}$, $x$ is still odd. In both cases, $x\in C$

Proposition

Let $A,B,C$ be sets.
Suppose $A\subseteq B\wedge B\subseteq C$. Is it true that $A\subseteq C$?

What Sets Can’t Be

Let $S$ be a set
Call $S$ normal if $S\notin S$
Let $X=\text{set of all normal sets}$
Is $x$ itself normal?

Midterm 1 Review

Problem 2

Prove that $6|{13}^n-7^n$

Inductive Hypothesis

Strong Induction

Assume that for $k=1,2,3\dots m,6|{13}^k-7^k$,

Weak Induction

Assume that for some $m\in \mathbb{N},6|{13}^m-7^m$

Show that $6|{13}^{m+1}-7^{m+1}$

Problem 3

Show by induction that $\mathrm{\forall }n\in \mathbb{N}\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$

Base Case

$$\sum _{i=1}^1{i}^2=1^2=1,\frac{1(1+1)(2(1)+1}{6}=1$$

Inductive Hypothesis

Weak Induction

Suppose that for some $m\in \mathbb{N},\sum _{i=1}^m{i}^2=\frac{m(m+1)(2m+1)}{6}$
We will prove that $\sum _{i=1}^{m+1}{i}^2=\frac{(m+1)(m+2)(2m+3}{6}$

4.2: Set Operations

Let $A$ and $B$ be sets.

Union

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

Commutative since or is commutative

Intersection

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

Commutative since and is commutative

Relative Complement or Set Difference

$$A-B=\{x:x\in A\wedge x\ne B\}$$

Not commutative

Example

Let $A=\{0,\pi e,i,1\}$
Let $B=\{\pi ,e,\sqrt{2},\sqrt{3}\}$

a. $A\cup B=\{0,\pi ,e,i,1,\sqrt{2},\sqrt{3}\}$
b. $A\cap B=\{\pi ,e\}$
c. $A-B=\{0,i,1\}$

Universal Set

$U-A=A^C$

Proposition

1. $A\cup B=B\cup A$
2. $a\cap B=B\cap A$
3. $(A\cup B)\cup C=A\cup (B\cup C)$
4. $(A\cap B)\cap C=A\cap (B\cap C)$
5. $A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$
6. $A\cup \mathrm{\varnothing }=A$
7. $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
8. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Proof of 8

$$A\cap (B\cup C)=\{x:x\in A\wedge x\in B\cup C\}$$
$$=\{x:x\in A\wedge (x\in B\vee x\in C)\}$$
$$=\{x:(x\in A\wedge x\in B)\vee (x\in A\wedge x\in C)\}$$
$$=(A\cap B)\cup (A\cap C)$$

Cardinality

If $A$ and $B$ are finite sets, then $\text{\#}(A\cup B)=\text{\#}A+\text{\#}B-\text{\#}(A\cup B)$

Cartesian Product

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

Power Set

If $X$ is a set, then $P(X)=\{A:A\subseteq X\}$ is called the power set

Example

$$x=\{a,b\}$$
$$P(X)=\{\mathrm{\varnothing },\{a\},\{b\},\{a,b\}\}$$

Proposition

Let $A$ and $B$ be sets.
$$(A\subseteq B)⟺(P(A)\subseteq P(B))$$

Proof:

Prove $(A\subseteq B)⟹(P(A)\subseteq P(B))$
$$C\in P(A)⟹C\subseteq A$$
$$A\subseteq B⟹C\subseteq B\text{ by transitivity}$$
$$C\subseteq B⟹C\in P(B)$$

Prove the converse
$$A\subseteq A⟹A\in P(A)$$
$$A\in P(B)⟹A\subseteq B$$

DeMorgan’s Laws

1. $A-(B\cup C)=(A-B)\cap (A-C)$
2. $A-(B\cap C)=(A-B)\cup (A-C)$

Proof of 1

$$x\in A\wedge (x\notin (B\cup C))$$
$$x\in A\wedge \mathrm{\neg }(x\in B\vee x\in C)$$
$$x\in A\wedge x\notin B\wedge x\notin C$$
$$(x\in A\wedge x\notin B)\wedge (x\notin C\wedge x\in A)$$
$$A-B\cap A-C$$

Converse
$$(A-B)\cap (A-C)$$
$$x\in (A-B)\wedge x\in (A-C)$$
$$x\in A\wedge x\notin B\wedge x\in A\wedge x\notin C$$
$$x\in A\wedge \mathrm{\neg }(x\in b\vee x\in C)$$
$$x\in A\wedge x\notin (B\cup C)$$
$$A-B\cup C$$

4.3: Arbitrary Unions and Intersections

$$(A\cup B)\cup C=A\cup (B\cup C)$$
$$(A\cap B)\cap C=A\cap (B\cap C)$$
so we can just write $A\cap B\cap C$ and $A\cup B\cup C$ without parentheses.

Definitions

Let $A_1,A_2,A_3,\dots ,A_n,n\in \mathbb{N}$ be sets

1. $\bigcap _{i=1}^n{A}_i=A_1\cap A_2\cap A_3\cap \dots \cap A_n$
2. $\bigcup _{i=1}^n{A}_i=A_1\cup A_2\cup A_3\cup \dots \cup A_n$

Proposition

Let $n\in \mathbb{N}$, and $B_1,B_2,B_3,\dots B_n$ be sets.

1. $A\cap \left(\bigcap _{i=1}^n{B}_i\right)=\bigcap _{i=1}^n(A\cap B_i)$
2. $A\cup \left(\bigcup _{i=1}^n{B}_i\right)=\bigcup _{i=1}^n(A\cup B_i)$
3. $A-\left(\bigcup _{i=1}^n{B}_i\right)=\bigcap _{i=1}^n(A-B_i)$
4. $A-\left(\bigcap _{i=1}^n{B}_i\right)=\bigcup _{i=1}^n(A-B_i)$

Proof of 2

Base Case: $n=1$
$$\bigcap _{i=1}^1(A\cup B_i)=A\cup B_1=A\cup \left(\bigcap _{i=1}^1{B}_i\right)$$

Inductive Hypothesis:
Suppose that for some $m\in \mathbb{N}$, $A\cup \left(\bigcap _{i=1}^m{B}_i\right)$ holds
Let $B_1,B_2,B_3,\dots B_n$ be sets
$$A\cup \left(\bigcap _{i=1}^{m+1}{B}_i\right)=A\cup (\bigcap _{i=1}^m{B}_i\cap B_{m+1})$$
$$A\cup \left(\bigcap _{i=1}^m{B}_i\right)\cap (A\cup B_{m+1})$$
$$\bigcap _{i=1}^m(A\cup B_i)\cap (A\cup B_{m+1})=\bigcap _{i=1}^{m+1}(A\cup B_i)$$

5.3: Injective and Surjective Functions

Definition

Let $X,Y$ be sets, and let $f:X\to Y$

1. $f$ is one-to-one (1-1) or injective if
   $$(\mathrm{\forall }{x}_1,x_2\in X)[f(x_1)=f(x_2)⟹x_1=x22]$$
   the contrapositive of the above is also true

2. $f$ is onto or surjective if
   $$(\mathrm{\forall }y\in Y)(\mathrm{\exists }x\in X)[y=f(x)]$$

3. $f$ is bijective $f$ is both injective and bijective.

Theorem 5.3.10

Let $X,Y,Z$ be sets. Let $f:X\to Y$ and $g:Y\to Z$

1. If $f$ and $g$ are both 1-1, then $g\circ f$ is also 1-1
2. If $f$ and $g$ are both onto, then $g\circ f$ is also onto
3. If $f$ and $g$ are both bijections, then $g\circ f$ is also a bijection
4. If $g\circ f$ is 1-1, then $f$ is 1-1, but $g$ is not necessarily 1-1
5. If $g\circ f$ is onto, then $g$ is onto, but $f$ is not necessarily onto

5.4: Invertible Functions

Definition

Let $X,Y$ be sets, and let $f:X\to Y$. We say that $f$ is invertible if there exists a function $g:Y\to X$ such that for all $x\in X$ and for all $y\in Y$
$$y=f(x)⟺x=g(y)$$

Proposition 5.4.3

Let $X$ and $Y$ be sets, and let $f:X\to Y$ and $g:Y\to X$. Then $f$ is invertible and $g$ is an inverse function of $f$ iff $g\circ f=I_X$ and $f\circ g=I_Y$

Theorem 5.4.7

Let $X,Y$ be sets and let $f:X\to Y$

1. $f$ is invertible iff $f$ is a bijection
2. If $f$ is invertible, then its inverse function is unique

7.1: Relations

Definitions

Let $A$ and $B$ be sets, and let $R\subseteq A\times B$ be a relation from $A$ to $B$. For $a\in A$ and $b\in B$,

$$aRb\text{ iff }(a,b)\in R$$
$$a\mathrm{R̸}b\text{ iff }(a,b)\notin R$$

7.2: Equivalence Relations

Definition

Let $\sim$ is a relation on a set $A$

1. $\sim$ is reflexive if $(\mathrm{\forall }a\in A)(a\sim a)$
2. $\sim$ is symmetric if $(\mathrm{\forall }a,b\in A)(a\sim b⟹b\sim a)$
3. $\sim$ is transitive if $(\mathrm{\forall }a,b,c\in A)[(a\sim b\wedge b\sim c)⟹a\sim c]$
4. $\sim$ is an equivalence relation if $\sim$ is reflexive, symmetric, and transitive

8.1: Introduction to Finite and Infinite Sets

$$A_m=\{1,2,\dots ,m\}=\{i\in \mathbb{N}:i\le m\}$$
$$A_0=\mathrm{\varnothing }$$

Definition 8.1.2

1. $X$ is equinumerous with $Y$, denoted $X\approx Y$, if there exists a bijection $f:X\to Y$

2. $X$ is finite if $X=\mathrm{\varnothing }$ or there exists $m\in \mathbb{N}$ such that $A_m\approx X$. In other words there exists a bijection $f:\{1,2,3,\dots ,m\}\to X$

3. If $A_m\approx X$, then the cardinality of $X$ is $n$, denoted as $\mathrm{\#}X=n$. We define $\mathrm{\#}\mathrm{\varnothing }=0$

4. We say $X$ is infinite if $X$ is not finite.

$\approx$ is an equivalence relation on the collection of all nonempty sets.

Example

Show $\mathbb{N}\approx \mathbb{Z}$

First, define $f:\mathbb{N}\to \mathbb{Z}$ for all $n\in \mathbb{N}$
$$f(n)=\{\begin{array}{ll}\frac{n}{2}& \text{ n is even }\\ \frac{-(n-1)}{2}& \text{ n is odd }\end{array}$$

Show $f$ is 1-1.
Define $n_1,n_2\in \mathbb{N}$ and suppose $f(n_2)=f(n_1)$
If both are even, then
$$\frac{n_1}{2}=\frac{n_2}{2}⟹n_1=n_2$$
If both $n_1$ and $n_2$ are odd,
$$\frac{-(n_1-1)}{2}=\frac{-(n_2-1)}{2}$$
One can’t be odd and one even.

Show $f$ is onto.
Suppose $n\in \mathbb{Z}$ If $n\ge 1$, then $$f(2n)=\frac{2n}{2}=n$$
If $n\le 0$
$$f(-2n+1)=\frac{-(-2n+1)-1}{2}=n$$
$n\in im(f)\mathrm{\forall }n\in \mathbb{Z}$, so $f$ is onto.

8.2: Finite Sets

Recall: Let $A$ be a set. $\mathrm{\forall }n\in \mathbb{N}$, let $I_n=\{1,2,3,\dots n\}$

1. We say $A$ is finite if $A=\mathrm{\varnothing }$ or $\mathrm{\exists }n\in Ns.t.\mathrm{\exists }f:A\to I_n$ (bijection)
   $$\mathrm{\#}A=0\text{ or }\mathrm{\#}A=n$$

2. Every subset of a finite set is finite.

3. If $A$ and $B$ are finite sets, and $A\cup B=\mathrm{\varnothing }$, then $\mathrm{\#}(A\cup B)=\mathrm{\#}A+\mathrm{\#}B$

Pigeonhole Principle

If $n+1$ or more pigeons are placed into $n$ pigeonholes, then at least one pigeonhole will contain more than 1 pigeon

Example 1

Choose 5 points interior to a 2m by 2m square. Prove that among these 5 there is a pair such that the distance between the two points in the pair is $\le \sqrt{2}$ m.

Answer: Divide square into four $1\times 1$ square. Notice that there must be one square with 2 points. The greatest distance between any two points in one of the sub squares is just the diagonal $\sqrt{2}$.

Example 2

Show there is a multiple of $7$ whose decimal digits are all 1’s or 0’s

Consider $1,11,111,1111,11111,111111,1111111,11111111$
2 numbers on this list must leave the same remainder upon division by $7$

Say there are

$$a_j=\underset{\text{j-ones}}{\underbrace{111\dots 1}}$$

$$a_k=\underset{\text{k-ones}}{\underbrace{111\dots 1}}k>j$$

Then $7|a_k-a_j$ since $a_k\equiv a_j\mathrm{mod}7$
Thus the $a_k-a_j$ have only 0 and 1 as digits.

More on Finite Sets

1. Suppose $A_1,A_2,A_3,\dots ,A_n$ are pairwise disjoint sets ($A_i\cap A_j=\mathrm{\varnothing },\text{ whenever }i\ne j$)
   Then $\mathrm{\#}\left({\cup }_{i=1}^n{A}_i\right)=\sum _{i=1}^n\left(\mathrm{\#}{A}_i\right)$

2. Let $A$ and $B$ be finite sets. Then $\mathrm{\#}(A\cup B)=\mathrm{\#}A+\mathrm{\#}B-\mathrm{\#}(A\cap B)$

$$\mathrm{\#}(A\times B)=(\mathrm{\#}A)\cdot (\mathrm{\#}B)$$

8.3: Infinite Sets

Definitions

1. The set $X$ is denumerable or enumerable or countably infinite if there is a bijection $f:\mathbb{N}\to X$ and $f$ is onto and 1-1.
   $$\mathbb{N}\approx X$$
2. The set $X$ is countable if $X$ is finite or denumerable.
3. The set $X$ is uncountable if $X$ is not countable, if $X$ is infinite and not denumerable

Theorem

Let $A$ be a nonempty set. Suppose $g:\mathbb{N}\to A$ is surjective. Then $A$ is countable.

Proof

Either $A$ is finite or it is not

If $A$ is finite, there is nothing to prove, since $A$ is obviously countable. So suppose $A$ is infinite.

We must construct a bijection from $\mathbb{N}\to A$ to show that $A$ is countable (countably infinite).

Put $f(1)=g(1)$

Suppose inductively, that we have defined $f(1),f(2),f(3),\dots ,f(n)$ so that $f(i)\ne f(j)$ whenever $i\ne j$

$$i,j\in \{1,2,3,\dots ,n\}$$
$$\{g(1),g(2),g(3),\dots ,g(n)\}\subseteq \{f(1),f(2),f(3),\dots ,f(n)\}$$

Define $f(n+1)$

$B_n=\{f(1),f(2),f(3)\dots ,f(n)\}$ is finite and $A$ is infinite, so $aB$ is nonempty

Then $X=\{m\in \mathbb{N}:g(m)\notin B_n\}$ is also nonempty, since $g$ is surjective.

Then $X$ is a nonempty subset of $\mathbb{N}$. Then by the Well-Ordering Principle, $X$ has a least element, say $m_0=min(X)$

$$\text{Let }f(n+1)=g(m_0)$$
$$f(n+1)\ne f(i)\mathrm{\forall }i\in \{1,2,3,..,n\}$$

$$\{g(1),\dots ,g(n)\}\subseteq B_n⟹m_0\ge n+1$$

$$g(n+1)\in \{f(1),f(2),f(3),\dots ,f(n),f(n+1)\}$$

$$\mathrm{\forall }a,b\in \mathbb{N},a<b⟹f(a)\ne f(b)$$
So $f$ is injective.

We have defined an injective function $f$ so that we don’t have “duplicate” values of $g(x)$ ($A$) in the codomain of $f$

Let $c\in A$
$$g\text{ is surjective }⟹\mathrm{\exists }x\in \mathbb{N}\text{ s.t. }c=g(x)$$
$$\{g(1),g(2),\dots ,g(x)\}\subseteq \{f(1),f(2),f(3),\dots ,f(x)\}⟹\mathrm{\exists }t\in \{1,2,3,\dots ,x\}\text{ s.t. }g(x)=f(t)$$

$$c\in img(f)⟹f\text{ is surjective }$$

Proposition

Let $A$ be a nonempty countable set. Then $\mathrm{\exists }g:\mathbb{N}\to A$ such that $g$ is surjective.

Proof

Note: $I_m=\{1,2,3,\dots ,m\}$

If $A$ is countably infinite, then $\mathrm{\exists }f:A\to \mathbb{N}$ which is bijective. Then $f^{-1}:\mathbb{N}\to A$ is also bijective and thus surjective.

If $A$ is finite, then $\mathrm{\exists }f:I_m\to A$ for some $m\in \mathbb{N}$
$$g:\mathbb{N}\to A$$
$$x\to \{\begin{array}{ll}f(x)& 1\le x\le m\\ f(1)& x>m\end{array}$$

Proposition

Let $A$ and $B$ be denumerable sets (countably infinite). Then $A\cup B$ is also enumerable.

Proof

If $A$ and $B$ are denumerable, then $\mathrm{\exists }f:\mathbb{N}\to A$ and $\mathrm{\exists }g:\mathbb{N}\to B$ which are also bijections.

Define the following:
$$h:\mathbb{N}\to A\cup B$$
$$x\to \{\begin{array}{ll}f(x/2)& \text{ x is even}\\ g(\frac{x+1}{2})& \text{x is odd}\end{array}$$

Let $y\in A\cup B$

If $y\in A$, then $y=f(x)$ for some $x\in \mathbb{N}$, ($f$ is surjective)
$$h(2x)=f\left(\frac{2x}{2}\right)=f(x)=y$$

If $y\in B$, then $y=g(x)$ for some $x\in \mathbb{N}$, ($g$ is surjective)
$$h(2x-1)=f\left(\frac{(2x-1)+1}{2}\right)=g(x)=y$$

In either case, $g(x)=y$, so $y\in im(h)$, and $h$ is surjective.

By the previous theorem, $A\cup B$ is denumerable.

Corollary

If $A_1,A_2,A_3,..,A_n$ are all countable, then ${\cup }_{i=1}^n{A}_i$ is also countable.

Proposition

$\mathbb{N}\times \mathbb{N}$ is countable

$$g:\mathbb{N}\to \mathbb{N}\times \mathbb{N}$$
$$x\to \{\begin{array}{ll}(m,n)& \text{ if }x=2^m{3}^n\\ (1,1)& \text{ else}\end{array}$$

Fundamental Theorem of Arithmetic

Let $n\in \mathbb{N}-\{1\}$. Then $n$ is a “product” of prime numbers (i.e. $n$ is either prime itself or a product of primes). Moreover, this prime factorization is unique.

Proof (Existence)

We can use induction to prove the existence of a prime factorization.

See this proof

Proof (Uniqueness)

Lemma: Let $a_1,a_2,a_3,\dots ,a_n\in \mathbb{Z}$. Let $p$ be prime and suppose $p|\left(\prod _{i=1}^n{a}_i\right)$, then $p|a_i$ for some $i\in \{1,2,3,\dots ,n\}$. (Based on Euclid’s Lemma by induction)

Now suppose $n=p_1\cdot p_2\cdot p_3\dots \cdot p_s$ and $n=q_1\cdot q_2\cdot q_3\dots \cdot q_s$ are both prime factorizations of $n$ ($q_i$ and $p_i$ are always prime).

Assume without loss of generality (WLOG), $s\le t$

$$p_1(p_2{p}_3...p_s)=q_1{q}_2{q}_3\dots q_t$$
$$p_1|q_1{q}_2{q}_3\dots q_t$$

By Euclid’s Lemma $p_1|q_i$ for some $i\in \{1,2,3,\dots ,t\}$. By reordering the $q_i$'s, WLOG, we can assume that $p_1|q_1$.
But $p_1=q_1$, since the only positive integer factors of $q_1$ are $1$ and $q_1$, but $p_1$ is prime $⟹p_1\ne 1$.

$$p_1{p}_2{p}_3...p_s=q_1{q}_2{q}_3\dots q_t$$
$p_1=q_1$, so
$$p_2{p}_3...p_s=q_2{q}_3\dots q_t$$

We can use the same technique to show that $p_2=q_2$, $p_3=q_3$, and so on.

After $s$ repetitions, we get $p_i=q_i$ for $i=1,2,3,\dots ,s$

Now we need to show that $s=t$

We assumed $s\le t$. Suppose BWOC $s<t$

$$p_1{p}_2\dots p_s=n=q_1{q}_2{q}_3\dots q_s{q}_{s+1}{q}_{s+2}\dots q_t$$
But $p_i=q_i$ for $i\in \{1,2,\dots ,s\}$, so
$$1=q_{s+1}{q}_{s+2}\dots q_t$$
This is a impossible since $q_j\ge 2$ for all $j$. So $s=t$

Proof that $\mathbb{Q}$ is countable

Proposition

$\mathbb{N}\times \mathbb{N}$ is countable

Proof

Define $g:\mathbb{N}\to \mathbb{N}\times \mathbb{N}$

$$x\to \{\begin{array}{ll}(m,n)& x=2^m{3}^n\\ (1,1)& else\end{array}$$

Example: $$g(96)=g(2^5{3}^1)=(5,1)$$

Uniqueness of prime factorization guarantees there’s only one way to write $x$ as a prime factorization of $2$ and $3$, so this means the function is well defined. Let $(x,y)\in \mathbb{N}\times \mathbb{N}$. Then $g(2^x{3}^y)=(x,y)$, so $g$ is surjective.

Continuing Proof

Now let ${\mathbb{Q}}^{+}=\{\frac{a}{b}:a,b\in \mathbb{N}\}$
$$h:\mathbb{N}\times \mathbb{N}\to {\mathbb{Q}}^{+}$$
$$(a,b)\to \frac{a}{b}$$
$h$ is surjective. Then $(h\circ g):\mathbb{N}\to \mathbb{Q}$ is surjective (composition of surjective functions is surjective). So ${\mathbb{Q}}^{+}$ is countable.

Put ${\mathbb{Q}}^{-}=\{-\frac{a}{b}:a,b\in \mathbb{N}\}$
${\mathbb{Q}}^{-}\approx {\mathbb{Q}}^{+}$, so ${\mathbb{Q}}^{-}$ is also countable. (Construct bijection between them to show that they are equiponent (e.g. $f(x)=-x$))

$\{0\}$ is clearly countable.

$$\mathbb{Q}={\mathbb{Q}}^{-}\cup \{0\}\cup {\mathbb{Q}}^{+}$$
So $\mathbb{Q}$ is countable!

Example

Is it true that if $A$ and $B$ are countable sets, then so is $A\times B$?

If $A=\mathrm{\varnothing }\vee B=\mathrm{\varnothing }$ , then answer is yes, since $A\times B=\mathrm{\varnothing }$. So assume $A$ and $B$ are nonempty.

Since $A$ and $B$ are also countable, there are surjections $f:\mathbb{N}\to A$ and $g:\mathbb{N}\to B$

We will use the fact that $\mathbb{N}\times \mathbb{N}$ is countable.

$$h:\mathbb{N}\times \mathbb{N}\to A\times B$$
$$(x,y)\to (f(x),g(y))$$

h is surjective:
$$\text{Let }(a,b)\in A\times B$$
$$\text{f is surjective }⟹(\mathrm{\exists }c\in \mathbb{N})(f(c)=a)$$
$$\text{g is surjective }⟹(\mathrm{\exists }d\in \mathbb{N})(f(d)=b)$$

$$h((c,d))=(f(c),g(d))=(a,b)$$
$$(a,b)\in im(h)$$
So $h$ is surjective.

Now since $\mathbb{N}\times \mathbb{N}$ is countable, there is a surjection
$$t:\mathbb{N}\to \mathbb{N}\times \mathbb{N}$$

$$h\circ t:\mathbb{N}\to A\times B$$
$h\circ t$ is also a surjection, so $A\times B$ is also countable.

Proposition

Let $A$ and $B$ be sets with $A$ being countable. Let $B\subseteq A$. Then $B$ is also countable.

Proof

If $B=\mathrm{\varnothing }$, then $B$ is finite and thus countable. Assume $B\ne \mathrm{\varnothing }$

Since $A$ is countable, there is a surjection
$$f:\mathbb{N}\to A$$

Fix $b\in B$. Define
$$g:\mathbb{N}\to B$$
$$n\to \{\begin{array}{ll}f(n)& f(n)\in B\\ b& f(n)\notin B\end{array}$$
Let $b\in B$. Since $f$ is surjective, $\mathrm{\exists }x\in \mathbb{N}$ with
$$f(x)=y\in B$$

Then $g(x)=f(x)=y$, so $y\in im(g)$, so $g$ is surjective.

$$\text{B is countable}$$

Corollary

Let $X$ be a set and suppose $Y\subseteq X$

If $Y$ is uncountable, then $X$ is uncountable.

Theorem (Cantor): $[0,1)$ is uncountable.

Proof

Suppose BWOC, that $[0,1)$ is countable.

In this case, there would exist a surjection $f:\mathbb{N}\to [0,1)$
Super scripts are not exponents, 0.abcd denotes decimal expansion of a numer
$$f(2)=0.d_1^1{d}_2^1{d}_3^1\dots$$
$$f(2)=0.d_1^2{d}_2^2{d}_3^2\dots$$
$$f(3)=0.d_1^3{d}_2^3{d}_3^3\dots$$
$$f(4)=0.d_1^4{d}_2^4{d}_3^4\dots$$
$${d}_i^t\in \{0,1,2,3,\dots 9\}$$

Consider the following number
$$r=0.r_1{r}_2{r}_3{r}_4\dots$$
$$r=\{\begin{array}{ll}4& d_i^i\ne 4\\ 5& d_i^i\ne 4\end{array}$$

$$(\mathrm{\forall }n\in \mathbb{N})(f(n)\ne r_n)$$
since
$$(\mathrm{\forall }n\in \mathbb{N})r_n\ne d_n^n$$

So $r\notin im(f)$, contradicting surjectivity of $f$.

Hence $[0,1)$ is uncountable.

Corollary

$\mathbb{R}$ is uncountable

Proof

$[0,1)\subseteq \mathbb{R}$

Groups

Definitions

Let $G$ be a set.

An operation, $\star$, on $G$ is a function $\star :G\times G\to X$
where $X$ is a set. We write $g\star h$ instead of $\star (g,h)$.

We say that $\star$ is closed if $im(\star )\subseteq G$

Addition is closed
$$+:\mathbb{Z}\times \mathbb{Z}$$
Multiplication is closed
$$\cdot :\mathbb{Z}\times \mathbb{Z}$$
Division is not closed
$$/:(\mathbb{Z}-\{0\})\times (\mathbb{Z}-\{0\})$$

Identity

$$a\star x=b$$
$$a^{-1}\star (a\star x)=a^{-1}\star b$$
$$(a^{-1}\star a)\star x=a^{-1}\star b$$
$$e\star x=a^{-1}\star b$$
where $e$ is the identity element
$$x=a^{-1}\star b$$

Property of a Group

Let $G$ be a set and let $\star$ be a closed operation on $G$.

We say that $(G,\star )$ is a group if

1. Commutative: $(\mathrm{\forall }a,b,c\in G)(a\star (b\star c)=(a\star b)\star c)$
2. Identity Element: $(\mathrm{\exists }e\in G)(\mathrm{\forall }a\in Ga\star e=e\star a=a)$
3. Inverse: $(\mathrm{\forall }a\in G\mathrm{\exists }{a}^{-1}\in G)(a\star a^{-1}=a^{-1}\star a=e)$
4. (If $\mathrm{\forall }a,b,\in Ga\star b=b\star a$, then the group is an abellian group)

Examples of a Group

1. $(\mathbb{Z},+)$
2. $(\mathbb{Q}-\{0\},\cdot )$
3. $(V,+)$, where $V$ is only $\mathbb{R}$-vector space
4. $(\mathbb{R},+)$
5. $(\mathbb{R}-\{0\},\cdot )$

Is the Identity Element Unique?

Suppose that
$$\mathrm{\forall }a\in Ga\star e=e\star a=a$$
$$\mathrm{\forall }a\in Ga\star d=d\star a=a$$
$$d\star e=d$$

$$d\star e=e$$

$$d=e$$
Thus the identity is unique.

Is the Inverse Unique

Suppose $b\star a=a\star b=e$ and $c\star a=a\star c=e$ (i.e. both $b$ and $c$ are inverses of $a$

$$b\star a\star c=(b\star a)\star c=e\star c=c$$
$$b\star a\star c=b\star (a\star c)=b\star e=b$$

$$⟹b=c$$
$a^{-1}$ is unique

Notation

We often just write “let $G$ be a group” and use multiplication for the operation on $G$, even if the operation isn’t traditional multiplication

$ab$ instead of $a\star b$
$a+b$ instead of $a\star b$ sometimes when group is abelian

Examples of Finite Groups

Fix $n\in \mathbb{N}$. Then $\mathbb{Z}/n\mathbb{Z}=\{[0],[1],[2],\dots [n-1]\}$ with
$$[a]+[b]=[a+b]$$
forms a group

• $[0]$ is the identity
• $[-a]$ is the inverse of $a$

Example of Non-Abelian Groups

$$G=\{\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]:ab-bc\ne 0\}$$

Example of Non-Abelian Groups

Let $X=\{1,2,3\}$
Let $S_3=\{f:f:X\to X\text{ and f is bijective}\}$

$$f_1=\left(\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right)$$
means $f_1(1)=1,f_1(2)=2,f_1(3)=3$

$$f_2=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$$
means $f_2(1)=1,f_1(2)=3,f_1(3)=2$

$$f_3=\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$$
$$f_4=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$$
$$f_5=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$$
$$f_6=\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$$

$$f_1,f_2,f_3,f_4,f_5,f_6\in S_3$$
If $f,g\in S_3$
$f\circ g=g\circ f$ is not true in general, so the group is not abelian.

More generally, if $X$ is any nonempty set,
$$Sym(X)=\{f:f:X\to X,f\text{ is bijective }\}$$
is the symmetric group with composition of functions as its operation.

More Definitions

• If $(G,\star )$ is a group and $H\subseteq G$ is nonempty, we say that $H$ is a subgroup of $G$ if the restriction of $\star$ to $H\times H$ makes $H$ into a group itself.
• Equivalently, if $G$ is a group and $H\subseteq G$ is nonempty, then $H$ is a subgroup if $\mathrm{\forall }a,b\in H,a{b}^{-1}\in H$

Homomorphisms and Isomorphisms

Let $G_1$ and $G_2$ be groups. We say that $\varphi :G_1\to G_2$ is a homomorphism if
$$\mathrm{\forall }a,b,\in G_1\varphi (ab)=\varphi (a)\cdot \varphi (b)$$

If $\varphi$ is also bijective, it is instead called an isomorphism