[Math] Representing predicate logic as arithmetic

arithmeticlogicmodular arithmeticpredicate-logicpropositional-calculus

Summary

Since the below is quite long, I thought I'd add this summary.

Given the following:

The question: is it possible to apply these ideas to predicate logic as well? How? Or, why not?

Original question

Disclaimer: I'm not a mathematician so possibly the following concepts are wrong or boring. Also this might be long.

Representing Propositional Logic as Arithmetic

I've been spending some time looking at how to represent logical statements as arithmetic expression modulo 2, with $0$ representing 'false' and $1$ representing 'true'. For proposition logic, this is not so hard. For example:

$$
a \wedge b \Rightarrow a \times b \text{ (mod 2)} \\
a \vee b \Rightarrow a + b + ab \text{ (mod 2)} \\
\neg a \Rightarrow a + 1 \text{ (mod 2)} \\
a \rightarrow b \Rightarrow 1 + a + ab \text{ (mod 2)}
$$

Examples

Using these rules, any statement in proposition logic can be represented as an arithmetic expression. For instance,

$$
a \vee b \rightarrow \neg ( \neg a \wedge \neg b ) \tag{1}
$$

is converted through

$$
a \vee b \rightarrow \neg ( \neg a \wedge \neg b ) \\
1 + (a \vee b) + (a \vee b)(\neg ( \neg a \wedge \neg b )) \\
1 + (a + b + ab) + (a + b + ab)(\neg ( \neg a \wedge \neg b )) \\
1 + (a + b + ab) + (a + b + ab)(( \neg a \wedge \neg b ) + 1) \\
1 + (a + b + ab) + (a + b + ab)(( (\neg a)(\neg b)) + 1) \\
1 + (a + b + ab) + (a + b + ab)(( (a + 1)(b + 1)) + 1) \\
$$

Under modulo 2 this reduces to $1$, or 'true', indicating that the original logical statement is a tautology, which is indeed the case. As another example, $a \rightarrow (a \wedge b)$ reduces to $1 + a + ab$ or $a \rightarrow b$, which is also correct.

Representing Predicate Logic as Arithmetic

As shown these rules can be used to simplify proposition-logical statements and to check tautologies. Now I'm trying to extend to predicate logic. To find matching arithmetic operators for the quantifiers is not very difficult: (assume $x$ as shorthand for $x \in X$ with $X$ some set)

$$
\forall x, P x \Rightarrow \prod_x P x \\
\exists x, P x \Rightarrow ( \prod_x P x + 1 ) + 1
$$

Alternatives using sums rather than products:

$$
\forall x, P x \Rightarrow 2^{\sum_{x} P x + 1} \\
\exists x, P x \Rightarrow 2^{\sum_{x} P x} + 1
$$

Note that these alternatives only work if $\forall x, Px \in \{0,1\}$, which is a deviate from the rules for proposition, which work regardless (only the parity of the atomic statements matters). Because of this I don't feel sure that these equations using sums are the best solutions, so I've been utilizing the ones using products.

Examples

We can use these rules to represent a statement in predicate logic in arithmetic form. For example:

$$
(\exists x, P x) \rightarrow \neg (\forall x, \neg P x)
$$

This is the predicate equivalent of propositional statement 1. It's also a tautology. Writing it as arithmetic using the given rules results in:

$$
(\exists x, P x) \rightarrow \neg (\forall x, \neg P x) \\
1 + (\exists x, P x) + (\exists x, P x)(\neg (\forall x, \neg P x)) \\
1 + ((\prod_x \neg P x) + 1) + ((\prod_x \neg P x) + 1) ((\prod_x \neg P x) + 1) \\
1 + ((\prod_x P x + 1) + 1) + ((\prod_x P x + 1) + 1) ((\prod_x P x + 1) + 1) \\
$$

Again, this reduces to $1$ under modulo 2, though this is a trivial example because we defined the arithmetic versions of $\exists x, P x$ and $\neg (\forall x, \neg P x)$ to be equal. A more complex case:

$$
(\forall x, P x \rightarrow Q x) \wedge (\exists x, P x) \rightarrow (\exists x, Q x) \tag{2}
$$

Conversion yields:

$$
1 + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1) + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1)((\prod_x Q x + 1) + 1) \tag{3}
$$

This is where I get stuck and where my question lies. I haven't found a way to reduce this to $1$, as it should. I have since, see update below.

Reducing Multiplied Products

I did find the following:

$$
(\prod_{x \in X} P x)(\prod_{x \in X} Q x) = \sqrt{ \prod_{x \in X} \prod_{y \in X} P x Q y } \tag{4}
$$

More generally:

$$
\underbrace{(\prod_{x \in X} P x)(\prod_{x \in X} Q x) \ldots (\prod_{x \in X} R x)}_{n\text{ products over }n\text{ predicates}} = \sqrt[2^{n-1}]{ \underbrace{ \prod_{x \in X} \prod_{y \in X} \ldots \prod_{z \in X} }_{n\text{ products}} \underbrace{ P x Q y \ldots R z }_{n\text{ predicates}} }
$$

