Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I already asked this question here, but unfortunately no acceptable answers were provided. Also, I hope this is not too basic for MathOverflow.

I'm studying on K. Hrbacek and T. Jech, Introduction to Set Theory. In the third chapter, they prove the usual properties of the strict ordering on natural numbers in the following way:

  1. They prove transitivity using induction.
  2. They prove irreflexivity using induction and transitivity.
  3. They prove asymmetry by contradiction and using transitivity and irreflexivity.

There is nothing wrong with this, but I'd like, if possible, to prove the previous properties (in particular irreflexivity and asymmetry) independently and using induction only.

For example, let $\phi(x)$ be $x\not\in x$. Of course $\phi(0)$ is true ($0\not\in 0$ since $0$ is the empty set). Now I should suppose that $\phi(x)$ is true and show that $\phi(x+1)$ is true, too. $\phi(x+1)$ stands for $x+1\not\in x+1$, that is $x+1\not\in x$ and $x+1\not=x$. But here I cannot go on, mainly because $x+1$ is at the left of the relations symbols.

$x+1$ is defined as $x\cup\{x\}$.

Any hint? Thank you.

share|improve this question

2 Answers 2

With the common set-theoretic approach of defining the order in terms of $\subseteq$ or $\in$, appealing to eg transitivity/ordinality is unavoidable. But if you take a slightly different approach to the definitions, these can certainly be done with just induction and a couple of basic facts about the surrounding set theory; and the end result is in a sense more natural, not depending on the specific implementation of the numbers.

Suppose $N$ is any set, $0 \in N$, and $s: N \to N$, and $(N,0,s)$ satisfy the usual induction principle.

Then firstly, you can bump this up to the recursion principle: that you can define functions on $N$ (in particular, $\{0,1\}$-valued functions, i.e. predicates) by recursion. This is where you need to use a few things in how the surrounding theory treats functions and so on. (You could also start by saying that recursion, rather than induction, should be the basic defining principle of the natural numbers.)

Now you can define the strict ordering by recursion:

  • $0 \not < 0$;
  • $0 < s(n)$;
  • $s(n) \not < 0$;
  • $s(n) < s(m)$ iff $n < m$.

Now irreflexivity, transitivity and antisymmetry are all immediate by induction… just divide up into the appropriate cases, and the induction steps fall straight out :-)

share|improve this answer

$x+1\neq x$ just follows from $\phi (x)$. Now you need $x+1\not\in x$. Suppose the opposite. Then $x+1\in x$ and by ordinality $x+1\subseteq x$. But this will imply that $x\in x$, contradiction with the induction assumption.

share|improve this answer
    
At this point of the book addition is not yet defined, so I can't show that $x+y\not\in x$. –  Francesco Turco Sep 27 '10 at 11:11
    
You don't need addition, just the order. But I see a shortcut that will do it without the order. Bear with me, doc. –  Bugs Bunny Sep 27 '10 at 12:34
    
I feel this answer is somewhat unsatisfying, since it appeals to the specific implementation of numbers as ordinals, whereas the numbers could just have well been implemented in many other ways; the only crucial thing is induction. I'll address this in a separate answer... –  Peter LeFanu Lumsdaine Sep 27 '10 at 15:30
    
Oh — OK, I realise I was forgetting that Jech/Hrbacek actually define the order in terms of the specific ordering, so appeals to eg ordinality are unavoidable! –  Peter LeFanu Lumsdaine Sep 27 '10 at 15:33

Your Answer

 
discard

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

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