This question already has an answer here:

Strange set notation (a set as a power of 2)?

2 answers

I have an exercise that involves this set: 2N2^\mathbb{N}, but I don’t know what set it is. I know that the elements of the set are functions whose domain is N\mathbb{N}, but no idea which type of functions they are.

Thanks in advance.

=================

=================

3 Answers

3

=================

2N2^\mathbb{N} can mean the power set of N,\mathbb{N}, which is the set of all subsets of N.\mathbb{N}.

2N2^\mathbb{N} can also mean the set of all functions from N\mathbb{N} to {0,1}.\lbrace 0, 1 \rbrace. (In set theory, 22 is taken to mean the set {0,1}.)\lbrace 0, 1 \rbrace.)

These two sets have a canonical bijection between them.

2N2^\Bbb N is another notation for P(N)\mathcal P(\Bbb N) which is the power set of the natural numbers; the set of all subsets of the natural numbers.

To generate a subset you decide which elements of the set to include. This decision is basically a function mapping the set to {0,1}\{0, 1\} (don’t or do include).

Thus the set of subsets is bijective with a set of all such functions, and 2N2^\Bbb N can also be used as a notation for this.

2N≡{f∣f:N↦{0,1}}2^\Bbb N \equiv \{ f\mid f:\Bbb N\mapsto \{0,1\}\}

Which leads to similar notations such as:

3N≡{f∣f:N↦{0,1,2}}3^\Bbb N \equiv \{ f\mid f:\Bbb N\mapsto \{0,1,2\}\}

In set theory, if AA and BB are sets, ABA^B (sometimes written BA^BA) is the set of all functions f:B→A.f:B\to A. To interpret 2N2^\mathbb N you have to know what sets N\mathbb N and 22 are. N\mathbb N is either the set of all positive integers or the set of all nonnegative integers, depending on what book you’re using. If 22 is a set, it’s probably the set {0,1}.\{0,1\}. So 2N2^\mathbb N is the set of all infinite sequences of zeros and ones.