- 11 Oct '04 15:47 / 1 editLet 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.) - 12 Oct '04 11:09 / 2 edits

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

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. - 12 Oct '04 12:26 / 2 edits

That's quite nice, how about this method for F(R) to R...*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.

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 - 12 Oct '04 13:14 / 1 edit

A={tan(2*pi/5),tan(3*pi/5)} and B={tan(pi/5),tan(4*pi/5)} are different sets in F(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.

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. - 12 Oct '04 13:25Here 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<a_2<...<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! - 12 Oct '04 13:59 / 1 edit2. 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. - 12 Oct '04 14:51 / 1 editTip: 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 - 12 Oct '04 16:37

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:*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.

3. Suppose X is an infinite set. Must there exist an injection from F(X) to X? - 12 Oct '04 17:23 / 1 edit

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 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 - 13 Oct '04 06:27

Whoopsee. Read the question wrong. I thought it was a general problem, when in fact, it isn't*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,** - 13 Oct '04 07:21

Wrong?*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.

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

f(A) is an element of [ 0, -> 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, -> 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. - 14 Oct '04 13:53

What's wrong with the simple mapping :*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

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. - 14 Oct '04 15:32 / 1 edit
*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.)**