Surjections and Cardinal Numbers

Page last updated 13 May 2023

A surjection from a set A onto a set B means that for every element in B there is an element in A that is mapped to that element in B. Note that there can be more than one element in A that maps to an element of B. If there is a one-to-one correspondence (a bijection) between two sets A and B, then there is also a surjection A onto B, and a surjection B onto A.

This means that if there is no surjection either way between two sets, then ipso facto, there cannot be any one-to-one correspondence between them. For finite sets, the absence of any surjection from A onto B coincides with the fact that A has fewer elements than B, and this applies for all finite sets regardless of the properties of the elements - in other words the absence of any surjection is unaffected by the properties of the elements of the sets.

But for infinite sets this is not the case. It is explained in One-to-one Correspondences and Properties that the absence of a one-to-one correspondence between two infinite sets implies that this is due to certain properties of the elements of the sets rather than a difference in any property of the sets that is independent of the specific characteristics of the elements of the sets.

The same applies to surjections between infinite sets - it is impossible to make a “list” of infinitely many matching elements, hence a definition is required and which refers to the properties of the elements of the sets, rather than any property of the sets that is independent of the precise nature of the elements. Hence, as for a bijection, the absence of a surjection between two infinite sets implies that this is due to certain properties of the elements of the sets rather than any difference in some property of the sets that is independent of the properties of their elements.

On the page Cardinal Numbers I refer to a fundamental assumption regarding Cardinal Numbers in transfinite set theory, see The fundamental axiom of Cardinal Numbers. One could also say that there is another assumption/axiom of Cardinal Numbers in transfinite set theory, which is:

If there is no surjection from set A onto set B, then:

the Cardinal Number of A < the Cardinal Number of B.

The usage of the symbol “ < ” with regard to natural numbers and real numbers is that if a < b (a real, b real or infinite) implies that there exists an x, x real or infinity, where a + x = b, and that given a set A which has the number of elements a, a set B which has the number of elements b, and a set X which has the number of elements x, then the union of sets A and X, if they have no elements in common, has the number of elements b.

Extending that same usage to Cardinal Numbers as defined by transfinite set theory would imply that where a < b (a, b Cardinal Numbers), there exists an x, x a Cardinal Number, where a + x = b, and that given a set A which has the number of elements a, a set B which has the number of elements b, and a set X which has the number of elements x, then the union of sets A and X, if they have no elements in common, has the number of elements b.

So, for example, if A is the set of all natural numbers, and B is the set of all real numbers, and X is the set of all real numbers except natural numbers, then the union of A and X, since they have no elements in common, has the same number of elements as B (since the union of A and X is B) - in other words this implies that the set A, which has no limit to the number of its elements, has fewer elements than the set B, which also has no limit to the number of its elements. In terms of transfinite notation, we have that given that:

there exists a one-to-one correspondence A ∪ X to B

then, in terms of the corresponding Cardinal Numbers we have:

ℵ₀ + ℵ_X = ℵ_B

This implies the contradiction that one set that has limitlessly many elements can have fewer elements than another set that also has limitlessly many elements. Some people, including some commenters to this site, such as on the page Cardinal Numbers don’t like this conclusion and attempt in various ways to evade this conclusion. But in fact, as I explain in One-to-one Correspondences and Properties the real reason why there is no surjection from A onto B, but there is a surjection from A ∪ X onto B depends completely on the properties of elements of the sets in question, rather than anything to do with the quantities of elements in the sets.