I was wondering if it is possible to construct an explicit bijection from the set of primes to the set of square-free integers. Thanks.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The $2$ sets have the same cardinality, so there exists a bijection. One explicit example would be mapping the $n$-th prime to the $n$-th square-free number: $$2 \mapsto 1 \\ 3 \mapsto 2 \\5 \mapsto 3 \\7 \mapsto 5 \\11 \mapsto 6 \\ \ldots $$
There is an obvious bijection between the set of finite sets of primes and the set of positive squarefree integers, which sends each finite set of primes to the product of all elements in that set (where the empty product is considered to be $1$). This is clearly surjective, and is injective. I wonder whether there is a nice general proof which exhibits a "natural" bijection between a countable set $S$ and the set of all finite subsets of $S$ (there is a bijection- it's just a question of whether it can be done in a uniform manner) I suppose some sort of lexicographic order should work, but I don't see a quick "trick" .