2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ math.stackexchange.com/q/314383/28555 shows how to construct square-free numbers from each successive prime. There will be $2^{n-1}$ square-free numbers where $p_n$ is the greatest divisor. Proportionally, each prime will be a factor of $\frac{1}{2}$ all the square-free numbers. $\endgroup$ May 10, 2014 at 1:37

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How do I prove that they have the same cardinality? I'm trying to convince myself that they do, but I don't seem to see the correspondence between them. $\endgroup$ May 10, 2014 at 0:18
  • 5
    $\begingroup$ They are both infinite and subsets of the natural numbers, so they both have the cardinality of $\mathbb{N}$. There are many proofs that there are inifintely many primes and every prime is square-free, so there are at least as many square-free numbers. $\endgroup$ May 10, 2014 at 0:20
0
$\begingroup$

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

$\endgroup$
0

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.