# Does every sequentially ordered infinite set contain sequentially ordered infinite subsets?

I am not very familiar with mathematical proofs, or the notation involved, so if it is possible to explain in 8th grade English (or thereabouts), I would really appreciate it.

Since I may even be using incorrect terminology, I'll try to explain what the terms I'm using mean in my mind. Please correct my terminology if it is incorrect so that I can speak coherently about this answer, if you would.

Sequential infinite set: A group of ordered items that flow in a straight line, of which there are infinitely many. So, all integers from least to greatest would be an example, because they are ordered from least to greatest in a sequential line, but an infinite set of bananas would not, since they are not linearly, sequentially ordered. An infinite set of bananas that were to be eaten one-by-one would be, though, because they are iterated through (eaten) one-by-one (in linear sequence).

Sequential infinite subsets: Multiple sets within a sequential infinite set that naturally fall into the same order as the items of the sequential infinite set of which they are subsets. So, for example, the infinite set of all integers from least to greatest can be said to have the following two sequential infinite subsets within it: all negative integers; and all positive integers. They are sequential because the negative set comes before the positive set when ordered as stated. They are infinite because they both contain an infinite qty of items, and they are subsets because they are within the greater infinite set of all integers.

So I'm wondering if every (not some, but every) sequential infinite set contains within it sequential infinite subsets. The subsets (not the items within them) being sequentially ordered is extremely important. Clearly, a person could take any infinite set, remove one item, and have an infinite subset. Put the item back, remove a different item, and you have multiple infinite subsets. But I need them to be not only non-overlapping, but also sequential in order.

Please let me know if this does not make sense, and thank you for dumbing the answer down for me.

-
Let our set be the positive integers, under the usual order. Would the two sets "even positives" and "odd positives" qualify? – André Nicolas Sep 13 '12 at 2:15
No. The two sets don't come entirely one after the other. Rather, they are intermingled in the order of positive integers. I realize they don't overlap in terms of having shared items, but they do overlap in terms of their location in the number line. I am wondering about a whole infinite set followed in order by another whole infinite set. Does that make sense? – Tim Sep 13 '12 at 11:10
:** Sure it makes sense. For example you can have a "red" copy of the positive integers, followed by a blue copy. That has a name, it is the ordinal $\omega+\omega$. Or take all conceivable "words" however long, listed in alphabetic order. You have infinitely many words a, aa, aaa, aaaa, and so on and have barely started the a's! Many examples, manyorder types. – André Nicolas Sep 13 '12 at 13:54
Wow. I like your "aaaaaa"s example. That would be exactly the type of thing I'm talking about. Thanks for the example. I believe that Henning demonstrated that there is at least one infinite set that does not fit my criteria, so it seems that not every infinite set conforms to this idea. But I'll wait a little bit to see if someone can demonstrate Henning's example is incorrect before I say his answer is correct. Thanks André! – Tim Sep 13 '12 at 14:23
It is not clear what your conditions really are, Once they are fully known, counterexamples or a proof become routine, since mathematicians in many fields have to deal with weirdly ordered sets. – André Nicolas Sep 13 '12 at 14:56

Given your objections to the other answers, here is how I understand your concept of "sequentially ordered":

• The set is totally ordered (i.e., for any $a$, $b$ we must have $a\le b$ or $b\le a$).
• Any element that has a successor has a first successor.
• Any element that has a predecessor has a last predecessor.

And you want to divide such a set into two subsets $A$ and $B$ such that there is no element of $A$ that comes between two elements of $B$, and vice versa.

Under this interpretation of the question, one example would be the set $$\{0,1\}\times \mathbb Z$$ -- that is, the set of ordered pairs such that the first element is either 0 or 1 and the second element is a (possibly negative) integer -- with the lexicographical ordering such that $(0,a)<(1,b)$ for all $a$ and $b$, and pairs with the same first element are compared according to their second element.

Then the sets of pairs with 0 as the first element and pairs with 1 as the first element should satisfy (my interpretation of) your conditions.

On the other hand, it is clearly not the case that every infinite "sequentially ordered" set can be split into infinite subsets that match this condition -- $\mathbb N$ itself with the usual ordering would be a counterexample, because the one of $A$ and $B$ that contains the "smaller" elements would necessarily be finite.

