Re: Constructibility of X -> X^2 bijection


"Stephen J. Herschkorn" <sjherschko@xxxxxxxxxxxx> wrote in message news:MFJqi.246$vq1.121@xxxxxxxxxxxxxxx
Peter Webb wrote:


"David C. Ullrich" <ullrich@xxxxxxxxxxxxxxxx> wrote in message news:tkmja31elrat2jo5sj2fvcdrhrfvrf6720@xxxxxxxxxx

On Fri, 27 Jul 2007 10:55:45 +1000, "Peter Webb"
<webbfamily@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:


"Rupert" <rupertmccallum@xxxxxxxxx> wrote in message
news:1185493816.987737.13210@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

On Jul 27, 12:23 am, theronr...@xxxxxxxxx wrote:

Let X is an infinite set.
Is it possible to be constructed explicitly a bijection between X and
X^2 for X as parameter?

In other words: without any information about set X (except that it is
known that X is not finite) is it possible to exist explicitly
constructible bijection between X and {(x, y) | x, y in X}?

If the answer is no, is it possible to exist explicitly constructible
infinite set Y such that it is provable that it doesn't exist
explicitly constructible bijection between Y and Y^2?

Thank you,
Theron


I believe that the proposition that X is equipollent to X^2 for all
infinite X is equivalent to the axiom of choice.


Maybe so.

But you will note that the bijection between N and NxN doesn't need choice.


True. But curiously, the fact that a countable union of countable
sets must be countable does require some version of AC. The two
statements sound equivalent at first...

(I'm not _quite_ sure whether that comment is relevant here.
It does show that ensuring you're not using AC can be tricier than
you think.)


Indeed. The advantage of N being we have an explicit choice function.

But I hadn't actually thought of it that way, its an interesting insight.

And neither does the standard bijection between R and RxR.


You are unfortunately silent on that one.

It also raises the question of whether we can show

P(R) bijects with P(R)xP(R)

(with P the Powerset)

which is the next logical step.

Its also somewhat frustrating that the proofs for N and R use what seem to me to be different "tricks", and I can't even see how either technique could me modified to include the other.


N and N x N is easy because N is well-ordered (with every element by the first a successor ordinal.) Could you please remind me what the standard bijection between R and R x R is? It must use the total order on R.


The standard one is interleaving the decimals in the decimal expansions of the two numbers. This fails for countably many points of form 0.4999....

A similar one is through considering the continued fraction form; just alternate the terms of the continued fractions for x and y to get the bijected real. This works for all pairs of Reals.


Without AC, can we place a total order on P(R)? I think the answer is no, but no immediate proof comes to mind.


It seems unlikely ... I certainly can't think of one.

And can we come up with an explicit bijection between w1 and w1 x w1 (where w stands for omega) without appeal to Cantor-Schroeder-Bernstein?


If you mean w1 = w+1 = N U {N} I would have thought of course - just re-order the elements.

Whilst CBR uses choice, its a non-issue for countable sets as we have an explicit choice function.

Or maybe I am misunderstanding you?


.

Relevant Pages

  • Re: Calculus XOR Probability
    ... bijection, with 1-1 correspondence between elements of two infinite sets, ... perhaps one can prove that an explicit bijection cannot be ... doesn't sound familiar. ...
    (sci.math)
  • Re: Constructibility of X -> X^2 bijection
    ... Kunen's hint gave an explicit definition of a total ordering on k x k (for k an infinite initial ordinal). ... So that induces a bijection by carrying each k x k element to its rank in that ordering. ...
    (sci.math)
  • Re: Constructibility of X -> X^2 bijection
    ... constructible bijection between X and? ... its a non-issue for countable sets as we have an explicit choice function. ... the set {all countable ordinals} U has countably many elements; so there shouldn't be a problem. ... (This assumes that there is no well-ordering of R without AxC, which I think is believed to be true but has not yet been proven). ...
    (sci.math)
  • Re: Galileos Paradox
    ... To establish an explicit bijection between infinite sets does require ... That one uses ordered sets to construct unordered but structured sets ...
    (sci.math)
Quantcast