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

no

https://en.wikipedia.org/wiki/Power_set#Properties

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

>>8731211
Whats a finite subset? Sry 4 pleb

https://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

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

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

>>8731252
>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

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

>>8731272
If you can find a can find a surjective map from N to an infinite set OR an injective map from an infinite set to N, there exists a bijective one. In other words, all countably infinite sets are in bijection. Unless your issue is that you want an explicit one, in that case I got no idea how to construct one.

>>8731211
The easiest bijection I can think of looks as follows:
Consider the naturals in binary. If the [math]n[/math]-th digit (counting from the right) is [math]1[/math], include it in the set, if it is [math]0[/math], don't.
As such, for example, [math]19=10011_2[/math] would map to [math]\{1,2,5\}[/math].

>>8731272
Explicit bijections between infinite sets are usually hard to make. That's why Schroeder-Bernstein is such a big deal.

>>8731286
I like this one.

>>8731286
Ah, yes that works. Here we can e.g. write
2^7 + 2^5
as
2^5 + 2^7
and thus we never get into the ordering issue that the prime listings with p_k have

>>8731290
Okay, that's the theorem for injections in both directions. So with m->{m} there's an injection and we can use it to "get" some bijection (like some kind of math deity :)

So new related question:
Q: Is a countable infinite set necessarily in bijection with the natural numbers?
countable infinite like [math] {\mathbb Q} [/math] (which is in bijection with [math] {\mathbb N}\times {\mathbb N} [/math]) can bijectively mapped to [math] {\mathbb N} [/math] and the same is true for [math] {\mathbb N}^n [/math] for any n.
The set [math] {\mathbb N}^{\mathbb N} [/math] is not countable and not in bijection with [math] {\mathbb N} [/math].
But is ANY countable infinite set necessarily in bijection with the natural numbers?

>>8731317
yes, I already said so earlier: >>8731283
, also countably infinite can (and oftentimes is) defined as "in bijection with N"

>>8731322
sure, you said it in this post
...but I can also say that the Riemann hypothesis is true :>

>>8731326
sigh, then define countably infinite for me since I know it as in bijection with N, is it there exists a surjective map from N to X or an injective one from N to X?

>>8731317
>But is ANY countable infinite set necessarily in bijection with the natural numbers?

That's literally the definition of countably infinite

>>8731331
>>8731337

>B is finite
there exists an m in N so that there exists a bijection between B and {1,...,m}

>A is infinite
A is not finite

>countable A
there exists an injection from A to N

>>8731364
ok so we have f:A->N injective so |A|<=|N|
lets assume there is a smaller infinity than |N|
(otherwise we are done)
B:=Im(f) is a subset of N and has to be infinite since it is in Bijection with A.
(B,<) is an well-ordered( I dunno the english word, there exists one "next" element for each element) set and has a smallest element since it is a subset of N, so we can find a map g:N->B which is bijective if we map 1 to the smallest element and 2 to the next and so forth, per construction it is injective and we know it has to be surjective since we already have |N|>=|B|
so |N| is the smallest infinity

Damn this is terribly dirty, I should clean it up but I am too lazy now

>>8731211
Easy. Imagine successive binary numbers written under the natural numbers. 1s are included under the set
>t. cs pajeet

>>8731384
No... that is a trick for counting the cardinality of this set of subsets, where the cardinality is the number of different binary strings of that length. So in this case it's 2^(cardinality of N)

t. CS person who isn't a retard