2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fishermansfriend Jan 13 '17 at 21:39
  • 1
    $\begingroup$ 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". $\endgroup$ – Fishermansfriend Jan 13 '17 at 21:42
  • $\begingroup$ @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$. $\endgroup$ – Mauro ALLEGRANZA Jan 14 '17 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.