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

  • #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
 
Physics news on Phys.org
  • #2
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
    [tex]\left\lbrace n\in\mathbb N \mid (\forall x\in\mathbb N)(nx=n \Rightarrow x=1)\right\rbrace = \mathbb N.[/tex]
  2. Your ##G## is quantified like this
    [tex]G = \left\lbrace n\in\mathbb N \mid (\forall x,m\in\mathbb N)(nx = mx \Rightarrow n=m) \ \right\rbrace .[/tex]
    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.
 
Last edited:
  • Like
Likes issacnewton and MatinSAR
  • #3
Thanks nuuskur. If I write many equations like (1) and (2), it will take lot of space and I may not get any responses.
 

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
725
  • Calculus and Beyond Homework Help
Replies
1
Views
491
  • Calculus and Beyond Homework Help
Replies
3
Views
559
  • Calculus and Beyond Homework Help
Replies
3
Views
846
  • Calculus and Beyond Homework Help
Replies
1
Views
571
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
608
  • Calculus and Beyond Homework Help
Replies
6
Views
816
  • Calculus and Beyond Homework Help
Replies
26
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
829
Back
Top