A calculus of the absurd

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

\begin{equation} f_{i}^{(k)}(t_1, t_2, ..., t_k) \end{equation}

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.

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

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

\begin{equation} \forall x \forall y \forall z \Big (P(x, y) \land P(y, z) \rightarrow P(x, z)\Big ). \end{equation}

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

\begin{equation} P(x, z) \lor \exists x \forall y Q(x, y, z). \end{equation}

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

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

\begin{equation} P(f(y,z), z) \lor ... \end{equation}

Example 21.2.5 Consider the formula

\begin{equation} \forall x \Bigl (P(x) \lor P\big (f(x, a)\big )\Bigr ). \end{equation}

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

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

and further define

\begin{equation} f(x, y) = x + y \end{equation}

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:

\begin{equation} \{F_1, F_2\} \text { is satisfiable} \iff F_1 \text { is satisfiable} \land F_2 \text { is satisfiable}? \end{equation}

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

\begin{equation} (\underline {A} \lor \lnot \underline {B}) \land (\underline {B} \lor \lnot \underline {C}) \end{equation}

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

\begin{equation} \mathcal {A}((F \land G)) = 1? \end{equation}

Here’s a sensible definition of what this means semantically

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

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