- #1

issacnewton

- 1,007

- 31

- 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

$$ 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