9

If it is known from context that variables $x$ and $y$ represent integers, an open Boolean formula such as $x \ge y \Rightarrow x+1 > y$ evaluates to true regardless of the value assigned to variables $x$ and $y$, at least in the standard interpretation of arithmetic. What should (or could or would) one call such a formula?

I've been using the term "valid", but am not very happy with this. Logicians (e.g. Boolos and Jeffery") use "valid" for closed formulas that are true regardless of the interpretation. I could just call it "true", but this seems to fail to acknowledge that there are free variables. It might be called a "theorem", but I'd rather stay away from issues of provability.

Just for context: This is not a course in logic, but a course that uses logic as a tool for proving things about software. So I'd like to be consistent with standard logical terminology without getting into the possibility of multiple interpretations.

Incnis Mrsi
  • 378
  • 2
  • 12
Theodore Norvell
  • 529
  • 2
  • 12
  • 17
    It seems to me that you're looking for the word tautology – Jim Belk Mar 30 '14 at 15:31
  • 5
    No, tautology doesn't take into account interpretation. In the question $+, \ge$ and $>$ are all being interpreted. – Git Gud Mar 30 '14 at 15:33
  • 6
    It seems to me that what makes this tricky to describe is the absence of universal quantifiers. If the formula were $\forall x \forall y : x \geq y \Rightarrow x + 1 > y$ there would be no free variables and you would just say that it is "true". I note that your statement of the question does include quantifiers, but they are in the surrounding text ("regardless of the values...") rather than in the formula itself. – mweiss Mar 30 '14 at 16:33
  • 5
    @GitGud This depends on which symbols you think are open to interpretation. Even a statement like $A \lor (\lnot A)$ is only a tautology if you use the standard interpretation of the symbols $\lor$ and $\lnot$. Of course, if we are discussing formal logical systems, then it is usual to think of the interpretations of logical symbols as fixed, while other symbols are open to interpretation. However, I think in the more general context of mathematics, it's perfectly reasonable to refer to a statement like $x \geq y \Rightarrow x+1 > y$ as a tautology. – Jim Belk Mar 30 '14 at 16:42
  • 2
    Thanks for the comment's so far. I used to use the word "tautology" on the grounds that this was an extension of the idea of a propositional tautology. But I rejected it on the grounds that it wasn't consistent with the literature on logic, which says that a formula is only a tautology if it is true on the basis of logic only; i.e. only if it does not depend on the interpretation of extralogical symbols. – Theodore Norvell Mar 30 '14 at 17:44
  • @mweis Yes. That's the point. I am looking for a word that implies that a potentially nonclosed formula would be true if only one were to add the missing quantifiers to make it a closed formula. – Theodore Norvell Mar 30 '14 at 17:51
  • 4
    Writing formulas with free variables where the universal quantifiers are implicit is common enough that it might be worthwhile to be explicit about this convention with your students. The formula you mention in your question is a great example with which to introduce this standard ellipsis. (Note that existential quantifiers are never left implicit in this way.) Once you read the formula with implicit universal quantifiers, the word you're looking for becomes merely "true". – Adam Bjorndahl Mar 30 '14 at 20:34
  • 1
    If "tautology" is unacceptable, there is certainly some precedent for using the word "law". – Jim Belk Mar 31 '14 at 00:47
  • 1
    @TheodoreNorvell, if the universal quantifiers are understood, they are present (implicitly) anyway. Better make them explicit. – vonbrand Mar 31 '14 at 03:24
  • Thanks for everyone's thoughtful input. I think I will go with "universally true", as in "${P};x:=E;{Q}$ is a valid triple if and only if $P\Rightarrow Q[x:E]$ is universally true". – Theodore Norvell Apr 01 '14 at 17:57
  • 1
    Is "fact" not a feasible option for you? – Andrew Sanfratello Apr 04 '14 at 20:53
  • "fact" and "law" are both good suggestions – Theodore Norvell Apr 06 '14 at 12:47
  • "Valid" is an adjective I used to use. The reason I stopped is given in the question. I once called a boolean expression a "predicate" in a conference presentation and was rebuked that an expression is not a predicate, which I thought was getting a bit picky, because when a computer scientists writes down a boolean expression, they are generally using it as a way to specify a predicate (i.e. boolean valued function) on states. But still, when I'm teaching I try to avoid language that might confuse me, not to mention my students. – Theodore Norvell Aug 11 '21 at 20:37
  • @RyanG Yes, that's what I want. Although, as mentioned in a recent comment, I'm skittish around the word "predicate". I like 'identity' because it's a word that students already know, e.g. from trig. The question is whether it's too much of a reach to extend the word to boolean expressions that aren't equalities. – Theodore Norvell Sep 08 '21 at 02:47
  • [deleted previous comment to expand into Answer] – ryang Sep 08 '21 at 07:06

