Question: Infinity A bigger than Infinity B ?

[D H]

You compare two infinite sets by trying to put them into a one-to-one correspondence with one another. The sets have the same cardinality if this one-to-one correspondence can be constructed. If all members of one set can be mapped to members of the other set, and that other set has members that have not yet been mapped, the first set has a lesser cardinality than does the other.

Alternatively, given two sets one can assume that the two sets do have the same cardinality, that is, assume a one-to-one correspondence exists between the two sets. Now suppose you can construct a member of the second set that is not in that one-to-one correspondence. You've just arrived at a contradiction. This means the initial assumption that the two sets have the same cardinality is false.

This is exactly how Cantor showed that the reals have a greater cardinality than do the integers. Here's how he did it.

Assume the reals between 0 and 1, exclusive, can be put into a one-to-one correspondence with the integers. That means there's some real number in (0,1) that we designate as real #1, another that we designate as real #2, and so on. Now I'll construct a real number between 0 and 1 that isn't in this list. I'll start with the tenths digit of real #1 and pick some other digit that's different from that. This is the tenths digit of my constructed number. I'll do the same with the hundredths digit of real #2, the thousandths digit of real #3, and so on. My constructed number is different from real #1 by construction, different from real #2, different from real #3, and so on. It is not in my list, and yet by construction it is a real number in (0,1). Contradiction! The reals between 0 and 1 cannot be put into a one-to-one correspondence with the integers. (On the other hand, it's easy to make a one-to-one correspondence between (0,1) and ℝ.) The reals between 0 and 1 form an uncountable set, and thus so do the reals.

 

[YYaaSSeeRR]

I think there is only one infinity :) when we are talking about NUMBERS.

@EVO:
do you always review people post-history?? if yes ,why??

 

[D H]

I think there is only one infinity :) when we are talking about NUMBERS.

Three questions:
Have you read any of the posts in this thread? That you said this suggests you did not.
Have you performed the internet searches suggested in those posts?
What do you think a NUMBER is?

 

[lendav_rott]

infinity by definition is not a scalar, therefore you can't compare "different" infinities. It's just something we use when our brain goes "does not compute".

 

[D H]

infinity by definition is not a scalar, therefore you can't compare "different" infinities.

Once again, have you read any of the posts in this thread? Have you googled the search terms?

It's just something we use when our brain goes "does not compute".

Since there are examples about that show the concept does make sense, this is just wrong.


However, countability and "does not compute" bump heads in a number of ways. Here's one: The set of all functions, as shown above is an uncountable. On the other hand, the number of computer programs is a countable set. There are functions that cannot be computed. In fact, almost all mathematical functions cannot be computed.

Another one is whether it's possible to write a computer program that tests whether any given computer program will run to completion in a finite amount of time. This is the "halting problem." One way to show that this program cannot be written is to use a diagonalization argument, the same kind of argument that was used to show that the reals are not countable.

Another way to show that this program cannot be written is to assume that it can be done. Next we'll write a little python module that calls this program so we can test whether other python functions run to completion. What does this python script print?

import halting_problem
# halting_problem.halts (func) returns True if func returns in a finite amount of time,
#                                      False otherwise.

def ask_a_cretan () :
    all_cretans_are_liars = False
    if halting_problem.halts (ask_a_cretan) :
        while True :
            all_cretans_are_liars = True
    return all_cretans_are_liars


print "Are all Cretans liars? Let me ask a Cretan.\n"
print ask_a_cretan() ? "Yes\n" : "No\n"