5

Let A be a countable subset of $\Bbb R$ which is well-ordered with respect to the usual ordering on $\Bbb R$ (where ‘well-ordered’ means that every nonempty subset has a minimum element in it). Then A has an order preserving bijection with a subset of $\Bbb N$.

It is given that the above statement is FALSE.

But I think it is true. The following is my reasoning.

If A is empty then the statement is true. Because I can give a order preserving bijection from empty set to empty set.

Let A be a non empty set. Since A is well ordered I can arrange the elements of A as $ \{x_1, x_2,x_3,....,x_n\} $ in such a way that $x_1<x_2<....<x_n.$ . So I can give a bijective function $f$ from {1,2,3,...n} to $\{x_1,x_2,...,x_n\}$ defined by $f(i)=x_i$ which is order preserving.

Similarly I can do it for infinite set too. Somehow I am not satisfied with my reasoning for the empty set. I want to know whether the given statement is true or false. If it is false why?

Brozovic
  • 2,264
Cloud JR K
  • 2,466
  • The sentence beginning "Since $A$ is well ordered$\ldots$" is false! See @Hagen von Eitzen's answer for examples of well-ordered sets where it fails. You might like to think on why your intuition is wrong in this case. – TonyK Oct 21 '18 at 12:08

2 Answers2

12

Try $$A=\{-\tfrac1n\mid n\in\Bbb N\}\cup \{42\}$$ which is an inifnite well-ordered set with a largest element - a property $\Bbb N$ does not have. Or even try $$A=\{k-\tfrac1n\mid n,k\in\Bbb N\}$$ (and there are still weirder countable well-ordered subsets of $\Bbb R$)

bof
  • 78,265
Hagen von Eitzen
  • 374,180
  • What about my reasoning for the empty set. Whether it's true? – Cloud JR K Oct 21 '18 at 11:31
  • 1
    @CloudJR There is no problem with the empty set. Why are you asking about the empty set, when Hagen von Eitzen's answer shows that your reasoning is erroneous in the infinite case? There are lots of infinite well-ordered subsets of $\mathbb R$ which do not admit an order-preserving bijection to a subset of $\mathbb N$. – bof Oct 21 '18 at 11:54
  • I asked that to know whether I'm correct or not – Cloud JR K Oct 21 '18 at 11:56
1

The statement is False. To prove that, we just need to provide an example of well-ordered subset of R that doesn't have order-preserving bijection with a subset of N.

Any set A of this type $((-1/(n)^k)UL)$ where $n$ and $k$ belong to $N$ and $L$ is any proper subset of $(0UN)$ except empty set. This is generalization of the answer above. Awesome example which I didn't see clearly before & I thought was (-n) (because I got a test tomorrow and I'm maxed out).

Also any set A of type $0U1/(n)^k$ where $n$ and $k$ belong to $N$.

Both of the sets have an infimum which makes them well-ordered and they are countable subsets of R. But also, they've a supremum, a property which N does not have.

Why this works is because in order-preserving bijection $x1<x2$ implies $f(x1)<f(x2)$ And so if a certain countably infinite set has a supremum and has an order-preserving bijection with $N$, then it would imply $N$ also has a supremum, which is a contradiction.

Shreya Singh
  • 51