I am currently reading *Boolean Function Complexity - Advances and Frontiers* by Stasys Jukna and on page 7 of the latest edition there is a paragraph titled **Boolean functions as set systems** with the following quote:



> 
> By identifying subsets $S$ of $[n] = \{1, \cdots, n\}$ with their characteristic $0–1$ vectors $v\_S$, where $v\_S(i) = 1$ iff $i \in S$, we can consider boolean functions as set-theoretic predicates $f: 2^{[n]} \longrightarrow \{0, 1\}$.
> 
> 
> 


Now, I have never seen the notation $2^{[n]}$ before and I am not sure how to interpret it. I have looked into the notation section of the book but there is no mention of that particular usage. If anyone could help me, it would most appreciated.



Unknown notation in "Boolean function complexity" by Stasys Jukna
The notation $[n]$ is an $n$-element set of integers. Usually, it means $[n] = \{1,2,\ldots,n\}$, but sometimes it goes from 0 to $n-1$ (this will basically never matter, and just assume it’s the first one).


In general, $2^{S}$ could mean either the powerset of $S$ (i.e., all the subsets of $S$), or could mean the set of functions mapping from $S$ to the set $\{0,1\}$. People use these interchangeably via characteristic functions as in your quote.


People also call $2^{[n]}$ the $n$-cube or the Boolean cube. It’s just the collection of subsets of $[n]$.


You’ll know what folks mean by the surrounding notation (if ever unsure).


For instance, $A \in 2^{[n]}$ would suggest that $A$ is a set (since it’s a capital letter near the beginning of the alphabet), so in this context, $2^{[n]}$ seems to be the set of subsets of $[n]$.


On the other hand, if someone wrote $\forall f \in 2^{[n]}$, I would say this must be referring to the collection of functions. But this second notation is sort of odd.


Let me spice it up once more!


Say $\Omega = \{0,1\}^n$ (now there is no ambiguity since the exponent is a number. This must be the collection of length $n$ strings consisting of $0$’s and $1$’s) Then $\Omega$ is also called the Boolean cube and there’s a natural correspondence between these vectors, subsets of $[n]$ and functions from $[n]$ to $\{0,1\}$. The corresponding vector is called the “characteristic vector” of the corresponding set.


Then we can say things like $f : \Omega \to \{0,1\}$, which is saying $f$ is a function that takes 01-strings of length $n$ and outputs a value of 0 or 1. (I.e., $f$ is a “boolean function”).


Good luck with it all. You’ll get the hang of it soon enough, I’m sure!


**Added:**


By the way, looking at your quote, I’m guessing boolean functions were defined as mapping from strings (aka vectors) to $\{0,1\}$, i.e., maps from $\Omega$ (as above) to $\{0,1\}$. And the author is using $2^{[n]}$ to mean the collection of subsets of $[n]$. So the author’s point is that instead of viewing the inputs as strings, you could view them as sets, and in that way you could say boolean functions take in a subsets of $[n]$, and they spit out a number.


**Example:**


Say $n=3$, and $f(x\_1 x\_2 x\_3) = x\_3$ [this is called a dictator function, since the output is determined by only one bit of the input string (they like social choice metaphors)].


Then a string like $011$ corresponds to the set $\{2,3\}$ (where the $011$ can be interpreted as describing a set one element at a time as “it’s missing 1, it contains 2, it contains 3”).


Then viewed a function on sets the same map $f$ would be $f(S) = \begin{cases} 1, \qquad \text{if $3 \in S$}\\ 0, \qquad \text{otherwise}\end{cases}$.


