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

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.

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.

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.

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 😀

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.

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,

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.

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

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.