# Yet another infinity question

**URL:** <https://boards.straightdope.com/t/yet-another-infinity-question/681803>\
**Category:** Factual Questions\
**Created:** [February 20, 2014, 5:03pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803 "2014-02-20T17:03:23Z")\
**Posts on this page:** 11\
**Page:** 2

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [February 21, 2014, 5:26pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/21 "2014-02-21T17:26:59Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 21, 2014, 6:21pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/22 "2014-02-21T18:21:25Z")

</div>

Yes, this is the [Cantor-Schroeder-Bernstein theorem](http://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_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.)

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 21, 2014, 6:23pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/23 "2014-02-21T18:23:15Z")

</div>

Just to make sure we’re all on the same page:

> [@ZenBeam](#):
>
> Why wouldn’t showing that you could always make the one-to-one correspondence require the well-ordering theorem in the first place? It doesn’t seem obvious, otherwise.

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?

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 21, 2014, 6:27pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/24 "2014-02-21T18:27:45Z")

</div>

[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…]

---

<div class="post-metadata">

**Author:** ![Buck\_Godot](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/buck_godot/32/6573_2.png) [@Buck\_Godot](https://boards.straightdope.com/u/Buck_Godot)\
**Post date:** [February 21, 2014, 8:37pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/25 "2014-02-21T20:37:07Z")

</div>

> [@Indistinguishable](#):
>
> There are as many alephs as there are transfinite ordinals, which is more than there are in any set. For given any set of alephs S, we can construct the new aleph corresponding to the number of ordinals of cardinality less than or equal to some aleph in S, which will be larger than any particular aleph in S.

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.

---

<div class="post-metadata">

**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\
**Post date:** [February 21, 2014, 8:45pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/26 "2014-02-21T20:45:50Z")

</div>

> [@Indistinguishable](#):
>
> 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?

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… :))

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 21, 2014, 9:30pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/27 "2014-02-21T21:30:12Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 21, 2014, 9:38pm UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/28 "2014-02-21T21:38:36Z")

</div>

> [@Indistinguishable](#):
>
> [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.][/SIZE]

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…

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [February 22, 2014, 4:21am UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/29 "2014-02-22T04:21:55Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 22, 2014, 6:03am UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/30 "2014-02-22T06:03:26Z")

</div>

> [@ZenBeam](#):
>
> You’re not saying that for sets of a given size, either they are all well-orderable, or none of them are, are you?

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”.

---

<div class="post-metadata">

**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\
**Post date:** [February 24, 2014, 12:47am UTC](https://boards.straightdope.com/t/yet-another-infinity-question/681803/31 "2014-02-24T00:47:34Z")

</div>

> [@Chronos](#):
>
> 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.

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.

[Previous page](https://boards.straightdope.com/t/yet-another-infinity-question/681803.md?page=1)