0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Thank you, I've seen and used all the other notations you have mentionned but I have never met the powerset one, this is quite enlightning! $\endgroup$
    – DatCorno
    Commented Jun 16, 2020 at 14:57
  • 2
    $\begingroup$ "Now there is no ambiguity" is always optimistic in mathematics. :-) I'd argue that there's some ambiguity even in $\{0, 1\}^n$, since some authors use just $n$ for $\{0, \dotsc, n - 1\}$ (in accord with the von Neumann construction), so it could equally be interpreted as a function space. This is the same trick as one plays when using $2$ for $\{0, 1\}$, as in $2^{[n]}$; and, of course, the apotheosis of this sort of notation would be writing $2^n$ for a power set, with the consequence that $\lvert2^n\rvert = 2^n$, which is a true statement in both set theory and real arithmetic …. $\endgroup$
    – LSpice
    Commented Jun 16, 2020 at 16:28

Not the answer you're looking for? Browse other questions tagged .