Exercise 2.2.3

Prove Proposition 2.2.12.

Proposition 2.2.12 (basic properties of order for natural numbers):

Let $a, b, c$ be natural numbers. Then

(a) (Order is reflexive) $a\ge a$.

(b) (Order is transitive) If $a\ge b$ and $b\ge c$, then $a\ge c$.

(c) (Order is antisymmetric) If $a\ge b$ and $b\ge a$, then $a=b$.

(d) (Addition preserves order) $a\ge b$ if and only if $a+c\ge b+c$.

(e) $a<b$ if and only if $a++\le b$.

(f ) $a<b$ if and only if $b=a+d$ for some positive number $d$.

(a) By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge a$ if and only if $a=a+x$ for some natural number $x$. 

To show $a\ge a$, it is sufficient to show $a=a+x$ is true for some natural number $x$. Choosing $x=0$ gives $a=a+0$. By the symmetry axiom of equality this is $a+0=a$, which is indeed true by Lemma 2.2.2. 

We have shown $a=a+x$ is true for some natural number $x$, and so by Definition 2.2.11 we conclude $a\ge a$. 

(b) By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge b$ if and only if $a=b+x$ for some natural number $x$, and $b\ge c$ if and only if $b=c+y$ for some natural number $y$. 

Together we have $a=(c+y)+x$ for some natural numbers $x,y$. By Proposition 2.2.5 (addition is associative), we have $a=c+(y+x)$. The sum of two natural numbers, $x$ and $y$, is also a natural number $x+y$. By Definition 2.2.11 this means $a\ge c$. 

For completeness we should prove the sum of two natural numbers is a natural number. We'll use induction. Let $P(a)$ be the statement that the sum $a+b$ of natural numbers $a$ and $b$ is also a natural number. We need to show the base case $P(0)$, and the inductive step $P(a)\implies P(a++)$. The base case $P(0)$ states $0+b$ is a natural number. Definition 2.2.1 (addition of natural numbers) tells us $0+b:=b$ where $b$ is a natural number, and so the base case is true. For the inductive step we need to show $P(a++)$, assuming $P(a)$. That is, we want to show $(a++)+b$ is a natural number. Again by Definition 2.2.1, we have $(a++)+b:=(a+b)++$. The assumption $P(a)$ tells us $(a+b)$ is a natural number, and Axiom 2.2 tells us $(a+b)++$ is a natural number, proving the inductive step. So by induction we have shown the sum of two natural numbers is a natural number.

(c) By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge b$ if and only if $a=b+x$ for some natural number $x$. By the same definition we have $b\ge a$ if and only if $b=a+y$ for some natural number $y$. 

Together this means $a=(a+y)+x$ for some natural numbers $x,y$. By Proposition 2.2.5 (addition is associative), we have $a=a+(y+x)$. Intuitively we can see $x$ and $y$ must both be zero. Let's show this.

By Proposition 2.2.6 (cancellation law) this gives $0=y+x$. The symmetry axiom of equality gives us $y+x=0$. Corollary 2.2.9 tells us that both $x=0$ and $y=0$.

Substituting $x=0$ into $a=b+x$ gives us $a=b+0$. Lemma 2.2.2 tells us $b+0=b$ which finally gives us $a=b$.

(d) We need to show both $a\ge b\implies a+c\ge b+c$ and $a\ge b\impliedby a+c\ge b+c$.

$(\implies)$

By Definition 2.2.11 (ordering of the natural numbers) we have $a\ge b\implies a=b+x$ for some natural number $x$.

By the substitution axiom of equality, $a=b+x$ means $a+c=(b+x)+c$, for some natural number $c$. By Proposition 2.2.5 (addition is associative) we have $a+c=b+(x+c)$. Proposition 2.2.4 (addition is commutative) gives us $a+c=b+(c+x)$. Applying Proposition 2.2.5 again gives us $a+c=(b+c)+x$. By Definition 2.2.11 this means $a+c\ge b+c$, and so we have shown $a\ge b\implies a+c\ge b+c$.

$(\impliedby)$

By Definition 2.2.11 (ordering of the natural numbers) we have $a+c\ge b+c\implies a+c=(b+c)+y$ for some natural number $y$. Proposition 2.2.4 (addition is commutative) we have $c+a=(c+b)+y$. Proposition 2.2.5 (addition is associative) then gives us $c+a=c+(b+y)$. The Proposition 2.2.6 (cancellation law) reduces this to $a=b+y$, which by Definition 2.2.11 means $a\ge b$, and so we have shown $a+c\ge b+c\implies a\ge b$.

