How do mathematicians reconcile that an infinite set does not have to be larger than its proper subset?

If we imagine an infinite number of fractions and, within them, an infinite number of integers, doesn't the former constitute a "larger" infinite set of numbers?

This has always been paradoxical for me. I would like to know how (or if) mathematicians reconciled this.

• I made an edit which you may roll back or continue editing. You can see the versions by clicking on the "edited" link above. Regarding the question, there would be no fractions within the set of integers unless one considered fractions such as 2/1 or 5/1. – Frank Hubeny Aug 16 '18 at 2:51
• Well, the set of all odd integers is a subset of the set of all integers. But they have equal cardinality. – rus9384 Aug 16 '18 at 2:51
• Notice that the rationals (fractions) are the superset here, not the subset. You are thinking of them as "inside" the integers because they're between them. But the integers are a proper subset of the rationals. That said, they have the same cardinality, meaning that there's (surprisingly) a function that corresponds each integer to a different rational and each rational back to its corresponding integer. This is counterintuitive. There's a nice proof here. homeschoolmath.net/teaching/rational-numbers-countable.php – user4894 Aug 16 '18 at 3:19
• Why would a mathematician have to reconcile this? There's proofs on the subject, and it's clear that the idea that a proper subset of a set is smaller than the set only works for finite sets. There are other fields in which normal assumptions don't hold in different circumstances. Electrons spin, for example, but not on any defined axis. – David Thornley Aug 17 '18 at 21:34

There is a long controversy as to what should count as the "size" of an infinite set, and there provably does not exist a notion that satisfies both the bijectivity principle, a.k.a. Hume's principle (bijective sets have equal size), and the part-whole principle (whole is greater than its part). So any notion of size for infinities will be counterintuitive in one way or the other. The history of philosophical debates surrounding this clash of intuitions is described by Mancosu in Measuring the size of infinite collections of natural numbers: was Cantor's theory of infinite number inevitable? (his answer is no).

Modern mathematics adopted the notion of cardinality that satisfies the bijectivity principle, but its downside are the "paradoxes of infinity" like the Hilbert's hotel that can accomodate any 10 (or 100, or 100000) additional guests at any time. It has rooms numbered by positive integers and to free up rooms 1 to 10 (or 100, or 100000) the manager needs only to move all existing guests from room n to room n+10 (n+100, n+100000).

The part-whole principle can be accomodated, but only if one gives up the bijectivity principle. One version was introduced by Katz, who shared the OP sentiment, in Sets and their Sizes:

"Cantor’s theory of cardinality violates common sense. It says, for example, that all infinite sets of integers are the same size. This thesis criticizes the arguments for Cantor’s theory and presents an alternative. The alternative is based on a general theory, CS (for Class Size)... Because the language of CS is restricted... the notion of one-one correspondence cannot be expressed in this language, so Cantor’s definition of similarity will not be in CS, even though it is true for all finite sets."

Another alternative was introduced by Benci in 1995, and is called numerosity, "an Aristotelian notion of size", as he put it. Numerosity is always smaller for proper subsets, but... it depends on how a subset is given, it "counts" labeled subsets, not just subsets. So as long as a bijection changes the labeling too much it does not count. Bijective sets can, and do, have different numerosities. Mancosu uses numerosities to give an interesting counter to Gödel's argument that adoption of Cantor's cardinality was "inevitable":

"Gödel’s reflection aims at showing that in generalizing the notion of number from the finite to the infinite one inevitable ends up with the Cantorian notion of cardinal number. The key step in the argument is the premise and the theory of numerosities can help us see that the premise already contains in itself the Cantorian solution. In fact, the premise takes as evident the request that “the number of objects belonging to some class does not change if, leaving the objects the same, one changes in any way whatsoever their properties or mutual relations (e.g., their colors or their distribution in space).” While the premise constitutes no problem when dealing with finite sets, one might question its acceptability in the realm of the infinite.

Indeed, in the theory of numerosities we cannot grant the premise when it comes to infinite sets. For, while it is possible to abstract from the nature of the objects themselves there is one type of relation that affects the counting, namely the way in which the elements are grouped. Such grouping makes no difference in the realm of finite sets of integers. But when we move to infinite sets a rearrangement of the grouping will in general affect the approximating functions and thus the numerosity of the set. Someone committed to the counting embodied in the theory of numerosities might thus reasonably resist accepting the premise on which Gödel bases his argument and thus also resist the claim that the generalization of number from the finite to the infinite must perforce end up with the notion of cardinal number."

