Posers and Puzzles

Posers and Puzzles

  1. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    19 Oct '04 23:52
    Hmm, it seems no-one got 2. Well, injections do exist from F(R) to R. For example:

    - Put each number in the set through an injection R -> [0,1) by e.g. 'zigzagging' through the decimal expansion (so 123.456 becomes 0.342516);
    - Interlace the resulting numbers by putting the first DP of the first, then the first of the second, etc (so 0.123, 0.45 and 0.6789 would combine to give 0.146257308009);
    - Add n, the size of the set, so you get n point something or other.

    Can anyone answer the general question, whether there exists an injection F(X) -> X for an arbitrary infinite set? Remember an arbitrary set X needn't have an ordering, addition or multiplication, and it could be a different size from both N and R.
  2. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    20 Oct '04 00:27
    Originally posted by Acolyte
    Hmm, it seems no-one got 2. Well, injections do exist from F(R) to R. For example:

    - Put each number in the set through an injection R -> [0,1) by e.g. 'zigzagging' through the decimal expansion (so 123.456 becomes 0.342516);
    - Interlace the resulting numbers by putting the first DP of the first, then the first of the second, etc (so 0.123, 0.45 and ...[text shortened]... ave an ordering, addition or multiplication, and it could be a different size from both N and R.
    Very clever 😲!

    I tried to think of a couple of geometric ones, but I didn't manage anything. I'll try the other one, though.
  3. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    29 Nov '04 03:41
    Okay, if X is countable, then there is some way of numbering the elements ie {x1,x2,x3,...}. As Acolyte pointed out in the ineffable number thread, we don't necessarily know what the bijection is, but here we don't care. Let X(n) = {x1,x2,...xn} for any n in N. X(n) has n choose 0 + n choose 1 + ... n choose n = 2^n finite subsets. Each element of F(X(n)) is clearly a subset of X(n), so F(X) = F(X(1))UF(X(2))U... is a union of countably many finite sets, so there is an injection from F(X) to X.

    Is there some way to use induction on the cardinality of X involving the fact that there are no sets with cardinality between X and P(X)?
  4. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    29 Nov '04 18:35
    Originally posted by royalchicken
    Okay, if X is countable, then there is some way of numbering the elements ie {x1,x2,x3,...}. As Acolyte pointed out in the ineffable number thread, we don't necessarily know what the bijection is, but here we don't care. Let X(n) = {x1,x2,...xn} for any n in N. X(n) has n choose 0 + n choose 1 + ... n choose n = 2^n finite subsets. Each element of ...[text shortened]... rdinality of X involving the fact that there are no sets with cardinality between X and P(X)?
    I believe the trick I used to find an injection F(R) -> R can be generalised to a procedure for turning F(X) -> X into F(P(X)) -> P(X). By ordinary induction, the result is then true for any sets of cardinality 'beth-n' for n an integer, where beth-0 = aleph-0, beth-n = 2^beth-(n-1).

    The generalised continuum hypothesis is "all aleph numbers are beth numbers", so that would deal with all the aleph-n. Unfortunately, there are more cardinals than that, eg aleph-omega. I don't know if or how the induction I referred to can be turned into a transfinite induction using Zorn's lemma, but if it can, I think that finally deals with all the cardinalities. The question is then whether the two extra axioms used are necessary for provability. I'd be surprised if Zorn was unnecessary, but there might be some way of bypassing the GCH.
  5. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    29 Nov '04 19:30
    Originally posted by Acolyte
    I believe the trick I used to find an injection F(R) -> R can be generalised to a procedure for turning F(X) -> X into F(P(X)) -> P(X). By ordinary induction, the result is then true for any sets of cardinality 'beth-n' for n an integer, where beth-0 = aleph-0, beth-n = 2^beth-(n-1).

    The generalised continuum hypothesis is "all aleph numbers are beth ...[text shortened]... y. I'd be surprised if Zorn was unnecessary, but there might be some way of bypassing the GCH.
    May I quote this in the next meeting of Plus?
  6. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    30 Nov '04 00:34
    Originally posted by royalchicken
    May I quote this in the next meeting of Plus?
    You could, but it's just a rather hazy outline of how I imagine things would work, based on my very limited knowledge of cardinality and set theory. I'm sure a set theorist could point you in the right direction.
  7. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    30 Nov '04 01:31
    Originally posted by Acolyte
    I believe the trick I used to find an injection F(R) -> R can be generalised to a procedure for turning F(X) -> X into F(P(X)) -> P(X).
    Something like this should work:

    Claim: Let X be infinite. If there exists an injection F(X) -> X, then there exists an injection F(PX) -> PX.

    Proof:

    Let A be a collection of subsets of X, with |A| = k.

    1. Choose surjections f1,...,fk from X onto each of the sets in A.

    2. Define a new set B by replacing each element x of X with the k-tuple (f1(x),...,fk(x)). Then B is a subset of X^k, and B completely specifies A.

    By doing this for all finite subsets of PX, we have an injection F(PX) -> P(X)uP(X^2)u...

    It now suffices to find an injection P(X^k) -> P(X) , as there's no problem mapping PXuPXu... into PX as PX is infinite. In fact, we can map X^k into X (which can clearly be generalised to an injection P(X^k) -> PX) by the following:

    1. For each element of F(X), choose an ordering of its elements. Then each k-tuple may be regarded as an element of F(X) together with a permutation of its 'default' order, and this gives rise to an injection X^k -> F(X)*Sk, where Sk is the symmetric group of order k.

    2. F(X) is infinite and Sk is finite, so F(X)*Sk -> F(X) injectively since the sets are the same size.

    3. By assumption F(X) -> X injectively.

    I've assumed Choice in various places (basically, whenever I choose an unspecified map between sets of the same size) - I don't think there's much getting away from it at this level of generality. But hopefully the result follows under ZFC.
Back to Top