The reals are uncountable

Got a great idea? Tell the world about it here.

Moderators: mvs_staff, forum_admin, Marilyn

The reals are uncountable

Postby mathsman1963 » Sat Sep 12, 2015 9:44 am

People forget ( such is the fame of the diagonal argument) that Cantor produced another uncountability argument a few years prior. This is probably the nicest version of it:

Suppose that there is a sequence {rn} which exhausts the real numbers. Then we can choose a closed interval [a1,b1] which avoids r1. Next, choose a sub-interval [a2,b2]⊂[a1,b1] which avoids r2. Continue in like manner to obtain a decreasing sequence of intervals {[an,bn]} such that for all n, [an,bn] avoids rn.
Now, the an form an increasing sequence, bn a decreasing sequence, and for all n we have an≤bn. It follows that supan≤infbn and in particular, there exists a point x∈[supan,infbn]. Then for all n we have x≠rn, since x∈[an,bn] and we said that [an,bn] avoids rn. But this contradicts the exhaustive nature of {rn}.
mathsman1963
Thinker
 
Posts: 19
Joined: Thu Sep 12, 2013 5:06 am

Re: The reals are uncountable

Postby davar55 » Mon Sep 14, 2015 10:19 am

mathsman1963 wrote:People forget ( such is the fame of the diagonal argument) that Cantor produced another uncountability argument a few years prior. This is probably the nicest version of it:

Suppose that there is a sequence {rn} which exhausts the real numbers. Then we can choose a closed interval [a1,b1] which avoids r1. Next, choose a sub-interval [a2,b2]⊂[a1,b1] which avoids r2. Continue in like manner to obtain a decreasing sequence of intervals {[an,bn]} such that for all n, [an,bn] avoids rn.
Now, the an form an increasing sequence, bn a decreasing sequence, and for all n we have an≤bn. It follows that supan≤infbn and in particular, there exists a point x∈[supan,infbn]. Then for all n we have x≠rn, since x∈[an,bn] and we said that [an,bn] avoids rn. But this contradicts the exhaustive nature of {rn}.

Looks right to me. The assumption that is disproven is that the reals can be listed in a sequence
(not necessarily in order of size or value, which is of course impossible since between any two
reals are an infinite number of more reals), which is the same as saying they can't be put into
a one-to-one correspondence with the counting numbers.
The next mathematical leap is to say there is a cardinality associated with the integers, which is
shared by the rational fractions, but which is not shared by the reals and which must therefore
be greater for the reals. It can then be shown that the cardinality of the imaginaries (the
product of reals times i ) is the same as that of the reals, and with a little effort so is the cardinality of the complex numbers a+bi for a and b real.
Hence the alephs.
The next issue is, is that all? Is there an even greater cardinality? It takes more math, and it's
only important in math, but therefore in anything supported by higher math. Where the issue
becomes relevant outside of pure math I leave alone.
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Re: The reals are uncountable

Postby davar55 » Sat Nov 14, 2015 12:28 am

This proves that there are at least two different levels of infinity.
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Re: The reals are uncountable

Postby davar55 » Fri May 13, 2016 9:07 pm

The infinite cardinality of the integers is called Aleph-null or A0.

The infinite cardinality of the reals is called Aleph-one or C (for Continuum).

The infinite cardinality of the functions from R to R is called Aleph-two or F (for Functions).

Cantor proves that the first two are not equal, that A0 < C.

We must also show C < F.
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Re: The reals are uncountable

Postby tvelection » Sun Apr 23, 2017 11:51 am

I'm posting in here so as not to interfere with Robert46, Gofer, and JeffJo's discussion in the Cantor/Disproof thread. But I agree with Mathsman's conclusion of this thread's title but still not Cantor's way. The Counting Numbers cannot count the Real numbers, if that is Cantor’s conclusion then I agree that far but it says nothing relative about "infinite sets" (or better said "infinitely applied functions").

