# Is there a "smallest" infinite subset of the naturals?

• I
jordi
The natural numbers are the smallest infinite set, aleph_0.

By taking out an infinite subset to the natural numbers (the odd naturals), we get an infinite subset, the even numbers, which has the same size, aleph_0 (e.g. the map n->2n).

We can take an even "sparser" subset of the natural numbers: the prime numbers. This subset of the natural numbers also has the same size, aleph_0 (e.g. the map n->n-th prime number).

My question is: is there an "sparsest" subset of the natural numbers, such that if we take out any infinitely sized subset of it, it is not aleph_0 anymore?

Jarvis323
The natural numbers are the smallest infinite set, aleph_0.

By taking out an infinite subset to the natural numbers (the odd naturals), we get an infinite subset, the even numbers, which has the same size, aleph_0 (e.g. the map n->2n).

We can take an even "sparser" subset of the natural numbers: the prime numbers. This subset of the natural numbers also has the same size, aleph_0 (e.g. the map n->n-th prime number).

My question is: is there an "sparsest" subset of the natural numbers, such that if we take out any infinitely sized subset of it, it is not aleph_0 anymore?

No.

Suppose there were, and call it ##S##, then ##\{ 2s \mid s \in S \}## is "sparser", and also countably infinite.

nuuskur, WWGD and topsquark
jordi
I do not agree. This new "sparser" set could be the same as the original set, except for a finite set of points (for example, if the points in the original set are even).

Jarvis323
I do not agree. This new "sparser" set could be the same as the original set, except for a finite set of points (for example, if the points in the original set are even).

I'm not sure what you mean. If the original points are the multiples of 2, { 2, 4, 6, 8, ... }, then the new points will be the multiples of 4, { 4, 8, 12, 16, ... }.

topsquark and jordi
willem2
I'm not sure what you mean. If the original points are the multiples of 2, { 2, 4, 6, 8, ... }, then the new points will be the multiples of 4, { 4, 8, 12, 16, ... }.
And if the original points, are the powers of two, the new points will also be the powers of two, except for the single number 1. This set is apparently equally sparse by Jordi's definition. Of course, using the odd-numbered powers of two will work.

Of course, even the powers of two aren't scratching the surface of the sparse sets.
A faster growing function will produce a sparser set, and there are many examples of those:
factorials, iterated factorials, non primitive recurse, non- computable functions etc.
https://en.wikipedia.org/wiki/Fast-growing_hierarchy

WWGD, Jarvis323 and topsquark
Gold Member
MHB
I do not agree. This new "sparser" set could be the same as the original set, except for a finite set of points (for example, if the points in the original set are even).
The Natural numbers do not have any infinite subsets "smaller" than themselves, which Jarvis 323 demonstrated. But if we step this up a bit, there is something called the "minimal uncountable well-ordered set (in which every section is countable)", ##S_{ \Omega }##. It still has the cardinality of the reals, but it is, in some sense, the "smallest" such set in that we can take any section of it and get a countably infinite set. (Obviously, the term "smallest" here is not a measure of cardinality.)

-Dan

My question is: is there an "sparsest" subset of the natural numbers, such that if we take out any infinitely sized subset of it, it is not aleph_0 anymore?
Obviously no. Whatever set you have. Put it in a sequence. Remove every other term. You have removed an infinite subset and you are left with an infinite subset.

Klystron, jbriggs444 and topsquark
Simple example. Assume s1,s2,s3,.. is "smallest", but s2,s4,s6,... is still smaller and infinite.

Gold Member
2022 Award
Simple example. Assume s1,s2,s3,.. is "smallest", but s2,s4,s6,... is still smaller and infinite.
Uh ... isn't that the same thing as saying that infinity minus one is smaller than infinity (which it isn't) ? Seems to me you're falling into the trap of thinking that infinity can be treated as a number.

topsquark
Warp
From an intuitive point of view, an infinite set that's "smaller than the set of natural numbers" would have to be "less than countable". It's hard to imagine what "less than countable infinity" would even mean. How would you even define such a thing? I don't think it can logically be defined.

Uh ... isn't that the same thing as saying that infinity minus one is smaller than infinity (which it isn't) ? Seems to me you're falling into the trap of thinking that infinity can be treated as a number.
All that I was trying to show was that the original question ("smallest" infinity?) is no. You always keep removing half.

phinds
Homework Helper
Uh ... isn't that the same thing as saying that infinity minus one is smaller than infinity (which it isn't) ? Seems to me you're falling into the trap of thinking that infinity can be treated as a number.
No. There is no trap here. The notion of "smaller" being invoked here is sparseness, not cardinality.

We are up against a problem in that "sparseness" has not yet been defined as a total order on the set of all infinite subsets of the naturals. But it seems clear that ##\{s_2, s_4, s_6, ...\}## is more sparse than ##\{s_1, s_2, s_3, ...\}##. We at least have a partial order. This is enough to demonstrate that no compatible total order can yield a minimum.

