# tautologies in predicate logic

Let FO$(\Sigma)$ be a first order language over signature   $\Sigma$. Recall that the axioms for FO$(\Sigma)$ are (universal  ) generalizations  of wff’s belonging to one of the following six schemas:

1. 1.

$A\to(B\to A)$

2. 2.

$(A\to(B\to C))\to((A\to B)\to(A\to C))$

3. 3.

$\neg\neg A\to A$

4. 4.

$\forall x(A\to B)\to(\forall xA\to\forall xB)$, where $x\in V$

5. 5.

$A\to\forall xA$, where $x\in V$ is not free in $A$

6. 6.

$\forall xA\to A[a/x]$, where $x\in V$, $a\in V(\Sigma)$, and $a$ is free for $x$ in $A$

where $V$ is the set of variables and $V(\Sigma)$ is the set of variables and constants, with modus ponens  as its rule of inference  : from $A$ and $A\to B$ we may infer $B$.

Call a wff of FO$(\Sigma)$ quasi-atom if it is either atomic, or of the form $\forall xA$, where $A$ is a wff of FO$(\Sigma)$. Let $\Gamma$ be the set of all quasi-atoms of FO$(\Sigma)$.

###### Proposition 1.

Every wff of FO$(\Sigma)$ can be uniquely built up from $\Gamma$ using only logical connectives $\to$ and $\neg$.

###### Proof.

Induction  on the complexity of wff. For any wff $A$ of FO$(\Sigma)$, it has one of the following forms: $B\to C$, $\neg B$, or $\forall xB$, where $B,C$ are wff’s. If $A$ were $B\to C$ or $\neg B$, by induction, since $B$ and $C$ were in $\Gamma$, $A$ is in $\Gamma$ as a result. If $A$ were $\forall xB$, then $A$ is quasi-atomic, and therefore in $\Gamma$ by the definition of $\Gamma$. Unique readability follows from the unique readability of wff’s of propositional logic. ∎

Since no quantifiers  are involved in the built-up process, the language  based on $\Gamma$ as the set of atoms can be considered as the language of propositional logic. Call this logic PL$(\Gamma)$. So the atoms of PL$(\Gamma)$ are precisely the quasi-atoms of FO$(\Sigma)$.

###### Proof.

Suppose wff $A$ is a tautology in FO$(\Sigma)$. Then it is a tautology in PL$(\Gamma)$ by definition, and therefore a theorem in PL$(\Gamma)$ since propositional logic is complete     with respect to truth-value semantics. If $A_{1},\ldot,A_{n}$ is a deduction   of $A$ (with $A_{n}=A$), then each $A_{i}$ is either an axiom, or is obtained by an application of modus ponens. If $A_{i}$ is an axiom (of PL$(\Gamma)$), it is an instance of one of the first three axiom schemas of FO$(\Sigma)$ above, which means that $A_{i}$ is an axiom of FO$(\Sigma)$. Furthermore, since modus ponens is a rule of inference for FO$(\Sigma)$, $A_{1},\ldots,A_{n}$ is a deduction of $A$ in FO$(\Sigma)$, which means that $A$ is a theorem of FO$(\Sigma)$.

On the other hand, any wff that is an instance of one of the last two axiom schemas of FO$(\Sigma)$ is a theorem that is not a tautology. For example, $\forall x(x=y)\to(z=y)$ is an instance of the fourth axiom schema, which takes the form $C\to D$, where $C$ is a quasi-atom, and $D$ an atom, both of which are atoms of PL$(\Gamma)$. Any truth-valuation that takes $C$ to $1$ and $D$ to $0$, takes $C\to D$ to $0$. Therefore, $\forall x(x=y)\to(z=y)$ is not a tautology. ∎

Title tautologies in predicate logic TautologiesInPredicateLogic 2013-03-22 19:32:25 2013-03-22 19:32:25 CWoo (3771) CWoo (3771) 15 CWoo (3771) Definition msc 03B10