How is “interpretation” used differently in propositional vs. first-order logic?

I am confused on the usage of the word "interpretation" and/or "model" when it comes to propositional logic versus first-order logic because there are so many conflicting / unclear notions that I would like to clear up.

My current understanding is as follows and I would like any corrections / elaborations on where I am confused:

I am using the definition of a "model" being an interpretation that satisfies a formula / set of formulas. In the case of a theory we can treat its axioms as a set of formulas, and so a "model of a theory" meaning any interpretation that satisfies the set of axioms of that theory.

In propositional logic an "interpretation" is an arbitrary assignment of true/false values to all the atomic propositions in the alpha set. For example $$p_0 = T, p_1 = F, p_2 = T, p_3 = F, ...$$ and so on. This tells us which row of any given truth table we should look at when evaluating the "truth value" of any fixed proposition.

But then in first-order logic, it seems like an "interpretation" is no longer some specific assignment of values to non-logical terms, but rather entire number systems like "the natural numbers," which would also be a "model" of, for instance, peano arithmetic, which satisfies its axioms.

Why is this? Why wouldn't we say "boolean variables" model propositional logic then? Why wouldn't we say some specific assignment of values satisfy first-order logic / PA / etc?

Why is interpretation seemingly being used differently in both cases? If an interpretation is what we'd call the specific T/F assignments in propositional logic, then what do we call the choice of a boolean system in the first place?

And more of a side question, but then what of propositional logic systems like natural deduction which have no axioms at all? What models "satisfy" it if there's no set of axioms to represent the theory?

2 Answers

In both propositional and predicate logic, the truth value of a formula is always either true or false, once an interpretation has been given. The set $$\{true, false\}$$ is not something you choose; it is a fixed part of how the logic works.

However, in predicate logic, formulas are not everything there is. Predicate logic also has terms, which are expressions that can be the arguments of relation symbols. (For example, in the language of arithmetic $$2>3$$ or $$5=x+2$$ are formulas; $$2\cdot 3$$ or $$x+2$$ are terms).

An interpretation in predicate logic tells you

• A set that the value of terms can be drawn from. (This is implicitly also the set that variables have their values in).
• An interpretation of each of the function symbols in the logical language. (For example, $$+$$ in the language of arithmetic).
• An interpretation of each of the predicate symbols -- that is a set of ordered tuples of values that make the predicate true when given as argument.

In propositional logic there are no terms, no functions, and predicates. All of the atomic formulas are propositional letters. Seen from the predicate-logic end we can view a propositional letter as a "predicate symbol" that takes no operands. Thus, if we apply the above sense of interpretation, such as symbol should be represented either by the set $$\{()\}$$ that contains the (unique) tuple of length 0, or by the empty set.

But this corresponds to a choice of whether the propositional letter is true or false -- so an "interpretation" for propositional logic is effectively the same as a map from the propositional letters to $$\{true, false\}$$. All we need to do is to write $$true$$ and $$false$$ instead of $$\{()\}$$ and $$\varnothing$$.

Since there are no terms, there is no need for an interpretation to specify which kind of values the terms would have if there were any.

• Does the set $\{true, false\}$ in the logic system have a name, or is it just "there"? How would we satisfy natural deduction systems that have no axioms? Does it make sense for a model of a theory to satisfy a set of inference rules? If so, does "model of a theory" generalize to satisfying the axioms and inference rules? – user525966 Oct 18 '18 at 14:42
• Trying to digest your answer a bit more... an interpretation involves a set of terms, function symbols, and predicate symbols -- where would logical connectives fit in (i.e. when we assign truth-functionals / truth tables to those connectives, or is this independent of "interpretation"? If so where does this fit in)? Are the atomic propositions distinct from the set of terms? Or are you saying the set of terms is also partially built from the alpha set? – user525966 Oct 18 '18 at 14:45
• @user525966: One distinguishes between logical axioms and non-logical axioms. The logical axioms come with the logic, and can differ between proof systems. For example, Hilbert systems usually have $(A\to B)\to(A\to (B\to C))\to (A\to C)$ as one of the logical axioms. The logical axioms serve to tell us how the connectives work. They are automatically satisfied in every interpretation as a consequence of how the truth tables work -- it is impossible to come up with an interpretation that doesn't satisfy them. – hmakholm left over Monica Oct 18 '18 at 15:57
• Non-logical axioms are the formulas that make up a theory. Their job is to tell us how the predicate, function and constant symbols behave. For example in many theories of arithmetic, one of the non-logical axioms is $\forall x(x+0=x)$, which tells us something about how the $0$ and $+$ symbols interact. It is possible to give an interpretation where this is not satisfied -- for example, the interpretation where the set of values are $\mathbb N$, the symbol $0$ evaluates to the number zero, but the symbol $+$ stands for multiplication of natural numbers instead of addition. – hmakholm left over Monica Oct 18 '18 at 16:00
• Another way of saying this is that the job of non-logical axioms is to define which interpretations we're interested in proving things about -- namely the ones that satisfy the axioms. And those are the interpretations we call models. – hmakholm left over Monica Oct 18 '18 at 16:02

In both cases, a formula is an expression assembled from some variables/constants (formula-level constants were not allowed in propositional logic, in the course I've taken, but they were allowed in first-order theory). The variables, simply speaking represent placeholders for objects of a certain type.

In propositional logic variables are placeholders for Boolean values.

In a first-order theory, there can be some confusion, as it has formula-level variables. This is a meta nomenclature conundrum, very typical for mathematical logic (i.e. theorems, as objects studied by mathematical logic, and meta-theorems about objects, studied by mathematical logic). For this reason, in propositional calculus, what I called 'variables' above, are properly called propositional letters.

Returning to first order theories, there are several types of 'meta-variables' allowed:

1. Constant letters
2. Variable letters
3. Function letters
4. Predicate letters

These things really only make sense when an interpretation of these letters is introduced. An interpretation involves a nonempty set $$D$$ (interpretation domain). Furthermore, all constant letters are assigned a concrete value from $$D$$, function letters are assigned concrete functions from Cartesian degrees of $$D$$ into $$D$$ and predicate letters are assigned concrete Boolean-valued functions from Cartesian degrees of $$D$$.

You notice variable letters are not assigned anything yet? This is because, on a fixed interpretation variable letters become true variables from $$D$$. They are allowed to take any value from $$D$$ but, unlike constants, are not bound to it within the frame of interpretation.

This is interpretation of a theory. Within it, we can interpret formulae. The interpretation of a formula is defined on a concrete sequence $$\{s_n\}$$ of values from $$D$$. When we substitute each $$x_n$$ for $$s_n$$ in a formula, we get a computable expression which is either true or false. Thus, an interpretation of a formula depends on which values we substitute for variables.

Basically, in a first-order theory, we first interpret the theory itself, and only then we can actually interpret its formulae, whereas in propositional calculus we can immediately interpret the formulae. To some extent, you can think of propositional calculus as a first-order theory, by default interpreted on the set of Boolean values, and whose formulae forbid quantifiers.