Intuitive way to explain |Q| = aleph zero?

  • Thread starter EnumaElish
  • Start date

EnumaElish

Science Advisor
Homework Helper
2,273
123
What is an intuitive, calculus-grade way to explain that rationals have the same cardinality as N? (Same question for perfect squares.)
 

LeonhardEuler

Gold Member
858
1
I'm not trying to be difficult, but aren't the standard proofs pretty inuitive? Especially for the perfect squares. To every element of the set of perfect squares you can correspond exactly on element of the set of naturals: its square root. The same goes for the other way around. So you have a one to one correspondance between the squares and naturals, so they have the same cardinality. The proof is nearly identical for the rationals, except that the bijection is somewhat more complicated
 
13
0
Look at http://home.att.net/~numericana/answer/sets.htm [Broken] in the section called "The countability of rational numbers".
 
Last edited by a moderator:

cristo

Staff Emeritus
Science Advisor
8,045
72
Heres a pictorial way to show it for the rationals. Start with the positive rationals and start listing them like so
1/1 1/2 1/3 1/4 1/5......
2/1 2/2 2/3 2/4 2/5 .......
3/1 3/2 3/3 3/4 3/5 ....

Now, to count, follow this sequence: 1/2, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3,.... (I hope you can see what I'm doing). Now, it should be clear that this list is countable. Now, insert the negative rationals just before their positive counterparts, i.e. -1/1, 1/1, -1/2,..., and just put zero at the top left. Now, using the same arguement, the full set of Q is countable.

I'm not sure whether this was something like what you were after, but it seems quite intuitive!
 

matt grime

Science Advisor
Homework Helper
9,392
3
Ah, diagonal method - possibly because a proof that Q is countable is called diagonal, and that R isn't yet has the same adjective, people have wrong impressions.


One way is a standard method using prime decomposition.

Send a/b to 2^a*3^b (for a and b >0) or 2^a*3^b*5 for negative rationals. This is a bijection from Q onto a subset of N. This proof shows that any finite product of countable sets is countable, and shows an important difference between union and product (in the categorical sense, perhaps).
 

EnumaElish

Science Advisor
Homework Helper
2,273
123
I thought both the "perfect squares" and the "rationals" demonstration can use the cross-tabulation square where row and column headings are the natural numbers. For the perfect squares, each cell holds the product "row # * column #"; all perfect squares are on the diagonal, which you can count linearly.

For the rationals, each cell is row #/column # (or the inverse), but I wasn't sure how to count them. Now I know. Thanks.
 

Want to reply to this thread?

"Intuitive way to explain |Q| = aleph zero?" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top