1
$\begingroup$

I'm a high school student new to propositional logic. This is only my second attempt at writing a proof. I originally started with trying to prove the associativity of addition, but that was a bit complicated due to my minimal knowledge. I was advised to try and attempt to prove $1a = a$, that is $S(0)\cdot a = a$. Here is my attempt:

Prove from Peano axioms that for a natural number $a$, $1a = a$.

Assume that $a$ is a natural number. Assuming Peano's axioms apply to natural number $a$, we can say that if $a=0$, $a$ can also equal natural numbers $(1, 2, 3,...)$. So if $0$ multiplied by $1$ equals $0$, then $1a=a$ is true for every natural number.

Edit:

Lol, I know how to do proofs now:

Prove that for a natural number $a$, $1a = a$.

I'm not going to use Peano's axioms for this, I've been reading Spivak:

Taking the statement $ax = a$, I can perform the following manipulation:

$a^{-1} \cdot ax = a \cdot a^{-1}$

Which yields: $ x = 1$

(Or I can just divide both sides by $a$)

Proved it

Spivak FTW

$\endgroup$
  • 1
    $\begingroup$ just a remark: you're learning Peano's axioms in high school? that's so cool. $\endgroup$ – user29418 May 20 '18 at 5:32
  • 1
    $\begingroup$ Um, it's really good to see you try but... where is your proof? Where is your argument? Why do you believe the things you claim? What do you mean if $a=0$ can equal any natural number? $0 \ne 1,2,3 etc$. "So if 0 multiplied by 1 equal 0" (how do you know that) then "$1a =a is true for every natural number" (why does that follow. $\endgroup$ – fleablood May 20 '18 at 6:19
  • $\begingroup$ @user29148 Lol, it's kind of independent at the moment, hence the obvious gaps in knowledge. $\endgroup$ – CaptainAmerica16 May 20 '18 at 7:08
  • $\begingroup$ @fleablood To be fair, $0a=0$ is one of the Peano axioms. $\endgroup$ – Jack M May 20 '18 at 8:55
  • $\begingroup$ @Jack M So you came back! Can you see any sort of improvement over my original proof or does it seem I made the same mistakes? (I think I did) $\endgroup$ – CaptainAmerica16 May 20 '18 at 11:43
4
$\begingroup$

You seem to be trying to use induction here. While that's a valid approach, what you have done does not work. Think about what your reasoning would allow you to extrapolate here: you are basically saying any property that holds for zero holds for all numbers. This can't be right.

To use induction to prove something is true of all natural numbers requires two steps. First you show it holds for zero (the base case). Second, you show that if it holds for an arbitrary number $n$ then it also holds for $n+1.$ The second step is missing here.

Here is an informal proof, based on the PA axioms on wikipedia.

The base case follows from the axiom $\forall x(x\cdot 0=0).$

For the induction step you need to prove $\forall x(1\cdot x = x \to1\cdot S(x)=S(x)).$ To show this, we can assume $1\cdot x=x$ and from this we must prove $1\cdot S(x)= S(x).$ We use the axiom $$x\cdot S(y) = x\cdot y+x.$$ Plussing in $1$ for $x$ and $x$ for $y$ gives $$ 1\cdot S(x) = 1\cdot x+1.$$ Now we can use our assumption and substitute $x$ for $1\cdot x.$ We will also remember that $1$ is just an abbreviation for $S(0)$ and sub that into the RHS. This gives $$ 1\cdot S(x) = x+S(0).$$

Now we use the axiom $x+S(y) = S(x+y).$ This axiom with $0$ subbed in for $y$ is $x+S(0) = S(x+0).$ We can use the axiom $x+0= x$ to reduce this to $$x+S(0) = S(x).$$ Finally, plugging this in to what we had before gives us $$1\cdot S(x) = S(x),$$ which completes our proof of the induction case.

