Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates

[issacnewton]

Homework Statement

Prove if $a\cdot c = b \cdot c$ then $a = b$ using Peano postulates, given that $a,b,c \in \mathbb{N}$

Relevant Equations

The book I am using ("The real numbers and real analysis" by Ethan Bloch) defines Peano postulates little differently.

Following is a set of Peano postulates I am using. (Axiom 1.2.1 in Bloch's book)

There exists a set $\mathbb{N}$ with an element $1 \in \mathbb{N}$ and a function $s: \mathbb{N} \rightarrow \mathbb{N}$ that satisfy the following three properties.

1) There is no $n \in \mathbb{N}$ such that $s(n) = 1$
2) The function $s$ is injective.
3) Let $G \subseteq \mathbb{N}$ be a set. Suppose that $1 \in G$, and that if $g \in G$ then $s(g) \in G$. Then $G = \mathbb{N}$

And addition operation is given in Theorem 1.2.5 as follows

There is a unique binary operation $+: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ that satisfies the following two properties for all $n, m \in \mathbb{N}$

a. $n + 1 = s(n)$
b. $n + s(m) = s(n + m)$

Multiplication operation is given in Theorem 1.2.6 as follows

There is a unique binary operation $\cdot: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ that satisfies the following two properties for all $n, m \in \mathbb{N}$

a. $n \cdot 1 = n$
b. $n \cdot s(m) = (n \cdot m) + n$

I am also going to assume following results for this proof. I have proven the following results using Peano postulates already.

Identity law for multiplication for $a \in \mathbb{N}$

$$ a \cdot 1 = a = 1 \cdot a $$

Distributive law

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

Commutative Law for addition

$$a + b = b + a$$

Cancellation law for addition

$$\text{ If } a + c = b + c \text{ then } a = b $$

This law
$$ a + b \ne a $$

Also, I am going to assume the following lemma which is proven in the book (Lemma 1.2.3)

Let $a \in \mathbb{N}$. Suppose that $a \ne 1$. Then there is a unique $b \in \mathbb{N}$ such that $a = s(b)$.
=============================================================

with this background, we proceed to the proof. Let us define a set

$$ G = \{ x \in \mathbb{N} | \; y, z \in \mathbb{N}\; \text{ if } (x \cdot z) = (y \cdot z) \text{ then } x = y \} $$

We want to prove that $G = \mathbb{N}$. For this purpose, we will use part 3) of Peano postulates given above. Obviously, $G \subseteq \mathbb{N}$. Let $y, z \in \mathbb{N}$ be arbitrary. Suppose $1 \cdot z = y \cdot z$. Using Identity law for multiplication, we have $y \cdot z = z$. So, we need to prove that $y = 1$, so that $1 \in G$. Assume $y \ne 1$. Now using lemma 1.2.3 given in relevant equations, $y = s(t)$ for some $t \in \mathbb{N}$. So, we have $s(t) \cdot z = z$. Or $(t + 1) \cdot z = z$. Now using Distributive law, $t \cdot z + 1 \cdot z = z$. And using Identity law for multiplication, this becomes $t \cdot z + z = z$. Using Commutative Law for addition, $z + t \cdot z = z$. But this violates one of the given equations $a + b \ne a$. So, our assumption that $y \ne 1$ is wrong and we must conclude that $y = 1$. So, this proves the implication that if $(1 \cdot z) = (y \cdot z)$ then $1 = y$. Since $1 \in \mathbb{N}$, and since $y, z \in \mathbb{N}$ are arbitrary to begin with, this proves that $1 \in G$. Next thing, we need to prove that if $r \in G$ then $s(r) \in G$. So, suppose that $r \in G$. This means that $r \in \mathbb{N}$ and

$$ \forall y,z \in \mathbb{N} \; \bigl[ (r \cdot z) = (y \cdot z) \longrightarrow (r = y) \bigr] \cdots\cdots (1) $$

From the definition of function $s$, is seen that $s(r) \in \mathbb{N}$. So, to prove $s(r) \in G$, we need to prove that

$$ \forall y,z \in \mathbb{N} \; \bigl[ (s(r) \cdot z) = (y \cdot z) \longrightarrow (s(r) = y) \bigr] \cdots\cdots (2)$$

So, let $y, z \in \mathbb{N}$ be arbitrary and suppose that $s(r) \cdot z = y \cdot z$. Using addition definition, we have $y \cdot z = (r + 1) \cdot z$. Using Distributive law, $y \cdot z = r \cdot z + 1 \cdot z$ and using Identity law for multiplication, $y \cdot z = r \cdot z + z$. Now if $y = 1$, then $y \cdot z = 1 \cdot z = z = r \cdot z + z$. Using Commutative Law for addition, we have $z + r \cdot z = z$ and this contradicts one of the laws given in relevant equations section ($a + b \ne a$). So, our assumption that $y = 1$ is wrong. So, $y \ne 1$ and using lemma 1.2.3 given in relevant equations section, $y = s(k)$ for some $k \in \mathbb{N}$. Now, we have $y \cdot z = r \cdot z + z$. It implies that $s(k) \cdot z = r \cdot z + z$. Using, addition definition and using Distributive law, we get $(k \cdot z) + z = (r \cdot z) + z$. Using, Cancellation law for addition, we have $(k \cdot z) = (r \cdot z)$. Now since $r \in G$, we can use equation (1) given above to conclude that $r = k$. It follows that $s(k) = y = s(r)$. So, we proved the implication that
$(s(r) \cdot z) = (y \cdot z) \longrightarrow (s(r) = y)$. Since $y, z \in \mathbb{N}$ are arbitrary, we prove equation (2). It then implies that $s(r) \in G$. Using part 3) of Peano postulates, it follows that $G = \mathbb{N}$. Now since $a,b,c \in \mathbb{N}$, it follows that $a,b,c \in G$ and it implies that if $a \cdot c = b \cdot c$ then $a = b$. This proves the final result.

Is this a valid proof ?
Thanks

 

[nuuskur]

You could save so much space and the reader's (and your own) sanity by writing things more concisely.

1. Show by induction on $n\in\mathbb N$ that $nx=n$ implies $x=1$. I.e
   $$\left\lbrace n\in\mathbb N \mid (\forall x\in\mathbb N)(nx=n \Rightarrow x=1)\right\rbrace = \mathbb N.$$
2. Your $G$ is quantified like this
   $$G = \left\lbrace n\in\mathbb N \mid (\forall x,m\in\mathbb N)(nx = mx \Rightarrow n=m) \ \right\rbrace .$$
   Quantifiers are important. Base case follows from 1. Suppose $n\in G$ and let $s(n)x=mx$ for some $m,x$. If $m=1$, then $s(n)x=x$ implies $s(n)=1$, which can't happen. Write $m = s(k)$ for some $k$, then $s(n)x = s(k)x$. By distributivity we have $nx+x = kx +x$, which implies $nx = kx$ due to cancellative property of $+$. Therefore, $n=k$ by induction assumption and $s(n)=s(k)=m$, as required.
3. It's often regarded as bad style to write predicate formulae inside sentences. Use display mode for those as you do with (1) and (2).

Otherwise, it's correct.

 

[issacnewton]

Thanks nuuskur. If I write many equations like (1) and (2), it will take lot of space and I may not get any responses.