More counting puzzles

Let F(X) be the set of all finite subsets of X. For each of the following, either give an explicit example or show why it can't be done.

1. an injection from F(N) to N (counting numbers);
2. an injection from F(R) to R (real numbers).

(For those who don't know, an injection is a function f for which f(x) is different from f(y) whenever x is different from y.)

1. Let A={a_1,a_2,a_3,...,a_n} where a_i is in N and a_1<a_2<...<a_n
Then A is a unique expression of a finite subset of N.
Let f(A)=the sum from k=1 to a_n of b_i*2^k, where b_i=0 if i is not in A and b_i=1 if i is in A.
Then f is an injection from F(N) to N.

Originally posted by Acolyte
Let F(X) be the set of all finite subsets of X. For each of the following, either give an explicit example or show why it can't be done.

1. an injection from F(N) to N (counting numbers);
2. an injection from F(R) to R (real numbers). ...[text shortened]... which f(x) is different from f(y) whenever x is different from y.)

Both R & N are infinite sets. According to the conditions specified, F(R) and F(N) will be the power sets of R and N respectively. Why restrict F(X) to be only the set of finite subsets? For greater generality why not let F(X) be the set of all subsets of X whether finite or infinite?
The power set of any given set has higher cardinality (the number of elements in a set) than the original set. Therefore there cannot exist any injection from F(X) into X.

Originally posted by garethn
1. Let A={a_1,a_2,a_3,...,a_n} where a_i is in N and a_1<a_2<...<a_n
Then A is a unique expression of a finite subset of N.
Let f(A)=the sum from k=1 to a_n of b_i*2^k, where b_i=0 if i is not in A and b_i=1 if i is in A.
Then f is an injection from F(N) to N.

That's quite nice, how about this method for F(R) to R...

1. Let A={a_0,a_1,a_2,...,a_n} where a_i is in R and a_1&lt;a_2&lt;...&lt;a_n
Then A is a unique expression of a finite subset of R.

We can map a given real number r onto an open range x..x+1 with the function: map(r,x) = atan(r)/pi + 1/2 + x.

let f(A) = the sum from k=0 to n of map(a_k,k)

then f is an injection from F(R) to R

Originally posted by iamatiger
1. Let A={a_0,a_1,a_2,...,a_n} where a_i is in R and a_1<a_2<...<a_n.
Then A is a unique expression of a finite subset of R.
We can map a given real number r onto an open range x..x+1 with the function: map(r,x) = atan(r)/pi + 1/2 + x. ...[text shortened]... om k=0 to n of map(a_k,k).
Then f is an injection from F(R) to R.

A={tan(2*pi/5),tan(3*pi/5)} and B={tan(pi/5),tan(4*pi/5)} are different sets in F(R).
But f(A)=2/5+1/2+0 + 3/5+1/2+1=3
and f(B)=1/5+1/2+0 + 4/5+1/2+1=3.

Here is an attempt at 2.
2. Let A={a_1,a_2,a_3,...,a_n} where a_i is in R and a_1&lt;a_2&lt;...&lt;a_n
Then A is a unique expression of a finite subset of N.
Let d_i be the number of digits before the decimal point in a_i.
Write each a_i as a decimal of the length max{d_i}, using preceding 0s if necessary.
Now, construct a number as follows:
Take digit 1 of a_1 followed by digit 1 of a_2 ... followed by digit 1 of a_n followed by digit 2 of a_1 followed by digit 2 of a_2 ... followed by digit max{d_i} of a_n followed by the '.' followed by digit max{d_i}+1 of a_1 ...
This gives you a real number f(A), but fails because you can just use the set B={f(A)} to get the same result!

2. Suppose you can do it.
Let f be an injection from F(R) to R.
Then B={y in R such that f(A)=y for some A in F(R)} is a subset of R.
So f is a bijection from F(R) to B.
Let g be the inverse of f.
Then g is a bijection from B to F(R).
Let X={y in B such that g(y) does not contain y}
Then X is a subset of B and is thus an element of F(R). [** Not true, since X may be an infinite subset of B! **]
Since g is a bijection, there is some x such that g(x)=X.
Suppose x is in X. Then g(x)=X contains x and so x cannot be in X.
Suppose x is not in X. Then g(x)=X does not contain x and so x is in X.
This is a contradiction, so such a function f cannot be an injection.

