Set Theory

Arithmetic of the Natural Numbers

Table of contents

Addition

Once we have a way to count elements in finite sets, the definition of addition becomes clear. Take a set with \(m\) elements and a disjoint set with \(n\) elements, and the size of their union will be the sum. We first verify that the definition does not depend on the choice of representatives.

Claim:

Let \(n\in\mathbb{N}\) be natural, let \(A\) be a set with \(S(n)\) elements, and let \(a\in A\). Then \(|A\setminus\{a\}|=n\).

Proof:

There exists a function \(f:A\rightarrow S(n)\) such that \(f(a)=n\). Then \(f\upharpoonright(A\setminus\{a\})\) is a one-to-one and onto function to \(n\).

Claim:

Let \(n\in\mathbb{N}\) be natural, let \(A\) be a set with \(n\) elements, and let \(b\notin A\). Then \(|A\cup\{b\}|=S(n)\).

Proof:

There exists a one-to-one and onto function \(f:A\rightarrow n\). Then \(f\cup\{(b,n)\}:A\cup\{b\}\rightarrow S(n)\) is a union of one-to-one and onto functions with disjoint domains and disjoint images, hence it is one-to-one and onto. Therefore \(|A\cup\{b\}|=S(n)\).

Claim:

Let \(n\in\mathbb{N}\) be natural, and let \(A\) be a set with \(n\) elements. Then for every natural \(m\in\mathbb{N}\), there exists \(k\in\mathbb{N}\) such that for every set \(B\) with \(m\) elements satisfying \(A\cap B=\emptyset\), we have \(|A\cup B|=k\).

Proof:

If \(m=0\), every set \(B\) with \(m\) elements satisfies \(B=\emptyset\), hence \(A\cap B=\emptyset\) and \(|A\cup B|=|A|=n\). Let \(m_{0}\in\mathbb{N}\) be such that there exists \(k_{0}\in\mathbb{N}\) such that for every set \(B\) with \(m_{0}\) elements satisfying \(A\cap B=\emptyset\), \(|A\cup B|=k_{0}\).

Let \(B_{0}\) be a set with \(S(m_{0})\) elements such that \(A\cap B_{0}=\emptyset\), and let \(b\in B_{0}\). Then \(|B_{0}\setminus\{b\}|=m_{0}\). Since \(B_{0}\setminus\{b\}\subset B_{0}\), we also have \(A\cap(B_{0}\setminus\{b\})=\emptyset\), and therefore \(|A\cup(B_{0}\setminus\{b\})|=k_{0}\). Hence, by the previous claim, \(|A\cup B_{0}|=|(A\cup(B_{0}\setminus\{b\}))\cup\{b\}|=S(k_{0})\). By the principle of induction, the claim is true for every natural \(m\in\mathbb{N}\).

Definition:

Let \(\{n,m\}\subset\mathbb{N}\) be natural numbers. We denote by \(m+n\) the unique \(k\in\mathbb{N}\) such that for every pair of disjoint sets \(A,B\) satisfying \(|A|=n\) and \(|B|=m\), \(|A\cup B|=k\). We call \(k\) the sum of \(n\) and \(m\).

Corollaries:

Let \(\{n,m,k\}\subset\mathbb{N}\) be natural numbers. Then:

1. \(m+n=n+m\)
2. \(S(n)=n+1\)
3. \(n+0=n\)
4. \((n+m)+k=n+(m+k)\), and we may write \(n+m+k\) briefly.

Claim:

Let \(m\in\mathbb{N}\) be natural. Then for every \(n\in\mathbb{N}\), \(m\le m+n\), and in addition, if \(n\neq0\), then \(m<m+n\).

Proof:

If \(n=0\), then \(m+n=m\). Let \(n_{0}\in\mathbb{N}\) be such that \(m\le m+n_{0}\). Then \(m+n_{0}<S(m+n_{0})=m+n_{0}+1\), and by transitivity \(m\le m+n_{0}<m+n_{0}+1\). Hence \(m<m+n_{0}+1\), and by the principle of induction the claim holds for every natural \(n\in\mathbb{N}\).

Claim:

Let \(\{n,m\}\subset\mathbb{N}\). Then \(n\le m\) if and only if there exists \(k\in\mathbb{N}\) such that \(n+k=m\). In addition, if \(k\neq0\), then \(n<m\).