By showing both $a\ge b\implies a+c\ge b+c$ and $a+c\ge b+c\implies a\ge b$, we have shown $a\ge b\iff a+c\ge b+c$.

(e) We need to show both $a<b\implies a++\le b$ and $a<b\impliedby a++\le b$.

$(\implies)$

By Definition 2.2.11 (ordering of the natural numbers) $a<b$ implies both $b=a+x$ for some natural number $x$, and $b\ne a$. 

For the purpose of contradiction let's assume $x=0$. This would mean $b=a+0$, which by Lemma 2.2.2 gives $b=a$. This contradicts $b\ne a$. And so $x\ne0$, that is, $x$ is a positive number.

By Lemma 2.2.10 there exists a unique natural number $y$ such that $y++=x$. This gives us $b=a+(y++)$. By Lemma 2.2.3 this is $b=(a+y)++$, and by Definition 2.2.1 (addition of natural numbers) this is $b=(a++)+y$. By Definition 2.2.11 this means $a++\le b$, and so we have shown $a<b\implies a++\le b$.

$(\impliedby)$

By Definition 2.2.11 (ordering of the natural numbers) $a++\le b$ implies $b=(a++)+x$ for some natural number $x$. 

Definition 2.2.1 gives us $b=(a+x)++$, and by Lemma 2.2.3 this is $b=a+(x++)$. 

For the purpose of contradiction let's assume $a=b$. This would mean $b=b+(x++)$, and by Definition 2.2.1 this is $0+b=b+(x++)$. The symmetry axiom of equality gives us $b+0=b+(x++)$. Proposition 2.2.6 (cancellation law) then gives us $0=x++$. This contradicts Axiom 2.3, and so $a\ne b$. 

By Definition 2.2.11, having both $b=a+(x++)$ and $a\ne b$ means $a<b$, and so we have shown $a++\le b\implies a<c$.

By showing both $a<b\implies a++\le b$ and $a++\le b\implies a<c$, we have shown $a<b\iff a++\le b$.

(f) We need to show both $a<b\implies b=a+d$ and $a<b\impliedby b=a+d$, where $d$ is a positive number.

$(\implies)$

By Definition 2.2.11 (ordering of the natural numbers) $a<b$ implies both $b=a+d$ for some natural number $d$, and $b\ne a$. 

For the purpose of contradiction let's assume $d=0$. This would mean $b=a+0$, which by Lemma 2.2.2 gives $b=a$. This contradicts $b\ne a$. And so $d\ne0$, that is, $d$ is a positive number.

We have shown that $a<b\implies b=a+d$, where $d$ is a positive number.

$(\impliedby)$

For the purpose of contradiction let's assume $b=a$. This would mean $a=a+d$, which by Definition 2.2.1 (addition of natural numbers) is gives $0+a=a+d$. By the symmetry axiom of equality, this is $a+0=a+d$. Applying Proposition 2.2.6 (cancellation law) then gives $0=d$, which is $d=0$ by the symmetry axiom of equality. This contradicts $d$ being a positive number. And so $b\ne a$. 

Applying Definition 2.2.1 to $b=a+d$ and $b\ne a$ gives us $a<b$, and so we have shown $b=a+d\implies a<c$, where $d$ is a positive number.

By showing both $a<b\implies b=a+d$ and $b=a+d\implies a<c$, where $d$ is a positive number, we have shown $a<b\iff b=a+d$.

Exercise 2.2.2

Prove Proposition 2.2.10.

Lemma 2.2.10:: 

Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++=a$.

Let $S(a)$ be the statement "if $a$ is a positive number then there exists exactly one natural number $b$ such that $b++=a$". We will use induction on $a$.

We need to show the base case $S(0)$, and the inductive step $S(a)\implies S(a++)$.

Base Case

We need to show that if $0$ is a positive number then there exists exactly one natural number $b$ such that $b++=0$.

However, 0 is not a positive number, and so the base case is vacuously true.

Inductive Step

We assume $S(a)$ and aim to show $S(a++)$, if $a++$ is a positive number then there exists exactly one natural number $b$ such that $b++=(a++)$. We need to show both the existence and uniqueness of $b$.