(Note. This proof was partly cribbed from http://pirate.shu.edu/projects/reals/infinity/proofs/cardpwst.html)

Edit - Ok, so this proof only works for power sets and not just the finite subsets.

Tip: if you prove 1, you have automatically proven 2, since N is a subset of R, and no surjection is asked.

Correction: IF it can be done of course. I mean, if X is overcountable, there are overcountable finite subsets (every subset with one element is included - these are overcountable). So 1 can't be done allways, I guess 😕.
But, my tip is still true 😀

Originally posted by sarathian
Both R & N are infinite sets. According to the conditions specified, F(R) and F(N) will be the power sets of R and N respectively. Why restrict F(X) to be only the set of finite subsets? For greater generality why not let F(X) be the set of all subsets of X whether finite or infinite?
The power set of any given set has higher cardinality ...[text shortened]... in a set) than the original set. Therefore there cannot exist any injection from F(X) into X.

I think you've answered your own question. Both 1. and 2. would clearly be impossible if I had said power sets rather than specifying finite subsets. garethn's answer to 1. is correct, but I don't think anyone has answered 2. yet. If someone does, here's a third question:

3. Suppose X is an infinite set. Must there exist an injection from F(X) to X?

Originally posted by piderman
Tip: if you prove 1, you have automatically proven 2, since N is a subset of R, and no surjection is asked.

Correction: IF it can be done of course. I mean, if X is overcountable, there are overcountable finite subsets (every subset wit ...[text shortened]... can't be done allways, I guess 😕.
But, my tip is still true 😀

Hmm, if my injection from F(R) to R does not produce an integer output from an integer input then I have automatically got an injection from F(N) to R, but I do not necessarily have an injection from F(N) to N do I? Equally, my injection method from F(N) to N may not be computable if I feed it a set of real numbers,

Originally posted by garethn
A={tan(2*pi/5),tan(3*pi/5)} and B={tan(pi/5),tan(4*pi/5)} are different sets in F(R).
But f(A)=2/5+1/2+0 + 3/5+1/2+1=3
and f(B)=1/5+1/2+0 + 4/5+1/2+1=3.

Eek! Back to the drawing board!

Originally posted by iamatiger
Hmm, if my injection from F(R) to R does not produce an integer output from an integer input then I have automatically got an injection from F(N) to R, but I do not necessarily have an injection from F(N) to N do I? Equally, my injection method from F(N) to N may not be computable if I feed it a set of real numbers,

Whoopsee. Read the question wrong. I thought it was a general problem, when in fact, it isn't 😳

Originally posted by garethn
2. Suppose you can do it.
Let f be an injection from F(R) to R.
Then B={y in R such that f(A)=y for some A in F(R)} is a subset of R.
So f is a bijection from F(R) to B.
Let g be the inverse of f.
Then g is a bijection from B to F(R).
Let X={y in B such that g(y) does not contain y}
Then X is a subset of B and is thus an element of F(R). [** Not true ...[text shortened]... wst.html)

Edit - Ok, so this proof only works for power sets and not just the finite subsets.

Wrong?

Let f(A) = { sqrt( |a|) for wich |a| is maximal in A}

f(A) is an element of [ 0, -&gt😉 so also a subset of R.

B = { y in R such that f(A) = y for some A in F(R)} is a subset of [ 0, -&gt😉 and thus a subset of R

f is NOT a bijection, for { -1, 0 } and { 0, 1} are placed on the same element of R under f.

Originally posted by iamatiger
That's quite nice, how about this method for F(R) to R...

1. Let A={a_0,a_1,a_2,...,a_n} where a_i is in R and a_1<a_2<...<a_n
Then A is a unique expression of a finite subset of R.

We can map a given real number r onto an open range x..x+1 with the function: map(r,x) = atan(r)/pi + 1/2 + x.

let f(A) = the sum from k=0 to n of map(a_k,k)

then f is an injection from F(R) to R

What's wrong with the simple mapping :
f(A) =a_1+a_2+.............+a_n?
After all the puzzle does not exclude many-to-one injection.
Different subsets having the same sum of elements will map to a common element. Does the puzzle exclusively rule out such mapping? I dont know if injection, by definition rules it out.

Originally posted by gamebitlover
What's wrong with the simple mapping :
f(A) =a_1+a_2+.............+a_n?
After all the puzzle does not exclude many-to-one injection.
Different subsets having the same sum of elements will map to a common element. Does the puzz ...[text shortened]... uch mapping? I dont know if injection, by definition rules it out.

Originally posted by Acolyte
(For those who don't know, an injection is a function f for which f(x) is different from f(y) whenever x is different from y.)

😛