Is the set of finite subsets of N in bijection with N?

Is the set of finite subsets of N in bijection with N?

Other urls found in this thread:

en.wikipedia.org/wiki/Power_set#Properties
proofwiki.org/wiki/Set_of_Finite_Subsets_of_Countable_Set_is_Countable
twitter.com/SFWRedditGifs

no

en.wikipedia.org/wiki/Power_set#Properties

errr now that i read 'finite' subsets i take that back

Whats a finite subset? Sry 4 pleb

proofwiki.org/wiki/Set_of_Finite_Subsets_of_Countable_Set_is_Countable
math.stackexchange.com/questions/200389/show-that-the-set-of-all-finite-subsets-of-mathbbn-is-countable

Thoughts:
A set of n elements has [math] \binom{n}{k} [/math] subsets of size k.

E.g., for {1,2,3,4} we have [math] \binom{4}{2} = 4!/(2!·2!) = 6 [/math], namely:
{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}

I think it's countable because of the following construction.

n=zero
1 -> {}

n=one
2 -> {}
3 -> {1}

n=two
4 -> {}
5 -> {1}
6 -> {2}
7 -> {1,2}

n=three
... -> {}
... -> {1}
... -> {2}
... -> {3}
... -> {1,2}
... -> {1,3}
... -> {2,3}
... -> {1,2,3}

n=four
...

This covers all subsets, although not surjectively.

In the other direction, map {m} to m.

So if you have two surjections in both directions, you should have a bijection? I think that's a nontrivial claim, though, formally speaking. I remember something

lets first proove that for n in N the set of subsets of N with n elements is countable(lets call such sets Cn), if we have that, we are done since the subset of finite subsets of N is a countable union of such sets Cn and if those are countable, the union is.
We use induction:
for n=1 we have nothing to prove since we essentially get N
for n|->n+1 we can find a surjective map f from B:=( (Cn x N) \ { ({a1,...,an},k) in (Cn x N)| k=ai for i in {1,...,n} } )
to Cn+1: f({a1,...,an},k)={a1,....,an,k}
B is a countable subset of a countable set and therefore countable, therefore we get a surjective map from N to Cn+1 (N->B->Cn+1).
I think this should suffice if I didn't make any mistake(which isn't that unlikely).

There is probably a way way easier way to proove this but I am too stupid for it

>So if you have two surjections in both directions, you should have a bijection? I think that's a nontrivial claim, though, formally speaking. I remember something

Schroeder-Bernstein is what you're thinking of

Your first argument is a little loose btw. Why map into say the empty set multiple times?

My intuitive idea was basically proof 1 on proofwiki.

i am in community college algebra 1 but isnt the set of subsets of N always greater than the sum of NBA basketball?

>Schroeder-Bernstein is what you're thinking of
Thx!

>Your first argument is a little loose btw.
Yeah, it's not supposed to be a proof, just
>Thoughts

>Why map into say the empty set multiple times?
I wanted to write down a systematic map, and a surjection at that

Those are all nice proofs that the finite subsets of N, call them F, are countable. I.e. they proof that you can injectively map F to N.

But nobody there constructs a bijection. The map to the prime powers, for example, needs you to order the sets first and thus leaves out numbers.
{5,6,9}
will be mapped to
p_1^5 · p_2^6 · p_1^9
but the number
p_1^9 · p_2^6 · p_1^5
is not in the range of this map.