Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $ D = 2^\mathbb{N} $, i.e., D is the set of all sets of natural numbers.

What's the meaning of this definition? Intuitively, I would suggest that $ D = \{1,2,4,...\} $ but the explanation "set of all sets" leads me to the guess that this is wrong.

share|improve this question
    
$n\to\{0,1\}{}{}{}{}$ –  Babak S. Aug 18 at 8:12
2  
$A^B$ denotes the set of all maps $B\to A$. Now set $2 = \{0,1\}$. –  Daniel Fischer Aug 18 at 8:12
    
Further to Asaf's comment: >In some parts of set theory where this notation can be confused with other types of exponentiation, you can see the notation $^BA$ used instead. Thanks for pointing this out, Asaf. To avoid any anomalies, you may indeed want to distinguish set exponentiation from, say, exponentiation on the natural numbers when it is defined only as repeated multiplication. –  Dan Christensen Aug 19 at 13:59

2 Answers 2

up vote 10 down vote accepted

We write $A^B$ as the set of all functions $f\colon B\to A$. Namely $f$ is a function whose domain is $B$ and takes values in $A$.

In this case $A=\{0,1\}$ and $B=\Bbb N$. So this is the set of all functions from $\Bbb N$ into $\{0,1\}$. If we think about those as indicator functions then we have a natural way of thinking about $2^\Bbb N$ as the power set of $\Bbb N$, also denoted by $\mathcal P(\Bbb N)$, which is the set of all subsets of $\Bbb N$.

(In some parts of set theory where this notation can be confused with other types of exponentiation, you can see the notation ${}^BA$ used instead.)

share|improve this answer
3  
Just to add to this nice answer: The reason that we use the exponential notation $A^B$ to denote the set of all functions $f:B\rightarrow A$ derives from the fact that the size of this set $A^B$ is, in finite cases, indeed given by exponentiation: $|A^B| = |A|^{|B|}$. We can even take this as the definition of exponentiation, providing an understanding of exponentiation that works even for infinite cardinal numbers. –  Matt Aug 18 at 22:12
    
Please keep comments on-topic. Thanks. –  Willie Wong Aug 19 at 9:14
    
@Matt: I think even in the absence of the other discussion your addendum is very on-topic (since this is a question about a notation after all). –  Willie Wong Aug 19 at 9:25
    
Comments are not for extended discussion; this conversation has been moved to chat. –  Alexander Gruber Aug 19 at 23:43

A power set $\mathcal P(S)$ of a set $S$ is sometimes denoted $2^S$. If $S$ is a finite set with $|S| = n$ elements, then the number of subsets of $S$ is $|\mathcal P(S)|=2^n$. This is the motivation for the notation $2^S$.

share|improve this answer
    
You might want to include @DanielFischers' comment to give motivation to this notation ;) –  AlexR Aug 18 at 8:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.