Relative sizes of sets of integers and rationals revisited - how do I make sense of this?

Question

I already asked if there are more rationals than integers here...

Are there more rational numbers than integers?

However, there is one particular argument that I didn't give before which I still find compelling...

Every integer is also a rational. There exist (many) rationals that are not integers. Therefore there are more rationals than integers.

Obviously, in a sense, I am simply choosing one particular bijection, so by the definition of set cardinality this argument is irrelevant. But it's still a compelling argument for "size" because it's based on a trivial/identity bijection.

EDIT please note that the above paragraph indicates that I know about set cardinality and how it is defined, and accept it as a valid "size" definition, but am asking here about something else.

To put it another way, the set of integers is a proper subset of the set of rationals. It seems strange to claim that the two sets are equal in size when one is a proper subset of the other.

Is there, for example, some alternative named "size" definition consistent with the partial ordering given by the is-a-proper-subset-of operator?

EDIT clearly it is reasonable to define such a partial order and evaluate it. And while I've use geometric analogies, clearly this is pure set theory - it depends only on the relevant sets sharing members, not on what the sets represent.

Helpful answers might include a name (if one exists), perhaps for some abstraction that is consistent with this partial order but defined in cases where the partial order is not. Even an answer like "yes, that's valid, but it isn't named and doesn't lead to any interesting results" may well be correct - but it doesn't make the idea unreasonable.

Sorry if some of my comments aren't appropriate, but this is pretty frustrating. As I said, it feels like I'm violating some kind of taboo.

---

EDIT - I was browsing through random stuff when I was reminded this was here, and that I actually ran into an example where "size" clearly can't mean "cardinality" fairly recently (actually a very long time ago and many times since, but I didn't notice the connection until recently).

The example relates to closures of sets. Please forgive any wrong terminology, but if I have a seed set of {0} and an operation $f x = x+2$, the closure of that set WRT that operation is the "smallest" set that is closed WRT that operation, meaning that for any member $x$ of the set, $x+2$ must also be a member. So obviously the closure is {0, 2, 4, 6, 8, ...} - the even non-negative integers.

However, the cardinality of the set of even non-negative integers is equal to the cardinality of the set of all integers, or even all rationals. So if "smallest" means "least cardinality", the closure isn't well-defined - the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...} is no larger than the set {0, 2, 4, 6, 8, ...}.

Therefore, the meaning of "smallest" WRT set closures refers to some measure of size other than cardinality.

I'm not adding this as a late answer because it's already covered by the answers below - it's just a particular example that makes sense to me.

---

Another addition - while skimming the first chapter of a topology textbook in a library some time ago, IIRC I spotted a definition of the set closure which did not use the word "smallest", and made no direct reference to "size". That led me to think maybe the common "definition" of closures I'm familiar with is just a stopgap for those of us who aren't ready for a formally precise definition.

However, while searching for another source, I instead found this answer to a topology question that uses the word "smallest" in its definition of closure (and "largest" in its "dual definition of interior"). And then I found this answer which describes a concept of size based on partial ordering of topological embeddings. I think that's another example to add to those in answers below.

Answer 1

Of course, there are other notions of size. In particular, your notion of "a partial order based on inclusion of sets" is a very fruitful concept which has been used frequently. As a quick example, there is a technique in mathematical logic/set theory called "forcing" which is used to show that certain mathematical statements are unprovable. Forcing often starts with a partial ordered set where the order is given by inclusion of subsets.

In terms of the everyday world interpretation of the word "size", there are (at least) two problems with the using the partial order given by inclusion of subsets. The first is, as you said, a partial order: there are two sets which cannot be compared, i.e., there are 2 sets where you cannot say one is bigger than the other. The second is that two things will have the same size precisely when the two things are absolutely the same. There is no notion of different things which happen to be the same size - that can't happen in this partial order.