3 Answers3

7

I asked

What should (or could or would) one call such a formula?

Several good suggestions came up in the comments

  • "a law"
  • "a fact"
  • "a tautology"
  • "true"
  • "universally true"

I'd like to thank everyone who commented. Given that these are all good suggestions, I'm willing to consider the question answered.

Many people up voted "tautology". In fact, it is a word I've used in the past. I'd like to warn that there is at least one competing definition for "tautology" applied to a first order formula. This is that a formula is a tautology if and only if it is an instance of a propositional tautology. For example $x=0 \vee \neg(x=0)$ is a tautology, as it is an instance of $P\vee \neg P$, but $2+2=4$ is not a tautology. As I said in the OP, I wanted to be consistent with the standard logical terminology, so that ruled out "tautology" for me.

I ended up with "universally true". For context, this is a computing course and the kinds of formulas we typically deal with describe states of the computer. E.g. $x=y$ describes all states in which the location called "x" contains the same value as the location called "y". Usually the right question to ask about such a formula is not whether it is "true" or not, but which states is it true of. This is the reason I preferred not to use simply "true". "Law" and "fact" are to me slightly more suggestive than "true", but I didn't think that they went far enough in emphasizing the universality.

Finally, I'll note that Dijkstra and Scholten in their book Predicate Calculus and Program Semantics use the square brackets as an operator which they call "everywhere". This operator is applied to what they call "Boolean structures", which are essentially the same as what most of us would call Boolean functions. For them a condition $x\ge y\Rightarrow x+1 > y$, where $x$ and $y$ are integer variables, is a "Boolean structure" which represents a set of states, while $[x\ge y\Rightarrow x+1 > y] = \mathit{true}$.

Theodore Norvell
  • 529
  • 2
  • 12
2

Expanding my comment into an answer:

So you want the umbrella term for a predicate (propositional function), like the triangle or Cauchy–Schwarz inequality, that's always true, but not necessarily so regardless of interpretation. So, ‘validity’ and ‘tautology’ are ruled out.

If the object is an equality instead of inequality, I'd have suggested ‘identity’ (a universally-quantified equation)...

@RyanG Yes, that's what I want. Although, as mentioned in a recent comment, I'm skittish around the word "predicate". I like 'identity' because it's a word that students already know, e.g. from trig. The question is whether it's too much of a reach to extend the word to boolean expressions that aren't equalities.

...For inequalities, we might similarly distinguish between “identity inequalities” and non-identity inequalities? This is clearly not standard terminology either, but a google search did return this definition as the first result:

“An identity inequality is an inequality that is true no matter what values we plug in for the variable.”

P.S. I agree that "predicate" is a bad choice for the purpose: not only is it distractingly formal-logical, it even has two (related but) distinct definitions within the field of logic.

P.P.S. Possibly related.

ryang
  • 1,822
  • 13
  • 19
1

Your self-answer is wrong, because a tautology must be true under every interpretation, but your example is certainly not so. There is no single word for what you want, but the standard terminology is that your formula is true under standard/intended interpretation. And you can note that it is conventional to say just "true" to mean that when dealing with arithmetical formulae. The failure to understand this conventional meaning of "true arithmetical sentence" underlies a large fraction of misunderstandings of Godel's incompleteness theorems due to the phrase "true but unprovable statements".

Nor is "universally true" correct for the same reason.

user21820
  • 2,555
  • 17
  • 30
  • Thanks for the input. I agree that tautology is problematic not only for the reason I gave in my answer, but also for the reason you give. I think context is important (see the last paragraph of the question). For example, in the context of most math, CS, or Engineering courses if you said "'for any integer $x$, $x+x = 2\times x$' is a true statement" that would not be wrong. In the context of a logic course, you'd want to specify an interpretation before claiming any formal statement to be true. – Theodore Norvell Sep 28 '21 at 13:33
  • @TheodoreNorvell: "True statement" is not the same as "tautology". I don't get why you fail to recognize that. – user21820 Sep 28 '21 at 13:38
  • I do understand the difference between "True statement" and "tautology". – Theodore Norvell Oct 07 '21 at 19:36
  • 1
    @TheodoreNorvell: Maybe I misread you, since in your answer you do say you rule out "tautology". However, your comment was misleading because you said "in the context of a logic course" as if outside that context we do not need to specify an interpretation for the matter of truth. It is this kind of imprecision that leads to the extremely common conceptual error regarding the incompleteness theorems. – user21820 Oct 08 '21 at 04:34