0
$\begingroup$

I wish to prove

$$(\forall x)(\forall y)(\forall z)((x < y \land y < z) \rightarrow x < z)$$

only using the rules of Peano Arithmetic (PA) including the induction rule. I have seen other resources here:

Induction proof of transitivity

Prove by induction that P is transitive

but they do not answer my question and I am stuck on performing the induction given several free variables.

$\endgroup$
  • 1
    $\begingroup$ The first important question is: how have you defined $<$? Equally important, what kind of axioms are you using for Peano Arithmetic? $\endgroup$ – Carl Mummert Mar 11 at 2:28
  • $\begingroup$ I am using the Robinson's Axioms as described here: web.mit.edu/24.242/www/Robinson'sArithmetic.pdf where Q11 defines <. Sorry - this should be been more specific $\endgroup$ – Nucl3ic Mar 11 at 2:46
  • $\begingroup$ The system of Robinson's Axioms (Q) is not the same as Peano Arithmetic (PA). Most notably, Q does not include induction which makes it a lot weaker .... indeed, note that the reference you provided states how you can't even prove basic commutativity, associativity, or distribution laws in Q ... and I don't see how you can prove transitivity in Q either. So ... are you using Q or are you using PA? $\endgroup$ – Bram28 Mar 15 at 16:05
1
$\begingroup$

We start proving by Induction in the meta-theory:

$\forall z \ [(\text m < \text n ∧ \text n < z) → (\text m < z)]$.

Basis : $z=0$.

We assume $(\text m < \text n ∧ \text n < 0)$; from it : $(\text n < 0)$.

From (Ax.Q9) we get : $\lnot (\text n < 0)$. Using tautology : $\lnot p \to (p \to q)$ we conclude with :

$(\text m < 0)$.

Induction step : let assume $(\text m < \text n ∧ \text n < z) → (\text m < z)$.

Assume : $(\text m < \text n ∧ \text n < s(z))$. From it we get : $(\text n < s(z))$.

Using (Ax.Q10) we get : $(\text n < z) \lor (\text n = z)$.

Two cases : (a) $(\text n < z)$.

With $(\text m < \text n)$ and Induction Hyp we get : $(\text m < z)$.

(b) $(\text n = z)$. Again, using $(\text m < \text n)$ and axioms for equality we get : $(\text m < z)$.

From $(\text m < z)$ we get $(\text m < z) \lor (\text m = z)$.

Using (Ax.Q10) we get : $(\text m < s(z))$.

Thus, we conclude with :

$(\text m < \text n ∧ \text n < s(z)) \to (\text m < s(z))$.

In this way, we have proved by Induction :

$\forall z \ [(\text m < \text n ∧ \text n < z) \to (\text m < z)]$.

By Generalization, we have :

$\forall x \ \forall y \ \forall z \ [(x < y ∧ y < z) \to (x < z)]$.

$\endgroup$

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.