Jarvis323, pbuk, Mark44 and 2 others
SSequence
A very similar example occurs in comparison of functions with respect to eventual domination. Given two functions ##f_1:\mathbb{N} \rightarrow \mathbb{N}## and ##f_2:\mathbb{N} \rightarrow \mathbb{N}## we say that ##f_2## eventually dominates ##f_1## iff:
##\exists N \in \mathbb{N} \, \forall i \in \mathbb{N} \,[\, i \geq N \rightarrow f_2(i)>f_1(i) \, ]##

For example, if we have ##f_1(x)=2x## and ##f_2(x)=2x+1## then ##f_2## eventually dominates ##f_1##. However, note that ##f_1## doesn't eventually dominate itself [and same for ##f_2## and in fact no function eventually dominates itself]. Similarly, if we have ##f_3(x)=10+x## then ##f_1## and ##f_2## both eventually dominate ##f_3##.

We might ask whether there is a function (from ##\mathbb{N}## to ##\mathbb{N}##) which is eventually dominated by every function (other than itself). Or, in other words, whether there exists a function ##g:\mathbb{N} \rightarrow \mathbb{N}## such that every function (other than ##g##) eventually dominates ##g##.

The answer is no because of the following reasoning. Given any such specific candidate function ##g:\mathbb{N} \rightarrow \mathbb{N}## [which is supposed to be eventually dominated by every other function], we can define a function ##F:\mathbb{N} \rightarrow \mathbb{N}## as:
##F(x)=floor \left [\dfrac{g(x)}{2} \right ]##
We can see that that there exists a function ##F## (with ##F \neq g##) which is eventually dominated by ##g##. This runs counter to the claim that every other function eventually dominates ##g##.

Last edited:
topsquark
We could view this as a density problem. In this case, the subset of primes has density zero, so the primes could be considered minimal in this respect.

Density roughly refers to the proportion of primes up to a fixed range.

Cardinality wise only, there is no smallest countably infinite set. Any subset of ##\mathbb N## is either bounded (hence finite) or has the same cardinality as ##\mathbb N##. Without the axiom of choice, one could have infinite sets that are incomparable to ##\mathbb N## in terms of cardinality (e.g Dedekind-infinite sets).

Last edited:
topsquark
Gold Member
We could view this as a density problem. In this case, the subset of primes has density zero, so the primes could be considered minimal in this respect.
In a sense, the primes are the “biggest smallest” subset. They have a density of zero but the sum of their reciprocals diverges. There are other subsets of ##\mathbb{N}## whose sum of reciprocals converges, and the sum can be made arbitrarily small, e.g.,
$$\lim_{a\rightarrow\infty}\sum_{n\in\mathbb{N}}{\frac{1}{a^n}}=0$$
And of course, one can always remove a finite number of members from these ultra-sparse sets to get an even sparser infinite set. I don’t know if there’s a meaningful limit to this notion of sparseness, but I doubt it.

nuuskur and topsquark
Jarvis323
A few years ago I was thinking about these kinds of things. Like the apparent motivation of the OP, it stemmed from being unsatisfied with the idea that a "sparser" set is the same "size" as a less "sparse" one, and wanting to come up with a more interesting way to quantify infinite subsets of natural numbers.

I don't think I made much progress in the end. But what I though was the right starting point was to think about the amount of information represented by the set.

When you think about it, what makes the even numbers a different set than the natural numbers? You could just as well rename the natural numbers as if they had a different alphabet, and then { 2, 4, 6, 8, ...} is just the same set described with different symbols. This is what putting them into a bijection sort of amounts to. But the sets ARE fundamentally different, because these numbers have meaning outside of just being infinite sets of combinations of symbols. There is some amount of information providing this meaning that differentiates them. We can think of sets with our physical intuition as containers of objects, but is that really what they are? Or are they better characterized as some kind of body or system of information?

First we need to have the information that defines the natural numbers and our encoding of them. Then you need more information to specify which ones to leave out or not. E.g., the even numbers come with a small amount of additional information compared with the natural numbers. In this sense, the set of even numbers represents more information. If we decide sets are fundamentally informational objects, then it makes sense to say the evens is larger. And both, despite being countably infinite in cardinality, are actually finite and quite small objects.

We could try to formally define the size this way based on Kolmogorov complexity, where the size of the set is the size of the minimal program that enumerates it, relative to some computing model.

There are some questions I personally don't know the answers to, and issues and consequences worth thinking about:

(1) Some sets of natural numbers aren't computably enumerable.

(2) The Kolmogorov complexity depends on the order of the elements in the set. Our minimal program can print the set in any order it wants.

(3) I guess the subsets which cannot be printed by any finite program would have an infinite size. But conventionally a program has to be finite, so you need another model of computation besides, say Turing machines, to formalize this properly. Anyways, assuming you do, then you still have a similar annoying problem as the one which motivated this all in the first place, how to differentiate the "sizes" of these sets which are representations of infinite amounts of information.

Last edited:
Homework Helper
(3) I guess the subsets which cannot be printed by any finite program would have an infinite size. But conventionally a program has to be finite, so you need another model of computation besides, say Turing machines, to formalize this properly. Anyways, assuming you do, then you still have a similar annoying problem as the one which motivated this all in the first place, how to differentiate the "sizes" of these sets which are representations of infinite amounts of information.
We are getting seriously astray from the original subject matter of this thread. However, there is an existing notion along these lines -- Chaitin Randomness. As I recall, the idea is that you have this infinite sequence and you want to characterize "how random is it?". So you take the limit, if it exists, of the ratio of the length of an initial sub-sequence and the size of the smallest program (relative to some computing model) that can reproduce that sub-sequence.

A perfectly "random" sequence will have a limit of 1 -- the programs that describe it will be approximately as long as the subsequence itself. Roughly speaking, those program will just hard code the sequence into the program. The only discrepancy is the fixed overhead to code up your hard code regurgitator in the selected computing model.

I hope that I've not butchered the idea of Chaitin Randomness too badly.

Jarvis323
Mentor
Granted, this is off-topic, but comments seemed to be needed.
For example, if we have ##f_1(x)=2x## and ##f_2(x)=2x+1## then ##f_2## eventually dominates ##f_1##.
It's not just "eventually" -- ##f_2(x) > f_1(x)## for all real numbers.
However, note that ##f_1## doesn't eventually dominate itself [and same for ##f_2## and in fact no function eventually dominates itself].
How could any function dominate itself as you have defined domination?

SSequence
How could any function dominate itself as you have defined domination?
Yes it isn't possible for any function to eventually dominate itself given how I defined it (using strict inequality). Of course if we change the definition slightly using ##f_2(i) \geq f_1(i)## instead of ##f_2(i)>f_1(i)## in the definition, then it changes.

Mentor
Yes it isn't possible for any function to eventually dominate itself given how I defined it (using strict inequality). Of course if we change the definition slightly using ##f_2(i) \geq f_1(i)## instead of ##f_2(i)>f_1(i)## in the definition, then it changes.
Even at that, don't you think that it's rather pointless to say that a function dominates itself, either eventually or otherwise? A given function will always equal itself. No need to talk about "eventually" or even domination. Granted, if you're talking about two different functions, then ##f_2(x) \ge f_1(x)## does make sense and we can talk about one of them dominating the other.

SSequence
Well the example I gave in post#13 was faulty. I didn't notice it when I wrote the post. That's because what I really had in mind was a function that was positive for all but finite number of values (in which case the explanation I mentioned is OK).

Basically if we take just the set of all "strictly increasing" functions from ##\mathbb{N}## to ##\mathbb{N}## then post#13 is fine. However, somehow I didn't write this assumption. Note that in this case we could also take ##F## as:
##F(x)=g(x)-1##
Where ##-## is to be interpreted as truncated subtraction [that is, returns ##0## if the result is supposed to be negative].

================================================================

If we try to apply post#13 on set of all functions from ##\mathbb{N}## to ##\mathbb{N}## then it is a bit faulty. For example, if we have ##g:\mathbb{N} \rightarrow \mathbb{N}## with ##g(x)=0## for all ##x## then consider the function ##F:\mathbb{N} \rightarrow \mathbb{N}##:
##F(x)=floor \left [\dfrac{ g(x) } {2} \right]##
This also turns out to be ##0## and hence identical to ##g##.

On the other hand, we could use a function ##F## that fluctuates between values ##0## and ##1## periodically. Such a function ##F \neq g## and further ##F## doesn't eventually dominate ##g## [following the exact definition mentioned in post#13]. However, this is quite artificial I think. This is seen if we change the definition slightly to ##f_2(i) \geq f_1(i)## from ##f_2(i) > f_1(i)##, as discussed in last few posts.

================================================================

Now if we were instead considering (all) functions from ##\mathbb{Z}## to ##\mathbb{Z}## or from ##\mathbb{R}## to ##\mathbb{R}## then we could define the function ##F## simply as:
##F(x)=g(x)-1##
and it would work as a suitable counter-example.

Last edited:
Mentor
Well the example I gave in post#13 was faulty. I didn't notice it when I wrote the post. That's because what I really had in mind was a function that was positive for all but finite number of values (in which case the explanation I mentioned is OK).
Two possibilities:
1. Your original "dominates" definition with > -- a function can't be greater than (i.e., dominate) itself.
2. Your later "dominates" definition with ##\ge## -- a function can't be greater than itself, but is certainly equal to itself. Is that useful in any way, though?
I don't see how "positive for all but a finite number of values" makes any difference whatsoever.