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}.
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.
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.
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.
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.
Posts: 364
Joined: Tue Sep 26, 2006 12:44 am
Location: Pittsburgh, PA

Re: The reals are uncountable

Postby tvelection » Sun Sep 03, 2017 11:09 pm

A quick post that concerns an issue that arises in math threads sometimes:

This is how I understand the difference between an algorithm and a function

An algorithm is a set of instructions. A garbage truck must find the most efficient path through city streets, or a hospital the most efficient way to fill beds and move patients around. Yet an algorithm is not so broad that by instructions it means things like cooking recipes. Algorithms are also involved in number language, that is, the algorithm for Base systems (such as decimals) that tells the user how to increase place value to the left and to put a place holder zero in the former position after "9" is an algorithm . . . or another algorithm is "the order of operations."

A function involves a purely mathematical expression with an operator/symbol that can predict the nth element if it results in a series. Otherwise it is an algebraic expression that has an unique input and output.

I suppose if it were generalized one could say all functions are algorithms but not all algorithms are functions, but I don't like that and would wholly separate them and say that no algorithm is a function and no function is an algorithm. Depends on how broadly "algorithm" is defined

Sure I could simply look up the definitions but I'd rather think it through. Are these distinctions/definitions between function and algorithm technically correct? Can any of the mathematicians critique the above for precision? Or tell me, what is the difference between the two according to your greater knowledge of the subject. I think I have it right on this but would like other's knowledge or opinions.

I wanted to make this clear because I used the terms with regard to Cantor that way ---to mean that his diagonal flip is an algorithm (instruction without an operator) and of course that is being performed on number set functions like (n+1). His algorithm cannot tell us the next element until the functions have revealed on the next one to flip. So my point was that he was manipulating predictable-to-nth-functions with an algorithm that has nothing to do with the order or predictability of the all functions themselves. He's creating another "infinite" set of flipped functions not demonstrating that some series are missing. So now we have infinite functions, infinite elements and an infinitely applied algorithm. Or ---he is trying to capture an unseen series based on two infinities, functions (down) and elements (across), with one algorithm and there will always be some missing because that cannot be done when you purposely alter the functions with a false outcome (with regard to the function whose nth element in the diagonal, when flipped, is no longer correct with regard to the function. Or maybe it could. Yet why would we expect a functions list to contain algorithm results (or in that specific location of functions when we have blatantly altered them all.) This causes me to conclude that the product of an algorithm is in commensurable with the product (series) of a operational function. Can Cantor produce a functional series that is missing from all functional series? No. We can come up with a missing element with any incomplete infinity and smaller ones by mere inspection --there I'd be accused of using a finite part, so I just do like him (we can't write out the infinity(?) {and yes, infinity is not a number) and after my four by four grid I'll just draw same dots downward and outward (ellipses) and say, "See? these "mean" infinite." I do now understand JeffJo's point that nothing is "missing" from T itself but how do we prove that S is missing anything unless we have all of T (all sets)?
Posts: 364
Joined: Tue Sep 26, 2006 12:44 am
Location: Pittsburgh, PA

Re: The reals are uncountable

Postby JeffJo » Fri Sep 08, 2017 10:43 am

tvelection wrote:This is how I understand the difference between an algorithm and a function

An algorithm is a set of instructions. ...

A function involves a purely mathematical expression with an operator/symbol that can predict the nth element if it results in a series. Otherwise it is an algebraic expression that has an unique input and output.

I suppose if it were generalized one could say all functions are algorithms but not all algorithms are functions, ...
No. In fact, that last bit is pretty much backwards.

An algorithm is a set of instructions that takes a set of inputs and tries to reach an end state that represents a set of outputs. You can quibble about how "It is shown that it will never reach a satisfactory end state" and "we give up because it seems it will never reach a satisfactory end state" might be handled, but how isn't really important, at this point, to what you are saying.

A function is defined by three things:
  1. A set, A, called the domain.
  2. A set, B, called the co-domain.
  3. A relationship that associates (or "maps") every element of A with an element of B.
#3 can be accomplished with an algorithm; in fact, it usually is. A "purely mathematical expression with an operator/symbol" is just notation that describes an algorithm, not the function. For that, you need to define the set of all possible inputs A, and the set that includes, possibly with other members, all possible outputs. The algorithm can also describe how to get to "the nth element [of] a series," but then you might need those two extra conditions, about end states, in your co-domain set.

Did you notice something tricky there? I just put two objects that are not numbers into the co-domain. There is nothing in the definition of function that requires it to operate on, or produce, numbers.
    When you look at a menu in a restaurant, the list of entrées can be called set A. Your mind associates some preference value with each entrée in the list, and the set of all possible preference values – whether or not there is an entrée with that value – can be set B. Even if that value is something like “ugh, it says ‘squid’ in the name so I’m not going to read any further.” The “function” is not how you arrive at these preferences - that could be an algorithm, or something more subjective. The function is the set of links produced by that algorithm (or whatever), that map elements in a defined set A with elements in a defined set B.
In fact, if you look up the definition of a function on in Wikipedia, many of the examples are Venn diagrams with lines and arrows demonstrating these links; not an algorithm in sight.

Sets can include anything you want, even other sets. Cantor's proof is about set theory, not any form of number theory. And despite how it gets taught, it was designed SPECIFICALLY to NOT be about numbers.

In set theory, the Axiom of Infinity says we assume that there exists a set I that includes the empty set {} and, for any set X in I, it also includes {{X},{}}. Note that this additional set has two elements, one that is the null set {} and one that is the set that contains only X. This can get very confusing very fast, so a theory of numbers can use a different version based on counting the number of elements recognized: There exists a set N that contains the natural number 1 and, if it contains the natural number n, it also contains the natural number n+1.

This set can be demonstrated with an algorithm suggested by the definition:
  1. N includes 1.
  2. Since N includes 1, it also includes 2.
  3. Since N includes 2, it also includes 3.
  4. ...
Just be careful not to confuse such a demonstration with the definition. The definition does not tell you to start with any number, or to produce a sequence. My point is that the definition of N is neither an algorithm nor a function. You don't need to complete this demonstration to show what it is, or that it exists (since it is assumed to exist as a postulate of our mathematics).

Cantor[1] didn't use real numbers, he used what I call Cantor Strings: infinite-length strings combining the two characters '0' and '1'. "Infinite length string" means that a Cantor String can be defined as a function whose domain is the set N. "Combining the two characters '0' and '1'" means the co-domain is the set {'0','1'}. And while you can interpret such a string as the binary representation of a real number between 0 and 1, there are reasons why that makes the proof more difficult. So I like to stick to strings.

Cantor's set T is the set of all such strings. This set can be defined in a similar way to N (if it contains a string with '0' in any position m, it also contains the string with that '0' replaced with a '1'), which is assumed to be an acceptable way to define "exists."

What Cantor assumes, is that you can create a function s(n) that maps N into **A** set of Cantor Strings, not all of them. This set is called S. Again, you don't have to complete the demonstration of the function in order for it to exist. I can define a trivial one - s(n) is a Cantor String that has a '0' in every position except position n, which is a '1'. Note that the members of the co-domain S are themselves functions, the ones that I call Cantor Strings, whose domain is N and co-domain is {'0','1'}.

Now note that a function s(n) whose domain consists of functions f(m) can be considered to be the two-dimensional function s(n,m). By using the same index for both functions, we can now define yet another function d(n) = ~s(n,n).

This new function satisfies the requirements to be a Cantor String, that the domain is N and the co-domain is {'0','1'}. So it is in T. This new Cantor String can't be in S because, for any n, the function s(n) is not the same function as d(n).



[1] I'm using the names and characters from the Wikipedia article, not Cantor's.
Posts: 2609
Joined: Tue Mar 10, 2009 11:01 am

Re: The reals are uncountable

Postby tvelection » Tue Sep 12, 2017 8:13 am

JeffJo, Thanks, that post was exactly what I was looking for (needed) ---and not for me to try to argue someone who knows the subject and its prerequisite knowledge to a much higher degree than my amateur level. And without being too self-deprecating let me say that I’m humbled both by your knowledge of the subject in your response and the ignorance of it in my post, my lack of understanding, of what a function and algorithm are in a technical sense . . . let alone the distinction between them. The menu example was surprising (I think I see). That is simply the best brief explanation one could ask for without reviewing page after page in other threads on this topic. I certainly cannot claim you, or Cantor, are wrong anymore. I also see that it’s not necessarily about number sets but rather series, used as a mere example of number sets and counting. As a layman, uneducated in higher math, every time I read your answer slowly and carefully I can better understand it. There are just a few loose ends with regard to my original post. Philosophically, I’m still against the notion of “infinite cardinalities” and “infinite sets of all X” but a mathematician could laugh at that and say, “That is none of our concern” (or as JeffJo has said, “it’s simply axiomatic”) there is no empirical/logical (synthetic) foundation.

Please address these however you like, all, in part, with explanation, or just yes or no if you think that will suffice. If you could help me with these issues JeffJo, I won’t belabor the issue with further responses. I’ll leave you with the last word.

(1) Then I assume I was wrong about the order-of-operation instruction and placement value instructions because there is not set B “mapping” in that regard and therefore they are not algorithms.

(2) Isn’t the garbage truck route (efficiency) an algorithm? I could swear I remember that used an example at some point in my education. Yet there would be no “B” set either and what would be the mapping relation?

(3) Is a logical proposition an algorithm since it maps to truth value (true or false as the “b” set)? If so what would be considered the relation mechanism in that case? Fortunately, I have some limited experience with Venn diagrams but only for logical/categorical statements. It almost seems as if we label something true or false ultimately without basis in a purely analytic sense, just formal validity in an Aristotelian sense.

(4) As to my categorical comparison between the two can you give me (A) statement of relation such as All Algorithms or All functions or Some X are Y and Some X are not Y with specificity. You said it was more just the opposite, so is it that: All algorithms are functions but not all functions are algorithms? Or would you say that such categorical logic distinctions cannot be made between the two because (to use a cliché) they are apples and oranges.

I actually wanted to do this post and delete it so I could leave your post as the last and most definitive statement but since I’ve mentioned further issues it would be seem odd to expect you to quote me from a deleted post. Also I felt that leaving your post without a response would either seem unresponsive or at worst cowardly.

I’m out of the Cantor arguments, I see that I lack the necessary knowledge to judge on this. Although I think in other posts I made some good observations about the nature of number sets with regard to infinite division and irregular intervals v. regular ones contained in Real numbers. Aside from Cantor I agree that the Real Numbers are not countable with a one function set (counting numbers) because it is simply illogical to count divisions and irrational numbers.

Finally JeffJo, and you need not respond to this paragraph, I have been here for years reading posts and have been impressed by your knowledge, logical thinking, and linguistic precision. I don’t want to throw the words “math genius” around because as a layman I’m not qualified to make that judgment. Yet I suspect it to be so. The point is: I hope you use such exacting intelligence and ability to make a contribution, to make the world a "better" (admittedly a subjective and ambiguous word, but you know what I mean in general ---for instance, reduce hardship, disease, or suffering) . . . a "better" place in some way, although you are under no imperative or obligation to do so.
P.S. I recommend anyone reading this who wants an explanation of differences between "algorithms" and "functions" read JeffJo’s definitive post previous to this one. And if any other mathematician can find a flaw in his explanation go for it. I can’t. But rather than be argumentative maybe other mathematicians can add anything they think was left out or anything imprecise instead. I’ll take the previous post as an education on the matter, read any response given, and leave it at that for now.
One correction I wanted to make in my original post (and I try not to edit after a response except for spelling or grammar). I used the term “mathematical expression” where I meant “algebraic,” that is, with variables not a number/constant expression like (2+3). But I think that mistake was seen, understood, and not an issue in the larger sense.
Posts: 364
Joined: Tue Sep 26, 2006 12:44 am
Location: Pittsburgh, PA

Re: The reals are uncountable

Postby JeffJo » Tue Sep 12, 2017 3:44 pm

tvelection wrote:Philosophically, I’m still against the notion of “infinite cardinalities” ...
This is usually the complaint people have, when they think "all" must mean "found the end;" or that "cardinality" is synonymous with "natural number."

Consider the subtle differences in meaning between these statements:
  1. The set N contains all natural numbers.
  2. The set N contains every natural number.
  3. The set N contains any object that is a natural number.

Statement C is clearly true; anything that can be called a natural number can be found by starting with 1, and adding 1 until you reach it. And that's the definition of N.

To prove statement A, however, it seems that you would have to examine every possible thing that could be called a number and decide whether or not it belongs in N. This is clearly impossible, simply because we already have admitted that the set has no end.

You can quibble over exact meanings, but to me statement B is somewhere in between the two. That's the only reason why I include it.

The point of the Axiom of Infinity is not how it defines the natural numbers, but how a definition that satisfies statement C is sufficient to call something a set. It doesn't say that we have calculated all natural numbers, or every natural number. Just that we know we that, given enough time, could calculate any natural number.

"Cardinality" is just a concept that can always put sets into an order |A|<=|B|<=|C|... based on how their members can be associated with members of other sets. If a function from A to B (remember, every member of A is mapped to exactly one member of B) has an inverse function that maps every member of B back to the member of A that is mapped to it, it called a bijective function.
  • If a bijective function exists between A and B, then we say that they have the same cardinality. That is, |A|=|B|.
  • If no such bijective function exists, but there is one between A and a strict subset of B, then we say that A has a lesser cardinality; |A|<|B|.
Note that the expression |X| is meant to be a function. Its domain is the set of all sets, and its co-domain is - well, we haven't defined what a cardinality is, just a property that it has. I could call the cardinalities of {1}, {1,2}, {1,2,3}, and {1,2,3,4} to be "George," "Ringo," "Paul," and "John" respectively, as long as I also define "George"<"Ringo"<"Paul"<"John" with no values in between. But I might get arguments about their relative values. :).

One very useful example of equal cardinality, is if one of the sets is a set of consecutive natural numbers starting with 1. Then the number of elements in either set is the last natural number in that set. And we get the very convenient property that these numbers can be used as cardinalities that always satisfy the two parts of my definition, with none of the arguments I mentioned.

The point is that, while natural numbers can be USED as cardinality values, cardinality is not DEFINED to be the natural numbers. It is defined by the existence of a bijective function. And this distinction is important with infinite sets. An infinite set can have a bijective function with a strict subset of itself: e=2n is a bijective function between the natural numbers N and the even natural numbers E. That's why the second part of my cardinality definition had to state that no such bijective function exists.

Again, for a finite set of consecutive natural numbers N(m) (that is, 1 thru m), we can treat the number m as the cardinality. And you can easily see that there is no bijective function between N(m) and N, but there is with a subset (N(m) itself). So my definition of cardinality says that |N(m)|<|N|. This proves that the concept I defined as cardinality can't always be treated as a natural number. So we call it Aleph 0, and have shown that it has the property that it is "greater than" any natural number, whatever it is that this means when you compare something that isn't a natural number to something that is.

In all of your questions, I think you are placing too much emphasis on what is, or is not, an algorithm. It isn't a term that needs to be used in this discussion, and it gets in the way. It is just one of many possible ways to define the mapping.
Posts: 2609
Joined: Tue Mar 10, 2009 11:01 am

Return to Great Ideas

Who is online

Users browsing this forum: No registered users and 3 guests