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

  • Thread starter favq
  • Start date
  • Tags
    Injection
In summary, S is a set that is bigger than [0,1], but it is not surjective. There is a bijection from [0,1] to S^1.
  • #1
favq
8
0
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 [itex]a_1[/itex] in A, [itex]a_2[/itex] in A and [itex]b[/itex] in B such that [itex]a_1 \neq a_2[/itex] and [itex]a_1 R b[/itex] and [itex]a_2 R b[/itex] (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:
[tex]
f(x)=\left\{\begin{matrix}
1/2+1/(2x),\ x>0
\\
0,\ x=0
\\
-1/(2x),\ x<0
\end{matrix}\right.
[/tex]
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 [itex]S=\mathbb{R}[/itex], 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:
[tex]
f(x)=\left\{\begin{matrix}
x/4,\ 0 \leq x \leq 1
\\
0.25 +1/(4x),\ x>1
\\
0.5-x/4,\ -1 \leq x \leq 0
\\
0.75 -1/(4x),\ x<-1
\end{matrix}\right.
[/tex]
Next, I wondered whether [itex]\mathbb{R} \times \mathbb{R}[/itex] could work.
However, I'm stuck now. Out of ideas to see why [itex]\mathbb{R} \times \mathbb{R}[/itex] has or has not a total injection to [0,1].
Any hints on how to find S?
Thank you in advance.
 
Physics news on Phys.org
  • #2
I haven't checked, but how about the unit circle?
 
  • #3
If I understand the terminology, you are looking for a set that is "bigger" than ##[0,1]##?
 
  • #4
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##?)

fresh_42 said:
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.
 
  • Like
Likes mathwonk and sysprog
  • #5
Infrared said:
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.
 
  • #6
fresh_42 said:
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.
 
  • Like
Likes Infrared
  • #7
fresh_42 said:
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.
 
  • Like
Likes sysprog
  • #8
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 (?)
 
  • #9
hilbert2 said:
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.
 
  • Like
Likes sysprog
  • #10
@hilbert2, if it weren't for what @PeroK said, you might have had a candidate for a disproof of the continuum hypothesis.
 
  • #11
PeroK said:
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}##.
 
  • #12
hilbert2 said:
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.
 
  • Like
Likes hilbert2 and sysprog
  • #13
PeroK said:
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.
 
  • Like
Likes hilbert2, PeroK and sysprog
  • #14
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.
 
Last edited:

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

1. What is a total injection from R to [0,1]?

A total injection from R to [0,1] is a function that maps every real number in the set R to a unique value between 0 and 1 in the set [0,1]. This means that no two real numbers will be mapped to the same value in [0,1].

2. How is a total injection from R to [0,1] discovered?

A total injection from R to [0,1] can be discovered by finding a function that satisfies the definition of a total injection. This means that the function must be one-to-one, with each input having a unique output, and it must map every real number to a value between 0 and 1.

3. What is the significance of discovering a total injection from R to [0,1]?

Discovering a total injection from R to [0,1] has several applications in mathematics and computer science. It can be used in data compression, encryption, and creating bijections between different sets. It also has implications in understanding the properties of real numbers and their relationships with other mathematical concepts.

4. Can there be multiple total injections from R to [0,1]?

No, there can only be one total injection from R to [0,1]. This is because the definition of a total injection requires each real number to have a unique mapping to a value in [0,1]. If there were multiple total injections, then there would be more than one mapping for some real numbers, which would violate the definition.

5. What is the difference between a total injection and a partial injection?

A total injection is a function that maps every element in the domain to a unique element in the codomain, while a partial injection only maps some elements in the domain to unique elements in the codomain. In other words, a total injection is a one-to-one function, while a partial injection may have some elements in the domain that are not mapped or are mapped to the same element in the codomain.

Back
Top