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

http://math.stackexchange.com/questions/1311/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.

-
In the range 1-100 there are roughly 100 integers, but there are an infinity of rationals. –  anon Aug 2 '10 at 13:16
It's not taboo, but this question is a philosophical question about the meanings of 'size'. So it is more philosophy than mathematics. –  anon Aug 2 '10 at 14:46
@muad - I'm basically specifying an informal axiom and asking how to formalise it, how to fit it into a larger axiomatic system, and whether interesting conclusions will result. One possible formalism - the partial order - is explicit. I'm certain this is mathematics. It may be philosophy too, but I've often seen terms similar to "mathematical philosophy of ...". –  Steve314 Aug 2 '10 at 15:54
The even integers are a subset of the integers, but they also have the same size. –  Qiaochu Yuan Aug 2 '10 at 17:20

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

-
The logic for relative cardinality of infinite sets is obviously a way of extending the more powerful counting approach to infinite sets. It's completely defined, but it doesn't define everything (which of two unequal-cardinality infinite sets is the larger?). I could argue the same - that partial ordering is consistent with counting, yet allows me to consider infinite sets. While it isn't complete, it can allow me to define some things that cardinality cannot. Still, big thanks for the "forcing" reference, and acceptance for by far the most useful answer here. –  Steve314 Aug 2 '10 at 15:43
Just to add, I don't know of a name of the concept you're considering, but I do know that it is VERY useful. It's just not very useful interpretation of "size". –  Jason DeVito Aug 2 '10 at 15:47
@Steve314 I'm not sure what you mean by "... doesn't define everything (which of two unequal cardinality infinite sets is the larger?)" This IS defined with cardinality. Assuming the axiom of choice, one is always bigger than the other, or they have the same size. Also, the point of the {0} {1} example is that the partial order is NOT consistent with counting for finite things. –  Jason DeVito Aug 2 '10 at 15:49
@Jason - Maybe I'm wrong, but I don't see how the non-existence of a bijection proves one set or the other larger. As for {0} {1}, the partial order isn't defined in that case. A common meaning of being "consistent" implies "where both are defined" - maybe there's an overriding definition in math, but this is probably just one of the frustrations of mixing informality with formality. –  Steve314 Aug 2 '10 at 16:10
@Steve314. It is a set theoretical fact that (again, assuming the axiom of choice), given two sets A and B, there is always either a 1-1 function f:A->B or a 1-1 function f:B->A. If the first case holds, the size of A is less than or equal to that of B. Likewise, if the second holds, the size of B is less than or equal to the size of A. If BOTH cases hold, then the Cantor-Schroeder-Bernstein theorem implies that there is a bijection g:A->B, so both have the same size. In short, there is more to cardinality than bijections, and in this larger framework, one can tell sizes of unequal sizes. –  Jason DeVito Aug 2 '10 at 16:16

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!

-
You are still creating bijections based on applying functions. Every integer is a rational. Even with different representations such as "1" vs. "1/1", they are only different representations of the same number. Your argument looks like just another bijection - valid for set cardinality where the existence of any bijection is sufficient, but it still ignores the question I'm asking. Put it another way - two different-sized squares are still different sizes, though you can represent both with the same drawing (ignoring scale). I can ask about "size" in more senses than just set cardinality. –  Steve314 Aug 2 '10 at 13:51
The point I am making here is that it is about point of view. You see 1 (integer) and 1/1 (rational) as the same because you are thinking about them as rings. Whereas I see 13 and 8/3 as the same because they have the same binary encoding. That is why in your view there are more rationals and in my view there are equally many. Someone else could even come along with a new viewpoint which to her, makes it seem like there are more integers than rationals. –  anon Aug 2 '10 at 14:54

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.

-
In many contexts, it is possible to remove infinite subsets in one go. I can remove an infinite set of points from a surface using a pair of scissors, for instance. That infinite set of points might easily be the region of a Venn diagram representing the set of integers. That cut-out region still has "size". The point here is that "size" is ambiguous, and the question explicitly states that "by the definition of set cardinality this argument is irrelevant". –  Steve314 Aug 2 '10 at 13:42
how could you be sure you removed the same amount? your reasoning is circular. –  mau Aug 2 '10 at 13:55
besides, if your point is just "we cannot talk about size", the answer is "mathematicians don't talk about size of a set, but of cardinality of a set", so there is no confusion at all. –  mau Aug 2 '10 at 13:58
No - my point is that mathematicians have many things that map roughly to "size". Are you arguing that it is impossible to form a partial-ordering of sets based on the is-a-proper-subset-of operator, or that it is impossible to name that partial order, or that it is impossible to think of it as indicating relative size, or what? –  Steve314 Aug 2 '10 at 14:03
I just argue that the notion of partial ordering has nothing to do with the definition of cardinality. When you talk of cardinality, you are labeling the objects in a set, changing thus their name. If you allow this, you may relabel integers and rationals so that the relabeled rationals are a subset of the relabeled integers. –  mau Aug 2 '10 at 15:09

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.

