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
    Are you asking whether the set of well-orderings of the real numbers has cardinality strictly larger than the set of real numbers?2012-02-02
  • 0
    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.2012-02-02
  • 0
    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.2012-02-02
  • 0
    Cantor's Theorem is the statement that if $X$ is any set, and $f\colon X\to P(X)$ is any function from $X$ to its power set, then $f$ is not onto; the proof is to consider the set $\{y\in X\mid y\notin f(y)\}$ and show it is not in the image of $f$. This is the general version of "Cantor's diagonal argument", but it doesn't need you to consider well orderings (the existence of well orderings requires the Axiom of Choice, whereas Cantor's Theorem holds even in the absence of the Axiom of Choice). (cont)2012-02-02
  • 0
    I edited again to be hopefully clear - if anything needs more elaboration please say so, I find it hard to describe exactly the thing I want to be shown.2012-02-02
  • 0
    (cont) I can't really make out whether you are using the Diagonal Argument "correctly", because I don't understand what it is you are trying to show. Hence my question trying to figure out what *your* question is. Your reply seems to indicate that I did *not* interpret your intention correctly.2012-02-02
  • 0
    I'm not sure what you are trying to prove. Could you please state this clearly?2012-02-02
  • 0
    Let X be a set and A a set with at least two elements. Then the set of all functions from X to A does not have the same cardinilty as X (call the set S). I know this is true as we can find a bijection from (a subset of) S to P(X) (because {0,1}^X has the same cardinilty as P(X) for example). I wanted to use some kind of diagonal argument for the proof however, though from what I could gather it only works if you can somehow order the set X, which allows you to choose a new element of A at every point of X for this new function that is not in the bijectiion.2012-02-02
  • 0
    in my question I was trying to be concrete and use an example (the first one I thought up before coming to the idea) as I assumed it would be easier - I am not very good with explanations though so the confusion is my fault.2012-02-02
  • 1
    @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.2012-02-02
  • 0
    I'm unsure if I should edit the original question - do you think that would be best?2012-02-02
  • 0
    Ah right, makes more sense - thanks Arturo!2012-02-02
  • 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