Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So i've been stuck on this problem for about an hour. I can't figure out how to do it, and help would be absolutely amazing. This is what's given:

$0 + 1 = 1$

$\forall x (x + 0 = x)$

$\forall x \forall y [x + (y+1)= (x+y)+1]$

$[0 + 1 = 1 + 0 \wedge \forall x(x + 1 = 1 + x \rightarrow (x+1)+1 = 1+(x+1)))] \rightarrow \forall x (x+1=1+x)$

And with these premises, I need to get $\forall x (x+1=1+x)$.

Help would be great. I keep getting closeish, only to find I'm actually doing it totally wrong.

share|cite|improve this question
Sometimes it's good to give yourself more than an hour! – Yuval Filmus Dec 2 '10 at 4:54

The last axiom is basically your induction statement: it says that if you can prove that $x+1 = 1+x$ for $x=0$, and you can prove that if it holds for $x$ then it holds for $x+1$, then you can conclude that the statement $x+1=1+x$ holds for all $x$. So you want to use your first and second axioms, as well as your third axiom, to show that the premises of the last axiom hold. That will give the conclusion you want.

share|cite|improve this answer

Step 1: Prove 0+1=1+0

Apply premise #2 for x=1, and substitute into premise #1.

Step 2: Prove Ax [x+1=1+x -> x+1+1=1+(x+1)]

Suppose k+1=1+k (premise)

Apply premise #3 for x=1, y=k. Substitute from last premise. Apply symmetry of = to get k+1+1=1+(k+1).

Generalize. Apply premise #4 to get required result.

share|cite|improve this answer

$0 + 1 = 1 \Longrightarrow (0 + 1) + (0 + 1) \Longrightarrow (0 + 1 + 1)$ (associativity axiom) $\Longrightarrow (1 + 1)$ (identity axiom)

Continue this for $x$ number of $1$'s.

share|cite|improve this answer
Do you mean $x$ ones instead of $n$ ones? – apnorton Dec 21 '14 at 4:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.