• @present Why not? Cardinality makes for a technically superior theory for currently prevailing applications. It is the same reason that the classical logic is adopted over the intuitionistic one, the Zermelo set theory and Grothendieck's algebraic geometry formalism over alternatives, and so on. – Conifold Aug 16 '18 at 20:13
• nice answer (+1). but isnt bijection forced on us if we want an isomorphism in the category of sets? that seems like a pretty strong recommendation coming from outside set theory. or do these other notions give rise to a different SET? – Tim kinsella Aug 16 '18 at 22:13
• @Timkinsella I am not sure about the "outside". Category theory was built to clean up the system of Bourbaki "structures" produced within the standard set theory, it is not surprising that its notions are suitable to the task. But even if, the idea that size should be invariant under isomorphism is just a rephrasing of the Hume's principle, its acceptance can not be an argument for accepting it, as Mancosu pointed out. – Conifold Aug 16 '18 at 22:28
• yeah i had forgotten that uniqueness fails if you only require finitely additive. Interestingly that's not true for n \geq 3 though (though you need to require translation invariance also) cambridge.org/core/journals/… – Tim kinsella Aug 16 '18 at 23:31
• rotation invariance (not translation) – Tim kinsella Aug 17 '18 at 0:08

There are ways to think about this that do make it intuitive. Suppose I have 5 objects, each with a different name. Now, my boss tells me that she doesn't like those names and wants me to use different names for the objects, from a set of names that she likes. If her set contains at least 5 names, then there is no problem; I can map the original names to new names so that no two objects have the same name. On the other hand, if her set contains only 4 names, then I'm in trouble; I will not be able to keep track of the objects without confusion. This is in a sense what it means that 4 is less than 5.

But then, suppose that I'm keeping track of objects that are naturally labeled by rational numbers. Again my boss complains, and tells me that I'm only allowed to use integers to refer to these objects because she doesn't like fractions. Am I in trouble? No! I can map each rational to its own separate integer so that I can keep track without any confusion. This is the sense in which the set of rationals is no larger than that of the integers, and in this way the "paradoxes of infinity" actually reflect a very real and even practically useful property of infinity.

In general, we would also like to compare sets neither of which is a subset of the other. For example, consider the set of rational numbers p/q such p and q are both prime numbers. Is it smaller or larger than the set of integers? The correspondence approach allows us to answer this question (they are the same size).

Mathematicians say that if there is a one to one and onto function from one set to another, they are the same size which makes sense on finite sets. For example, if you have 5 apples and 5 oranges then you can assign every orange an apple and there will be no leftovers.

Mathematicians do this on infinite sets, too. As an easy example, consider the number of positive integers and even integers. If you map every even integer, 2n, to integer, n, it will be one to one and onto. Therefore, they are the same size.

• I made some edits. You may roll these back or continue editing. You can see the versions by clicking on the "edited" link above. – Frank Hubeny Aug 17 '18 at 3:19

The thing is, the actual mathematical statement in question is:

An infinite set can have the same cardinality as one of its proper subsets

Cardinality is a technical notion given by a precise mathematical definition, and one acclimates to this fact as you would any other technical mathematical notion: you study examples and solve exercises relating to the various features of the notion and how they can be used to describe things and solve problems.

The notion of size only has any bearing insofar as many people have the intuition that cardinality is a generalization of certain aspects of the notion of size. Furthermore, many aspects of calculating with and reasoning about cardinal numbers can be inspired by analogous calculations and reasoning about size of finite sets.

As with any analogy, comparing cardinality to size is imperfect; some aspects of size don't carry over to cardinality, and vice versa. The intention of a great many examples of how cardinality behaves is meant to help the reader understand what aspects don't carry across the analogy.

In particular, you're supposed to learn to avoid applying to the notion of cardinality that part of your intuition that would insist that a proper subset have smaller size than the whole.

There seem to be a handful of people who seem to get too fixated on the aspects of size that don't carry over, and that they simply can't take advantage of this analogy. If you are one of these people, then if you want to understand the notion of cardinality you have to ignore any heuristic size-based intuitions that people give.

You can learn just from doing studying and exercises via the formal properties until you learn how to apply them to solve problems.

You may also have some fortune by finding other similar concepts that might be more intuitive to you. For example, cardinality can also be viewed as a measure of complexity, and one might draw intuition about cardinality from analogous features of computability theory.

It might help to understand that set A is said to be smaller than set B if and only if it is impossible to map A onto every element of B, i.e. there exists no surjection mapping A to B. This definition is independent of whether these are finite or infinite sets.

If A is not smaller than B, and B is not smaller than A, then we can say that A and B are equal in size, i.e. there must exist a bijection from A to B (not a trivial proof).