Logic: one vs many structures for a given language

Question

i'm self-studying logic. I'm comparing three texts (though Chiswell & Hodges (C&H) so far remains the most comprehensible). For my question regarding structures I found this, this, and this question; yet i remain bothered on one point. In one example in C&H pg.112 & 129, which is consistent with the other two texts, we have

signature (pg.112):

• a constant symbol $\overline 0$
• a function symbol $\overline S$ of arity 1
• two binary function symbols $\overline +$ and $\overline \cdot$.

Followed by the structure (pg.129):

• domain: the list of all natural numbers
• $\overline 0$: the number 0
• $\overline S$(x): x + 1
• $\overline +$(x,y): x + y
• $\overline \cdot$(x,y): xy

Then on pg.64 we have for LP($\sigma$) $$ \frac{q_1...q_n}{A(q_1)...A(q_n)} $$ Which is to say, a particular row in a truth table.

It almost feels like some structures (the former) are abstract class definitions like one might find in a programming language and that a single structure will do, while others (the latter) are instantiations of said class, or do we need many structures in place of one to understand a single language? It seems...excessive or inefficient.

When we get to the completeness proof, all 3 texts appear to discuss many structures of the latter sort, $2^k$ structures (would the set of such structures be the power set P(A) of A: {T, F}?! Or is P(A) just {T, F, {T,F}}? What do we call the set for $2^k$ combos?). Yet I'm guessing the latter structure isn't an "instantiation", but rather merely incomplete, yes? It must be more like the first structure and also include the logical constants ($\land, \lor, \rightarrow$, etc.), a generic expression for predicate relations in FOL, and so on. And yet, it seems painfully redundant to have these additional symbols+interpretations in each and every structure, when one would just do, and then have "sub structures" for each combination of truth values for the "constants".

Do we go back and forth between a "complete" structure and "incomplete" structure depending on context to simplify dialogue? I intend to post a question re: the completeness/adequacy theorem in a few days, and I'd like to make sure I understand what structures/models are so I can pose it properly.

Answer 1

We have two "environments": the syntactical one: the symbols of the language, and the semantical one: the "objects of the world".

We want to connect them: to use the language in order to "speak of" the world.

This is an interpretation.

The "basic" concept of $\sigma$-structure, used to interpret a signature [a language] $\sigma$ is defined for first-order languages, but we can easily adapt it to the propositional case.

In this case, the symbols of the language we want interpret are the sentential letters: $p_i$, and the "world" we assume as the domain of discourse of our (ultra-simplified) propositional language is made of only two objects: $\text T$ and $\text F$.

Thus, $\{ \text T, \text F \}$ is the domain of Definition 5.5.2 (a) [page 129]: a non-empty set.

The propositional language has no individual constants nor function symbols, and we may say that the sentential letters $p_i$ are $0$-ary relation symbols.

$0$-ary relations can thus be seen as truth values, which in propositional logic play the role of the interpretations of propositions.

All this boils down to Definition 3.5.3 [page 64]:

By a $σ$-structure [for a propositional language $\sigma$; see page 33] we mean a function $A$ with domain $σ$, that assigns to each symbol $p$ in $σ$ a truth value $A(p)$.

We call this object a ‘structure’ in preparation for Chapters 5 and 7, where the corresponding ‘structures’ are much closer to what a mathematician usually thinks of as a structure.

Every $σ$-structure $A$ gives a truth value $A^*(\chi)$ to each formula $χ$ of $\text {LP}(σ)$ in accordance with [the usual truth tables for the connectives].

In a nutshell, if we consider a propositional formula $\chi$ with sentential letters $p,q,r$, we have that a structure (or interpretation) $A$ is a mapping that assigns a truth value to $p,q$ and $r$.

But such a structure is exactly the row $A(p), A(q), A(r)$ in the truth table for $\chi$.

---

The Completeness Th is the basic result linking the syntactical view with the semantical one.

In the "syntactical world" we define the concept od derivation: $\Gamma \vdash \varphi$, i.e. the formula $\varphi$ is derivable from the set of formulas $\Gamma$ in the proof system (or calculus).

In the "semantical world" we define the concept of logical consequence: $\Gamma \vDash \varphi$, i.e. the formula $\varphi$ is true in every structure that satisfies (makes true) all the formulas in $\Gamma$.

Completeness (of the proof system) means [see page 86]:

$Γ \vdash \psi$ iff $Γ \vDash \psi$.

More specifically about propositional calculus, we can consider the "simple" case of completeness:

$\vdash \varphi$ iff $\vDash \varphi$,

that reads: a formula $\varphi$ is provable in the calculus iff it is a tautology.

A formula $\varphi$ is a tautology iff it is true in every interpretation, i.e. in every truth assignment $A$ (where $A$ is the mapping above from sentential letters to truth values).

We can easily prove the obvious result that, for every formula $\varphi$, where $p_1,\ldots, p_k$ are the only sentential letters occuring in it, and for every pair of mappings $A_1$ and $A_2$:

if $A_1(p_i)=A_2(p_i)$, for $i=1,\ldots,k$, then $A_1^*(\varphi)=A_2^*(\varphi)$.

It is more difficult to write it than to grasp it...

This amounts to say that what counts for the truth value of a formula are only the truth values assigned to the sentential letters occurring in it.

For a formula $\varphi$ with $k$ sentential letters, we have only $2^k$ possible truth assignments: they are exactly the rows in the truth table.

Conclusion: to check if a formla is a tautology we have "only" to consider the $2^k$ possible combinations of the truth table and check if the formula has always $\text T$.