Comparing infinite countable sets

[Demystifier]

TL;DR Summary

Is there a sense in which one infinite countable set can be bigger than another?

The uncountable sets [0,1] and [0,2] have the same cardinality $2^{\aleph_0}$. Yet the second set is twice as big as the first set, in the sense of measure theory.

Is there something similar for countable sets, by which we can say that the set of integers is twice as big as the set of odd integers, despite the fact that they have the same cardinality $\aleph_0$?

 

[fresh_42]

You could use the natural (given by their algebraic construction: half group - group - prime field) embedding. $\mathbb{Z}$ contains two copies of $\mathbb{N}$ plus $\{\,0\,\}$ and $\mathbb{Q}$ contains even $\aleph_0$ many copies. It doesn't look well-defined as their bijections are embeddings, too, and this might cause problems though.

 

[pbuk]

It doesn't look well-defined as their bijections are embeddings, too, and this might cause problems though.

Yes, I don't see how this approach could be consistent - as long as you are looking at sets from the perspective of their construction from/division into elements and/or subsets then you haven't got away from the concept of cardinality. You need something that looks from a different perspective in the same way as measure theory does for the reals. Interesting.

 

[fresh_42]

Yes, I don't see how this approach could be consistent

I think it's a bit like the length of coding above $\mathbb{N}, \mathbb{Z}_2, \ldots$

In order to define something analogue to a measure, we have to find content first. Code length is a possible measure of content aka information. However, as long as all countable sets can be seated on the same tape of a TM, this won't be easy either. So what makes $\mathbb{N},\mathbb{Z},\mathbb{Q}$ different? It's only their use, i.e. algebraic structure. So part of this structure has to be encoded in their measure. $\mathbb{N}+\text{ prime field }$ is significantly more information than $\mathbb{N}+\text{ half group }$. Thus we have $|S|<\infty\, , \,(\mathbb{N},+)\, , \,(\mathbb{N},+,-)\, , \,(\mathbb{N},+,-,\cdot ,\backslash)$. Now we run into the next problem: Do we consider the group above $\mathbb{N}$ to be equal to the ring above $\mathbb{N}$ or not?

 

[AplanisTophet]

If we allow for the selection of a real uniformly at random and partition the set of reals that we select from into countably many Vitali sets (requires the axiom of choice), then we can further select which Vitali set and assert the selection points to a natural number belonging to (some infinite subset of) the set of natural numbers. The chances of selecting any given natural number remain undefined as the chances of selecting any given natural cannot be a real number. The Lebesque Measure of a Vitali set is undefined, equivalently.

https://en.wikipedia.org/wiki/Vitali_set

Does that answer your question?

 

[pbuk]

I think it's a bit like the length of coding above $\mathbb{N}, \mathbb{Z}_2, \ldots$

In order to define something analogue to a measure, we have to find content first. Code length is a possible measure of content aka information. However, as long as all countable sets can be seated on the same tape of a TM, this won't be easy either. So what makes $\mathbb{N},\mathbb{Z},\mathbb{Q}$ different? It's only their use, i.e. algebraic structure. So part of this structure has to be encoded in their measure. $\mathbb{N}+\text{ prime field }$ is significantly more information than $\mathbb{N}+\text{ half group }$. Thus we have $|S|<\infty\, , \,(\mathbb{N},+)\, , \,(\mathbb{N},+,-)\, , \,(\mathbb{N},+,-,\cdot ,\backslash)$. Now we run into the next problem: Do we consider the group above $\mathbb{N}$ to be equal to the ring above $\mathbb{N}$ or not?

I think I see where you are going with this, but isn't this something different from what the OP was looking for - how could this help distinguish the set of even numbers from its superset?

PS I think I would say "Do we consider the group over $\mathbb{N}$..." rather than above, although again I understand where you are coming from.

 

[pbuk]

If we allow for the selection of a real uniformly at random and partition the set of reals that we select from into countably many Vitali sets (requires the axiom of choice), then we can further select which Vitali set and assert the selection points to a natural number belonging to (some infinite subset of) the set of natural numbers. The chances of selecting any given natural number remain undefined as the chances of selecting any given natural cannot be a real number. The Lebesque Measure of a Vitali set is undefined, equivalently.

But doesn't that simply say that Lebesque Measure is not going to work, not that there cannot be any quantitative property that works?

 

[AplanisTophet]

But doesn't that simply say that Lebesque Measure is not going to work, not that there cannot be any quantitative property that works?

The archimedean property of the real numbers is what it boils down to. If you want that quantitative property that works, you'll have to work with a set of numbers that doesn't obey the archimedean property. This is because the measure must be less than any real number greater than 0.

 

[fresh_42]

