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

[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.

 

[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, ... }.

 

[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

 

[topsquark]

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

 

[martinbn]

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.

 

[mathman]

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

 

[phinds]

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.

 

[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.

 

[mathman]

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.

 

[jbriggs444]

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.

 

[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$.

 

[nuuskur]

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).

 

[TeethWhitener]

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.

 

[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.

 

[jbriggs444]

(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.

 

[Mark44]

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.

 

[Mark44]

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.

 

[Mark44]

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.

 

[.Scott]

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?

This thread has offered the primes and exponential series as examples of aleph null sets with zero density. In both those cases, ordering the set and then "dealing out" the elements into two new sets - yields two sets of size aleph null and density zero.

Since that "dealing out" process can be done with any countable set (aleph null included), the answer is "No".