Exercose 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)$, if $a$ is a positive number, then there exists exactly one natural number $b$ such that $b++=a$. 

We want to show $S(a++)$, if $a++$ is a positive number, 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, we can 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, assume $x$ and $y$ are distinct natural numbers such that $x++=(a++)$ and $y++=(a++)$. By transitivity of equality we have $x++=y++$, and by Axiom 2.4, if $x++=y++$ then $x=y$. This contradicts $x$ and $y$ being distinct. And so there is at most one natural number $b$ 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++$.

By showing the base case and the inductive step, we have proved that for 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

$$ \begin{align*} (0+b)+c & =b+c \\ \\  & =0+(b+c) \end{align*}$$

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 also $(a++)+(b+c):=(a+(b+c))++$.

And so

$$ \begin{align*} ((a++)+b)+c & =((a+b)++)+c\\ \\  & =((a+b)+c)++\\ \\  & =(a+(b+c))++\tag{induction hypothesis}\\ \\  & =(a++)+(b+c) \end{align*}$$

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.

Exercise A.1.4

Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $Y$ is false, then $X$ is false. Have you now demonstrated that $X$ is true if and only if $Y$ is true? Explain.

To show that $X$ and $Y$ are logically equivalent, $X\iff Y$, we need to show both $X\implies Y$ and $Y\implies X$.

Demonstrating that whenever $X$ is true, then $Y$ is true, is equivalent to demonstrating $X\implies Y$. 

$X\implies Y$ is equivalent to $\neg Y\implies\neg X$. Demonstrating that whenever $Y$ is false, then $X$ is false, is again showing $X\implies Y$, and not the required $Y\implies X$.

So we have not demonstrated that $X$ and $Y$ are logically equivalent.