2
$\begingroup$

I know that there is a bijection between naturals and rationals. I also know that there is no bijection between naturals and reals (diagonal argument).

But, I have never heard of the existence of a bijection between uncountable sets (ex aleph-one). Is there a way to create a (computable ?) function that takes an element from an uncountable set and outputs (in infinite time ?) an element from another uncountable set ?

(I do not have a strong mathematical background, so please keep it simple or use terms of computer science)

[EDIT]
It seems that my question was very trivial. An answer would be y = f(R) where f is just one-to-one. I was hoping for something more sophosticated :( . Sorry for the inconvenience.

[EDIT2]
How we would construct a bijection between these sets ?
A = reals
B = reals without naturals
C = reals without primes

$\endgroup$
  • 4
    $\begingroup$ There is a whole hierarchy of uncountable sets, between which no bijection is possible. $\endgroup$ – Yves Daoust Feb 15 '20 at 10:19
  • $\begingroup$ @A.G Do you have an example from reals to another set not having reals (maybe another entity) ? $\endgroup$ – entropyfeverone Feb 15 '20 at 10:19
  • 1
    $\begingroup$ @YvesDaoust I know that. I am talking about sets with same cardinality (but bigger than aleph-null) $\endgroup$ – entropyfeverone Feb 15 '20 at 10:20
  • 2
    $\begingroup$ @entropyfeverone: sets are said to have the same cardinality if there is a bijection between them. So by definition, … there is a bijection between them. Maybe are you asking "are there uncountable sets with the same cardinality" ? $\endgroup$ – Yves Daoust Feb 15 '20 at 10:21
  • 1
    $\begingroup$ I agree to be serious but I have no idea what you mean. $\endgroup$ – Yves Daoust Feb 15 '20 at 13:10
1
$\begingroup$

For a bijection between $A$ and $B$, consider the application that sends every natural $n$ to $e^n$, and $e^n+m$ to $e^n+m+1$ for non-negative integer $m$.

$\endgroup$
  • 1
    $\begingroup$ I find it really difficult to apply mathematical terms into a computer program. For example, your answer is really understandable in the context of mathematics. But a computer program cannot even compare two reals in finite time. I mean a program of the form: for each a in A: if log(a) == n then return e^(n + 1) doesn’t make any sense at all :p Maybe I will have to read about symbolic languages that automatic provers use. $\endgroup$ – entropyfeverone Feb 15 '20 at 13:44
  • 1
    $\begingroup$ @entropyfeverone: what is the relevance of discussing infinity (or even big numbers) in computer programs ? $\endgroup$ – Yves Daoust Feb 15 '20 at 13:46
  • $\begingroup$ There is no relevance. I was just adding a comment. I liked your answer. $\endgroup$ – entropyfeverone Feb 15 '20 at 13:46
  • $\begingroup$ Caution: my answer was wrong. I have fixed. Every natural corresponds to an infinite chain of irrationals, without overlaps. $\endgroup$ – Yves Daoust Feb 15 '20 at 14:55
1
$\begingroup$

Example: from $\Bbb R$ to $(-\pi/2,\,\pi/2)$ with $\arctan x$.

$\endgroup$
1
$\begingroup$

The following is a bijection from $\mathcal P(\mathbb N)$ to the Cantor set: $$f(A) = \sum_{n\in A}\frac{2}{3^{n+1}}$$

$\endgroup$
0
$\begingroup$

Since you are asking about computable bijections, and the other answers (at the time of writing this) do not address this point, let me weigh in on this.

1) There is no computable bijection $f : \mathbb{R} \to \mathbb{R}\setminus\mathbb{Q}$.

In fact, whenever $f : \mathbb{R} \to \mathbb{R}\setminus \mathbb{Q}$ is a computable function, then it already is a constant function. The reason is that computable functions are always continuous, and the image of a connected space such as $\mathbb{R}$ under a continuous function has to be connected again.

2) There is no computable bijection $g : \mathbb{R}\setminus\mathbb{Q} \to \mathbb{R}$.

This one is slightly trickier, but still follows from the continuity considerations. Here, however, it is demanding the injectivity that gets us. We can have a computable surjection from $\mathbb{R}\setminus \mathbb{Q}$ to $\mathbb{R}$.

3) As for 1), we cannot have a computable surjection from $\mathbb{R}$ to $\mathbb{R} \setminus \mathbb{P}$. The most we can get is the interval between two primes.

4) We don't get a computable bijection from $\mathbb{R}\setminus\mathbb{P}$ to $\mathbb{R}$ either, but a computable surjection works.

5) There is a computable surjection from $\mathbb{R}\setminus\mathbb{Q}$ to $\mathbb{R}\setminus\mathbb{P}$, but not the other way around.

The bijection between $2^\mathbb{N}$ and the Cantor middle third set inside $\mathbb{R}$ mentioned by celtschk is computable in both directions.

The standard (but a bit out-dated) textbook in this area is Weihrauch: Computable Analysis (2000). A briefer intro in a semilar style is Brattka, Hertling & Weihrauch: A tutorial on computable analysis (2008). More general, but maybe also less newcomer friendly is Pauly: On the topological aspects of the theory of represented spaces (2016).

$\endgroup$
-3
$\begingroup$

Use $\sim$ to indicate the existence of a bijection between two sets.

Thanks to a theorem of Cantor, there is no set $A$ for which $$A\sim \mathcal P(A)$$ so not every uncountable set can be made into bijection. Moreover thanks to Cantor-Bernstein theorem, two infinite sets $A,B$ can be made in a bijection if and only if $$\exists A_1 \subset A: A_1\sim B$$ $$\exists B_1 \subset B: B_1\sim A$$ lastly, the question about computability does not hold since Turing machines only deal with a countable imput

$\endgroup$
  • $\begingroup$ Computability works perfectly fine on sets of size up to continuum. $\endgroup$ – Arno Feb 15 '20 at 21:05
  • $\begingroup$ Please give me a reference if you are so good $\endgroup$ – Davide Maran Feb 16 '20 at 12:20
  • $\begingroup$ The standard (but a bit out-dated) textbook in this area is Weihrauch: Computable Analysis (2000). A briefer intro in a semilar style is Brattka, Hertling & Weihrauch: [A tutorial on computable analysis][1] (2008). More general, but maybe also less newcomer friendly is Pauly: [On the topological aspects of the theory of represented spaces][2] (2016). $\endgroup$ – Arno Feb 16 '20 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.