2

I apologize if the title is inadequate. I am reading Loomis and Sternberg's Advanced Calculus textbook. After introducing the notation of a quantification and defining a tautology, they state:

Indeed, any valid principle of reasoning that does not involve quantifiers must be expressed by a tautologous form.

I cannot figure out what they mean by this. Surely I can reason in terms of implications with free, unbounded variables. Other than this, I cannot think of a good counterexample, but I must be misunderstanding them.

John P.
  • 2,136
  • You can’t assign a truth value when variables are unbound, usually reasoning like what you describe implicitly features universal quantifies in front to make it closed. –  Jul 05 '20 at 21:37
  • Ok, this makes sense. So if I don't quantify variables, the statement has to be tautologically true in which case I don't need quantifiers? (If I say something like $P \lor \neg P$, that's surely automatically true no matter what $P$ is, though in some sense there's an implicit universal quantifier in front of it.) – John P. Jul 05 '20 at 21:39
  • No, $P\lor \lnot P$ is not automatically true no matter what $P$ unless you assume that $P$ does not have free variables. If there are free variables then it is a predicate that happens to always evaluate to be true but that's not the same as being true. –  Jul 05 '20 at 22:07

1 Answers1

2

This is dealt with in Shoenfield's Mathematical Logic, Chapter 3 (especially the first section and the first exercise), though be warned that that book is terse! I don't wish here to prove the relevant theorem, but just state the definitions in order to clarify the situation. To simplify, let's assume the language has only existential quantifiers (the universal quantifier can be defined in terms of existential and negation in the usual way). I'm assuming you know the definition of atomic formula, etc., and that the background language is fixed.

Before starting, here's the idea behind the whole thing. We usually talk of tautologies only with respect to propositional languages. But there is a sense in which it can be extended to first-order languages in a natural way, so that, e.g., $Px \vee \neg Px$ or $\exists x Px \vee \neg \exists x Px$ can be said to be tautologies. The definitions below show how to accomplish that; the gist of it is that you treat existential and atomic formulas as if they were propositional variables. The quoted excerpt then is claiming that if you can derive a formula without using any logical rule that is specific to the first-order calculus, that formula is a tautology. So let us see the definitions in question.

Definition 1: A formula of the form $\exists x A$ is called an instantiantion of $A$.

Definition 2: A formula is called elementary if it is either an atomic formula or an instantiation.

Definition 3: A truth valuation is a mapping from the set of elementary formulas to the set of truth-values.

Fact 1: If $V$ is a truth valuation, it is possible to extend it to all formulas of the language in the usual way, i.e. by setting $V^*(\neg A) = T$ iff $V^*(A) = F$, etc. Call $V^*$ a boolean valuation for the language.

Definition 4: $B$ is a tautological consequence of $A_1, \dots, A_n$ if $V^*(B)=T$ for every boolean valuation $V^*$ such that $V^*(A_1)= \dots =V^*(A_n)$.

Definition 5: A formula $A$ is a tautology if it is a tautological consequence of the empty set.

So pick now your favorite first-order calculus. It will probably have rules that show to reason with the quantifiers (e.g. existential instantiation and generalization), with identity (say, substitution axioms), and with the propositional connectives (say, introduction and elimination rules, or modus ponens, or whatever). We have the following:

Theorem: If a formula is derivable from the empty set using only propositional rules, then the formula is a tautology. (Cf. Shoenfield, Chap. 3, Exercise 1)

Nagase
  • 5,467