(that is the $2^{n-1}$th root)
Since the further reduction of expression 3 results in many multiplied products, I thought this would come in handy. However, it did not help me yet, especially because the different variables introduced ($x$, $y$, $z$, …), although iterating over the same set, cannot be interchanged (that is, $PxPy \ne (Px)^2$, which would help a lot in reducing the expression). See update below for new thoughts on this.

The Question

This is where I am at so far. My question is: how can I represent any predicate logic statement as arithmetic, just like I can do with any proposition logic statement, such that I can reduce them and find tautologies? (in particular statement 2, update: done this, see below for continued questions) Is this at all possible? If not, why? Are any of my assumptions or earlier findings in fact wrong? Any feedback is appreciated!

Furthermore, is such a representation/reduction to arithmetic possible for all higher-order logic? Why (not)?

Thanks in advance!!

Update: Multiplied Products Revisited

I've been working on this some more and I realized two things, the second of which enabled me to make some progress.

Root of Products

Firstly, I realized that for $a \in \{0,1\}$:

$$
\sqrt{a} = a \text{ (mod 2)}
$$

This means that the statment in equation 4 can be further simplified to:

$$
\prod_{x \in X} \prod_{y \in X} P x Q y
$$

Simplified Multiplied Products

This led me to realize that in fact, the following simplification is possible:

$$
(\prod_{x \in X} P x)(\prod_{x \in X} Q x) = \prod_{x \in X} P x Q x
$$

Logically this makes sense, because of course, if for all $x$, $P x$ is true, and also for all $x$, $Q x$ is true, then for all $x$, $P x$ and $Q x$ are true.

Knowing this allows us to simplify statement 2 down to the value $1$:

$$
(\forall x, P x \rightarrow Q x) \wedge (\exists x, P x) \rightarrow (\exists x, Q x) \tag{2}
$$
$$
1 + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1) + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1)((\prod_x Q x + 1) + 1) \tag{3}
$$
$$
1 + (\prod_x 1 + P x + P x Q x)(\prod_x Q x) + (\prod_x 1 + P x + P x Q x)(\prod_x P x + 1)(\prod_x Q x + 1) \\
1 + (\prod_x (1 + P x + P x Q x)(Q x)) + (\prod_x (1 + P x + P x Q x)(P x + 1)(Q x + 1)) \\
1 + (\prod_x 1 + P x + Q x + P x Q x) + (\prod 1 + P x + Q x + P x Q x) \\
1 + 2(\prod_x 1 + P x + Q x + P x Q x) \\
1
$$

(that last step works because $2a = 0 \text{ (mod 2)}$)

As another example: $(\forall_x, P x \rightarrow Q x) \rightarrow (\exists_x, Q x)$ is simplified to $(\prod_x P x + Q x + P x Q x + 1) + 1$, or $\exists_x, P x \vee Q x$. Although unintuitive (to me), truth tables show that these two logical formulas are in fact equivalent.

The Question Remains

So that's pretty neat, some predicate statements can now be simplified and checked for tautologies. However, this trick does not work for all statements. For example the following statement:

$$
\forall_x, \forall_y, R(x,y)
$$

Here, the two introduced variables $x$ and $y$ have some interaction. The statement cannot be pulled apart and written in the form $(\forall_x, \ldots)(\forall_x, \ldots)$. It seems that, when there is "interaction" between the variables, the multiplication trick can not be applied, as something like $\prod_x R(x,x)$ would not be equivalent.

I am now focusing on trying to reduce the following statement to $1$ (as it should):

$$
(\exists_x, \forall_y, R(x,y)) \rightarrow (\forall_x, \exists_y, R(y,x)) \tag{5}
$$

My original question remains, but now aimed at statement 5.

Best Answer

You have discovered the same problem that Kracht discusses in "The Mathematics of Language", chapter 4, section 5, the variable $y$ is dependent on $x$ in the sentence $(\forall x, \exists y(x), R(y(x),x))$. (Kracht does not originate this observation; this is just a discussion of the difficulty which I have read.)

You appear to be re-inventing the bijection between Boolean rings and Boolean algebras. See the English Wikipedia's Boolean Algebra:Boolean Rings for the discussion of this bijection and statements of your initial formulas. That section also references Hsiang's (1985) algorithm for testing formula equivalence (of which your particular problems are a specilization -- you wish to verify that your formulas are equivalent to $1$) as well as the paper by Boudet, Jouannaud, and Schmidt-Schauß (1989). That section also indicates that these results are relevant for automated theorem proving. So this appears to be well-travelled ground.

The English Wikipedia section Automated Theorem Proving:Decidability of the Problem gives some insight into the feasibility of this method (more accurately into the time feasibility of all known methods, including this one). Although the guarantees for arbitrary problems are weak (exponential running times or unbounded running times for propositional logic and predicate calculus, respectively), practical results are not so pessimistic.

Related Question