More counting puzzles

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.

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.

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)?

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.

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?

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.

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.