# Set Theory where Some Countably Infinite Sets are Smaller than Others? [duplicate]

In a recent question people have talked about a smallest set S in terms of inclusion/subsets instead of cardinality. S is a countably infinite set (or at least potentially could be). The (classical) set theory I'm familiar with though has all countably infinite sets as having the same size. But, for the notion of a set they reference, it seems that some countably infinite sets will have a greater size than others. To give just one example of what such a set theory would entail, that would enable us to say that the size of the set of even numbers is less than the size of the set of natural numbers.

What sort of set theory is that? Where might one read about such a set theory?

• This has nothing to do with set theory. – Andrés E. Caicedo Dec 19 '17 at 1:13

This is not some exotic set theory: it's just using inclusion as a partial order on some family of sets.

As others have said - but let me elaborate - you're not changing the set theory, you're changing the informal language we use to describe various things. If you want to refer to proper inclusion as "smaller than," and refer to the usual notion as "of smaller cardinality" (say), you can do that. And indeed we do sometimes use the informal phrase "smaller than" to describe something other than cardinality.

The reason "smaller than" is pretty much universally understood within set theory as referring to cardinality is simply a social convention. I think it's the "right" convention, but there's ultimately nothing really mathematical about it, it's just a choice of language.

Now there are various genuine changes we can make to set theory to add more "nuance" to cardinality notions. For example, we can weaken the axioms of ZFC (specifically, separation/replacement) so that relations don't behave the way we expect. An important example of this is Kripke-Platek set theory. The structure $L_{\omega_1^{CK}}$ is a model of KP, but it has the odd property that there is a definable injection from the class $\omega_1^{CK}$ (indeed, from the whole structure) to $\omega$. Of course, the image of this definable injection isn't a set, but still there is a weak sense in which $L_{\omega_1^{CK}}$ sees itself to be countable. However, at the same time there is no surjection from $\omega$ to $\omega_1^{CK}$ in $L_{\omega_1^{CK}}$, so there is also a sense in which $L_{\omega_1^{CK}}$ doesn't think $\omega_1^{CK}$ is countable.

This is an important phenomenon: $\omega$ is clearly the least such ordinal, and so we say that $\omega$ is the $\Sigma_1$-projectum of $\omega_1^{CK}$, denoted $(\omega_1^{CK})^*$ or $\sigma1p\omega_1^{CK}$ (I hate the latter notation, but it is fairly common). There are also of course higher projecta, and we also care about definable cofinalities (in lieu of full replacement, a model of KP can notice that its version of $Ord$ is singular); these invariants prove important when doing admissible computability theory (specifically, the development of priority arguments in $\alpha$-recursion theory; see Sacks' book "Higher recursion theory").

(It's important to note, though, that this nuance re: cardinality is about complexity of definability, not proper containment.)

Assuming you mean "A is less than B" , means "A is a subset of B but not equal to B" then it is NOT true in classical set theory that "all countably infinite sets have the same size". "The set of all positive integers, x, such that x is a multiple of 3" contains "the set of all positive integers, x, such that x is a multiple of 6" but they both are "countably infinite".

• " "The set of all positive integers, x, such that x is a multiple of 3" contains "the set of all positive integers, x, such that x is a multiple of 3"" Didn't you just write the same thing twice? A bijection is easy for two supposed sets which don't differ in at least one element. – Doug Spoonwood Dec 19 '17 at 1:22
• @Doug replace their botched example by any two countably infinite sets such that one properly contains the other and they're making the same good point everyone else is making. (I think.) – spaceisdarkgreen Dec 19 '17 at 1:35
• @spaceisdarkgreen My understanding is that every countably infinite set could get paired off with the natural numbers N. Given such a bijection, if set A contains set B, then we have a bijection between N and A, and one between B and N. Since bijection is transitive, it follows that there exists a bijection between B and A. And that implies both A and B as countably infinite and having the same cardinality, doesn't it? – Doug Spoonwood Dec 19 '17 at 1:51
• @Doug they are eqiunumerous by the usual definition and one is less than the other by your definition. The point is that all you have done is made a new definition of ordering. It has nothing to do with the underlying set theory. You won't find the concepts of bijection, cardinality or inclusion anywhere in the axioms of set theory. These are defined concepts. – spaceisdarkgreen Dec 19 '17 at 2:13
• @Doug even my phrasing there is guilty of encouraging your misconception. There is no "definition of ordering" but rather various (partial) orderings one could define. Some may be more useful than others but they're all just defined things. It makes no sense to have one theory where one choice is "the ordering" and another theory where it's another choice cause there's no such thing as "the" ordering. – spaceisdarkgreen Dec 19 '17 at 2:25