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.

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

share|improve this question
2  
The short answer is that there are "as many" multiples of 3 than 17. The long answer requires us to precisely define "as many" or "equally many" in the context of infinite sets, which is the idea of set cardinality. Wikipedia has a nice introduction: en.wikipedia.org/wiki/Countable_set –  kigen Dec 12 '12 at 6:10
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. –  André Nicolas Dec 12 '12 at 6:13
add comment

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
add comment

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
share|improve this answer
    
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$. –  Mario Carneiro Dec 14 '12 at 6:41
add comment

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.