(I should add, that in "reasoning by induction", I am actually invoking PA's induction axiom for the formula $1\cdot x = x$.)

Proving things from the axioms is tedious work. Furthermore, I haven't given a formal proof. Since you seem interested in logic, I would look for an introduction to formal logic, which will show you how to lay out fully formal proofs. Also a lot of courses have software for students to use for proof writing. It might be challenging at first, and you needn't let studying that stop you from understanding and working out proofs in the style I did above.

$\endgroup$
  • $\begingroup$ That you for so much for the explanation! Coming from a background of strictly high school maths, I tend to make the mistake of setting things that need to be proven as true without explanation(ie. 1×0 =0). I've only just realized that proofs involve proving EVERYTHING that hasn't previously been determined an axiom. $\endgroup$ – CaptainAmerica16 May 20 '18 at 7:06
  • $\begingroup$ @CaptainAmerica16 The good news is that now that we've proven $\forall x(1\cdot x = x),$ we can use that theorem freely in the future. It can be a little strange putting so much effort into proving obvious things. It's really about learning the structure of the proof system. Then we can start using math to study mathematical proof itself. Things get really interesting when we learn to prove that PA (or even more powerful systems like ZFC) can't prove certain statements. $\endgroup$ – spaceisdarkgreen May 20 '18 at 7:31
  • $\begingroup$ @CaptainAmerica16 I guess I would be remiss not to add that the actual main reason to learn to prove obvious things (far more important except maybe to logicians) is to get practice with rigorous justification, since all advanced math (at least the non-applied fields) operates this way. $\endgroup$ – spaceisdarkgreen May 20 '18 at 7:44
2
$\begingroup$

You'll have to do a proof by induction if you are using Peano postulates.

We need two things.

1) The recursive definition of multiplication:

$a*0 =0$

$a*(S(b)) = a + a*b$

2) the 9th Peano axiom (induction axiom):

If a statement about a natural number $a$, is true when $a = 0$ and if whenever it is true for $a = n$ for some non-specific $n$, it follows that the statement must be true for $a=S(n)$ (but not because of any specific property of the $n$ in particular; the $n$ is non-specific) then the statement is true for all natural numbers $a$.

.....

So the statement is: $1*a = a$.

(base step) It is true for $a = 0$: as $1*0 = 0$ by the definition of multiplication.

(induction step) If we know that for some $n$ that $1*n = n$. (Not all $n$; just this one particular $n$) the we know that:

$1*S(n) = 1 + 1*n = 1 + n = S(n)$.

Thus $1*S(n)=S(n)$

(conclusion) the statement is true for $a=0$; if it is true of $a=n$ it is true for $a=S(n)$, thus the two conditions for the 9th axiom are satisfied, and therefore we conclude the statement is true for all natural numbers.

$\endgroup$
1
$\begingroup$

To show associativity, fix $m,k\in\mathbb{N}$.

Use induction on $n$ to show $\mathbb{N}=\{n\in\mathbb{N}:k+(m+n)=(k+m)+n\}$.

I clarify what our addition binary operation does. It is defined as follows.$$m+(0)=m\quad\text{and}\quad m+(n+1)=(m+(n))+1,$$where $(\cdot)+1$ is the successor function.

The proof you seek for $\mathbb{N}=\{n\in\mathbb{N}:1\times n=n\}$ is typically done by induction. First, I clarify what our multiplication binary operation does. It is defined as follows. $$m\times(0)=0\qquad\text{and}\qquad m(n+1)=(m\times(n))+m$$ A standard argument will begin with the Base Case. It is then followed by the Inductive Step.

Base Case. Observe $1\times 0=0$ by definition. The base case has been proven.

Inductive Step. Assume $1\times n= n$, where $n$ is any fixed natural number. Observe $$1\times(n+1)=(1\times(n))+1=(n)+1=n+1.$$ The inductive step has been proven.

Conclusion. By the principle of mathematical induction, for each natural number $n$, we have $1\times n=n$.

$\endgroup$
  • $\begingroup$ Is this associativity, or commutativity? $\endgroup$ – Lord Shark the Unknown May 20 '18 at 5:59
  • $\begingroup$ you're right! I for some reason thought of commutative... $\endgroup$ – Alberto Takase May 20 '18 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.