For example, lets say we're looking at subsets of the integers. You pull out your favorite subset: all the odd integers and I pull out mine: all the even integers. Using the partial order definition of size, these two sets are incomparable. Mine is neither bigger than, smaller than, or the same size as yours. To contrast that, using the cardinality notion of size, they have the same size. This is evidenced by simply taking everything in your set and adding 1 to it to get everything in my set. For an even more absurd example, consider the set {0} and the set {1}. One would expect these two sets to have the same notion of "size" (for any notion of "size"!), but using the partial order notion, one cannot compare these two sets.

By contrast, cardinality (or, the way I used "size" in the previous link) is defined on ALL sets (assuming the axiom of choice), even those which a priori have no subset relation. And there are many examples of sets which have the same cardinality, but which are not equal. (For example, the set of evens and odds, or the sets {0} and {1}).

Answer 2

Purely set theoretically, cardinality is the right way to think of the "size" of a set. A bijection $f:A\to B$ simply renames each element $x$ in $A$ to $f(x)$, and one reasonably wants the size of a set not to depend on the names given to its elements.

There are other notions of size if you let your sets have more structure. The natural density (if it exists) of a subset $A$ of the natural numbers $\mathbb N$ can be thought as the relative size of $A$ to $\mathbb N$. The natural density of the even numbers is $1/2$, for example, so one might say there are half as many even natural numbers as there are natural numbers altogether. If $A$ and $B$ have natural densities $d(A)$ and $d(B)$, and $A\subseteq B\subseteq \mathbb N$, then $d(A)\leq d(B)$. Not all subsets of $\mathbb N$ have a natural density though, so in particular we can't compare the "sizes" of all sets of naturals.

Another possibility is considering the (measurable) subsets of a set $X$ equipped with a measure $m$. If $A$ and $B$ are measurable subsets of $X$, and $A\subseteq B$, then $m(A)\leq m(B)$. For example, we can use the Lebesgue measure $m$ on $X=\mathbb R$, which gives measure 1 to the interval $[0,1]$ and measure $1/2$ to the interval $[0,1/2]$. But again, not all subsets of $X$ are measurable, so not all sets can be compared size-wise this way.

Note that in both the approaches above, we can only compare the size of a set relative to some other fixed set ($\mathbb N$ or $X$). Any finite set and the set of rational numbers both have measure 0 with respect to the Lebesgue measure on $\mathbb R$, for example, so we would be forced to admit them to have the same size in this setting.

Answer 3

Is there, for example, some alternative named "size" definition consistent with the partial ordering given by the is-a-proper-subset-of operator?

There is such an alternative. Maybe two, depending on how you count. Some references:

• Sets and Their Sizes (my dissertation, 1981) at http://arxiv.org/abs/math/0106100. Offers a general theory of set size that includes a proper-subset principle, trichotomy, and, in fact, all statements true of sizes of finite sets (in a restricted language) and constructs a model over sets of natural numbers that respects the ordering by asymptotic density.
• An article, Measuring the size of infinite collections of natural numbers: Was Cantor's theory of infinite number inevitable? by Paolo Mancosu that provides a good historical perspective and mentions more recent - and much more extensive - work on developing such a theory by V. Benci, M. Di Nasso, and M. Forti. Available at: http://philpapers.org/rec/MANMTS.
• A critical view of such theories, Set Size and the Part Whole Principle, by Matthew Parker, at philpapers.org as PARSSA-3. (It seems I've run out of link power!)

Fred M. Katz

Answer 4

Actually to elaborate a bit more on:

It seems strange to claim that the two sets are equal in size

Let us consider binary representations, every natural number can be written in binary. For example $13 = 1101_2$ but we can define two functions $N(q) = 1+q$, $D(q) = 1/(1+1/q)$ and interpret a binary sequence as a composition of these functions applied to 1, for example $1101_{\mathbb{Q}} = (N \circ N \circ D \circ N) 1 = 8/3$ and by Euclids algorithm this defines every (positive) rational number exactly once.

If all they are, are different interpretations of binary sequences, it would be weird not to claim have equal size!

Answer 5

I've found Hilbert's Hotel a useful example to understand (or fail to understand, but on a higher level), how much "infinity" really is, and how much the naive view on things fails when confronted with infinity.

It deals with the easier case, comparing the integers with even integers, but maybe it will help. =)

