Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Cantor convincingly argued for the proposition that two sets are of the same size exactly when there is some bijective function from one to the other.

However, "functions" are formally defined as sets themselves, and so the relative size of two sets can depend on which other sets (namely, functions between them) exist.

It seems to me that defining a function as a set of ordered pairs (or perhaps actually a triple- the domain, codomain, and then a set of ordered pairs) is a "neat formal trick" as Omar Antolín-Camarena says here, but "not really how anyone intuitively thinks about a function." Cantor's argument relating size to bijections depends crucially on our intuition.

Is there any way to define functions other than as sets and get around this 'issue', or alternatively formalize an absolute notion of size (something like two sets are equinumerous if a bijective function between them exists in any model of set theory)?

share|improve this question
Not everyone agrees that equivalent cardinality implies two sets have the same size. It turns out that the set of tautologies of propositional logic has the same cardinality as the set of contingencies. You can form a sequence of tautologies, using Polish notation with C as the material conditional, as follows: (Cpp, CCppCpp, CCCppCppCCppCpp, CCCCppCppCCppCppCCCppCppCCppCpp, ...):=**T-I** In this sequence you get the next term from the last term by substituting p with Cpp. Now we'll form a sequence of all the contingencies. Consider the truth tables of contingencies... –  Doug Spoonwood Aug 19 '13 at 15:16
We can write the values of those contingenices using truth tables as follows (01, 10, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 00000001, ...) [the next term in the sequence comes as what looks like the number in binary with 2^n digits.. this description is not complete, but it still can get written] := C. Now write a function G where G: [Cpp]->01, CCppCpp->10, CCCppCppCCppCpp->0001, etc. Consequently, you can map a subset of the set of all tautologies to the set of all contingencies. Since... –  Doug Spoonwood Aug 19 '13 at 15:23
You can reverse such a function, and that gives a bijection. So, the cardinality of the set of contingencies comes as equivalent to the subset T-1 set of tautologies. Since a subset of a set always has less than or equal cardinality of one of its supersets, it follows that the cardinality of the set of tautologies comes as greater than or equal to the cardinality of the set of contingencies. But, I don't think anyone believes the cardinality of the set of tautologies greater than that of contingencies, so I think it reasonable to infer that they have the same cardinality. However.. –  Doug Spoonwood Aug 19 '13 at 15:30
does it make any sense, any sense at all, to think that the set of tautologies have the same size as the set of contingencies? I don't think so. And consequently, I simply do NOT believe that it comes as convincingly argued that two sets actually have the same size when they have the same cardinality. –  Doug Spoonwood Aug 19 '13 at 15:33

2 Answers 2

up vote 6 down vote accepted

The generalization you suggest cannot work. Given two infinite sets we can add by forcing a bijection between them. This will result in all infinities collapsing into the same cardinality, rendering this notion completely useless.

Moreover there are models which have non-standard integers. In fact, one can even have more integers in one model than real numbers in another model. So it becomes impossible to even say what is the cardinality of "the integers" since those are not absolute between models of set theory.

But let me offer you an intuitive solution as to why this phenomenon is actually common in mathematics, only when we think about sets it becomes troubling to us. I will also explain why.

How many cubic roots are there to $2$? Well, that depends on the mathematical structure we are considering. In the rational numbers the number $2$ doesn't have any number $x$ such that $x^3=2$. On the other hand, in $\Bbb R$ there is exactly one $x$ with this property, whereas in the complex numbers there are three such numbers.

So the question becomes dependent on the context in which we are working, and which numbers exist in the "universe of numbers" we might consider at the moment.

But we never really find this issue troubling. Why? Well, we are used to think about the complex numbers as absolute, and the real numbers are absolute, and the rationals are absolute, and so on. This means that there is some "large" universe of "all numbers" (which is how a non-mathematician person usually see this) where everything happens. In fact, asking people what is a number often you will get answers ranging from "Uhm, $0,1,2\ldots$" to "Something signifying physical quantity" to "A complex number".

So we have these canonical models for all the things we think of as numbers. And so there is no issue in stepping up to a larger context when needed. On the other hand set theory has no such canonical model, so we are left with some sort of uncertainty with what sort of objects live in the model we consider at the moment.

The fact that we can switch models causes a lot of tension to people first hearing about it. How can sets be different between models? Well, how can $x^{412341}-2$ have so many different solutions in different contexts? Because context matters.

Equinumerosity depends on the context, much like the other question. It's fine.

share|improve this answer
Hmmm... the analogy to the context-sensitivity of questions about numbers is nice. Although, if your post shows why canonical models of numbers are so great, it does raise the question of why set theorists work with a big messy multiverse instead of very nice canonical models (i.e. why $V = L$ is never seriously accepted as an axiom). –  Sam Hopkins Aug 19 '13 at 14:22
@Sam: $V=L$ gives a very poor universe in a lot of sense. And not much is left to say after that. This is like suggesting that instead of general Banach spaces, everyone work with $\Bbb R^n$. Moreover, even $V=L$ doesn't have a canonical model. –  Asaf Karagila Aug 19 '13 at 14:29
Nice analogy; +1. –  Brian M. Scott Aug 19 '13 at 19:16
@Brian: Thanks. I figured it some while ago when I wrote some answer not too-distant from this one about how something is true but not provable (perhaps the continuum hypothesis was the center of the attention at the time). I've been using this analogy ever since. –  Asaf Karagila Aug 19 '13 at 19:17
"Given two infinite sets we can add by forcing a bijection between them." - I'm intrigued by this assertion; how does it not contradict Cantor's theorem? –  Sam Hopkins Aug 19 '13 at 20:18

Something along the lines of what you are proposing was developed in the article

Benci, Vieri; Di Nasso, Mauro, Numerosities of labelled sets: a new way of counting. Adv. Math. 173 (2003), no. 1, 50–67.

(the notion of numerosity is more "flexible" than that of cardinality).

Jörg D. Brendle's review of

Blass, Andreas; Di Nasso, Mauro; Forti, Marco, Quasi-selective ultrafilters and asymptotic numerosities. Adv. Math. 231 (2012), no. 3-4, 1462–1486

here specifically compares numerosities and cardinalities.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.