Problem 1715

To prove that any decision function $f: \mathbb{A}^n \rightarrow \mathbb{A}$ can be represented as a composition of dictatoric and democratic functions, we will proceed through the following steps:

1. **Define the sets $A_c$ and $A_s$:**
- $\mathbf{x} \in A_c$ if $f(x_1, \mathbf{x})$ changes its value when $x_1$ changes its value.
- $\mathbf{x} \in A_s$ if $f(x_1, \mathbf{x})$ does not change its value when $x_1$ changes its value.

2. **Properties of $f$ over $A_c$ and $A_s$:**
- For any $\mathbf{x} \in A_c$, $f(0, \mathbf{x}) = 0$ and $f(1, \mathbf{x}) = 1$. Thus, $f(x_1, \mathbf{x}) = x_1$.
- If $\mathbf{x} \in A_c$, then $\overline{\mathbf{x}} \in A_c$. Similarly, if $\mathbf{x} \in A_s$, then $\overline{\mathbf{x}} \in A_s$.

3. **Case when $A_s = \emptyset$:**
- If $A_s = \emptyset$, then $f(x_1, x_2, \dots, x_n) = x_1$, which means $f$ is a dictatoric function.

4. **Case when $A_s \neq \emptyset$:**
- Define $f_s$ over $A_s$ as $f_s(\mathbf{x}) := f(0, \mathbf{x}) = f(1, \mathbf{x})$ for $\mathbf{x} \in A_s$.
- Note that $f_s$ is a decision function over $A_s$.

5. **Constructing a decision function $\varphi$ over $\mathbb{A}^{n-1}$:**
- Define $\varphi: \mathbb{A}^{n-1} \to \mathbb{A}$ as:
$$\varphi(\mathbf{x}) := \begin{cases} f_c(\mathbf{x}) & \text{if } \mathbf{x} \in A_c \\ f_s(\mathbf{x}) & \text{if } \mathbf{x} \in A_s \end{cases}$$
- Verify that $\varphi$ is a decision function:
- For part (a), since $A_c$ and $A_s$ are closed under negation, $\varphi$ changes its value if all arguments are negated.
- For part (b), consider the two cases:
1. If $\mathbf{x} \in A_s$, then substituting any coordinate of $\mathbf{x}$ with $f_s(\mathbf{x})$ does not leave $A_s$, so $\varphi$ remains unchanged.
2. If $\mathbf{x} \in A_c$, substituting any coordinate of $\mathbf{x}$ with $f_c(\mathbf{x})$ either keeps $\mathbf{x}$ in $A_c$ or moves it to $A_s$, in both cases $\varphi$ remains unchanged.

6. **Constructing the final decision function $f$:**
- Define $f_i: \mathbb{A}^{n-1} \to \mathbb{A}$ for $i = 2, 3, \dots, n$ as the corresponding sewing of $p_i$ over $A_c$ and $f_s$ over $A_s$.
- The final function $f$ can be represented as:
$$f(x_1, \mathbf{x}) = \text{Vote}_{2n-3}(x_1, x_1, \dots, x_1, f_2(\mathbf{x}), f_3(\mathbf{x}), \dots, f_n(\mathbf{x}))$$
where $x_1$ is taken $n-2$ times as an argument.

7. **Reduction of $\text{Vote}_{2k-1}$ to compositions of $\text{Vote}_3$:**
- For example:
$$\text{Vote}_{2k-1}(x_1, x_2, \dots, x_{2k-1}) = \text{Vote}_m(\text{Vote}_3(x_1, x_2, \text{Vote}_{2k-3}(x_3, \dots, x_{2k-1})), \dots)$$
where $m$ is either $k$ or $k+1$ depending on the parity of $k$.

By following these steps, we have shown that any decision function can be represented as a composition of dictatoric and democratic functions.

$\blacksquare$