0
$\begingroup$

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
    @Adam: To read more about the diagonal argument in Cantor's proof: http://math.stackexchange.com/questions/85024/namesake-of-cantors-diagonal-argument/85066#850662012-02-02

2 Answers 2

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.

0

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.