Another idea would be an approach via the dimension term. Although most dimensions are like 1,2, many, infinite, one of the fractal dimensions could apply. There is an interesting list here:https://de.wikipedia.org/wiki/Fraktale_Dimension
Sorry, I found that better than the English version: https://en.wikipedia.org/wiki/Fractal_dimension

These are geometric means, but naturals and integers have the same geometry, which again rises the question what the difference is, if not algebra? It is neither the point set, nor the geometry, nor the topology, nor a difference in some Turing model. What's left is algebra or Chomsky.

 

[pbuk]

Sorry I couldn't read the German - knowledge of the alternative translations of uber is about my limit! Now is probably a good time to admit that algebra was my weakest subject as an undergraduate, and other than the internet I don't have any textbook more specific to this area than my Princeton Companion.

But don't all countable sets have dimension equal to 1?

 

[fresh_42]

I couldn't read the German

Chrome translates it, so I sometimes quote those. The translation isn't perfect but usually ok to the extent of understanding. And the formulas are the same anyway. It was only a list of possible definitions of fractal dimensions.

Yes, I think fractals won't work in our case. I found the Minkowski-Sausage funny. Maybe the similarity dimension is a possible measure. At least it distinguishes various distributions of our countable set. But that is again geometry. I don't believe that a measure can be achieved without any additional structure. My first idea to define something like a natural embedding is as context sensitive as the additional algebraic structures are. But with everything stripped off we just have the common cardinality.

Strassen once improved the matrix exponent in the late 80's. I remember that he used a concept which he called fitted tensors (my translation, so likely inappropriate to google for), but I can't find the paper and don't remember the details. This might be another path, settled in the realm of the Zariski topology. However, Krull dimension doesn't work either. Guess we should ask @Demystifier: What for?

 

[pbuk]

Referring to the original question...

Is there something similar for countable sets, by which we can say that the set of integers is twice as big as the set of odd integers, despite the fact that they have the same cardinality $\aleph_0$?

It seems hard to define an absolute property that would let us do this so that we could compare any two countable sets, but if we stick to a set and it's subsets then we can make progress.

For instance if we assign the value of 1 to the "Demystifier Measure" of ℕ then I think we can arrange formal definitions that will give a value of 0.5 for the Demystifier Measure relative to ℕ (DM_ℕ) of the odd numbers, and 0.25 for the DM_ℕ of the numbers divisible by 4. From the Prime Number Theorem, the set of primes has DM_ℕ = 0, and the set of compound numbers has DM_ℕ = 1. However any set of integers has DM_ℚ = 0.

 

[pbuk]

I found the Minkowski-Sausage funny.

Yes: the Wurstkatastrophe is a great example of German mathematical humour!

Guess we should ask @Demystifier: What for?

I hit 'post reply' on my previous post (before reading yours) when I came to the same conclusion!

 

[WWGD]

Summary:: Is there a sense in which one infinite countable set can be bigger than another?

The uncountable sets [0,1] and [0,2] have the same cardinality $2^{\aleph_0}$. Yet the second set is twice as big as the first set, in the sense of measure theory.

Is there something similar for countable sets, by which we can say that the set of integers is twice as big as the set of odd integers, despite the fact that they have the same cardinality $\aleph_0$?

How about strict containment ( up to translation) as a different measure? [0,1] is strictly-contained in [0,2] ( or, [2,4], after translation, which preserves cardinality). Is this what you are looking for? Of course, strict containment is not persistent up to homeomorphism, in that [0,1] is homeo to [x, y] ; athe standard Cantor , with measure zero, is homeomorphic to "Fat" Cantor of non-zero measure. sets x,y Real. EDIT: It depends ultimately on the properties you would like this new "measurement" to have. Do you want it t o be constant under homeomorphisms, etc?

EDIT2:
Re your original question, I wonder if the naive idea of :

|N|/|2N|= |N|/2|N|= 1/2 can be "rigorized"

 

[PeroK]

Summary:: Is there a sense in which one infinite countable set can be bigger than another?

The uncountable sets [0,1] and [0,2] have the same cardinality $2^{\aleph_0}$. Yet the second set is twice as big as the first set, in the sense of measure theory.

Is there something similar for countable sets, by which we can say that the set of integers is twice as big as the set of odd integers, despite the fact that they have the same cardinality $\aleph_0$?

You could define $\sigma(N) = |S \cap \{1,2 \dots N \}|$ for any subset $S$ of the natural numbers and take the limit of $\sigma(N)$ as $N \rightarrow \infty$.

 

[Demystifier]

You could define $\sigma(N) = |S \cap \{1,2 \dots N \}|$ for any subset $S$ of the natural numbers and take the limit of $\sigma(N)$ as $N \rightarrow \infty$.

I don't see how that helps. If I take $S$ to be the set of odd integers, I get $\sigma(\infty)=\aleph_0$, which does not distinguish from the set of all integers.

 