Since $a++$ exists so does $a$. We set $b=a$. By the substitution axiom of equality, we have $b++=a++$. And so at least one $b$ exists such that $b++=a++$. 

For the purpose of contradiction, let's assume a natural number $b'$, distinct from $b$, also satisfies $b'++=a++$. By Axiom 2.4 this would mean $b'=a$, contradicting that $b'$ is distinct from $b$. This means there is at most one natural number $b$, specifically $b=a$, such that $b++=(a++)$.

By showing there is at least one $b$, and at most one $b$, that satisfies $b++=a++$, we have shown there is exactly one $b$ such that $b++=a++$, proving the inductive step.

Note that we didn't require the induction hypothesis, $S(a)$.

By showing the base case and the inductive step, we have proved thatfor any positive number $a$, there exists only one natural number $b$ such that $b++=a$.

Exercise 2.2.1

Prove Proposition 2.2.5.

Proposition 2.2.5 (addition is associative). 

For any natural numbers $a$, $b$, $c$, we have $(a+b)+c=a+(b+c)$.

We will use induction on $a$, keeping $b$ and $c$ fixed. We need to show the base case $(0+b)+c=0+(b+c)$ and the inductive step

$$ (a+b)+c=a+(b+c)\implies((a++)+b)+c=(a++)+(b+c) $$

Base Case

By Definition 2.2.1, we have $0+b:=b$, and also $0+(b+c):=(b+c)$.

And so

$$  (0+b)+c  = b+c  = 0+(b+c) $$

And so we have shown the base case $(0+b)+c=0+(b+c)$.

Inductive Step

We assume $(a+b)+c=a+(b+c)$, and aim to show $((a++)+b)+c=(a++)+(b+c)$.

By Definition 2.2.1, we have $(a++)+b:=(a+b)++$, and $((a+b)++)+c:=((a+b)+c)++$, and also $(a++)+(b+c):=(a+(b+c))++$.

And so

$$  \begin{alignat*}{3} ((a++)+b)+c & =((a+b)++)+c & \hspace{4cm} &  & \text{Definition 2.2.1} \\ \\  & =((a+b)+c)++ & \hspace{4cm} &  & \text{Definition 2.2.1} \\ \\  & =(a+(b+c))++ & \hspace{4cm} &  & \text{induction hypothesis}\\  \\ & =(a++)+(b+c) & \hspace{4cm} &  & \text{Definition 2.2.1} \end{alignat*}$$ 

By showing the base case and the inductive step, we have proved that for any natural numbers $a$, $b$, $c$, we have $(a+b)+c=a+(b+c)$.

Exercise A.7.1

Suppose you have four real numbers $a,b,c,d$ and you know that $a=b$ and $c=d$.

Use the above four axioms to deduce that $a+d=b+c$.

The four axioms of equality are

1. Reflexivity. $x=x$
2. Symmetry. $x=y\implies y=x$
3. Transitivity. $x=y\land y=z\implies x=z$
4. Substitution. $x=y\implies f(x)=f(y)$

Since $c=d$, by the axiom of symmetry, we have $d=c$. Let's create a function $f(x)=a+x$. By axiom of substitution, since $d=c$, we have$f(d)=f(c)$, that is, $a+d=a+c$.

Let's create another function $g(x)=x+c$. By the axiom of substitution, since $a=b$, we have $f(a)=f(b)$, that is, $a+c=b+c$.

By the axiom of transitivity, $a+d=a+c$ and $a+c=b+c$ gives us $a+d=b+c$, the desired conclusion.

Exercise A.5.1

What does each of the following statements mean, and which of them are true? Can you find gaming metaphors for each of these statements?

(a) For every positive number $x$, and every positive number $y$, we have $y^{2}=x$.

(b) There exists a positive number $x$ such that for every positive number $y$, we have $y^{2}=x$.

(c) There exists a positive number $x$, and there exists a positive number $y$, such that $y^{2}=x$.

(d) For every positive number $y$, there exists a positive number $x$ such that $y^{2}=x$.

(e) There exists a positive number $y$ such that for every positive number $x$, we have $y^{2}=x$.

(a) The statement means that every positive number is the square of every positive number. This is false. 

In a game, an adversarial opponent picks both $x$ and $y$ from the set of positive numbers, and we have to show that $y^{2}=x$ holds no matter what the opponent chooses. We may be lucky and show that $y^{2}=x$ in some games, but we won't be able to do it for all possible choices for $x$ and $y$.

