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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.