Infinities

mathstudent1234

New member
Hi all, I'm a math student and I'm getting used to abstract concepts and contra intuitive things but there's one thing I still really struggle with. A set is called countable infinite if there exists a bijection from the set of the natural numbers to that set. It has been shown that the set of rational numbers is countable infinite. I know the proof, I understand it and I would never doubt that it is true. But whenever you ask someone why the set of real numbers is uncountable infinite they'll answer that you can't count them, I mean, where would you start? But you can't really count the rational numbers either? Where do you start? At 0.01? at 0.00000000001? This just messes with my head. I thought maybe there could exist a bijection from the set of natural numbers to the set of all real numbers as well we just haven't found it yet. Or is there a proof that such a bijection can't exist? I believe it's not too hard (tell me when I'm wrong) to construct a bijection from the natural numbers to all real numbers that are not transcendent... I just don't know what to do with those. I always thought we should maybe define the different infinities differently to what we've defined them because I think it is intuitively 'wrong' that there are as many rational numbers as natural ones but less than real ones. I mean you can approximate every real number by a rational one as accurate as you want. Has someone thought about this too and wouldn't mind to share their thoughts? Or does someone actually know an answer? Thanks so much! Excuse my English btw.

Romsek

Full Member
Re the rationals you start at 0 and run through the positive rationals in the diagonal fashion you say you are familiar with and understand.
This maps the non-negative rationals onto the non-negative integers.
Having done that the negative rationals are just mapped onto the negative integers using the obvious relation.

A quick wiki reveals no lack of proofs that the reals are uncountable. Have you tried reading any of them?

mathstudent1234

New member
I have now thanks. Yes it's clear. I just don't like the fact that it is true but that doesnt matter Thank you!

pka

Elite Member
I have now thanks. Yes it's clear. I just don't like the fact that it is true but that doesnt matter.
Here is one that is unbelievable.
A bit string is a sequence the entries of which are all either a zero or a one.
The collection of all bit strings is uncountable.

mathstudent1234

New member
Here is one that is unbelievable.
A bit string is a sequence the entries of which are all either a zero or a one.
The collection of all bit strings is uncountable.
Alright I've done research I get it still unbelievable.

HallsofIvy

Elite Member
Hi all, I'm a math student and I'm getting used to abstract concepts and contra intuitive things but there's one thing I still really struggle with. A set is called countable infinite if there exists a bijection from the set of the natural numbers to that set. It has been shown that the set of rational numbers is countable infinite. I know the proof, I understand it and I would never doubt that it is true. But whenever you ask someone why the set of real numbers is uncountable infinite they'll answer that you can't count them, I mean, where would you start? But you can't really count the rational numbers either? Where do you start? At 0.01? at 0.00000000001? This just messes with my head. I thought maybe there could exist a bijection from the set of natural numbers to the set of all real numbers as well we just haven't found it yet. Or is there a proof that such a bijection can't exist? I believe it's not too hard (tell me when I'm wrong) to construct a bijection from the natural numbers to all real numbers that are not transcendent... I just don't know what to do with those. I always thought we should maybe define the different infinities differently to what we've defined them because I think it is intuitively 'wrong' that there are as many rational numbers as natural ones but less than real ones. I mean you can approximate every real number by a rational one as accurate as you want. Has someone thought about this too and wouldn't mind to share their thoughts? Or does someone actually know an answer? Thanks so much! Excuse my English btw.
Yes, the set of all algebraic numbers is countable. Yes, there is a proof that "such a bijection" (from the natural numbers to all real numbers) can't exist. Here it is:

We prove that there exist no bijection from the set of all natural numbers to the set of all real numbers between 0 and 1. If that is true then there certainly cannot be a bijection to the set of all real numbers using proof by contradiction.

Suppose such a bijection exists. That is, suppose that we can assign one real; number to 1, another to 2, etc such that every natural number is assigned a unique real number and every real number, between 0 and 1, is assigned to a unique natural number, so we have a list of real numbers, between 0 and 1, r1, r2, r3, … that contains all such real numbers.

Construct a real number, x, thusly: The first digit of x is anything other than the first digit of r1, the second digit is anything other than the second digit of r2, etc. x is a real number between 0 and 1 and is not on that list since it differs from each number on the list at at least one decimal place. That contradicts the assumption that every real number is on the list.

(There are some technical points such as the fact that 0.4999... with the "9" infinitely repeating is the same as 0.5 but that is easily fixed by requiring that the choice of new digit is not always the same.)

JeffM

Elite Member
It seems to me that much of the resistance to Cantor's diagonal proof stems from a misunderstanding of the real numbers, which have a doubly unfortunate name. The name linguistically opposes real and imaginary numbers and so seems to imply that complex numbers are somehow less valid than real numbers. Moreover, the name also seems to imply that real numbers exist as physical facts. All types of number are mental concepts rather than physical objects, and, with respect to irrational numbers, no physical count or measurement can produce a single one. Real numbers are a convenience rather than a necessity for all applications of mathematics, albeit a huge convenience.

Once we accept that the real numbers are a purely mental construction (as of course are the transfinite numbers), we no longer get confused about what seems to be physically impossible. The diagonal proof is a proof by contradiction involving an infinite list of items each of which is itself an infinite list. The human imagination cannot truly visualize such a thing, but human reason can think about it without visualization.

Romsek