Proof:

Assume \(n\le m\). Then \(m\setminus n\subseteq m\), so there exists \(k\in\mathbb{N}\) such that \(|m\setminus n|=k\). Also \((m\setminus n)\cap n=\emptyset\), hence \(|n\cup(m\setminus n)|=m\), and therefore \(n+k=m\). If \(m=n\), then \(m\setminus n=\emptyset\), so \(k=0\).

Conversely, assume that there exists \(k\in\mathbb{N}\) such that \(n+k=m\). By the previous claim, \(n\le n+k=m\), and therefore \(n\le m\). If \(k\neq0\), then \(n<n+k=m\), and therefore \(n<m\).

Claim:

Let \(\{n,m,k\}\subset\mathbb{N}\) satisfy \(n\le m\). Then \(n+k\le m+k\). If in addition \(n<m\), then \(n+k<m+k\).

Proof:

If \(k=0\), then \(n+k=n\le m=m+k\), and if \(n<m\), then \(n+k<m+k\), as desired. Let \(x\in n\cup\{n\}\). Then \(x\in n\) or \(x=n\). If \(x\in n\), then \(x\in m\), and in particular \(x\in m\cup\{m\}\). Otherwise \(x=n\), and since \(n\in m\) or \(n=m\), we get \(x\in m\) or \(x=m\), hence \(x\in m\cup\{m\}\). Therefore \(n+1\le m+1\). If in addition \(n<m\), meaning \(n\neq m\), then \(n+1\le m\), hence \(n+1<m+1\). By induction, the claim holds for every \(k\in\mathbb{N}\).

Claim:

Let \(\{n,m,k\}\subset\mathbb{N}\) satisfy \(n+k\le m+k\). Then \(n\le m\). If in addition \(n+k<m+k\), then \(n<m\).

Proof:

If \(k=0\), the claim is clear. Assume \(n+1\le m+1\). Then \(n\cup\{n\}\subseteq m\cup\{m\}\). Since \(n\in n\cup\{n\}\), we get \(n\in m\cup\{m\}\), so \(n\in m\) or \(n=m\), hence \(n\le m\). If in addition \(n+1<m+1\), then \(n+1\neq m+1\), hence \(n\neq m\), and therefore \(n<m\). By induction, the claim holds for every \(k\in\mathbb{N}\).

Claim:

Let \(\{n_{0},m_{0},n_{1},m_{1}\}\subset\mathbb{N}\) satisfy \(n_{0}\le m_{0}\) and \(n_{1}\le m_{1}\). Then \(n_{0}+n_{1}\le m_{0}+m_{1}\).

Proof:

Since \(n_{0}\le m_{0}\), we get \(n_{0}+n_{1}\le m_{0}+n_{1}\). Since \(n_{1}\le m_{1}\), there exists \(k\in\mathbb{N}\) such that \(n_{1}+k=m_{1}\). Therefore \(n_{0}+n_{1}\le m_{0}+n_{1}\le m_{0}+n_{1}+k=m_{0}+m_{1}\), as desired.

Notation:

Let \(\{n_{i}\}_{i\in m+1}\subset\mathbb{N}\) be a finite set of natural numbers. We denote \(n_{0}+n_{1}+\cdots+n_{m}\) by \(\sum\limits _{i\in m+1}n_{i}\), or \(\sum\limits _{i=0}^{m}n_{i}\), or \(\sum\limits _{i<m+1}n_{i}\). We define the empty sum \(\sum\limits _{i<0}n_{i}:=0\).

Multiplication

Multiplication is almost as natural as addition; this time, instead of a union, we will use a Cartesian product.

Claim:

Let \(n\in\mathbb{N}\) be natural, let \(A\) be a set with \(n\) elements, and let \(b\) be arbitrary. Then \(|A\times\{b\}|=n\).

Proof:

Define \(f:A\rightarrow A\times\{b\}\) by \(f(a):=(a,b)\). It is easy to see that this function is one-to-one and onto.

Claim:

Let \(n\in\mathbb{N}\) be natural, and let \(A\) be a set with \(n\) elements. Then for every natural \(m\in\mathbb{N}\), there exists a natural \(k\in\mathbb{N}\) such that for every set \(B\) with \(m\) elements, \(|A\times B|=k\).

