Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Fred Kline May 10 at 1:37

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
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. –  David Cardozo May 10 at 0:18
5  
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. –  Leif Sabellek May 10 at 0:20

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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