Let us fix a well ordering of the real numbers then consider a 'list' of some subset of the real numbers (with at least two elements) - called A -, enumerated by the well ordering.

Say our well order is $ r_1, r_2 $ , ... [I know the real aren't countable].

Then to every 'sequence', $s$, (which itself is a function from the reals to the reals, where we start our sequence at $r_1$) let $s_{r_j}$ be the value of the sequence assigned to real number $r_j$ of the well ordering.

For example, let us say our well order looks like 1,5,6,1/23, at the start. Let our subset A be {2,5} Then the sequence (which is function from the real to the reals) with first 3 values 2 and fourth value 5 would be the function sending 1 and 5 and 6 to 2 and 1/23 to 5 - that is $s_1=s_{r_1} = 2$, $s_5=s_{r_2}=2$,$s_6=s_{r_3}=2$,$s_{1/23}=s_{r_4}=5$

Now, if the set of all such sequences had the same cardinalty as the real numbers, for ever sequence s there would correspond a real number - and vice versa. So we label the sequences under this supposed bijection;

$s^{r_1} , s^{r_2} , ... $

From the subset A we pick the elements (distinct) a and y.

Now consider the sequence with first value x if $s^{r_1}_{r_1}$ is y y if x, second value y if $s^{r_2}_{r_2}$ is x and vice versa, and "j'th value" x if $s^{r_j}_{r_j}$ is y and vice cersa . Then this sequence is not on the list so there was no bijection after all.

That look okay guys?

  • 1
    $\begingroup$ Are you asking whether the set of well-orderings of the real numbers has cardinality strictly larger than the set of real numbers? $\endgroup$ Feb 2, 2012 at 20:54
  • $\begingroup$ You are running into a potentially confusing issue: your well-ordering is given as a list, and so should be indexed by an ordinal; and that is more or less how you describe it; but you are saying that this "list" is "a function from the reals to the reals"; the problem is that if you are viewing it as a function from the reals to the reals, then there is no "first" value, no "second value", no "third value", etc., so that talking about "the start" does not make sense. You can fix this by first selecting a well-ordering for $\mathbb{R}$ and using that as a basis. $\endgroup$ Feb 2, 2012 at 20:59
  • $\begingroup$ Thanks for the reply Arturo - actually yes I would be interested in that question also, however for now I want to see if the (edited) version of the above has applied the diagonal argument correctly. For what I see, if we take a given set X and fix a well order (for X), we can use Cantor's diagonal argument to specify if a certain type of set (such as the function with domain X and image of {0,1} has the same cardinilty as X. $\endgroup$
    – Adam
    Feb 2, 2012 at 21:07
  • 1
    $\begingroup$ @Adam: The definition $\{y\in X\mid y\notin f(y)\}$ is a "diagonal argument". Intuitively, you "list" the elements of $X$ on the vertical of a "table", and you "list" the subsets of $X$ on the "horizontal" of a "table" (your "well-ordering") and then you put a $0$ on the $(x,S)$ entry if $f(x)\notin S$ and a $1$ if $f(x)\in S$. We are constructing the set $\{y\in X\mid y\notin f(y)\}$ by looking at the "diagonal" entries $(y,f(y))$ and "switching the value" to get a new subset. $\endgroup$ Feb 2, 2012 at 21:25
  • 1
    $\begingroup$ @Adam: To read more about the diagonal argument in Cantor's proof: math.stackexchange.com/questions/85024/… $\endgroup$
    – Asaf Karagila
    Feb 2, 2012 at 21:30

2 Answers 2


Suppose that the real numbers have cardinality $\kappa$, then there are $\kappa^+$ many ordinals which are in bijection with the real numbers, and $2^{2^{\aleph_0}}$ many ways to order them in every given order type.

This means that there are a lot more ways to order the real numbers, even if you consider them up to isomorphism.


Let $A$ be a set with at least two elements. You may be trying to give a diagonalization proof of the fact that there is no bijection from $X$ to the set $A^X$ of all functions from $X$ to $A$.

We show there is no mapping of $X$ onto $A^X$. The argument is standard diagonalization. No ordering is used.

Let $a$ and $b$ be two of the elements of $A$.
Suppose that $\varphi$ is a function from $X$ to $A^X$. For notational convenience, write $\varphi_x$ intead of $\varphi(x)$. Define a function $f$ from $X$ to $A$ as follows.

If $\varphi_x(x)=a$, let $f(x)=b$. Otherwise, let $f(x)=a$. It is easy to verify that $f$ cannot be $\varphi_x$ for any $x\in X$. For if $f=\varphi_e$, what is $f(e)$? If $f(e)=a$, then $f(e)=b$. If $f(e)\ne a$, then $f(e)=a$.

So given any mapping $\varphi$ of $X$ into $A^X$, we have produced $f\in A^X$ (where of course $f$ depends on $\varphi$) such that $f$ is not in the image of $\varphi$. So $\varphi$ cannot be onto, and therefore cannot be a bijection.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .