Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cantor set ℵ , inductive proofs by openly counting.

  1. Nov 8, 2013 #1
    I have been looking at the idea of 1:1 correspondence as a method of determining set size/cardinality, and have noticed that the principle allows for inductive proofs, which I think are properly constructed, that can come to conclusions which are clearly wrong under traditional set theory if used inconsistently; for integer sets are open -- (finite unbounded elements, having no supremium / therefore an open set) but not all sets are that way. Some sets CAN have supremiums.

    For, it's not clear to me that 1:1 bijection can really prove something is infinite, rather than "finite unbounded" and I'd like someone to discuss the distinction, and how his tool of 1:1 correspondence really provides a valid and consistent tool that can be used in inductive proofs without fear of randomly confounding something that is really finite unbounded with something infinite.

    eg: I'll show an inductive construction of the counting numbers, and then construct a proof based on the same principle that could potentially confound the two ideas (but doesn't have to) without making a mistake in the proof. (At least, I don't see a mistake...) and then could you explain to me exactly what kind of infinity Cantor had in mind for Aleph naught?

    First off, consider what the set of counting numbers is:
    The set of counting numbers, (A hereafter), is not something we can actually list all the elements of, physically; so the very idea of the set of all counting numbers is itself *inductively* constructed by making successive elements valued '1' larger than the previous element added to the set; eg: for every element, N, that is added, one adds the successor element who's value is N+1... literally, that's the idea of "counting" which gives the set it's name.

    eg: I would construct it like this for clarity.
    Na=1 and Aa := {} ⋃ { Na } = { 1 }
    The next step of the construction is always to add '1' to the last counting number that was united to the set.
    Nb=Na+1 and Ab := Aa ⋃ { Nb } = { 1 2 }
    Nc=Nb+1 and Ac := Ab ⋃ { Nc } = { 1 2 3 }
    Nd=Nc+1 and Ad := Ac ⋃ { Nd } = { 1 2 3 4 }
    Ne=Nd+1 and Ae := Ad ⋃ { Ne } = { 1 2 3 4 5 }

    And if the iterative process is allowed to go on forever, the set constructed is by definition the set of all counting numbers who's cardinality is therefore ℵ0.
    A = { 1 2 3 4 5 6 7 8 ... }, |A| = ℵ0

    When Cantor claimed this set size/cardinality to be the definition of the first infinity, I think he meant to say that the set contains (eg: *inside* the set) an infinite number of elements by axiom; and not by proof. And I am, of course, therefore not asking him to prove it -- but I am concerned that this has unintentional side effects -- for infinity is NOT the same as "finite but unbounded" in traditional set theory, eg: the individual elements of the set of counting numbers are each finite -- but by the same token (finite elements) I simply couldn't prove that the set is infinite inductively, but Cantor gives me an axiom with which I supposedly can always accurately measure when something is infinite; and exactly so -- not plus or minus one unmatched element; and I want to explore what that really means -- for I'm unsure that I truly understand it, or him.

    For I'm pretty sure Cantor is claiming that he is measuring an *infinite* number of elements, whenever a set has a inductively provable 1:1 correspondence with counting numbers. He doesn't intend a size that is finite, even if we don't know how large.

    For example; if I had all the decimal digit values of an irrational number that happens to have no zero digit places, and contained in a sequence for convenience, but not strictly necessary -- (eg: a sequence, is a set which in this example I'm making the successors be in strictly decreasing magnitude), and this set contains a supremium if there is one ... "0" ? but even if it doesn't it wouldn't affect the value -- for all nonzero values are in the set.

    irr = { 3 .1 .04 .001 .0005 .... }

    Then clearly that set would be infinite in length, for the value is irrational and the digit places summing up to the irrational value, by definition, can never end; Thus, such a sequence by even being listable is clearly in 1:1 correspondence with counting numbers; and the cardinality is aleph naught.
    So, if I add up ALL the values in the set which are in 1:1 correspondence, I must get the exact value of the irrational number -- and not some value that is missing some of the digits. (This is a set, not a series; so were not taking a limit -- we're adding everything up in the set.)

    So I think cantor means that kind of infinity, not finite unbounded -- but an actual infinite set capable of handling infinte digit values, and not just an approximation but in a countable ordering.

    Irra = { 3}
    Irrb = { 3 .1 }

    Therefore: If the set has an infinite cardinality, then the sum of all the elements must equal the value of the irrational number, not some subset of it -- or a finite but unbounded amount less than the irrational numbers value -- but rather, the true sum of everything in the set :: otherwise, the set's not infinite but truncated at some point short of all the digit values -- even if we couldn't determine exactly how far out it was truncated.

    Do I have this right? Infinite means infinite, all, forever, nothing short of it.... ? That's what cantor means?

    If this is so, and Cantor means it really is infinite, then it seems I should also be able to use 1:1 correspondence to inductively prove a construction could contain a subset with cardinality aleph naught; (which isn't a big deal at first sight... -- but let's do it, so I can show the obvious -- and then after I prove this, I'll show where even though I was careful to do this exactly like the counting set, that 1:1 correspondence allows me to prove something that is unexpected and I'm not sure what it means. )

    The task: Construct a set that by it's very nature, must by 1:1 correspondence, contain an element of cardinality -- ℵ. The set will be called "O" for obvious... and I will prove that it has the property: ∃ N ∈ O : |N| = |O| = ℵ0

    So, I'm going to do this the exact same way I did the construction of the set of counting numbers, but I'll count by the cardinality of the largest element in the previous set + 1, rather than by an integer number. It's a trivial change -- but it also will show how solidly the proof ties in with the very notion of counting by correspondence. (listing).

    Oa := {} ⋃ { Aa } = { {1} }
    The next step of the construction is always to add '1' element to the element which will be unioned to the set.
    Ob := Oa ⋃ { Ab } = { {1} {1 2} }
    Oc := Ob ⋃ { Ac } = { {1} {1 2} {1 2 3} }
    Od := Oc ⋃ { Ad } = { {1} {1 2} {1 2 3} {1 2 3 4} }
    and if allowed to continue forever, I have inductively constructed the set:
    O = { A {1} {1 2} {1 2 3} {1 2 3 4} ... }

    For, in any construction step it can be seen by inspection and definition that the cardinality of the element unioned has the same cardinality as the set created by that construction's step. Therefore the condition is ALWAYS met that for any step of the construction, XX - 1, that the next step of the construction XX will also fulfill the condition:
    ∃ N ∈ OXX : |N| = |OXX|

    Therefore, inductively this condition must hold in the infinite case;
    ∃ N ∈ O : |N| = |O| = ℵ

    It's no big deal that an infinite set could contain another infinite set; and this didn't bother me at first -- but the problem is that the proof is based on 1:1 correspondence to determine that it contains infinite elements; and therefore it automatically paves a way to prove that any construction done in 1:1 correspondence (by counting) using a subset (any aleph naught subset) in place of Axx; if that subset has a supremium -- then O contains the supremium of the set.

    eg: Consider the set 'irr' which I already described; and then Replace Axx in the above construction of O, with irrxx instead; the very proven fact that the set O must contain an element with cardinality of aleph naught would automatically prove that O must contain the set irr itself, and NOT just part of the set, and not missing even one element;

    What I'm getting at is that Either sets of cardinality Aleph naught must contain the supremium (if it exists) of any sequence used for counting by 1:1 correspondence, or else 1:1 correspondence does not prove a set length is truly infinite.

    Which is really what Cantor means by infinity?
    I'm not sure I understand.

    For, it seems that Cantor sets of size Aleph naught must always be closed sets when it is possible they could be closed sets; but I get the impression that Cantor assumes the sets are open because his example set of counting numbers is an open set -- although I have never seen him state that his method only works on open sets, eg: ones that don't have a supremium.

    Why is this?
    Last edited: Nov 8, 2013
  2. jcsd
  3. Nov 8, 2013 #2


    User Avatar
    Science Advisor

    I can't figure out what you mean by "open" and "closed" sets here. What topology are you using?
  4. Nov 8, 2013 #3


    User Avatar
    2017 Award

    Staff: Mentor

    What do you mean with "finite unbounded"? Clearly every finite set is bounded by one of its elements, if you have some ordering that is powerful enough to have such a thing.
  5. Nov 8, 2013 #4
    I've have been taught that the difference between open and closed sets is whether or not the set contains the supremium. At least that's what a mathematician told me, and I am going on trust for he has the degree and I don't.

    I am also thinking that the supremium of a set would be the element of a sequence which has no successors, but which is the successor to all other elements in the set.

    Is this somehow, incorrect?

    I am only working with sets, like irr, that I can arbitrarily organize as sequences for convenience.
    eg: I am assuming that taking an unordered set and then organizing it as a sequence doesn't change the cardinality of the set. If it does, than I might want to show the exact same example again -- but just treat it as an unordered set. The sequencing of the set does not affect the point I am trying to make -- that it contains all values of a decimal representation of an irrational number.

    I'm explicitly NOT doing infinite series, for I don't want to take the limit -- like calculus teaches us; for that's not basic set theory; I want this to be strictly a set theory issue.

    The point of the irrational number set, is that it contains (explicitly) all the digit values of an arbitrary irrational number; eg: irrespective of whether there is a supremium element or not; and irrespective of whether one can take a limit somehow -- so, choosing the example this way means that I know for certain that the value (sum) of all items in the set, irr, regardless of the sequence or lack of sequence that they are added up in -- is exactly equal to the value of the irrational number.

    I think I had to do that because, I was also told by another mathematician (with a degree) that this nice property would not be provably be the case if the set contained merely the elements of an infinite series -- for one could argue the problem is ill defined, for it technically would be missing the supremium value.

    So, to avoid the issue -- I made a "nice" example where the supremium, if it exists, must be zero. :)

    Oh, and don't assume the irrational number I chose is actually "pi" ; for that's not the point; but the start of the sequence does kind of look like it; so this is just a BTW -- please don't read more into what I said than what I said....!
    Mathematics can be hard.
  6. Nov 8, 2013 #5
    Good question.
    That's a place where the things I've been learning about Cantor sets gets very foggy.
    I find it difficult to keep the terminology straight.

    I think the phrase "finite unbounded" applies to the characteristic of a set where every element that one can inspect in the set during any step of it's inductive construction is either a finite number or (perhaps?) finite cardinality, but which leads inductively to the creation of a set of a cardinality of at least aleph naught.

    A counting number, by formal definition, is a finite element; vis: There is no integer having the value of "infinity". So the set of all counting numbers has the properties of finite element values, but an unbounded "number" of them, or considered from another perspective -- integers/counting numbers have no finite upper limit to the magnitude that they can represent ; although a specific instance of an integer must be finite in magnitude.

    I think that's what the invention of the notation aleph naught was for -- since computing cardinality usually produces a counting number; but numbers are invalid for sets having "infinite" lengths. So Georg Cantor wanted to formally invent a symbol to represent the cardinality of sets which can't be represented by an element of the counting number set.

    There is also another way the idea of finite unbounded might be usable, and that is instead of a set which has unboundedly large magnitude elements, one could have a set with unboundedly small -- BUT FINITE -- elements. Essentially, it would be like arguing that there are numbers that are 'nearly' as small as '0' but without being '0' for it has a finite value; But -- if a finite value is subtracted from an irrational number -- there would be a finite, but nonzero, difference.

    I don't see any way that those kind of numbers could affect the result of summing up everything in the 'irr' set I described, for they would cause the number to have a different value than the irrational number itself, that the set describes ; I may be being overly cautious -- but I want to make sure I'm considering everything possible, and ruling it out.

    -- as to your obervation --

    I'm not sure what "power" means, or if ordering is specifically important to the question.
    You may need to teach me, because this is a gray area in my understanding.
    I am starting with just aleph naught sets, and once I understand them -- then I was thinking about moving on to higher cardinalities ; but I'm not there yet -- for I'm still working on the basics.

    I'm under the impression that Georg cantor's invention of 1:1 correspondence to prove sets of equal "size"/cardinality works for both finite and infinite sets equally well, and with no errors. I don't recall ever being told that a specific ordering of the set is necessary for it to work -- but perhaps that is something that I overlooked?

    I know only a little bit of set theory, basically what I learned in high school and took my freshman year at college.
    When we talk about sequences, and predecessors and successors, I have no problem following the logic -- but when I try to read mathematics pages on ordered sets there appears to be more definitions that aren't required for mere sequences. SO, if Cantor's proofs work on sequences, I'd prefer sticking to them unless you're willing to give me a very gentle introduction, with clear proofs, as to why we need to use "power" ordering stuff ?
    Last edited: Nov 8, 2013
  7. Nov 9, 2013 #6


    User Avatar
    2017 Award

    Staff: Mentor

    That's certainly wrong.
    As subsets of the real numbers with the usual topology:
    (0,1] contains its supremum (without "i") and is neither open nor closed.
    [0,1] contains its supremum and is closed.
    [0,∞) does not contain its supremum and is closed.
    (0,∞) does not contain its supremum and is open.

    For subsets of complex numbers (and many more sets), the concept of a supremum does not work, but open and closed sets are well-defined.

    A sequence of what?
    Anyway: No.

    So you just consider countable sets?

    If you can do that, it does not change the cardinality. But that is an important "if", as it does not work for every set (see above).

    An irrational number has exactly one value, independent of its representation.

    Sorry, I think your posts don't make sense at all.
  8. Nov 10, 2013 #7
    I'm only interested in sets which I think should be of size aleph naught, so I think the answer to your question is "yes":
    If construction of a set by appending (unioning?) 1 element at a time means "countable", then definitely YES -- otherwise -- no, I don't know how to answer your question.

    Please focus on the examples I gave, for I'm not speaking about all kinds of sets in general as if trying to prove the theory in general, but am tying to understand it using very simple and clearly defined examples with a minimum of complications.

    Two of the examples I gave were explicitly constructed by the same method that the counting number set can be constructed by; -- therefore, I would expect that they should both be countable, and have a cardinality of aleph naught.

    The irrational number set wasn't explicitly constructed; but I imagine it to be constructable similarly.

    Thank you, it would appear I was either given bad information concerning what open means, or else he meant it in a way that he didn't make very clear to me.

    I used it, in the context of the examples, only to discern whether the set/sequence had a supremium that was included in the set ; Simply replace the word "open" with "not including a supremium" and, for "closed" replace it with "having a supremium" and the discussion will be back on track.

    You may ignore the idea of open sets in this discussion, for I only used the word once in the opening post -- but even a brief look back at the post will reveal that it was never used in any of the proofs. There is no need to derail the thread any more over "open" and "closed" sets.

    I apologize that the post was confusing to you.

    I am fully aware that the concept of supremium doesn't always apply; that's part of the point of the discussion.
    But I'm only interested in discussing two cases: When a supremium is considered part of a set, and the case where it is not -- ( regardless of why, eg: either because it exists but isn't in the set, or else doesn't exist / apply. )

    The reason the supremium interests me is that having a 1:1 correspondence assures that every element in one set has a corresponding element in the other set, and that there are no mismatched elements, not even 1 element. Therefore, if one could debate that given two sets (my examples, hypothetically) that one has a supremium and the other does not -- yet they are constructed in exactly the same way, then the sets might not be in 1:1 correspondence inductively speaking, although they are by inspection of size aleph naught. eg: Some examples might differ by 1 element only.

    Consider an example set to understand why I focus on the supremium:

    If I took pi, and defined a decimal sequence of all decimal string truncations;
    PiTruncate := { 3, 3.1, 3.14, 3.1415, 3.14159, ... }
    I can ask the question of whether or not PI is actually in such a set taken out infinitely far; and I'm often told by others -- "no it isn't", for inductively the error between an element and PI gets smaller at each successor in the sequence, but the error is still finite and non-zero at every step. ( Note, I could also argue that since I specified the use of a truncating function to generate the values, that a possible truncation is not to truncate at all... but induction is based on finite steps, to infer what happens at infinite steps -- and 'non' truncation would be at infinite steps.... )

    The supremium, then, is not an element of the PiTruncate sequence based on inductive reasoning.

    I gave three specific examples of sequences; although the particular items I used as elements, could potentially be exchanged with other items; There is no need to invent or consider others at this time, for the examples are sufficient.

    That sounds reasonable;
    So are you saying that the fixed cardinality is already proven as a theorem somewhere, or are you just saying that you would not expect it to change?

    So, in the opening post example I gave, am I to understand that you would agree that the sum of all elements in the set 'irr' would be equal to the exact value of the irrational number from which the individual elements of the set were computed? Or do you need more information?

    At all? That's rather harsh. It's at the high school level ; surely some of it made sense.

    But what do you think now, since I have tried hard to clarify; or are you saying that the proofs and examples I gave are in definitely in error ?

    eg: in the final set, O would you agree that I inductively proved a set of cardinality aleph naught is an element of the set O, or not ?

    If your answer is No-- then could you show which step of the proof is definitely false ??
    Last edited: Nov 10, 2013
  9. Nov 10, 2013 #8


    User Avatar
    2017 Award

    Staff: Mentor

    Okay, sorry, but if you are making up words (especially words that are used with a completely different meaning in mathematics), I'm out.
  10. Nov 10, 2013 #9
    Here is an example that shows the distinction between cardinality and order.

    First, consider the counting numbers 1, 2, 3, ... in their natural order.

    Then, consider the same set of counting numbers in a funny order:

    2, 3, 4, 5, 6, ..., 1

    In the second order we just make up a new rule that says that everything is less than 1. So it's the same set, but in a different order. In this funny order, 1 is the supremum of the set of counting numbers.

    Now there's still an obvious bijection between the two sets:

    1 <-> 1
    2 <-> 2
    3 <-> 3

    so their cardinality is the same.

    But there is no order preserving bijection between two sets. That's because they have a different order type. In the standard ordering, there's no largest element. But in the second, "funny" ordering, there is a largest element, namely 1. In the second ordering, the set contains its supremum.

    I think this example bears on the issues you are raising. You are correct that we can not find any way to biject the two ordered sets in a way that preserves the order. Nevertheless, we can biject the sets in a very natural way.

    So the two sets have the same cardinality but not the same order type.

    Cantor actually did sort this out for us a long time ago: he distinguished between cardinal and ordinal numbers. Cardinals tell us "how many" and ordinals tell us what order the sets are arranged in.

    We see that for a given cardinality there may be many different ways of ordering an infinite set, none of them order-equivalent to any others. And to determine if two sets have the same cardinality, we only require that there exists some bijection between them. We do not require an order-preserving bijection.

    Hope this helped.
  11. Nov 10, 2013 #10
    No, I'm not making up words ; so your "if" is false.

    I was at most given a bad piece of information by a mathematician with a degree, and if I could edit the opening post -- I would have done so. But the time to do so has expired... so my only two alternatives are to start a new thread, and hope this one disappears -- or continue on with this one in the state it is in.

    Since the words you complained about are not part of the proof, I don't see why you are avoiding commenting on it -- but thank you for your time, anyway.
  12. Nov 10, 2013 #11
    OK, yes, good...
    Sets can be arbitrary sequences, or unordered, and all we need is some arbitrary rule to decide which elements are successors, and predecessors of others, to be able to list them out as you have done. So you would have a rule that you want to call "funny" which determines why the latter example has 1 as not being before 2. And, I assume that "..." represents all other counting numbers, eg: numbers which aren't explicitly shown ...

    Hmm... I think you might have made a typo or didn't finish your sentence; for isn't "1" part of the set? So I don't quite see how everything is less than 1; unless you mean that the position of the element in the sequence is the "greatness" of that element.

    I usually make each successor in a sequence (when possible without a lot of effort) to be monotonically increasing in magnitude -- so that the supremium (dislaimer: when it exists, and is also an element of the set... ) comes last and therefore has no successors, although the sequence could be arranged with the supremium in a different location. It's just a habit of mine -- and I realize it can be done other ways.

    OK, you are matching the natural ordered set to the funny sequence, using an element by element basis, but not based on the actual sequence that funny's element appear in.

    hmm.... I don't quite understand:
    I would think one could correspond any element in one set, with any element in the other set; and call it a bijection... so long as the relationship is strictly one to one, and not one to many, or many to one, or having even one element with no relationship to the other set at all...

    So: Are you saying this can't be done?
    Natural <-> Funny, according to ordering:
    '1 <-> 2'
    '2 <-> 3'
    '3 <-> 4'

    Also, I don't quite understand why '1' is a supremium in the funny sequence:

    A supremium is the smallest possible element that will be larger or equal to all elements in a set.
    An infimium would be the largest possible element that will be smaller or equal to all elements in a set.

    So, I'm trying to figure out what you mean:
    What is the definition of larger or smaller in this particular context? In the sets you are listing out -- I see scalar values, so I think it's the magnitude of those values which is being compared as "greater" or "smaller";
    But, if I do that -- I will come up with a result that '1' is the infimum of the set, not the supremium.
    So, what function are you using to compare the numbers with?

    In my own examples, I seem to have forgotten to include the meaning of what is "greater" in the case of 'irr'... and nobody asked; but now that I'm re-reading the O.P. I realize I must have been tired. :redface: Not that it mattered in that case, for I was trying to eliminate the effect of what I think people would normally have considered the infimum ; and it's either zero -- or it doesn't exist; which has the same effect on the sum -- no effect at all.

    But, for future reference, is it necessary for me to state that for sets like "O", (where the elements are also sets in their own right) that the cardinality is what is being compared for "greater"; or is the fact that Cantor's work compares the cardinality of sets sufficient context for most readers ?

    In the O.P. I was thinking that the set of counting numbers "Aא" has no supremium; but the set "Oא" has a supremium, which is the set of all counting numbers "Aא".

    Yes, he does -- you are discussing part of the topic that I'm trying to grasp. I don't know exactly what "order type" means; but I get the general idea... and perhaps I can look it up.

    It does help a little. I appreciate your time.

    You do seem to have most of the issues outlined in your post, and perhaps if you could clarify the few things I have asked you about in this post -- I will either be able to figure out the answer myself, or at least we will be talking to each other clearly enough that I can actually ask the questions I have so that you can understand them well.
    Last edited: Nov 10, 2013
  13. Nov 10, 2013 #12
    Let's talk about order types.

    Imagine a room full of people. I can order them by height, by weight, by date/time of birth. In the by-age ordering, the oldest person in the room is the supremum. They're the smallest of all the upper bounds for the rest of the people in the room, ordered by age.

    Or I can order them by inverse income. Wealthiest first, then the next wealthiest, all the way "up," or left-to-right to the poorest person in the room at the end. Now the poorest person is the supremum, because they are the supremum in that particular order.

    An ordered set is a set plus a particular order relationship. And orders are arbitrary. You can just have a random order on the alphabet, say line up the five letters c, a, z, r, b. Then you'd say that c comes before a and r comes before b. And is there a sup in this order? Yes, it's b.

    An order is just an arbitrary relationship that satisfies some technical properties, such as if a < b and b < c then a < c. But we don't care what '<' is. It's just an arbitrary symbol.

    Now with infinite sets, things are a little more interesting. With our examples of order relations on a finite set of people, we can order them in different ways, but each ordering still follows the familiar pattern of 1, 2, 3, 4, ... N up to some largest element N. In technical terms, all the orderings on a given finite set are "order isomorphic" in the sense that they are all order-bijectable to the sequence 1, 2, 3, 4, ..., N where N is the cardinality of the set. [A bijection is an order-isomorphism or is order-bijection if it's a bijection that preserves order]

    So now consider some orderings on the infinite set of counting numbers 1, 2, 3, ... We have the usual order, in which we order the numbers by their associated cardinality.

    But how about the "funny" order I mentioned. Line up all the numbers starting with 2:

    2, 3, 4, 5, 6, ... all of them ... and then at the end, put 1.

    Remember an ordering is essentially arbitrary. It's just a rule you make up. It might have some natural analog, like the size of a number. Or it might not. It's like lining up a room full of schoolkids. It's not important how you line them up as long as you get them lined up!

    So in our new funny order we would write 2 < 5 and 12 < 47 and 6 < 1. Because '<' doesn't have its usual meaning, it has our new funny meaning.

    And in this order, 1 is indeed the supremum. It has the property that it's the smallest of all the upper bounds for the set. Same exact definition as always.

    Now the interesting thing is, in the usual order, there is no last element. The usual order does not have a supremum, but the funny order does. We also say that the usual order is unbounded, and the funny order is bounded by 1. Everything in the set is is less than or equal to 1.

    So these two orderings are not order-isomorphic. They're structurally different. Let me say that agin. they're structurally different, in the same way all the different orderings on a finite set are structurally the same.

    In fact -- and this is an important point -- the funny order is no longer even worthy of being called a "sequence." A sequence is defined as something that looks like 1, 2, 3, ... If it has any kind of funny order at all, it's a "well ordered set," but it's no longer called a sequence.

    I mention that because it's a semantic trap. When you use the word sequence, you need to remember that you're talking about an ordered set with the *usual* order type of the counting numbers. All "funny" orderings are still well ordered sets, but they are not sequences. So when you use the word sequence, you are talking about a very specific type of ordering on a countable set, namely the "natural" one. But there are a lot of unnatural ones too.

    [There is a technical definition of a well-ordered set, but I didn't want to bog down in details here. I linked the Wiki article on the subject below]

    Just to give you a small flavor of how wild countable well ordered sets (also called "ordinal numbers") can be, just take all the odd numbers followed by the even numbers:

    1, 3, 5, 7, 9, ..., 2, 4, 6, 8, ...

    So 3 < 5, 9 < 4, etc.

    This is an order type consisting of two copies of the counting numbers sitting side-by side.

    But what if we did the same thing with 3's?

    1, 4, 7, 10, 13, 16, ... 2, 5, 8, 11, 14, ... 3, 6, 9, 12, 15, ...

    Do you see what we did there? [Stop till you do!] We now have a countable order type consisting of three identical copies of the infinite set of counting numbers, side by side.

    And we could keep on doing this ... four copies ... five copies ... countably many copies ...

    The countable ordinals are actually one of the most mind-boggling objects in mathematics. There are a lot of ways to line up a schoolroom with countably many kids. [Hilbert's schoolroom!]

    I really wrote a lot here, I hope I didn't overwhelm you. I wanted to try to put order types in perspective for you. I have the sense that your question is really about countable sets that do or don't have last elements, and how you can still say they have the same cardinality. Let me know if this sheds any light on my earlier post.

    Here's the Wiki article on ordinals. But all you really need to remember is that there are a lot of different and amazingly complex ways to order, or line up, a countable set. In fact there are ... drum roll ... uncountably many different ways to well-order a countable set..

    In exactly the same way that there are infinitely many finite ordinals; there are uncountably many countable ordinals. And it's turtles all the way up. Set theory can make your head spin. Poor Cantor, being the first person to figure out all this stuff and then having his former mentor, of all people, totally trash him in public for his ideas. And Cantor already being a sensitive soul. What a tragedy.

    Last edited: Nov 10, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook