3
$\begingroup$

A question my wife and I were chatting about last night.

Are there more multiples of 3 than there are of 17, if we count from 0 to infinity One point of view was since there are infinite multiples of 3 and infinite multiples of 17, the number of multiples are equal.

Another point of view was in a reasonable range of numbers, there are more multiples of 3 than 17

So are either of us right? Or are we both wrong

  • 2
    It depends how you define "as many." In the sense of cardinality, there are just as many. In the sense of density, the multiples of $3$ are substantially more frequent.2012-12-12

2 Answers 2

9

It really depends on what you mean by "there are more". If I can line up one element of the first set with an element of the second set, then we call those sets "equinumerous" or "of the same cardinality". In this sense, the sets $3\mathbb Z$ and $17\mathbb Z$ are in fact the same size, the cardinality $\aleph_0$ (read aleph-null), because the function $f(x)=(17/3)x$ maps numbers in one set to the other without missing any and without putting two numbers on top of each other.

In another sense, the set $17\mathbb Z$ has fewer elements because in a given interval of integers, there are more of $3\mathbb Z$ in the set than $17\mathbb Z$. This is the idea of the "density" of a set, defined as

$d(A)=\lim_{n\to\infty}\frac{|A\cap\{1,2,\dots,n\}|}{|\{1,2,\dots,n\}|},$

where $|A|$ means the number of elements in $A$, and $\cap$ is set intersection (elements present in both sets). In this sense, $d(3\mathbb Z)=\frac13$ and $d(17\mathbb Z)=\frac1{17}$, so that there are "less numbers" in $17\mathbb Z$ than $3\mathbb Z$. But it's all a matter of definition.

1

Don't have enough reputations to comment yet, so adding this as an answer.

Just to add to Mario Carneiro's answer, what he means by "I can line up one element of the first set with an element of the second set" is not the same as saying "since there are infinite multiples of 3 and infinite multiples of 17, the number of multiples are equal".

For example the cardinality of real numbers is not the same as that of naturals though they're both infinite. If you're interested check out:

  1. http://en.wikipedia.org/wiki/Aleph_number
  2. http://en.wikipedia.org/wiki/Cardinal_number
  • 0
    Indeed, one of Cantor's greatest discoveries is that there are certain senses in which a set is "the same size" as proper subsets of itself, but *not all infinite sets are equal* in this sense, i.e. |\mathscr P(A)|>|A| for all sets $A$, so $|\mathscr P(\mathbb N)|\cong|\mathbb R|=2^{\aleph_0}>|\mathbb N|=\aleph_0$.2012-12-14