Sets with same Cardinality, but no Explicit Bijection?

Question

Are there any good examples of sets where we know that they have the same cardinality, but have not found any explicit bijection between them?

Answer 1

The real numbers have the same cardinality as the elements of a basis of the real numbers regarded as a vector space over the rationals. The existence of such a basis needs some appropriate form of the axiom of choice, so the basis cannot be given explicitly, let alone any bijection.

Answer 2

We do not know a bijection between $\omega_1$ (the first uncountable ordinal) and $\Bbb R$. While the existence of $\omega_1$ does not require the Axiom of Choice (in contrast to Mark Bennett's example), the existence of a bijection requires the Continuum Hypothesis and an explicit bijection would amount to an explicit well-ordering of $\Bbb R$.

If you don't like CH, just take a correspondingly larger ordinal, you would still need to well-order $\Bbb R$ to get a bijection.

Answer 3

If two sets of the same size are given explicitly and "constructively", then generally someone can find and/or has found an explicit bijection. But many sets are not so-defined: we may know that such a set must exist, and we may be able to state its cardinality, but without being able to provide much more detail.

For example, the Vitali set: a continuum-sized non-measurable set of reals "defined" using the Axiom of Choice (AC). (The Vitali set is a set of representatives of the equivalence relation on the reals: $x \sim y \iff x - y \in \mathbb{Q}$.) The set is guaranteed to exist by AC, but it's just one of many possible sets of representatives of $\sim$. We know that there's a bijection between this set and $\mathbb{R}$, but we know too little about the set to say much more.

Answer 4

The family of Borel subsets of $\mathbb{R}$ has the same cardinality as $\mathbb{R}$: $$ |\mathcal{B}(\mathbb{R})| = |\mathbb{R}|. $$ But there is no way to construct an "explicit" bijection.

---

Also I was thinking of continuous functions, but it is "easy" to construct an injection $C(\mathbb{R})\to \mathbb{R}$ in this case, so not so interesting.

Answer 5

If you don't require the sets to be explicitly given one could show that there exists subsets $A$ and $B$ of $\mathbb N$ such that there exists no explicit bijection.

If a injection is explicit it has to be possible to describe the injection and a description of the function is a finite string of symbols. By this fact these are only countable. The same is true for their images $\phi(\mathbb N)$.

But $\{x\in2^\mathbb N: |x|=\mathbb N\}$ is non-countable so there exists an infinite subset of $\mathbb N$ such that it is not the image of any of the explicit injections.

Answer 6

The set of transcendental numbers, set of irrational numbers and the set of real numbers are all uncountable and have the same cardinality. It is not clear (at least to me) how to construct a bijections among them.

The set of rational numbers and the set of algebraic numbers are both infinite countable sets. Here also it is not clear how to construct a bijection.