Wikipedia:Reference desk/Archives/Mathematics/2013 December 3

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 3

Are There Any R to C or C to R Bijective Functions ?

$f:\mathbb {R} \to \mathbb {C} ,\quad f(x)-$ bijective, or $f:\mathbb {C} \to \mathbb {R} ,\quad f(x)-$ bijective. I'm asking this with the following in mind: We know that $\mathbb {N} \to \mathbb {N} ^{2}$ and $\mathbb {N} ^{2}\to \mathbb {N}$ bijections do exist, given that they're both countable sets; and we also know that, say, a $\mathbb {N} \to \mathbb {R}$ or $\mathbb {R} \to \mathbb {N}$ bijection can't exist, for prescisely the opposite reason: But can such a bijection between two uncountable sets exist ? — 79.113.223.146 (talk) 09:47, 3 December 2013 (UTC)

The obvious one to me would be even and odd powers of ten being broken out so that in the R to C. 1234.567 maps to 24.6 + 13.57i. I know that only maps to half the complex plane (depending on where a negative value for the Real value goes to. But it is a start.Naraht (talk) 10:04, 3 December 2013 (UTC)

A space filling curve serves this purpose does it not? — Preceding unsigned comment added by 144.82.188.210 (talk) 11:57, 3 December 2013 (UTC)

No. A space-filling curve approaches arbitrarily close to every point, but doesn't actually pass through every point. Naraht has shown how to construct such a bijection, though. Looie496 (talk) 16:59, 3 December 2013 (UTC)

And then you take apart the resultant half of the complex plane on one unit wide stripes and rewallpaper alternating sides of the Complex axis.Naraht (talk) 17:30, 3 December 2013 (UTC)

Space-filling curves do hit every point; what you describe is impossible, since their image is closed. The problem is that they're not injective. It follows from algebraic topology that this is essential; there is no continuous bijection between R and C.

Naraht's approach also has a few details left to work out, since $11.000000\dots$ and $10.090909\dots$ both map to the same place. Fortunately, it's only a countable set of problem points.--80.109.80.78 (talk) 21:43, 3 December 2013 (UTC)

True. Just a first off the cuff idea. I'd be curious to see other possible solutions.Naraht (talk) 22:06, 3 December 2013 (UTC)

Well, you can use arctan to map C into the unit-square, and then use your idea to get an injection from C to R. Since there's an obvious injection from R to C, Schroeder-Bernstein finishes the job. Alternatively, you can note that the only problems with your idea come at decadic rationals, so fix some countable sequence of reals, slide them around to make room, then slide the decadic rationals in amongst them.--80.109.80.78 (talk) 22:30, 3 December 2013 (UTC)

Any infinite set A has a bijection to A x A, see Cardinal_number#Cardinal_multiplication (proofs probably require the axiom of choice). —Kusma (t·c) 14:08, 3 December 2013 (UTC)

In this case at least, the axiom of choice is not required. It's possible to construct explicit surjections from R to C and C to R. The Cantor-Bernstein-Schroeder theorem now does the heavy lifting. Sławomir Biały (talk) 17:49, 3 December 2013 (UTC)

Having surjections both ways, in the absence of choice, doesn't get you a bijection. You need injections both ways. But those are not hard to come by, so your first sentence is true. Actually all three of them are true; just the logical connection isn't quite there :-). (By the way, Schroeder–Bernstein theorem. That's a redirect, but Cantor's argument doesn't help you here, so I think it makes more sense to leave him out; it's not like there's a shortage of stuff named after him.) --Trovatore (talk) 21:52, 3 December 2013 (UTC)

Just a little post-hoc note: My "by the way" parenthetical above was written before another user corrected Sławomir's link — it was a redlink at the time. I wouldn't have bothered to add that, just to complain about Cantor in the name. --Trovatore (talk) 01:26, 4 December 2013 (UTC)

Two surjectives doesn't equal one bijection?

I guess I'm a little confused why you need the Axiom of Choice to take a Surjective function from R to C and a Surjective function from C to R and get a bijective function between R and C. Is it that you simply need the Axiom of Choice to create a specific bijective function or do you also need the Axiom of Choice to prove that such a bijective function exists?Naraht (talk) 03:04, 4 December 2013 (UTC)

OK, for the specific case of R and C, you can prove the existence of a bijection (even give a rather "explicit" one), with no need to invoke choice.

In general, though, if you know that there are surjections from X to Y and vice versa, you need choice to prove that there's a bijection between X and Y. If you know that there are injections in both directions, you don't need choice.

Here's a specific example: Let X be the reals, and let Y be the disjoint union of the reals with the set of all countable ordinals. Clearly there's a surjection from Y to X (send every real to itself, and every countable ordinal to some fixed real). To get a surjection from X to Y, take some surjection from the negative reals to all the reals, and apply that to every negative element of X. Doesn't matter what you do with 0∈X (for definiteness, send it to the 0 of the copy of the reals in Y). For every positive element of X (positive real), either it codes a countable ordinal or it doesn't. If it doesn't, send it to the ordinal 0; if it does, send it to the ordinal it codes.

But in a model of the axiom of determinacy, there can be no bijection between X and Y, because that would give you an injection of ω₁ into R, which contradicts AD. --Trovatore (talk) 03:14, 4 December 2013 (UTC)

I've been trying to see why that contradicts AD, but I'm stuck. Is there a straightforward construction of a game with no winning strategy from such an embedding?--149.148.254.102 (talk) 08:50, 5 December 2013 (UTC)

AD implies that every set of reals is either countable, or has a nonempty perfect subset. This is probably easier to see on 2^ω — something along the lines of one player plays 0 or 1 and the other player plays finite sequences (and that's the player trying to get into the set). A winning strategy for the finite-sequence player implies that the payoff set contains the branches of an ever-branching tree, whereas from a winning strategy for the first player, you can read off the countable set. Or something like that; I forget the details but you can probably work them out.

So suppose there's an injection from ω₁ into R. Its range is an uncountable set of reals, so it has a nonempty perfect subset, which therefore has the cardinality of the continuum. But that implies a bijection between ω₁ and R, which implies R can be wellordered. --Trovatore (talk) 09:12, 5 December 2013 (UTC)

Great, thanks. FYI, here's the details for the perfect set property, as I was able to work them out: suppose the avoiding player has a winning strategy. Fix a point $z$ in our set. There must be some partial run of the game consistent with the avoiding player following this strategy, such that it is the non-avoiding player's turn, the sequence played so far is an initial segment of $z$, and every play by the non-avoider generates a response from the avoider that takes us away from $z$. For if not, we could always extend to stay on $z$ and thus get a win against the strategy. But this means that the strategy computes $z$: have the non-avoiding player play the next $n$ bits of $z$, and the avoider will necessarily respond with $(1-z(n))$. So every element of our set is computable from the strategy, and thus our set is countable.--149.148.254.102 (talk) 10:24, 5 December 2013 (UTC)