Is there a bijection between uncountable sets?

Question

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

Answer 1

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$.

Answer 2

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

Answer 3

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}}$$

Answer 4

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).

Answer 5

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