# Logic: one vs many structures for a given language

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.

• More specifically, it is not clear your comment about "complete" and "incomplee" structures. – Mauro ALLEGRANZA May 18 '17 at 6:30
• Oops I missed this comment, and "replied" via a question on your answer. In the example structure for propositional calculus, the authors only refer to the sentential letters in $\sigma$, and not the logical connectives, yet equivalent relations are mentioned in $\sigma_arith$ such as $\overline +$. So what I meant by complete and incomplete is the inclusion of these additional relations/connectives. – Lugh May 18 '17 at 21:23
• Logical Constants, like connectives, are not interpreted, meaning that they do not change their "meaning" according to the context. Their meaning is defiend by their truth tables (in classical logic) and this does not change. – Mauro ALLEGRANZA May 19 '17 at 6:23

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$.

• This is amazing. I have so many more questions. I will start with the first half of your answer. 1) are sentential letters relations rather than names, e.g. $\overline 0$, because they act as variables rather than constants? 2) does this mean that the domain of predicate calculus, as one might find in a philosophy text rather than a mathematical one, is also just {T,F}? A philosopher would want the domain to include all the objects within scope. How do we reconcile these two paradigms? Does this mean that not all the symbols of $\sigma$ are in its domain, i.e. the sentential letters $p_i$? – Lugh May 18 '17 at 21:15
• Are not the logical connectives part of the structure in either propositional calculus or predicate? as in the same manner $\overline +$ is on pg.129? – Lugh May 18 '17 at 21:19
• @Lugh Predicate logic doesn't have sentential letters. Every expression in predicate logic is built out of the syntax that Mauro described; intuitively, they are sentences about structures (= sets with some prescribed relations/functions/constants). Note that this differs wildly from the propositional case, where a model is a map from the set of propositional letters to $\{\top, \perp\}$. They're just two different things entirely (although with a bit of work it's not hard to interpret propositional logic as a fragment of predicate logic). – Noah Schweber May 18 '17 at 21:24
• Meanwhile, the logical connectives are not part of the structure; they're taken as primitive. (In predicate logic, the quantifiers also fall into this category, as usually does "$=$".) I think the trouble you're having is from conflating aspects of propositional and predicate logic which are really not equivalent. – Noah Schweber May 18 '17 at 21:26
• @Lugh - 1) if we consider first-order languages, with function symbols we manufacture terms, i.e. "names", while with relation symbols we manufacture sentences, i.e. something that is true or false. Thus, in the "degenearte" cases, a $0$-ary function symbol acts as an individual constant, while a $0$-ary relation symbol acts as a sentential symbol. – Mauro ALLEGRANZA May 19 '17 at 5:54