0

Domains, Parses, and Power Sets

$$\big|\{\bar{\alpha}^{2^n}\}\big|=\big|2^{\{\textbf{A}^n\}}\big|\ni(\textbf{A}^n)_\alpha$$

This proof starts by defining a set of input variables to some truth function $\alpha$. $$\mathbb{A}=\{A_0,\ldots,A_{n-1}\}\ni(\textbf{A}^n)_\alpha$$ Now, consider some subset thereof, such that the presence of a variable is defined a condition value of the domain $\textbf{A}^n$. That is, if the condition value requires a variable to be equal to one, then that variable is part of the subset. $$\mathbb{B}_x=\{A_i\big|(\textbf{A}^n)_\text{CV}=x\Rightarrow A_i=1\}$$ In this way the power set of $\mathbb{A}$ is created using every condition value of $\textbf{A}^n$. $$2^\mathbb{A}=\{\mathbb{B}_0,\ldots,\mathbb{B}_{2^n-1}\}$$

Now, since each parse of the function $\alpha$ is associated with a unique condition value, there is a one-to-one mapping between each parse and the subset defined by the same condition value. $$\forall x(\mathbb{B}_x\mapsto\alpha_x)$$ Therefore, the set of all parses of $\alpha$ has the same cardinality as the power set of $\alpha$'s domain. $$\big|\{\bar{\alpha}^{2^n}\}\big|=\big|2^{\{\textbf{A}^n\}}\big|$$

Corollary: If the cardinality of $\alpha$'s input variables is some aleph number, then, by the definition of aleph numbers, the cardinality of $\alpha$'s parses will be the subsequent aleph number. $$\big|\{A_0,\ldots,A_{n-1}\}\big|=\aleph_n\Rightarrow\big|\{\alpha_0,\ldots,\alpha_{2^n-1}\}\big|=\aleph_{n+1}$$

Corollary: Since the cardinality of the set of a function's parses is greater than the cardinality of the set of that function's input variables, it is not possible for all of a function's parses to be the input variables to that function. $$(\bar{\alpha}^{2^n})_\alpha\text{ is not possible}$$

Next >