Yeah, isn’t the existence of a one-to-one correspondence itself a bit sticky (i.e., dependent on one of the independent axioms)? If there’s a distinct element of B corresponding to each element of A, then |B| >= |A|, and if there’s some other correspondence such that there’s a distinct element of A corresponding to each element of B, then |A| >= |B|, and if |B| >= |A| and |A| >= |B| then |A| = |B|, but is there necessarily always a single correspondence that goes both ways at once?
Yes, this is the Cantor-Schroeder-Bernstein theorem. I’m actually surprised you apparently take “|A| = |B|” directly to mean “There is an injection from A to B and there is an injection from B to A” rather than “There is a bijection between A and B”, since in my experience, it’s usually the latter definition which is stressed in introducing the concept of transfinite cardinality. Still, it makes no difference for us.
(The Cantor-Schroeder-Bernstein theorem can fail in non-classical logic (for example, there are intuitionistic contexts in which all maps are continuous, with the result that there will be no bijection between (0, 1) and [0, 1], despite injections both ways), but even then, we still take “A and B have the same size” to mean “There is a bijection between A and B”, and simply understand that this does not interplay so nicely with a notion of sizes being “>=” or “<=” than another. Regardless, everything I’m saying in this thread is about classical mathematics unless otherwise noted.)
Just to make sure we’re all on the same page:
It doesn’t seem obvious that two sets of the same size can be put in a one-to-one correspondence (i.e., bijection)? Generally, this is taken as the definition of two sets having the same size! What definition did you have in mind instead?
[There is the troublesome point that “one-to-one correspondence” is usually used to mean “bijection” but “one-to-one mapping” or “one-to-one function” is usually used to mean only “injection”. Is this a source of confusion? Perhaps we should avoid those terms altogether…]
Yeah, that’s what I was afraid you were going to say. Anytime you think you got a good set of axioms going, someone goes out and finds a set that’s just too damn big and breaks it. 
Thanks again.
I had in mind something like Chronos mentioned. Show A <= B and show B <= A, then A == B. But that doesn’t require explicitly showing a bijection between A and B.
It doesn’t seem any more or less obvious that two sets of the same uncountably infinite size can be put in a one-to-one correspondence, than that the Axiom of Choice is true.
I’ll note you link does at least say the proofs that don’t rely on the Axiom of Choice are non-constructive, so I don’t think it would have been that surprising if the proof depended on AoC. Since the proofs are non-constructive, there must be examples where you can’t construct the bijection, even though you know it exists. (Or at least, there must be cases where the bijection can’t be constructed, even if you can’t explicitly show an example of one… :))
They’re non-constructive in the specific sense that they require there to be Yes/No answers to questions of the form “Does there exist an x such that?” (so they fail in intuitionistic, as opposed to Boolean, logic). But the bijections are explicitly definable in classical mathematics.
Specifically, suppose you have an injection f: A -> B and an injection g : B -> A.
It may be that some elements of A are not in the range of g. Let’s say these are “A-originating”. Furthermore, let’s say that anything you can get (in either A or B) by repeatedly applying f and g to an A-originating element is itself considered A-originating. [Note: If you think of A and B as having any overlap, then whether an element in the overlap is A-originating can depend on whether you are thinking of it as part of A or as part of B. But you should be thinking this way anyway.]
Note that f gives a bijection from the A-originating elements of A to the A-originating elements of B. So we have a one-to-one correspondence for the A-originators.
Note also that g gives a bijection from the non-A-originating elements of B to the non-A-originating elements of A. So we have a one-to-one correspondence for the non-A-originators.
Putting these two together, we have a one-to-one correspondence overall. The “non-constructivity” is just in the supposition that every element is either A-originating or non-A-originating; this instance of the excluded middle is a Boolean tautology, but it may not be possible, in some contexts, to effectively compute which holds.
Alas, I missed the edit window, but I was going to augment this to read:
[Note: If you think of A and B as having any overlap, then whether an element in the overlap is A-originating can depend on whether you are thinking of it as part of A or as part of B. But you should be thinking this way anyway; there’s no need to imagine A and B as subsets of some common superset such that it makes sense to ask about their overlap; rather, think of then as abstract sets whose elements can’t be directly compared (the same way one wouldn’t generally meaningfully ask whether elements in different abstract topological spaces were equal, or different abstract groups, or what have you)).]
Alas, the fact that people are generally taught to think of “set theory” in the style of “material” set theory without consideration of “structural” set theory makes these discussions more difficult than they need to be…
OK, let me see if I can work through an example of that, using the sets A = [-1,1] and B = (-1,1). I’ll take f(x) = x/2 (thus mapping A to [-1/2, 1/2] ), and g(y) = y. This gives us as A-originating points -1 and 1, and by repeated application of f and g, also -1/2 and 1/2, and -1/4 and 1/4, and in general -1/2^n and 1/2^n.
So the desired bijection is then, h: A -> B, h(x) = {x/2: x = 1/2^n for some n; x otherwise . Hm, yes, I guess that works. It’s discontinuous (under most of the typical topologies), but then, I never specified anything about continuity.
For what it’s worth, even without the Cantor-Schroeder-Bernstein theorem and taking “A and B have the same size” to mean “Both A and B admit injections into each other (though possibly not a bijection)”, this is still true.
In fact, whenever |A| >= |B|, the well-orderability of A implies the well-orderability of B. For, given an injection from B to A and a well-ordering on A, we can define a well-ordering on B by the rule “The result of comparing two elements of B is the same as that of comparing their images in A under the injection”.
It can’t be continuous (at least, in the usual topology). Since A is compact (and B is Hausdorff), any continuous bijection h:A -> B is a homeomorphism, forcing B to be compact.