Edit: The wikipedia article linked is not great, but google will surely turn out more useful.

Answer 6

It may seem strange that the set of integers is a proper subset of the set of rationals, but this is exactly the definition of an infinite set.

Maybe it could be easier for you to see that there cannot be a size-based definition when talking about infinite set if you consider this: with two finite sets, in whichever way you choose elements to be removed one at a time from both sets at one, you'll end up with the larger set having still some element while the smaller remained empty. This does not happen with infinite sets; even if you find a way to remove all elements (for example, remove he first at T=0, the second a T=1/2, the third at T=3/4, and so on) you may always choose an ordering in which the "larger" set becomes empty, and the "smaller" has still some element.

Answer 7

You could consider the order relation generated by the operation of inclusion between sets. It is a partial order, and it is, in some way, related to the "size" of the sets.

Answer 8

Is there, for example, some alternative named "size" definition consistent with the partial ordering given by the is-a-proper-subset-of operator?

I think it is important to keep in mind the context you are looking at something when you want to talk about sizes. In a topological or geometric context, if $A \subset B$ then we may want to think of $A$ as smaller than $B$. However, when talking about cardinality of a set, we need to think of the structure of the set as a set (and not part of another set like the real numbers or in its geometric/topological context). In this way, the only reasonable definition for sets to be the same (isomorphic) is if there is a bijection between them. Therefore if we want to assign some cardinality to something as a set, it should be the same for all sets that are in bijection with it.

Answer 9

Every integer is also a rational. There exist (many) rationals that are not integers. Therefore there are more rationals than integers.

Here you are citing the Eucid's principle ("the whole is greater than a part"), which is opposed to the Cantor-Hume bijection principle.

Is there, for example, some alternative named "size" definition consistent with the partial ordering given by the is-a-proper-subset-of operator?

Yes, one can introduce a measure based on Euclid's principle and it is called "numerosity".

There is a clear way to express numerosities of sequences via $\omega$, which is the germ of the identity function at infinity or half the numerosity of $\mathbb{Z}$. It also can be considered a surreal number. This measure is more accurate than asymptotic density, because it gives the exact value.

Suppose you have a strictly increasing sequence $a_k\ge0$, where $k\in\mathbb{Z}, k\ge0$.

To find the numerosity, you have to

1. Perform operator $D\Delta^{-1}$ on your sequence, where $\Delta^{-1}$ is anti-difference (indefinite sum). This is quite sandard operator in umbral calculus.
2. Find inverse function of the resulting expression.

In other words, apply to your sequence the operator $N(a_k)=\left(D\Delta^{-1}a_k\right)^{[-1]}(\omega)$, where $f^{[-1]}$ is the inverse function.

The following Wolfram Language code does the thing:

a[k] := k^2
SolveValues[D[Sum[a[k], k], k] == \[Omega], k] /. C[1] -> 0 //
   FullSimplify // Expand

So, some examples:

• $N(2k)=\frac{\omega }{2}+\frac{1}{2}$ (we allow $k$ to be zero, but if you want non-zero naturals, subtract $1$ from this)

• $N(k+5)=\omega -\frac{9}{2}$

• $N(k^2)=\frac{1}{2}+\frac{1}{6} \sqrt{36 \omega +3}$ (again, subtract $1$ if you do not count zero)

• $N(1/3+k+k^2)=\sqrt{\omega}$

• $N(k^4)=\frac{1}{30} \sqrt{30 \sqrt{900 \omega +30}+225}+\frac{1}{2}$

• $N(7^k)=\log_7 \left(\frac{6 \omega }{\ln (7)}\right)$

So, yes, the numerosity of naturals is greater than the numerosity of perfect squares, and we even know exactly, by how much.

Regarding the numerosities of dense sets, like $\mathbb{Q}$, the question is more complicated.