Proof:

If \(m=0\), every set \(B\) with \(m\) elements satisfies \(B=\emptyset\), hence \(|A\times B|=|\emptyset|=0\). Let \(m_{0}\in\mathbb{N}\) be such that there exists \(k_{0}\in\mathbb{N}\) such that for every set \(B\) with \(m_{0}\) elements, \(|A\times B|=k_{0}\). Let \(B_{0}\) be a set with \(m_{0}+1\) elements, and let \(b\in B_{0}\). Then \(|B_{0}\setminus\{b\}|=m_{0}\), and

\[ \begin{align*} A\times B_{0} &=A\times((B_{0}\setminus\{b\})\cup\{b\})\\ &=(A\times(B_{0}\setminus\{b\}))\cup(A\times\{b\}). \end{align*} \]

Since \((A\times(B_{0}\setminus\{b\}))\cap(A\times\{b\})=\emptyset\), by the choice of \(m_{0}\) we get \(|(A\times(B_{0}\setminus\{b\}))\cup(A\times\{b\})|=k_{0}+n\).

Definition:

Let \(\{n,m\}\subset\mathbb{N}\) be natural numbers. We denote by \(n\cdot m\), or by \(nm\), the unique \(k\in\mathbb{N}\) such that for every set \(A\) with \(n\) elements and every set \(B\) with \(m\) elements, \(|A\times B|=k\). We call \(k\) the product of \(n\) and \(m\).

Corollaries:

Let \(\{n,m,k\}\subset\mathbb{N}\). Then:

1. \(n\cdot m=m\cdot n\).
2. \(n\cdot0=0\).
3. \(n\cdot1=n\).
4. \((n\cdot m)\cdot k=n\cdot(m\cdot k)\), and we may write \(n\cdot m\cdot k\) briefly.
5. \(n\cdot(m+k)=n\cdot m+n\cdot k\).

Corollary:

Let \(\{m,n\}\subset\mathbb{N}\) be natural numbers, and let \(\{n_{i}\}_{i<m}\subset\mathbb{N}\) be natural numbers. Then \(n\cdot\sum\limits _{i<m}n_{i}=\sum\limits _{i<m}(n\cdot n_{i})\).

Corollaries:

Let \(n\in\mathbb{N}\). Then:

1. For every \(m\in\mathbb{N}\), \(\sum\limits _{i<m}n=\overset{m\text{ times}}{\overbrace{n+n+\cdots+n}}=m\cdot n\).
2. If \(n>2\), then \(n+n<n\cdot n\).
3. For every \(m>1\), \(n<n\cdot m\).

Claim:

Let \(k\in\mathbb{N}\). Then for all natural \(n\le m\), \(n\cdot k\le m\cdot k\).

Proof:

If \(k=0\), then for all natural \(\{n,m\}\subset\mathbb{N}\), \(0=n\cdot k\le m\cdot k=0\). Let \(k_{0}\in\mathbb{N}\) be such that for all natural \(n\le m\), \(n\cdot k_{0}\le m\cdot k_{0}\). There exists \(\ell\in\mathbb{N}\) such that \(m=n+\ell\). Then \(n\cdot k_{0}+n\le m\cdot k_{0}+n\le m\cdot k_{0}+n+\ell=m\cdot k_{0}+m\). Hence \(n\cdot(k_{0}+1)\le m\cdot(k_{0}+1)\). Therefore, by the principle of induction, for every \(k\in\mathbb{N}\) and all natural \(n\le m\), \(n\cdot k\le m\cdot k\).

Claim:

Let \(k\in\mathbb{N}\setminus\{0\}\), and let \(\{n,m\}\subset\mathbb{N}\) be natural numbers satisfying \(n\cdot k\le m\cdot k\). Then \(n\le m\).

Proof:

Assume for contradiction that \(m<n\). Then there exists \(\ell>0\) such that \(n=m+\ell\). Hence \((m+\ell)\cdot k=m\cdot k+\ell\cdot k\le m\cdot k\), so \(\ell\cdot k\le0\). Since \(0\) is the minimal natural number and \(k\neq0\), we get \(\ell=0\), contradicting the assumption.

