4
$\begingroup$

Probably a really simple question:

I'm currently studying automata theory and I have come across the notation 2^S.

Wikipedia says it means the power set of S which is the set of all subsets of S including the empty set and S itself (S itself = all the elements in S).

This makes pretty good sense regarding the automata theory I'm reading about.

But I'm wondering whether the number, 2, is always the number to use, or if the number used depends on something. For instance, in my reading about automata theory, an alphabet like {0, 1} is being used and also on Wikipedia {0, 1} is being used. Also on Wikipedia it says the following: As "2" can be defined as {0,1}.

So does the number being used depend on the number of elements in the set/alphabet, or is it correct to always use the number 2?

$\endgroup$
  • $\begingroup$ It's simply notation. Many areas of maths seem to use $2^G$ to represent the power set of $G$. $\endgroup$ – Zestylemonzi Jul 28 '16 at 22:14
  • $\begingroup$ @Zestylemonzi It's not just notation. It is meaningful that a two is used. $\endgroup$ – Edward Evans Jul 28 '16 at 22:18
  • $\begingroup$ I agree that it is meaningful in certain cases - I'm just pointing out that there are many cases where the $2$ bares no relevance and is just notation that's carried over. $\endgroup$ – Zestylemonzi Jul 28 '16 at 22:23
10
$\begingroup$

In set theory, given two sets $A,B$, the notation $A^B$ is often used to denote the set of all functions $f : B \to A$.

So, as you say, if we take $2 = \{0,1\}$ then $2^S$ is the set of functions $f : S \to \{0,1\}$.

The connection with subsets is that there is a bijection between subsets $A \subset S$ and functions $f : S \to \{0,1\}$, where $A$ corresponds to $f$ if and only if $f$ is the "characteristic function" of $A$, meaning the function $$f(x) = \begin{cases} 1 & \quad\text{if $x \in A$} \\ 0 & \quad\text{if $x \not\in A$} \end{cases} $$

By the way, the origin of the equation $2 = \{0,1\}$ comes from Von Neumann's definition of the natural numbers, where $$0 = \emptyset, \,\, 1 = \{0\}, \,\, 2 = \{0,1\}, \,\, 3 = \{0,1,2\}, ... $$

$\endgroup$
3
$\begingroup$

The number 2 is used because there are $2^n$ subsets of a set of $n$ elements.

An often-used alternative notation for the power set of a set $G$ is $\mathcal{P}(G)$.

$\endgroup$
1
$\begingroup$

In set theory, $X^Y$ is the set of functions from the set $Y$ to the set $X$. Now, as you already noted, in the standard construction of the natural numbers, $2=\{0,1\}$, and thus $2^S$ is the set of functions from $S$ to the set $\{0,1\}$. Each such function can be interpreted as the indicator function $1_M$ of a subset $M$ of $S$ ($1_M(x)$ is $1$ for $x\in M$ and $0$ for $x\in S\setminus M$), and therefore there's a one-to-one correspondence between those functions and the subsets of $S$. This is the reason why often also the power set, the set of subsets, is denoted $2^S$.

Bases other than $2$ probably would not be useful in this context, except maybe $\omega^S$ for the set of multisets with underlying set $S$ (essentially, $\omega$ here is another notation for $\mathbb N$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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