21

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.

Willie Wong
  • 73,139
Rodnay
  • 313
  • 1
    $n\to{0,1}{}{}{}{}$ – Mikasa Aug 18 '14 at 08:12
  • 3
    $A^B$ denotes the set of all maps $B\to A$. Now set $2 = {0,1}$. – Daniel Fischer Aug 18 '14 at 08:12
  • 1
    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 '14 at 13:59
  • @Mikasa If you were to re-write the statement $\begin{pmatrix} n \implies \begin{Bmatrix} 0, 1 \end{Bmatrix} \end{pmatrix}$ in English, then what would the English words say? – Toothpick Anemone Mar 11 '23 at 15:01
  • @Mikasa There are many different notations in the world. Some people write $\begin{pmatrix} f: \mathbb{N} \implies \mathbb{R} \end{pmatrix}$ to indicate that $f$ is a function whose inputs are whole numbers such as 1, 2, 3 adn the outputs are decimal numbers such as $45.981$. However, I have never seen $\begin{pmatrix} n \implies \begin{Bmatrix} 0, 1 \end{Bmatrix} \end{pmatrix}$. MAybe $n$ is a whole number such as 1, 3, 7, etc. $\begin{pmatrix} n \implies \begin{Bmatrix} 0, 1 \end{Bmatrix} \end{pmatrix}$ looks like $\begin{pmatrix} 8 \implies \begin{Bmatrix} 0, 1 \end{Bmatrix} \end{pmatrix}$ – Toothpick Anemone Mar 11 '23 at 15:06

2 Answers2

24

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

Asaf Karagila
  • 393,674
  • 8
    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 '14 at 22:12
  • Please keep comments on-topic. Thanks. – Willie Wong Aug 19 '14 at 09: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 '14 at 09:25
  • Comments are not for extended discussion; this conversation has been moved to chat. – Alexander Gruber Aug 19 '14 at 23:43
  • Is there a mathematical term for this (given two sets A and B, taking the set of functions from B to A)? Can I say "the ... of A and B" (replace ... with an appropriate word)? – martinkunev Jun 18 '16 at 17:44
  • 1
    @martinkunev: "$A$ to the power of $B$", or "the set of functions from $B$ to $A$", depending on your context. – Asaf Karagila Jun 18 '16 at 18:01
9

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

Cm7F7Bb
  • 17,364
  • You might want to include @DanielFischers' comment to give motivation to this notation ;) – AlexR Aug 18 '14 at 08:13