Exponentiation

We now want to define exponentiation, and we do this using the set of all functions from one set to another.

Definition:

Let \(A,B\) be sets. We denote \(B^{A}:=\left\{ f\in P(A\times B):f:A\rightarrow B\right\}\).

Claim:

Let \(n\in\mathbb{N}\) be natural, and let \(A\) be a set with \(n\) elements. Then for every natural \(m\in\mathbb{N}\), there exists a natural \(k\in\mathbb{N}\) such that for every set \(B\) with \(m\) elements, \(|A^{B}|=k\).

Proof:

If \(m=0\), every set \(B\) with \(m\) elements satisfies \(B=\emptyset\), and therefore \(A^{B}=\{\emptyset\}\), so \(|A^{B}|=1\). Let \(m_{0}\in\mathbb{N}\) be natural such that there exists \(k_{0}\in\mathbb{N}\) such that for every set \(B\) with \(m_{0}\) elements, \(|A^{B}|=k_{0}\). Let \(B_{0}\) be a set with \(m_{0}+1\) elements, and let \(b\in B_{0}\). Then \(|B_{0}\setminus\{b\}|=m_{0}\), so \(|A^{B_{0}\setminus\{b\}}\times A|=k_{0}\cdot n\).

Define \(g:A^{B_{0}\setminus\{b\}}\times A\rightarrow A^{B_{0}}\) by \(g(f,a):=f\cup\{(b,a)\}\). Then the function \(h:A^{B_{0}}\rightarrow A^{B_{0}\setminus\{b\}}\times A\) defined by \(h(f):=(f\upharpoonright(B_{0}\setminus\{b\}),f(b))\) is its inverse. Hence \(g\) is one-to-one and onto, and \(|A^{B_{0}}|=|A^{B_{0}\setminus\{b\}}\times A|=k_{0}\cdot n\). By the principle of induction, the claim holds for every natural \(m\in\mathbb{N}\).

Definition:

Let \(\{n,m\}\subset\mathbb{N}\) be natural numbers. We denote by \(m^{n}\) the unique \(k\in\mathbb{N}\) such that for every set \(A\) with \(n\) elements and every set \(B\) with \(m\) elements, \(|B^{A}|=k\). We call \(k\) the power of \(m\) by \(n\).

Definition:

Let \(\{A_{\alpha}\}_{\alpha\in I}\) be nonempty sets, and write \(A:=\bigcup\limits _{\alpha\in I}A_{\alpha}\). Then \(\prod\limits _{\alpha\in I}A_{\alpha}:=\left\{ f\in A^{I}:\text{for all }\alpha\in I\text{, }f(\alpha)\in A_{\alpha}\right\}\).

Definition:

Let \(m\in\mathbb{N}\) be natural, and let \(\{n_{i}\}_{i<m+1}\subset\mathbb{N}\) be natural numbers. Then we denote \(\prod\limits _{i<m+1}n_{i}:=n_{0}\cdot n_{1}\cdots n_{m}\), and define the empty product \(\prod\limits _{i<0}n_{i}:=1\).

Claim:

Let \(n\in\mathbb{N}\), and let \(\{A_{i}\}_{i<n}\) be finite sets. Then \(|\prod\limits _{i<n}A_{i}|=\prod\limits _{i<n}|A_{i}|\).

Proof:

If \(n=0\), then \(\prod\limits _{i<n}A_{i}=\{\emptyset\}\), and also \(\prod\limits _{i<n}|A_{i}|=1\). Therefore \(|\prod\limits _{i<n}A_{i}|=\prod\limits _{i<n}|A_{i}|\).

Let \(n_{0}\in\mathbb{N}\) be such that for every collection \(\{A_{i}\}_{i<n_{0}}\) of finite sets, \(|\prod\limits _{i<n_{0}}A_{i}|=\prod\limits _{i<n_{0}}|A_{i}|\). Let \(\{B_{i}\}_{i<n_{0}+1}\) be finite sets. Then \(|\prod\limits _{i<n_{0}}B_{i}|=\prod\limits _{i<n_{0}}|B_{i}|\).

