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

Question

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?

Answer 1

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.

Answer 2

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.