-
I'm already familiar, and it seems relevant to my point. There is more than one possible meaning of "size" WRT a set. One formally defined one is cardinality. Another based on partial-ordering based on the is-a-proper-subset-of operator would (when defined) be consistent with cardinality for finite sets, but not for infinite sets - but is it named and, if so, what is it called? –  Steve314 Aug 2 '10 at 13:56
@Steve314: I don't think it is named. While you can surely (partially) order sets by the "proper subset" operator, I don't think that this is a good way to indicate "size" of a set. You could not decide if $\{1,2,3\}$ has the same size as $\{2,3,4\}$ that way. –  Jens Aug 2 '10 at 14:52
that's true, but by the definition of cardinality, when two infinite sets don't have equal cardinality, can you decide which is larger? Each approach diverges from the "size" intuition in a different way. Also, handling finite set sizes by counting is still a possible way (consistent with the partial order) to define otherwise undefined cases. This is basically what cardinality does anyway - choose an argument consistent with counting for the finite case that extends to the infinite case even though it can't handle everything that the finite-case logic could. –  Steve314 Aug 2 '10 at 15:23
@Steve314: That's easy. One set A is larger or equal than a set B if there is a bijective mapping from a subset of A to B. –  Jens Aug 3 '10 at 6:11

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.

-
Thankyou - I was beginning to wonder if I'd asked a taboo question. But still - I said as much myself in the question, but is there a name for this etc. –  Steve314 Aug 2 '10 at 14:17

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.

-
Is there a rule that states "the only definition of size that shall ever be tolerated for sets is cardinality"? Quite clearly, every integer is a rational, so it is possible to formalise "size" in ways that aren't possible for arbitrary sets. Normally, mathematics seems less picky - not all algebras are commutative, for instance, but no-one says "therefore you shall not discuss non-commutative algebras". –  Steve314 Aug 2 '10 at 14:15
Certainly you can define size in whatever consistent way you want. There is nothing stopping you from saying that $A$ is smaller than $B$ if $A \subset B$. But the point is that you won't be able to compare sets that have different objects. But if you want to think of sets purely as sets, then it really shouldn't matter what the objects are (this is the idea of calling sets isomorphic if they are in bijection). –  Eric O. Korman Aug 2 '10 at 14:21

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.

-
Sets can have elements in common. That's not the same as having element "names" in common. The number 1 is the number one is the number 1.0 irrespective of how it is represented. It isn't the same as saying "I can draw arrows between the members of these sets". It's not just about numbers, either. The set of shapes is infinite, the set of convex shapes is infinite, every convex shape is a shape yet there are shapes that aren't convex. In cardinality terms the sets are equal - but is it unreasonable to say "there are more shapes than convex shapes"? –  Steve314 Aug 2 '10 at 15:31
It's common to say that the set of convex shapes is larger than the set of all shapes, and it is understood that by this one means precisely that the first set is a subset of the other. This compares two sets relative to eachother, but it is not a useful measure of their individual, intrinsic sizes. Anyway, I gave you two notions of "size" which do respect the subset relation: if A is a subset of B, then A is smaller than or equally large as B. –  Samuel Aug 2 '10 at 16:19
The concept of "natural density" seems like a perfect answer to the question. Can it be extended to other base sets? For example, can we define "rational density"? If so, then the rational numbers obviously have a rational density of 1, but the integers have a rational density of 0, which is compatible with intuition. –  Erel Segal Halevi Dec 15 '13 at 10:58
@ErelSegalHalevi: I don't know. It's a good question; you should ask it on math.SE. Of course you could pick a bijection $f$ between $\mathbb Q$ and $\mathbb N$ and then just use the natural density definition, but that is not very satisfying since there is no canonical such bijection $f$. –  Samuel Dec 15 '13 at 12:32

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

-