Every set trivially maps (one to one) into itself, and if S maps into T maps into U then S maps into U. We almost have a partial ordering on cardinal classes. But we're missing one thing: S ≤ T and T ≤ S → S = T. If S maps into T and T maps into S, are they the same size? Is there a bijection that implements the correspondence?
If two finite sets embed in each other then they are the same size. We only need consider infinite sets. So it's ok to use the infinite axiom, and talk about an element's infinite ancestry etc. There is another proof that avoids this, but I think it is less intuitive.
Let f map S into T and g map T into S. These are 1-1 functions of course. For any x in either set, trace the ancestry of x, going backwards through f inverse and g inverse, until we reach a parentless element that is not in the range of f or g. Let S1 be the subset of S whose members have parentless ancestors in S. Let S2 be the subset of S whose members have parentless ancestors in T. Let S3 be the subset of S whose members have infinite ancestry.
Let h = f on S1 and S3, and g inverse on S2. Clearly h is invertible when restricted to S1∪S3, or S2. We need to show h is invertible across all of S. In other words, we don't want h(x) to equal h(y), when x comes from S1∪S3 and y comes from S2.
Let f(x) = g inverse of y. Thus y = g(f(x)). If x is in S3 (infinite ancestry) then so is y. Yet y is in S2, so x is in S1. This means x has a parentless ancestor in S, and the same holds for y, so y should be in S1. That takes care of 1-1.
Finally we need to show that h maps S onto all of T. Select any y in T and first consider the case when, for some x in S, we have f(x) = y. If x is in S1 or S3 we are done, so x has a parentless ancestor in T. Let g(y) = z, and z has a parentless ancestor in T. Thus z is in S2 and h(z) = y.
Now consider the remaining case, when y is not in the image of f. Once again z=g(y) is in S2 and h maps z to y. Therefore h maps onto all of T and both sets have the same cardinality.
This completes antisymmetry, and also completes the proof of the Schroder Bernstein Theorem.
If two sets fit inside each other they are the same size. Cardinal classes are partially ordered. This provides another method for proving cardinal equality. Mapping two sets into each other is often easier than finding a perfect 1-1 correspondence. For instance, the integers map into the rationals in the obvious way, and rationals map into integers by sending the fraction a/b (lowest terms) to 2a3b. (Send -a/b to -2a3b, and send 0 to 0.) That's it. The integers and the rationals are the same size. (Of course it is also not so difficult to write down explicit examples of one to one maps of the integers onto the rationals.)
Are S and T the same size if a function takes S onto all of T, and another function carries T onto S? If S and T are finite then the answer is yes. For infinite sets, if both these functions are one to one then the Schroder Bernstein theorem gives a positive answer. Otherwise we need the well ordering principle.
Start with any subset of the positive integers. Take the lowest integer in the set and write it in binary, just after the decimal point. Then append 2 as a delimiter. Take the next element in the set, write it in binary, and append another 2. Continue this forever, or stop if the set is finite. We never use the digit 9, so there is no overlap, and the process is reversible, hence this is an embedding.
Start with any real number in [0,1) and write it in binary. Upgrade the digits 0 and 1 to 1 and 2. read the first digit after the radix point and call that an integer, either 1 or 2. Put that in the set. Read the next two digits as an integer: 11, 12, 21, or 22. Put that in the set. Read the next 3 digits as an integer, then the next 4 digits, and so on. This builds a subset of the integers, which can be reversed to produce the original real number.
Both sets map into each other, and have the same cardinality.
There is, more directly, a bijection between the power set of S and the functions from S into 0 and 1. If x maps to 1 then include x in the subset of S, if x maps to 0 then do not include x in the subset of S. If S can be well ordered, then this function is a sequence of zeros and ones. So the sequence establishes the subset. This is similar to the proof above, equating reals with the power set of the integers.