I'm studying some Set Theory now and I oppose to a problem which I guess it is related to well ordering of Natural numbers. The problem is:

Prove that there is no function $f:\mathbb{N}\longrightarrow\mathbb{N}$ which for all $n\in\mathbb{N}$ we have $f(n+1) < f(n)$.


Maybe we answer it as below:

If there is any, we should have $f(0)>f(1)>f(2)>f(3)>\dots$ and it's not the case because the set of Natural numbers is not "left-unbounded".

but the MAIN problem is I must use the set theoretic construction of Natural numbers (Neumann's construction which is based on $\varnothing$ set. ($0=\varnothing, 1=\{\varnothing\}, 2=\{\varnothing,\{\varnothing\}\},\dots$)).

How can I describe well-ordering in $\mathbb{N}$ or what do I should to do?

Thank you in advance.

  • $\begingroup$ See Elements of set theory by Herbert B. Enderton books.google.com.br/… $\endgroup$ – MathOverview Jan 11 '13 at 13:31
  • $\begingroup$ thank you Elias, It's useful to know more for me. $\endgroup$ – RSh Jan 11 '13 at 14:47

Suppose you know that $\mathbb{N}$ is well-ordered by $<$. This means that every nonempty subset of $\mathbb{N}$ has a least element. Now, $\{ f(n)\, :\, n \in \mathbb{N} \}$ is certainly a non-empty subset of $\mathbb{N}$, and so it has a least element. Is this possible if $f$ is strictly decreasing?

If you need to show that $\mathbb{N}$ is well-ordered, you'll first need to tell me what set-theoretic construction you're using! (I've removed the answer I previously left about von Neumann's construction etc.)

Added: You can prove by induction that $\mathbb{N}$, as constructed in your post, has no infinite descending $\in$-chains. First note that if $n \in \mathbb{N}$ then $n$ is a natural number, so it suffices to show that no natural number $n$ has an infinite descending $\in$-chain.

The base case is just $\varnothing$: the length of the longest $\in$-chain is $0$ since it has no elements at all!

Now suppose that all $\in$-chains in the set $n$ have length $\le n$. (That is, if $a_1, a_2, \dots, a_k \in n$ and $a_1 \in a_2 \in \cdots \in a_k$ then $k \le n$.) Prove from this that all $\in$-chains in the set $n+1 = n \cup \{ n \}$ have length $\le n+1$.

  • 1
    $\begingroup$ I don't believe you need Foundation to show that $\in$ defines a well ordering on $\mathbb{N}$. (At least if you identify $\mathbb{N}$ with the least inductive set you can show that no element of $\mathbb{N}$ contains itself; Jech's Set Theory (3rd ed) has a series of exercises in the Chapter 1 which establishes this.) $\endgroup$ – user642796 Jan 11 '13 at 13:42
  • $\begingroup$ @RR: Maybe I was confused about what you mean by 'set theoretic definition'. What did you mean? I've updated my answer to give something less ZFC. $\endgroup$ – Clive Newstead Jan 11 '13 at 13:52
  • 1
    $\begingroup$ @Clive Newstead: Thank you for your help Clive. I have updated my question to make it more clear. I use Neumann's construction as described in updated question. If we may not use Foundation Axiom, how we answer to this problem? it seems my approach to this question is not true! (isn't it?) $\endgroup$ – RSh Jan 11 '13 at 14:10
  • $\begingroup$ @RR: I've added to my answer. $\endgroup$ – Clive Newstead Jan 11 '13 at 14:44
  • $\begingroup$ @RR: Is something wrong? I notice you accepted and then un-accepted the answer. $\endgroup$ – Clive Newstead Jan 11 '13 at 15:53

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.