There are differences between counting and mapping isn’t there? One who uses mapping might reasonably assume that all counting is mapping but not all mapping is counting. But I’m starting to believe that mapping is not counting at all. When we count we answer the question, “How many?” When we map we merely match like symbols and never find out how many because the process, not the quanta, is infinitely applied to compounding symbols. Counting is an iterated process (n+1) while mapping seems to be an instantaneously induced (attempted) matching of all elements where unmatched elements “fall out” (so to say). Counting has a function with an operator; mapping is a form of matching symbols between two different functional sets. This creates a tension between the words “infinite” and “all” we never have all of an “infinite function” we may have all of a finite one if we set limits to the infinite functions. An arguer will claim that it does not matter if we have "all" because mathematicians use induction from a finite limit to describe infinite unlimited “sets.” This mathematical induction connects the finite to the infinite. Such induction would simply say that what is true for “some” is true for “all” what is true for “finite” is true for “infinite.” But that is not the case. So it looks like Cantor is the one who mistakes “infinite sets” for “finite sets” by induction . . . ends up with cardinalities that are merely aspects of relative finite sets, different sizes, or simply, the set is always larger than the subset be it finite or infinite . . .

And certainly, I hope, Cantor is not just saying a set is “bigger” than any subset it contains. That is painfully obvious and already true by definition (of “set” and “subset”). I agree on uncountability of the Real Numbers by the Counting numbers for different reasons that say nothing about infinite sets. Many of us have already agreed that Infinity is not a number (so what is "it" then?) The proper view seems more that a function is infinitely applied, not that we have an “infinite set.” One cannot count the Complex Numbers (Reals + Imaginaries) with the set of Real Numbers alone either (which has nothing to do with “infinite set" sizes). The set of Real Numbers has two functions, n+1 and 1/(n+1), and the Counting Numbers just one (n+1). They are incommensurable.

Can the Real Numbers be produced with only one function?

A set with one function (Counting/Natural Numbers) cannot count a set with two functions any more than a set with two functions can count a set with three, n+1, 1/(n+1), square root of -1n+1. The Integers cannot even count the Rational Numbers because the Integers lack a richness of unique symbols to match/map anything to “½.” Which, if added would have be mapped to Integer "2" (1, 1) (2, ½) (3, 2) In this example we are just counting halves too. Since counting itself is infinitely iterated the infinity is found in the application of the function not in any set so that even by induction we never have “more” of one since we can only count one for each element produced which may produce (1000, 500) but that is a scale issue. One that can be dismissed only if the counting of intervals in the "counted" sets are also constant and regular intervals.

Does anyone disagree that the Real Numbers are produced by two functions? And the Counting numbers by one function. And that a set that does not (cannot) contain certain unique symbols cannot be mapped to another set without them? And this is uncountability, if we are mapping/pairing a mixed bag of red marbles to white marbles what do we do when we find a blue marble? It is not "more" it is indeterminate, undefined. And we are not counting we are matching like things.

So there are two approaches to mapping (one counts, one matches)
Take the Counting Numbers mapped to the Even Numbers {1 – 100} mapped to- - > {2 – 98}.

Method A “ - - - >” indicates a set mapping arrow

(4 - - - >8)
(3 - - - >6)
(2 - - - >4)
(1 - - - >2)
(Counting - - -> Even)

The above is what I meant in a post to JeffJo by "smashing them down" to count.

Method B

(4 - - - > 4)
(3 - - - > maps to no element)
(2 - - - >2)
(1 - - - > maps to no element)
(Counting - - - > Even)

----Notice in Method A the step (or interval size) does not matter as long as it they're regular
----Notice In Method A the produces unique pairings while in Method B produces pairings of like symbols only, doubles.

When we have counted a hundred even-numbers we have proven nothing about infinity even by induction as both sets are equally inexhaustible. There are as many "infinite" Counting Numbers as there are Even Numbers. There are not “more” Counting Numbers than Even Numbers in Method A neither set will be exhausted or miss anything. Both functions are infinite. While if we insist on matching only like symbols Method B produces an incommensurable mapping of uncounted unique elements/symbols that exist in one set but not the other. Method A is a kind of counting mapping while Method B is a kind of matching mapping. Neither proves anything about infinity or an infinite function unless each has the same number of functions for the set and the same number of unique symbols/expressions available. Edit: I take that last part after "and" back because we may count the base10 decimal numbers with binaries which have less symbols, in that case more compounding placement values allows the set with lesser symbols to create any amount of "unique" expressions.

So Cantor takes the Real Numbers *(which I agree cannot be counted but for a different reason)be they finite or infinite and simply says, "either way there are “more.” As if to simply say you cannot map or count a set with any subset it may contain . . . treating an infinite function that never reaches “all” like relative finite sets that have a definite number of "all" elements.

*the different reason, (besides the fact that a one-function set cannot map/count a two-function set) is that that even with the Counting Numbers vs. Rational/Irrational Numbers we have a problem of scale and regular intervals vs. irregular intervals. The Counting function is (n+1) and produces regular intervals. Yet the Rational Numbers also use the function 1/(n+1) which produces irregular intervals that travel in a negative/”subtractive” direction. There is no way we can count (or map) infinite irregular (at times indefinite) intervals with infinite regular (definite) intervals.

Infinity is not a number, as many here have already agreed, but an infinitely iterated function. All infinite functions are applied equally infinitely regardless of symbols or scales. By claiming alephs/cardinalities Cantor is treating “infinite sets” (fantasies) like finite sets, but in finite sets we have all elements and in infinite sets we may induce “infinitely” but we never really have “all.” To claim “all” infinite sequences is to subtly treat an infinite like a finite set.

Sets with implied infinite functions are so different than sets of “things” or mere gibberish symbols (which can be mapped with likes regardless of their meaninglessness or quantity). If we have a set of 35 specific coat buttons and a set of 60 specific pencils we have defined two finite sets. But Number sets involve a function to produce elements. There, of course, is a fundamental difference. Also the process of "counting numbers" (not the set of Counting Numbers) seems too self-referential like paradoxical self referencing sentences (e.g. “This statement is false” may be true or false but we do not know without content beyond self reference). Likewise, do we really “count” numbers or use numbers to count? I mean “100” means “100” it's as if we are “counting” symbols/expressions of any given set but if we count infinitely the functions are never exhausted and in that respect there is no “more” or “less,” just infinite counting. And if one were take-up this strange task of counting Real Numbers using an number subset to count its larger "more abstract" set. Where do I even began with pairing number one? {Counting Numbers - - - >Real Numbers} (1- - ->?) I can't start the Reals with 0, I'd never be able to move from there. How about 1/1000000000 . . . . ? How do I increase from infinite division. The whole exercise of counting mathematical object-sets with subsets does not make much sense. The properties are in the functions, the "Set of ( "all?" ) Reals" is just an amalgam of disparate sets and the infinite is induced function iterations, same for all. A count cannot even be started unless the scale of rational units is somehow limited.

If we take a limited sample (anti-diagonal) for induction we know already that there are more sequences missing than there are presented at any given point, that says nothing about infinity-sizes and is true of any finite diagonal area. No one is claiming "all" yet, and just like Cantor saying that the next {~d} will be missing too, whoever said it would not? His game, his rules, his pre-desired outcomes. We'd need a whole other set for these apples and oranges the set of all algorithmic sequences performed on the set of all functional sequences. One uses an iterated function and can arrive at any nth element, but ask Cantor what the next element of {~d} is and he cannot tell you until the functional sets produce a the next {d} element. But it can be argued that if we have all sequences it does not matter if they are created by algorithms or functions (when one is dependent on the other it does).

The question is then, if we have "all" elements of an "infinite" set then how can anything ever be missing? (if we have both "infinite" and "all" nothing can be missing). The algorithms will be found in the functions eventually the key, therefore must be that they come in different orders (as mentioned) that we already know some sequences (more) will be missing than present in any given diagonal range. We were counting functional sequences and are suddenly required to consider algorithms fabricated by their elements as missing, missing from what? The "infinite set of "all"??

So too we can produce/show the algorithms of {~d} miss many functions out of order (so what?) There are always more sequences of elements than elements but what if you have infinite elements? We can't count all functional sequences with the counting function. It is like an array there are infinite elements and/times infinite sets of functions (or functional number sets). So in forming a diagonal area we are "creating" those two different infinities elements and functions. So Cantor comes along and claims that this must be larger than infinity alone because there is always at least one sequence missing. No, we'd have to count elements or sets you can't count both at the same time and claim a greater infinity upon failure. Or is it that you can have "infinite" X but never "all" X? Two words like oil and water. And so you get odd statements like "The set of all infinite sequences does not contain all infinite sequences" or just treat infinite sets like finite ones and make up words like "cardinality" and "aleph" as an excuse for that.
tvelection
Intellectual
 
Posts: 340
Joined: Tue Sep 26, 2006 12:44 am
Location: Pittsburgh, PA


Return to Great Ideas

Who is online

Users browsing this forum: No registered users and 3 guests

cron