# A calculus of the absurd

##### 21.2.3 Definition of predicate logic
###### 21.2.3.1 Syntax of predicate logic
• Definition 21.2.8 We begin by defining the syntax of predicate logic; we have:

• 1. “variables”, which we can denote as $$x_i \in \mathbb {N}$$ (in order to ensure that we have an infinite reserve of these), but we normally write using letters (e.g. $$a, b, u, w$$) as it is easier for (most) humans to understand these

• 2. “functions” such as $$f_{i}^{(k)}$$ (where $$i$$ is an index used to identify a specific function, and $$k$$ denotes the “arity”, aka number of arguments the function takes)

• 3. Predicates, in the form $$P_{i}^{(k)}$$

This is not a particularly interesting language - we would ideally be able to build more complex syntactically valid objects out of these simple ones we have defined. We define a “term” inductively (or recursively). A term (from a purely syntactical point of view) is defined as something in the form

$$f_{i}^{(k)}(t_1, t_2, ..., t_k)$$

This is all very well, but we would also like our terms to be finite (infinitely recursive pieces of language are not particularly pleasant). We must also, therefore, define a “base case” (i.e. some terms which are not defined in terms of other terms, so that it is at least possible for our terms to terminate). todo: finish this part (above)

We also define formulae, using these rules

• 1. $$P_i^{(k)}(t_1, ..., t_k)$$ is a formula,

• 2. If $$F$$ and $$G$$ are formulae, then so are $$\lnot F$$, $$F \land G$$ as well as $$F \lor G$$

• 3. If $$F$$ is a formula, then $$\forall x_i F$$ and $$\exists x_i F$$ are also formulae.

• Example 21.2.1 The formula (in Equation 21.18, below) is not valid.

$$P(x) \lor P(y, z) \label {invalid formula predicate logic}$$

Why? Because $$P$$ may not be a variadic function (i.e. it may not have more than $$k$$ terms as arguments) but it is constructed with one term ($$x$$) and also with two terms $$y, z$$ which is not valid.

• Example 21.2.2 A syntactically valid formula in propositional logic is

$$\forall x \forall y \forall z \Big (P(x, y) \land P(y, z) \rightarrow P(x, z)\Big ).$$

Of course, we have not yet defined what this formula means (beyond whether or not we may write it), for that we require semantics.

• Example 21.2.3 Another syntactically valid formula is

$$P(x, z) \lor \exists x \forall y Q(x, y, z).$$

We still have no idea what this means semantically, just that it is a valid formula.

###### 21.2.3.2 Free variables in predicate logic
• Example 21.2.4 Consider Example 21.2.3. We can draw this as a tree,

TODO: complete

• Definition 21.2.9 Continuing with example 21.2.3, we can make a substitution of $$x$$ for $$f(y, z)$$, which would give us

$$P(f(y,z), z) \lor ...$$

###### 21.2.3.3 Interpretations in predicate logic
• Example 21.2.5 Consider the formula

$$\forall x \Bigl (P(x) \lor P\big (f(x, a)\big )\Bigr ).$$

we can consider this in the universe $$\mathbb {N}$$, and define

$$p(x) = 1 \iff \text {x is even}$$

and further define

$$f(x, y) = x + y$$

and then fix $$a = 3$$, in which case we can ask is $$\mathcal {A}$$ a “model” for $$F$$. It is, as for every $$x$$, either $$x$$ is even, or $$x + 3$$ is even.

• Example 21.2.6 Consider the previous example, but with a different interpretation

\begin{align} & U = \mathbb {R} \\ & P(x) = 1 \iff x \geqq 0 \\ & f(x, y) = x \times y \\ & a = 2 \end{align}

In this case, $$B(A) = 0$$.

• Example 21.2.7 Is this a true statement:

$$\{F_1, F_2\} \text { is satisfiable} \iff F_1 \text { is satisfiable} \land F_2 \text { is satisfiable}?$$

This is not a true statement! If the right-hand side is true, this does not necessarily mean that the two separate interpretations, one for $$F_1$$ and one for $$F_2$$ are true for $$\{F_1, F_2\}$$.

This is analogous to the fact that

$$\exists x (F \land G) \not \equiv \exists x F \land \exists x G$$

is not true, as although the left-hand implies the right, the other way is not true.

• Example 21.2.8 A predicate logic interpretation. Let us return to the familiar formula

$$(\underline {A} \lor \lnot \underline {B}) \land (\underline {B} \lor \lnot \underline {C})$$

We would like to find an interpretation which makes this true.

For example, we could define $$\mathcal {A}$$ as

\begin{align} & \mathcal {A} = 0 \\ & \mathcal {B} = 1 \\ & \mathcal {C} = 0 \\ & \mathcal {D} = 1 \end{align}

But how would we define the value of

$$\mathcal {A}((F \land G)) = 1?$$

Here’s a sensible definition of what this means semantically

$$\mathcal {A}\Big ((F \land G)\Big ) = 1 \iff \mathcal {A}(F) = 1 \text { and } \mathcal {A}(G) = 1$$

This might seem in some way informal, but here’s the problem; at some point we will need to introduce some axioms.