2

I'm learning predicate logic and my textbook says that some logical truths expressible in the language of predicate logic are not tautologies.

For example, according to my textbook, $∀x(Px ⊃ Px)$ is valid even though it doesn't instantiate a tautological schema.

However, I don't understand why $∀x(Px ⊃ Px)$ can't be regarded as a tautology. Can someone help me?

Thanks a lot

Mauro ALLEGRANZA
  • 94,169
user405159
  • 353
  • 2
  • 12

2 Answers2

4

A tautology is a formula of propositional calculus that is true for every assignment of truth values to the propositional letters (i.e. for every interpretation).

Example of tautologies : $A \to A, \lnot A \lor A$.

In first-order logic, a formula is valid iff it is true for every interpretation.

In first-order logic, a tautology is a formula that is obtained by a propositional tautology replacing uniformly propositional letters with formulae.

Example, $Px \to Px$ is a FOL tautology, as well as $\forall xPx \to \forall xPx$ and $\lnot \forall xPx \lor \forall xPx$, because they can obtained from the propositional tautologies $A \to A$ and $\lnot A \lor A$ replacing the propositional letter $A$ with the formulae $Px$ and $\forall xPx$ respectively.

Obviously every FOL tautology is valid, but not all FOL valid formulae are tautologies.

Examples:

$\forall x (Px \to Px), \forall x (x=x)$.

Mauro ALLEGRANZA
  • 94,169
  • I think I grasp the sense of your answer Mauro: when we write a formula like ∀x(Px→Px) we are not replacing PROPOSITIONAL LETTERS with formulae. – user405159 Jan 13 '17 at 21:39
  • 1
    A secondary point: is ∀xPx an atomic formula? Also, I suppose you mean "In first-order logic, a formula is valid IFF it is true for every interpretation". – user405159 Jan 13 '17 at 21:42
  • @Fishermansfriend - correct: the FOL formula ∀x(Px→Px) can be obtained by replacement from the propositional formula $A$, that of course is not a tautology. And no : in FOL atomic formulae are e.g. : $Px$ and $x=y$. – Mauro ALLEGRANZA Jan 14 '17 at 11:15
  • Thanks @MauroALLEGRANZA. To clarify, $∀x(Px⊃Px)$ is not a tautology because it has no tautological equivalence in propositional logic? Why is the definition of tautology in predicate logic restricted in this way? Some authors seem to adopt a less restrictive definition, e.g. my reference simply defines an FOL tautology as "an expression E is called a tautology if for every interpretation of E, the value of E is 1". So under this definition, wouldn't $∀x(Px⊃Px)$ be a tautology? – user51462 Sep 18 '22 at 03:27
0

Another example of a logical truth that is not a tautology is $$\forall x (Px \wedge Qx) \rightarrow \forall (Px) $$

Karl
  • 1