Full Member
The human imagination cannot truly visualize such a thing
Oh I don't know. Imagine the plane covered in tiles. Each row is an infinite list, and there are infinite rows.
Nevertheless I can pick a tile and proceed in a one tile per step spiral path that will, taken in the limit, include every tile.

That's pretty easy to visualize.

lev888

Full Member
Oh I don't know. Imagine the plane covered in tiles. Each row is an infinite list, and there are infinite rows.
Nevertheless I can pick a tile and proceed in a one tile per step spiral path that will, taken in the limit, include every tile.

That's pretty easy to visualize.
Except after you counted a tile it splits into a bunch of smaller tiles. You go back, count them and continue along your spiral. But the smaller tiles split yet again. Good luck.

JeffM

Elite Member
Except after you counted a tile it splits into a bunch of smaller tiles. You go back, count them and continue along your spiral. But the smaller tiles split yet again. Good luck.
My point exactly. You cannot stretch any physical analogy about the real numbers very far, particularly not with the infinite, because no one has any tangible experience with an infinite physical object. It is better to follow the logic without attempting a bijection onto a physical object.

Romsek

Full Member
Except after you counted a tile it splits into a bunch of smaller tiles. You go back, count them and continue along your spiral. But the smaller tiles split yet again. Good luck.
Well that's not what JeffM stated. He stated an infinite list of lists.

Of course the analogy breaks down for the reals otherwise they'd be countable... which they aren't.

lookagain

Senior Member
Here is one that is unbelievable.
A bit string is a sequence the entries of which are all either a zero or a one.
The collection of all bit strings is uncountable.
I don't find that unbelievable, because that includes all infinite length bit strings.

However, the collection of all and only finite length bit strings is countable.

pka

Elite Member
I don't find that unbelievable, because that includes all infinite length bit strings.
However, the collection of all and only finite length bit strings is countable.
To: lookagain, thank you for your comments. However, you failed to note that I defined a bit string as a sequence and because a sequence is a function from a countablely infinite set then there are infinitely long.
But you are quite correct the collection of bit strings of finite length is a countable collection.
Please post your proof of that fact, love to see it.

lookagain

Senior Member

Please post your proof of that fact, love to see it.

There are $$\displaystyle \ 2^1 \ \ 1-bit \ strings, \ \ 2^2 \ \ 2-bit \ \ strings, \ \ and \ \ in \ \ general, \ \ 2^n \ \ n-bit \ \ \ \ \ \ \ \ \ \ strings. \ \$$ Correspond the first two bit strings
with 1 and 2 in a count. Correspond the next four bit strings with 3 through 6.
Correspond the next eight bit strings after those with 7 through 14. And so on.

Last edited:

pka

Elite Member
There are $$\displaystyle / 2^1 / 1-bit / / strings, / / 2^2 / 2-bit / / strings, / / and / / in / / general, / / 2^n / / n-bit / / strings. / /$$ Correspond the first two bit strings
with 1 and 2 in a count. Correspond the next four bit strings with 3 through 6.
Correspond the next eight bit strings after those with 7 through 14. And so on.
I don't see how that works. It may, but I don't see it.
Please help me. To what does the string $$\displaystyle 00010111001100001111111001010111111$$ correspond?

lookagain

Senior Member
I don't see how that works. It may, but I don't see it.
Please help me. To what does the string $$\displaystyle 00010111001100001111111001010111111$$ correspond?
It's one of the 35-bit length sequences. It will correspond to somewhere
between location number $$\displaystyle \ 2^{35} - 1 \ \ and \ \ 2^{36} - 2, \ \ inclusive.$$

It's not required to be able to state what it corresponds to exactly.

Locations 1 --> 2, 3 --> 6, 7 --> 14, . . . , (2^n -- 1) --> [2^(n+1) - 2], . . .

Last edited:

JeffM

Elite Member
I don't see how that works. It may, but I don't see it.
Please help me. To what does the string $$\displaystyle 00010111001100001111111001010111111$$ correspond?
We start with a list that can be put into 1-1 correspondance with the natural numbers. Each element of the list consists of an infinite string of two symbols, say plus and minus, but there is no infinite repetition of either symbol.

We now assume that the list exhausts the possible configuration of such strings. But Cantor's diagonal argument shows that we can construct an infinite string that meets the criteria and is not in the list. Therefore there is no such list, and there are transfinite numbers greater than $$\displaystyle \aleph_0.$$

Moreover, we can put the binary representations of every irrational number > 0 and < 1 into 1-1 correspondence with the set of infinite strings of plus or minus with no infinite repetitions. This proves that the number of irrationals exceeds the number of positive integers. Therefore the number of reals exceeds the number of positive integers, and the number of irrational numbers exceeds the number of rational numbers.

pka

Elite Member
It's not required to be able to state what it corresponds to exactly.[/tex]
Oh my friend yes indeed that is exactly what is required. To show that a set is countable one must show that there is injection from the collect( the set) into a countable set.
Lookagain, I have long objected to your correcting posts on minor point about which I suspected you know nothing. Now I admit that when you replied to this thread the way you did, I knew that I had you. With this postings you have shown that you do not even have the level of mathematics that I expect of a third year mathematics major. In other words, you my friend are an amateur at mathematics. I happen to know that others here think that too. Your snide corrections are not well received.

Last edited:
• JeffM