Cantor's diagonal argument modified version

69 Views Asked by At

I have the following doubt regarding Cantor's diagonal argument. First of all, the "usual case" is quite clear for me. If $X$ is some set, then we can show there is no surjection from $X$ onto the set $\mathcal{F}(X;\{0,1\})$ of functions $f: X\to \{0,1\}$ by the following procedure:

We consider $\varphi : X\to \mathcal{F}(X;\{0,1\})$ to be any function. It sufices to construct $f \in \mathcal{F}(X;\{0,1\})$ such that $f\notin \varphi(X)$. This can be done quite directly as

$$f(x) = \begin{cases}1, & \text{if} \ \varphi(x)(x)=0, \\ 0, & \text{if} \ \varphi(x)(x)=1.\end{cases}$$

In that case, it is clear that $f(x)\neq\varphi(x)(x)$, so $f\neq \varphi(x)$ for any $x\in X$ and $\varphi$ is not surjective.

Now, a slightly modified version I've found is:

If $X$ is any non-empty set and $Y$ is a set with at least two elements, no function $\varphi : X \to \mathcal{F}(X;Y)$ is surjective.

If $Y$ has at least two elements, we can label them $0_Y$ and $1_Y$. I've tried the same procedure, that is, let $\varphi : X\to \mathcal{F}(X;Y)$ be given and define $f : X\to Y$ by

$$f(x) = \begin{cases}1_Y, & \text{if} \ \varphi(x)(x)=0_Y, \\0_Y, & \text{if} \ \varphi(x)(x)=1_Y.\end{cases}$$

But this is not well-defined. Indeed, since $Y$ has at least two elements, there can be more elements on $Y$. In that case, it could happen that $\varphi(x)(x)$ is neither $0_Y$ or $1_Y$ and in that case $f(x)$ is not well-defined.

My workaround was the following: first of all, it is quite easy to notice that if $A$ and $B$ are non-empty sets and $X\subset B$ is non-empty, then if there is no surjection $f : A\to X$ there is also no surjection $g : A\to B$. In that case, we can see that $\mathcal{F}(X;\{0_Y,1_Y\})\subset \mathcal{F}(X;Y)$, so we can use the usual argument to conclude there is no surjection from $X$ onto $\mathcal{F}(X;\{0_Y,1_Y\})$ and use this to conclude the same for $\mathcal{F}(X;Y)$.

Although my workaround works, I'd like to know if there is any other more direct way. Is any other, possibly better, way of proving this result?

1

There are 1 best solutions below

0
On

take map from $X$ to $Y$.

Pick a point of $Y$ say $y_0$.

Define $f: Y \to \{0,1\},$ by $f(y_0) =0,$ and all other points go to $1.$

Let $\theta : X \to F(X,Y).$ Consider the map $$ \theta' : X \to F(X,\{0,1\}) $$ obtained by composing the image function with $f.$ This is not onto. So $\theta$ cannot be onto either.