(b) The statement means that there is a positive number that is the square of every positive number. This is false.

In a game, we first pick a positive number $x$ and the adversarial opponent freely picks $y$ from the set of positive numbers. We can't pick a special $x$ such that $y^{2}=x$ no matter what the opponent chooses for $y$. 

(c) The statement means some positive numbers are the square root of some others. This is true. 

In a game, the adversarial opponent plays no part. We have complete control in picking positive numbers $x$ and $y$ to ensure $y^{2}=x$.

(d) The statement means that every positive number has a square. This is true.

In a game, the adversarial opponent first picks a positive number $y$. We then get to choose a number $x$ that is the square of $y$, to ensure $y^{2}=x$. 

(e) The statement means there is a positive number that is the square root of every positive number. This is false.

In a game, we first choose a positive number $y$, and then an adversarial opponent picks $x$ from the set of positive numbers. We may be lucky and show that $y^{2}=x$ in some games, but we won't be able to do it for all possible choices for $x$ our opponent makes.

Exercise A.1.6

Suppose you know that whenever $X$ is true, then $Y$ is true; that whenever $Y$ is true, then $Z$ is true; and whenever $Z$ is true, then $X$ is true. Is this enough to show that $X,Y,Z$ are all logically equivalent? Explain.

To show that X,Y,Z are all logically equivalent, we need to show logical equivalence between all three variables, X\iff Y, Y\iff Z, X\iff Z.

We are given that whenever $X$ is true, then $Y$ is true. This is $X\implies Y$.

We are given that whenever $Y$ is true, then $Z$ is true. This is $Y\implies Z$.

We are given that whenever $Z$ is true, then $X$ is true. This is $Z\implies X$.

To show $X\iff Y$ we need to show both $X\implies Y$ and $Y\implies X$. We are given $X\implies Y$. If $Y$ is true, then by $Y\implies Z$, we know $Z$ is true. Since $Z$ is true, then by $Z\implies X$, we know $X$ is true. From $Y$ we have shown $X$, that is $Y\implies X$. So we have shown $X\iff Y$.

To show $Y\iff Z$ we need to show both $Y\implies Z$ and $Z\implies Y$. We are given $Y\implies Z$. If $Z$ is true, then by $Z\implies X$, we know $X$ is true. Since $X$ is true, then by $X\implies Y$, we know $Y$ is true. From $Z$ we have shown $Y$, that is $Z\implies Y$. So we have shown $Y\iff Z$.

To show $X\iff Z$ we need to show both $X\implies Z$ and $Z\implies X$. We are given $Z\implies X$. If $X$ is true, then by $X\implies Y$, we know $Y$ is true. Since $Y$ is true, then by $Y\implies Z$, we know $Z$ is true. From $X$ we have shown $Z$, that is $X\implies Z$. So we have shown $Y\iff Z$.

By showing all three $X\iff Y$, $Y\iff Z$, and $X\iff Z$, we have shown $X,Y,Z$ are all logically equivalent.

Exercise A.1.5

Suppose you know that $X$ is true if and only if $Y$ is true, and you know that $Y$ is true if and only if $Z$ is true. Is this enough to show that $X,Y,Z$ are all logically equivalent? Explain.

To show that $X,Y,Z$ are all logically equivalent, we need to show logical equivalence between all three variables, $X\iff Y$, $Y\iff Z$, $X\iff Z$.

The first $X\iff Y$ is given to us as $X$ is true if and only if $Y$ is true. 

The second $Y\iff Z$ is given to us as $Y$ is true if and only if $Z$ is true.

The third $X\iff Z$ is not given to us. To show $X\iff Z$ we need to show both $X\implies Z$ and $Z\implies X$.

If $X$ is true, then by $X\iff Y$ we know $Y$ is true. Since $Y$ is true, then by $Y\iff Z$ we know $Z$ is true. From $X$ we have shown $Z$, that is, $X\implies Z$.

If $Z$ is true, then by $Y\iff Z$ we know $Y$ is true. Since $Y$ is true, then by $X\iff Y$ we know $X$ is true. From $Z$ we have shown $X$, that is, $Z\implies X$.

By showing both $X\implies Z$ and $Z\implies X$, we have shown $X\iff Z$, and this completes the requirements to show $X,Y,Z$ are all logically equivalent.