Define a function \(g:\left(\prod\limits _{i<n_{0}}B_{i}\right)\times B_{n_{0}}\rightarrow\prod\limits _{i<n_{0}+1}B_{i}\) by \(g(f,b):=f\cup\{(n_{0},b)\}\). Then the function \(h:\prod\limits _{i<n_{0}+1}B_{i}\rightarrow\left(\prod\limits _{i<n_{0}}B_{i}\right)\times B_{n_{0}}\) defined by \(h(f):=(f\upharpoonright\prod\limits _{i<n_{0}}B_{i},f(n_{0}))\) is its inverse. Hence \(g\) is one-to-one and onto, and

\[ |\prod\limits _{i<n_{0}+1}B_{i}| =|\left(\prod\limits _{i<n_{0}}B_{i}\right)\times B_{n_{0}}| =\left(\prod\limits _{i<n_{0}}|B_{i}|\right)\cdot|B_{n_{0}}| =\prod\limits _{i<n_{0}+1}|B_{i}|. \]

Therefore, by the principle of induction, the claim holds for every \(n\in\mathbb{N}\).

Corollaries:

Let \(\{n,m\}\subset\mathbb{N}\) be natural numbers. Then:

1. \(n^{0}=1\).
2. \(n^{1}=n\).
3. \(n\neq0\Longrightarrow0^{n}=0\).
4. \(1^{n}=1\).
5. \(n^{m+1}=n^{m}\cdot n\).

Claims:

Let \(\{n,m,k\}\subset\mathbb{N}\) be natural numbers. Then:

1. \(n^{m}\cdot n^{k}=n^{m+k}\).
2. \((n^{m})^{k}=n^{m\cdot k}\)
3. \((n\cdot m)^{k}=n^{k}\cdot m^{k}\).

Proof:

Let \(A,B,C\) be sets with \(n,m,k\) elements respectively.

1. Assume \(B\cap C=\emptyset\), and define \(h:A^{B}\times A^{C}\rightarrow A^{B\cup C}\) by \(h(f,g):=f\cup g\). This is a one-to-one and onto function, hence \(|A^{B}\times A^{C}|=|A^{B\cup C}|\).
2. Define \(h:(A^{B})^{C}\rightarrow A^{B\times C}\) by \((h(f))(b,c):=(f(c))(b)\). This is a one-to-one and onto function, hence \(|(A^{B})^{C}|=|A^{B\times C}|\).
3. Define \(h:A^{C}\times B^{C}\rightarrow(A\times B)^{C}\) by \((h(f,g))(c):=(f(c),g(c))\). This is a one-to-one and onto function, hence \(|A^{C}\times B^{C}|=|(A\times B)^{C}|\).

Claim:

Let \(A\) be a finite set with \(n\) elements. Then \(|P(A)|=2^{n}\).

Proof:

Define \(f:P(A)\rightarrow2^{A}\) by

\[ f(A_{0})(a):=\begin{cases} 1 & a\in A_{0}\\ 0 & \text{otherwise}. \end{cases} \]

Define \(g:2^{A}\rightarrow P(A)\) by \(g(h):=\left\{ a:h(a)=1\right\}\). Let \(A_{0}\in P(A)\). Then

\[ \begin{align*} (g\circ f)(A_{0}) &=g(a\mapsto\begin{cases} 1 & a\in A_{0}\\ 0 & \text{otherwise} \end{cases})\\ &=\left\{ a:a\in A_{0}\right\}=A_{0}. \end{align*} \]

Let \(h\in2^{A}\). Then

\[ \begin{align*} (f\circ g)(h) &=f(\left\{ a:h(a)=1\right\})\\ &=a\mapsto\begin{cases} 1 & h(a)=1\\ 0 & h(a)=0 \end{cases} =h. \end{align*} \]

Thus \(f,g\) are inverses of one another, hence they are one-to-one and onto. Therefore \(|P(A)|=|2^{A}|=2^{n}\).

Order of Arithmetic Operations:

Let \(\{n,m,k\}\subset\mathbb{N}\setminus\{0\}\) be natural numbers. When we write \(n+m\cdot k\), we mean \(n+(m\cdot k)\). Also, \(n\cdot m^{k}\) is equivalent to \(n\cdot(m^{k})\), and in particular \(n+m^{k}\) means \(n+(m^{k})\).