Lesson 11

Proof. [Proof of Post's theorem.] It is not difficult to see that all functions defined by connectives from any pre-complete class are themselves in that pre-complete class: if you only combine, for example, monotone functions, you get a monotone function (and the same holds for all five classes). Furthermore, none of the pre-complete classes coincide with the class of all functions: of course, there are functions that are not monotone (and this is true for all five classes). Therefore, the statement is proven in one direction. Now let's prove it in reverse.

Consider a function \(f \not \in \mathcal{S}_{0}\), which does not preserve zero, and substitute the same variable \(x\) for all its arguments: \(g(x)=f(x,\dotsc,x)\). Since \(f(0,\dotsc,0)=1\), we have \(g(0)=1\). There are only four functions of one variable: \(0\), \(1\), \(x\), \(\overline{x}\). Thus, \(g(x)\) is either the negation function \(\overline{x}\) or the constant \(1\). Similarly, taking a function \(f \not \in \mathcal{S}_{1}\), which does not preserve one, we get either the negation function \(\overline{x}\) or the constant \(0\). Thus, we either have two constants or negation. Now let's consider two cases.

1. Suppose we don't have negation yet. Then we already have two constants. We will then construct negation from the constants and a non-monotone function \(f \not \in \mathcal{M}\). For some set of input values, \(f\) decreases when one of the coordinates increases. We will substitute the necessary constants for all the other coordinates (since we already have them!) and obtain negation.

   Here’s an example. Let \(f \in B_{5}\) and \[f(1,1,0,1,1)=0, \quad f(0,0,0,1,0)=1 \ .\] We start increasing the coordinates of the second assignment one by one to gradually approach the first assignment: \[00010 \to 10010 \to 11010 \to 11011 \ .\] At some point, the function value will change from one to zero. Thus, we get two sets \(x \ge y\) differing in only one coordinate (\(x_{i}=1\), \(y_{i}=0\)), such that \(f(x)=0\) and \(f(y)=1\). We substitute constants for all other variables. We get a function \(g\) of one variable, such that \(g(1)=0\) and \(g(0)=1\). This is negation.

2. Suppose we already have negation. We will then construct both constants from negation and a non-self-dual function \(f \not \in \mathcal{D}\). For some input values, it holds that \(f(c_{1}, \dotsc, c_{n})=f(\overline{c}_{1}, \dotsc, \overline{c}_{n})\). Let \[h(x)=f(x \oplus c_{1}, \dotsc, x \oplus c_{n}) \ .\] Then \[h(0)=f(c_{1}, \dotsc, c_{n})=f(\overline{c}_{1}, \dotsc, \overline{c}_{n})=h(1)\ ,\] so \(h\) is a constant function. We get the second constant via negation.

   Here’s an example. Let \(f(0,1,0)=f(1,0,1)\). Consider the function \(g(x)=f(x, \overline{x}, x)\). Then \(g(0)=f(0,1,0)=f(1,0,1)=g(1)\). Therefore, \(g\) is a constant.

We know that the function \(f_{11}\) is not identically zero (otherwise, we wouldn't have the monomial). We substitute values for all other variables so that \(f_{11}\) becomes one. Thus, the function \(f\) reduces to a function of \(x_{1},x_{2}\) of degree two: \[x_{1}x_{2} \oplus c_{1}x_{1} \oplus c_{2}x_{2} \oplus c_{0} \ .\] If \(c_{0}=c_{1}=c_{2}=0\), then \(x_{1}x_{2}\) is already a conjunction. If \(c_{0}=1\), we can make \(c_{0}=0\) using negation. If, for example, \(c_{1}=0, c_{2}=1\), the function becomes \[x_{1}x_{2} \oplus x_{2}=(x_{1} \oplus 1)x_{2} = \overline{x_1}\land x_{2}\ ,\] so the conjunction can be obtained using negation and this function.

The case of \(c_{1}=c_{2}=1\) can be handled similarly. As a result, we obtain conjunction (or disjunction by De Morgan’s law). Thus, the reverse statement is also proven.◼