I have a question about the following formula. Is $\forall I: I(f)=1$ where $f$ stands for a formula and I for an interpretation the meaning / valid definition of tautology?

  • 3
    $\begingroup$ Follow the definition in your textbook. I an imagine such a thing in a textbook, although I would guess most textbooks do not write it that way, quantifying over interpretations, using $1$ for "true" and so on. $\endgroup$ – GEdgar Jul 26 '18 at 12:55
  • 1
    $\begingroup$ This is a question that really needs some context. Is this supposed to be first order logic? If it is I'd address the quantification over a function symbol. Is the quantifier happening in some meta-language with $f$ a formula in some object language? If so, what are the existing assumptions about the object language, the interpretation function, etc.? Is 1 here the top element of a Boolean algebra, a natural number, a real number, something else? $\endgroup$ – Malice Vidrine Jul 26 '18 at 17:07

There are two notions kicking around here, one syntactic and the other semantic.

  • Syntactic tautologies: $f$ is a theorem of the empty theory, with respect to whatever proof system is being used.

  • Semantic tautologies: $f$ is true in every structure in the language of $f$ (or, every interpretation).

In my experience, "tautology" refers primarily to the former notion, while sentences with the latter property are called "validities." You will need to look at whatever text you're using to tell whether the definition of tautology you've given is appropriate.

However, by the completeness theorem, these two notions are in fact the same (as long as we're using a reasonable proof system). This is one reason that it's not a big deal that texts sometimes define "tautology" in different ways.

... At least, in the context of first-order logic (or propositional logic, for that matter). The notions above make sense in much more general contexts: "syntactic tautology" makes sense in the context of any proof system, and "semantic tautology" makes sense in the context of any satisfaction notion (even if the structures involved are quite different from what we're used to!). In general these notions may not line up; e.g. second-order logic (with the standard semantics) has no complete proof system.


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.