Are the Positive Multiples of 17 and 11 in Bijection?

Let $A$ be the set of positive integers divisible by 17 and $B$ the set of positive integers divisible by 11. The numbers in these sets are different, but that does not prevent the sets from having the same cardinality. To decide whether they are in bijection, match their elements with a rule and check that every element on either side is matched exactly once.

Write the sets by their indices

Every positive multiple of 17 has a unique representation $17k$, where $k$ is a positive integer. Likewise, every positive multiple of 11 has a unique representation $11k$. Thus

$$A=\{17,34,51,68,\ldots\}=\{17k:k\in\mathbb{Z}_{>0}\}$$

and

$$B=\{11,22,33,44,\ldots\}=\{11k:k\in\mathbb{Z}_{>0}\}.$$

The index $k$ identifies the position of an element in its list: $17k$ is the $k$th element of $A$, and $11k$ is the $k$th element of $B$. Pair elements that have the same index.

Define the bijection

Define $f:A\to B$ by

$$f(17k)=11k\qquad\text{for every }k\in\mathbb{Z}_{>0}.$$

For example, this pairs $17$ with $11$, $34$ with $22$, and $51$ with $33$. Equivalently, for $n\in A$, the rule is $f(n)=\frac{11}{17}n$. This formula gives an integer in $B$ because every $n\in A$ is $17k$ for some positive integer $k$.

To prove that $f$ is a bijection, verify that it is both injective and surjective.

Injective: Suppose $f(17k_1)=f(17k_2)$. Then

$$11k_1=11k_2,$$

so $k_1=k_2$, and therefore $17k_1=17k_2$. Different inputs cannot have the same output.

Surjective: Take any $b\in B$. By the definition of $B$, $b=11k$ for some positive integer $k$. The number $17k$ belongs to $A$, and $f(17k)=11k=b$. So every element of $B$ is an output of $f$.

Since $f$ is both injective and surjective, it is a bijection. Hence $A$ and $B$ have the same cardinality.

Why the numbers being different does not matter

A bijection is not required to preserve the numerical value of an element. It must pair elements without repetitions or omissions. In this example, the sets are infinite, and each can be listed in a sequence indexed by the positive integers. Matching the $k$th element of one list with the $k$th element of the other establishes a one-to-one correspondence.

This is a standard way to show that two countably infinite sets have equal cardinality: write each as a sequence with no repeated terms and pair entries at the same position. The fact that 11 and 17 are different primes is not needed for the argument. For any positive integers $r$ and $s$, the positive multiples of $r$ and the positive multiples of $s$ are in bijection by sending $rk$ to $sk$.

Common mistakes

• Comparing the first few elements only. Seeing that the lists begin differently does not show whether they can be paired. The proof needs a rule covering every element.
• Using the wrong domain. The formula $f(n)=\frac{11}{17}n$ is defined here only for $n\in A$. It sends those inputs to integers in $B$; it is not a function from all positive integers to $B$.
• Checking only one property. Showing that different inputs have different outputs proves injectivity, but not surjectivity. You must also show that every element of $B$ is reached.
• Confusing equal cardinality with equal sets. The elements of $A$ and $B$ are not the same. A bijection shows that they have the same size in the set-theoretic sense, not that they are equal as sets.