Discovering a Total Injection from R to [0,1]

[favq]

Homework Statement

Give an example of a set S such that there is no total injective relation from S to the real interval [0,1]

Relevant Equations

A relation R from A to B is total injective iff:
- For all a in A, there is a b in B such that a R b (total property)
- There are no $a_1$ in A, $a_2$ in A and $b$ in B such that $a_1 \neq a_2$ and $a_1 R b$ and $a_2 R b$ (injective property)

My first thought was S = {1,2,3,...}. However, if I define R = { (x,y) | y = 1/x }, I have a total injective relation, so this doesn't work.
The second thought was to try S = {...,-3,-2,-1,0,1,2,3,...}. However, a total injective relation can also be found here. For example, if I do something like below:
<br /> f(x)=\left\{\begin{matrix}<br /> 1/2+1/(2x),\ x&gt;0<br /> \\<br /> 0,\ x=0<br /> \\<br /> -1/(2x),\ x&lt;0<br /> \end{matrix}\right.<br />
It is a total injective relation, because it maps 0 to 0, all positive integers to distinct values in the interval (0.5,1] and all negative integers to distinct values in the interval (0,0.5].
Even if I choose S=\mathbb{R}, it's still possible to find a total injective relation to [0,1] by using a similar piecewise definition. For example, I could define something like:
<br /> f(x)=\left\{\begin{matrix}<br /> x/4,\ 0 \leq x \leq 1<br /> \\<br /> 0.25 +1/(4x),\ x&gt;1<br /> \\<br /> 0.5-x/4,\ -1 \leq x \leq 0<br /> \\<br /> 0.75 -1/(4x),\ x&lt;-1<br /> \end{matrix}\right.<br />
Next, I wondered whether \mathbb{R} \times \mathbb{R} could work.
However, I'm stuck now. Out of ideas to see why \mathbb{R} \times \mathbb{R} has or has not a total injection to [0,1].
Any hints on how to find S?
Thank you in advance.

 

[fresh_42]

I haven't checked, but how about the unit circle?

 

[PeroK]

If I understand the terminology, you are looking for a set that is "bigger" than $[0,1]$?

 

[Infrared]

Fact: For any set $X$, there is no injection $2^X\to X$, where $2^X$ denotes the power set of $X$.

Proof: It's equivalent to show that there is no surjection $X\to 2^X$. Let $f:X\to 2^X$ be any function and consider $S=\{x\in X: x\notin f(x)\}.$ Then there is no $s\in S$ such that $f(s)=S$ (hint: is $s\in S$?)

I haven't checked, but how about the unit circle?

There is a bijection $[0,1)\to S^1$ by $x\mapsto (\cos(2\pi x),\sin(2\pi x))$ and $[0,1)$ injects into $[0,1].$ There is of course no continuous injection $S^1\hookrightarrow [0,1]$ though.

 

[fresh_42]

There is a bijection $[0,1)\to S^1$ by $x\mapsto (\cos(2\pi x),\sin(2\pi x))$ and $[0,1)$ injects into $[0,1].$ There is of course no continuous injection $S^1\hookrightarrow [0,1]$ though.

My idea was, that this is either not total (missing one point in the range) or otherwise not injective (twice a point in the range). But as mentioned, I haven't checked details.

 

[PeroK]

My idea was, that this is either not total (missing one point in the range) or otherwise not injective (twice a point in the range). But as mentioned, I haven't checked details.

I think that "total" refers to a relation and means that it includes the whole of the domain. I don't think it means surjective.

That means that what was required was a set with a higher cardinality than the real numbers.

 

[Infrared]

My idea was, that this is either not total (missing one point in the range) or otherwise not injective (twice a point in the range). But as mentioned, I haven't checked details.

In any event, there is definitely a bijection $S^1\to [0,1]$. First of all, $S^1$ is in bijection with $[0,1)$. Then to get a bijection $[0,1)\to [0,1]$, take a map which is bijective on their set of rational points (possible since both have countably many rationals), and the identity on irrationals.

 

[hilbert2]

The set of all functions $f:\mathbb{R}\rightarrow\mathbb{R}$ is larger, in the sense of cardinality, than $\mathbb{R}$ or any subset of it. But you have to justify it with your own words. Not sure if the set of all functions $f:\mathbb{R}^n \rightarrow \mathbb{R}$, with $n\in\mathbb{N}$ not limited, is of even higher cardinality (?)

 

[PeroK]

Not sure if the set of all functions $f:\mathbb{R}^n \rightarrow \mathbb{R}$, with $n\in\mathbb{N}$ not limited, is of even higher cardinality (?)

It's not higher cardinality, as you have a bijection from $\mathbb{R}^n$ to $\mathbb{R}$, as they have the same cardinality.

 

[sysprog]

@hilbert2, if it weren't for what @PeroK said, you might have had a candidate for a disproof of the continuum hypothesis.

 

[hilbert2]

It's not higher cardinality, as you have a bijection from $\mathbb{R}^n$ to $\mathbb{R}$, as they have the same cardinality.

Ok, then maybe the set of all functionals from $\left\{f:\mathbb{R}\rightarrow\mathbb{R}\right\}$ to $\mathbb{R}$.

 

[PeroK]

Ok, then maybe the set of all functionals from $\left\{f:\mathbb{R}\rightarrow\mathbb{R}\right\}$ to $\mathbb{R}$.

You can check it out here:

https://en.wikipedia.org/wiki/Aleph_number

I suspect that if $X$ is the set of all real-valued functions, then the next cardinality is the set of all functions from $X$ to $X$. And your set of functionals would have the lesser cardinality.

Informally, $|\mathbb{R}^{\mathbb{N}}| = |\mathbb{R}|$ etc. You need $\mathbb{R}^{\mathbb{R}}$ to get the next cardinal and so on.

 

[Infrared]

You can check it out here:

https://en.wikipedia.org/wiki/Aleph_number

I suspect that if $X$ is the set of all real-valued functions, then the next cardinality is the set of all functions from $X$ to $X$. And your set of functionals would have the lesser cardinality.

Informally, $|\mathbb{R}^{\mathbb{N}}| = |\mathbb{R}|$ etc. You need $\mathbb{R}^{\mathbb{R}}$ to get the next cardinal and so on.

$\mathbb{R}^{\mathbb{R}}$ has the same cardinality as $2^{\mathbb{R}}$ because $|\mathbb{R}^{\mathbb{R}}|=|\left(2^{\mathbb{N}}\right)^{\mathbb{R}}|=|2^{\mathbb{N}\times\mathbb{R}}|=|2^{\mathbb{R}}|$

Whether or not there are cardinalities between $\mathbb{R}$ and $2^{\mathbb{R}}$ is a case of the generalized continuum hypothesis (https://en.wikipedia.org/wiki/Continuum_hypothesis#The_generalized_continuum_hypothesis) which is known to be independent of ZFC.

 

[hilbert2]

I have to refresh my cardinality algebra, but intuitively I'd think that the set of all functionals taking a real function as an argument and producing a real number as result is of higher cardinality still than the set of real functions, at least if the functional doesn't have any restrictions about the continuity, differentiability and integrability of that real function. And the set of all mappings taking a functional as an argument and producing other functional as a result could be even larger.

Edit: OK, one version of this problem is mentioned on page 34 of this book.