-
You understood exactly what I was talking about. Wonderful. But couldn't the "smaller" element subset be represented as every item less than half of N (in the first half of N)? With the "greater" element subset representing every item more than half of N? Making 2 infinite sets that fit my criteria? Or maybe I am confusing the elements of N with N itself? Does it make sense to halve an infinite set? – Tim Sep 13 '12 at 13:48
@Tim: Suppose we have $\mathbb N$ partitioned into sets $A$ and $B$ as described. If one of them is empty, they are certainly not both infinite, so we can pick two arbitrary elements $a\in A$ and $b\in B$. Now if $a<b$, then $A$ is not allowed to contain anything that is larger than $b$, so every element in $A$ is less than be. This means that $A$ can have at most $b$ different elements and so is finite (because every $b\in\mathbb N$ is finite by definition of "finite"). If $a>b$, then repeat the argument with $A$ and $B$ interchanged. – Henning Makholm Sep 13 '12 at 13:53
Understood. If there is a greater element within an infinite set of positive finite integers (for example), then the lesser set (lesser than the greater element) must be finite by definition. Hmm. Interesting. Thanks Henning! – Tim Sep 13 '12 at 14:19

If I understand you correctly, what you mean by a sequentially infinite set is probably a countably infinite set with a specific ordering attached that makes it possible to specify a first element, a second element, and so on. In other words, you have what amounts to an infinite list:

$$a_1,a_2,a_3,\dots\;,$$

with an $a_n$ for every positive integer $n$. In more technical language, this is an infinite sequence of objects. If that is what you have in mind, just imitate what you did with the odd and even positive integers: take one set to be

$$\{a_2,a_4,a_6,\dots\}=\{a_n:n\text{ is even}\}\;,$$

and take the other set to be

$$\{a_1,a_3,a_5,\dots\}=\{a_n:n\text{ is odd}\}\;.$$

In the banana example, imagine that one banana is eaten every hour on the hour, starting at $1$ a.m. Then the first set consists of those bananas eaten at even-numbered hours, and the second set of those eaten at odd-numbered hours.

You can do this in general because (again, if I’m understanding you correctly) the numbering is an inherent (albeit implicit) aspect of your notion of sequentially infinite set.

If you want to get fancier, for any integer $m\ge 2$ you could form the $m$ subsets $A_0,A_1,\dots,A_{m-1}$, where

$$A_k=\{a_k,a_{k+m},a_{k+2m}\dots\}=\{a_n:n\text{ leaves a remainder of }k\text{ on division by }m\}\;.$$

In this way you break the original set into $m$ exhaustive but non-overlapping sequentially infinite sets.

-
The odd and even divisions don't actually accomplish what I'm looking for. I am looking for two (or more) sets that would not only not share members, but where, in the order given, one set would have to be completely finished before the other even begins. Does that make sense? – Tim Sep 13 '12 at 11:16
@Tim: It makes sense, but you can’t do it with something ordered like the natural numbers. You could put two such ordered sets end to end, though. For instance, consider the set of all numbers of the form $1-\frac1n$ and $3-\frac1n$ for positive integers $n$: $0,\frac12,\frac23,\frac34,\frac45,\dots,2,\frac52,\frac83,\frac{11}4,\frac{14}5‌​,\dots\;$. Now you have the sets $\{0,\frac12,\frac23,\frac34,\frac45,\dots\}$ and $\{2,\frac52,\frac83,\frac{11}4,\frac{14}5,\dots\}$ ordered the way you want. – Brian M. Scott Sep 14 '12 at 23:13

The short answer is, yes.

Every infinite set has a countably infinite subset. In lay terms, 'countably infinite' means that we can index each element of the set with an integer, such as $a_5$. Say your original set, call it $S$,has a total ordering on it (I am assuming this is what you mean); this says we have an inequality $<$ such that, for any two elements $x$ and $y$ in the set, either $x<y$, $y<x$, or $x=y$ (this is an abstract inequality, these elements don't have to be numbers).

With these conditions in place, we can rewrite our set as $S=\{...,a_{-3},a_{-2},a_{-1},a_0,a_1,a_2,a_3,...\}$, where we have $a_i<a_j$ whenever $i<j$. Notice that we can split up the set in the same ways we can split up the integers, say into elements of odd and even indices, or by indices evenly divisible by three and those that are not. You can see that every such partition splits our original set into multiple, totally ordered sets.

If you are interested in properties of infinity and infinite sets, the book Infinity:The Quest to Think the Unthinkable by Brian Clegg is a very accessible and interesting introduction to questions like this. It is written for a layperson, no math skills past junior high school level are required.

-

It sounds like you are thinking of your set as a tree and want to know if there is an infinite path. The path through the tree would be the ordering you are talking about. König's lemma assures you that if the tree is finitely branching that there will be an infinite path.

-