[Demystifier]

Guess we should ask @Demystifier: What for?

I don't know, I just find surprising that we can distinguish the sizes of continuous sets (by their measure), but not the sizes of discrete (countably infinite) sets.

 

[PeroK]

I don't see how that helps. If I take $S$ to be the set of odd integers, I get $\sigma(\infty)=\aleph_0$, which does not distinguish from the set of all integers.

Sorry, I meant $\frac{\sigma(N)}{N}$.

 

[Jarvis323]

I don't know, I just find surprising that we can distinguish the sizes of continuous sets (by their measure), but not the sizes of discrete (countably infinite) sets.

Maybe this is kind of unrelated, but there are some other interesting/surprising things about the reals vs the natural numbers:

We talked on Thursday about computability theory. We saw how certain problems are uncomputable -- like, given a statement about positive integers, is it true or false? (If we could solve that, then we could solve the halting problem, which we already know is impossible.)

But now let's suppose we're given a statement about real numbers -- for example,

• For all real x,y, (x+y)2=x2+2xy+y2

-- and we want to know if it's true or false. In this case, it turns out that there is a decision procedure -- this was proved by Tarski in the 1930's, at least when the statement only involves addition, multiplication, comparisons, the constants 0 and 1, and universal and existential quantifiers (no exponentials or trig functions).

Intuitively, if all our variables range over real numbers instead of integers, then everything is forced to be smooth and continuous, and there's no way to build up Gödel sentences like "this sentence can't be proved."

(If we throw in the exponential function, then apparently there's still no way to encode Gödel sentences, modulo an unsolved problem in analysis. But if we throw in the exponential function and switch from real numbers to complex numbers, then we're again able to encode Gödel sentences -- and the theory goes back to being undecidable! Can you guess why? Well, once we have complex numbers, we can force a number n to be an integer, by saying that we want e2πin to equal 1. So we're then back to where we were with integers.)

https://www.scottaaronson.com/democritus/lec5.html

https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers

And another interesting thing is that discontinuous dynamical systems can be chaotic with only 1 dimension, while continuous dynamical systems require at least 3 dimensions.

Sorry, I meant $\frac{\sigma(N)}{N}$.

Building on this, how about begin by assuming the elements of each have a common encoding as binary strings, $$(\forall x \in A, y \in B)(x=y \iff <x>=<y>)$$, then order them, shift each to start at 1 by subtracting the smallest element and add 1, $$S'=\{x -\min\limits_{s \in S} + 1 | x \in S\}$$ and then compare based on the properties/complexities of $$f(n)=\frac{s'_n}{n+1}$$.

But still, it should depend on your choice of encoding? So maybe you also need to consider some sense of minimal encoding which preserves the meaning?

If you try to do something like this,

$$\text{Let } c \text{ encode the elements of } A \text{ and } B \text{ such that }(\forall \text{ other encodings } d) m( c(A \cap B) ) \leq m( d(A \cap B) ) \text{ where } m : S \longrightarrow \mathbb R, |S|=|\mathbb{N}|, S \subseteq{\mathbb{N}}, c( A \cap B ) \text{ is the set of strings encoding the elements of } A \cap B$$

Then you run into the issue that you still need to compare encodings in some way. Maybe you need to apply information theory or Kolmogorov complexity? Which is where what I can say about it ends I guess.

 

[Demystifier]

Sorry, I meant $\frac{\sigma(N)}{N}$.

That seems to be a partial solution of my problem. It works for natural numbers and their subsets. With a trivial modification it can work also for integers (positive and negative whole numbers). But it is not so trivial to modify it to work also for rational numbers. Rational numbers can be viewed as pairs of integer numbers, so I guess their "measure" should be viewed as a discrete version of an "area".

 

[pbuk]

I think it would better to map the rationals (or any other countable set) to the non-negative integers using some ordering, much easier to take the limit then.

 

[fresh_42]

I think it would better to map the rationals (or any other countable set) to the non-negative integers using some ordering, much easier to take the limit then.

At least I would require that the according diagram commutes. Otherwise we are again in the context sensitive case.

 

[Stephen Tashi]

Is there something similar for countable sets, by which we can say that the set of integers is twice as big as the set of odd integers, despite the fact that they have the same cardinality $\aleph_0$?

Following the typical approach to questions about statistics, we could propose some answers before the question is defined and then try to define the question. After all, people answer questions like "What is the probability that a randomly selected integer is odd?" and "Are the digits of pi evenly distributed?"

I don't know, I just find surprising that we can distinguish the sizes of continuous sets (by their measure), but not the sizes of discrete (countably infinite) sets.

A set like the real numbers is "more than just a set". It has operations and an order. Using ordinary measure, we get the same measure for certain sets of real numbers as for some of their proper subsets. So the surprising aspects of the situation need to be better defined.