# Models and signatures for propositional logic

The following is a bit long, so I collected my questions at the end, but as this is the only opportunity I get for feedback I would appreciate it if anyone could also point out where I've gone astray in my reasoning.

I just finished the first chapter of Hodges Shorter Model Theory and the beginning of chapter 2 (up to the definition of well-formed formulas). I've been cross-referencing this with the way Terrence Tao introduces propositional, 0th order, and 1st order logics in this article.

The presentations are a little bit different, so I wanted to get a feel for what is absolutely necessary (and to get a feel for how this fits with my knowledge of formal languages), using the simplest case, propositional logic. Ultimately I'd like to understand non-standard systems of logic more fully (such as minimal logic).

My main line of inquiry here is "can you express propositional logic completely within the framework of structures and signatures without introducing externally defined logical connectives?" It's my understanding that logical connectives are part of the object language, not the metalangauge, so it seems like this could be possible.

Say you have a signature for propositional logic consisting only of nullary relations corresponding to propositional variables (where $R_0$ is the set of nullary relation symbols):

$$\sigma := (R_0 = \{P_1, P_2,...,P_n\})$$

I see right away that in this situation logical connectives could not be added to the signature as relations (because a relation is properly defined over elements of the domain of a structure) and because propositional variables resolve to truth values which are "outside" of this domain (the result being relations defined in the signature wouldn't be composeable and therefore a complete propositional logic would not be possible).

So for this signature there must be a logical connective outside of the signature that is defined over truth values, if we want to express arbitrary propositional formulas. For simplicity, I'll say there is one functionally complete logical connective, the NOR operator $\downarrow$. Now with the above signature and this logical connective, we should have a complete propositional logic, with a $\sigma$-language built up as follows (following Hodges):

1. Terms: none (there are no term variables, constants, or n-ary functions in the signature. A side question here is where do term variables fit into the picture? do they live in some other part of the object language, like the logical connectives?)
2. Atomic formulas: just the propositional variables taken individually $P_1, P_2,...,P_n$
3. Well-formed formulas: combinations of atomic formulas by the logical connective $\downarrow$: ex. $(P_1 \downarrow P_2) \downarrow P_3$

Now giving a structure with this signature ($\sigma$-structure) essentially amounts to an assignment of truth-values to the propositional variables in the signature. For example, given a formula $\phi := (P_1 \downarrow P_2)$, and a $\sigma$-structure $A = \langle \varnothing, \sigma \rangle$, with truth values $P^A_1 = false$ and $P^A_2 = false$, one could then write $A \vDash \phi$, or, in this particular case, if $A$ has any other truth assignment it results in a false formula, so $A \nvDash \phi$.

My next attempt is along these lines: "what if we again drop the logical connectives, and instead of propositions and relations, we created an equivalent signature using functions and constants over a boolean domain?". So here we could have a new signature:

$$\sigma := (F_2 = \{\downarrow\}, F_0 = \{c_1, c_2,..., c_n\})$$

where $F_0, F_2$ are the sets of nullary (constant), and binary function symbols, respectively. The parts of the language then look like this:

1. Terms: constants ($c_1, c_2,...,c_n$) and functions applied to terms, ex. ($c_1 \downarrow c_2$)
2. Atomic formulas: none
3. Formulas: none

Because there are no relations in this signature, there's no way to get atomic or even compound formulas.

A structure would look like $A = \langle \{0,1\}, \sigma \rangle$ and should produce terms, I believe, that are isomorphic to the propositional calculus above. I'm assuming the inability to actually have formulas would make it harder to make statements about the system, at least the satisfaction relation $\vDash$ would no longer be defined since it requires a truth-value (propositional formula) on the right.

I then considered a couple ways of extending the signature to allow formulas (by adding relation symbols), but because of the same problems with composition of relations, as in the first system, without a logical connective defined outside of the signature, all I would be able to get are atomic formulas, not compound formulas.

Adding a relation symbol $isTrue$ that maps $1$ to true and $0$ to false, or (perhaps more naturally) a binary equals ($=$) relation would be possible extensions. An atomic formula $\phi := (c_1 \downarrow c_2) = 1$ would be satisfied for a structure $A$ with constants $c_1^A = 0$ and $c_2^A = 0$: $A \vDash \phi$. But this still wouldn't allow a complete propositional logic (with the current definitions for atomic formulas or compound formulas being what they are) without adding a logical connective, "external" to the signature.

What about two signatures? One "lower-level" signature with a functionally complete binary function, and one "higher-level" signature, also with a functionally complete signature

$$\sigma_1 = (F_2 = \{\downarrow\}, F_0 = \{c_1, c_2,...,c_n\})$$

$$\sigma_2 = (F_2 = \{\downarrow\}, F_0 = \{P_1, P_2,...,P_n\})$$

Obviously these signatures are the same, the symbols are just different for the constants. I'll drop the second signature and just use the first. If two structures share the same signature then there may be a $\sigma$-homomorphism (as defined in Hodges). So let's define two structures using the first signature, the only difference being the "lower-level" structure will have domain $\{0,1\}$ and the "higher-level" structure will have domain $\{true,false\}$:

$$A = \langle \{0,1\}, \sigma\rangle$$

$$B = \langle \{true,false\}, \sigma\rangle$$

(Does $B$ now play the role of something like a T-schema?) There should be a straightforward homomorphism $f : A \rightarrow B$ that satisfies the properties for being a homomorphism (Hodges):

1. for each constant of $\sigma$, $f(c_i^A) = c_i^B$

2. (there are no relation symbols so this condition regarding relations can be ignored)

3. for each $n$-ary function symbol $F$ for $n > 0$, $f(F^A(\overline{a})) = F^B(f(\overline{a}))$ where $\overline{a}$ is Hodges' notation for a string of arguments in $|A|$.

I'm guessing that the "combined" language might look like (this is the most questionable part in my mind):

1. Terms: just the terms of $A$ ($c_1$, $c_2 \downarrow c_3$, ...)
2. Atomic formulas: the homomorphism $f$ applied to constants, ($f(c_1)$), that is, something in |$B$| (true or false)
3. Compound formulas: the homomorphism $f$ applied to functions, ($f(c_1 \downarrow c_2)$, which translates to $f(c_1^A)\downarrow^B f(c_2^A)$)

If this setup is allowed, what does this homomorphism represent? Is it the same as the "interpretation function" that is usually applied to give a realization of a structure into actual relations and formulas? There's also interpretations of structures later in Chapter 4 of Hodges, but it seems to be in a different sense (the signatures don't have to be the same).

One thing that's in the back of my mind, and maybe this is the big question that I can't answer, what if we realized the binary operator in these structures is different, say the symbol is $*$, and in $A$ it's taken to mean NOR and in $B$ it's taken to mean NAND. If I'm manipulating the symbols correctly there doesn't seem to be a homomorphism in this case, although both structures should represent a functionally complete propositional logic, the langauges seem incompatible.

The above is rather long, so my main questions collected here are:

1. Is it correct that logical connectives and term variables are part of the object language (not the metalanguage)?
2. Is there any way to put the logical connectives of a language into a structure and still be able to answer the same questions as usual, even if it's more inconvenient? I'm wondering if this is similar to "T-schema"?
3. If you construct a homomorphism $f : A \rightarrow B$ into a functionally complete structure isomorphic to propositional logic $B$, does this constitute an 'interpretation function' for $A$? If so, does choosing conflicting logical operators in these structures make such a homomorphism impossible? (e.g. $A$ has operator NOR and $B$ has operator NAND, both represented by the same function symbol $*$)
• Interesting questions. I'm not sure how to answer all of them hence I'm adding a comment. I recommend you to check other references, c.f., en.m.wikipedia.org/wiki/Formal_system. The book you are reading has a model theoretic approach to logic, and I've read that model theorists don't usually care much for the formalism behind. For example, Hodges book defines structures at the beginning but that is just the semantics for a formal language. Taking this into account, I believe that the answer for your first question is not only "yes", but "logical connectives are USUALLY(to be continued) – Jonathan Julián Huerta May 29 '15 at 8:11
• USUALLY part of the object language". The signature is a SUBSET of the alphabet of your object language. Connectives and quantifiers are in this alphabet but not in the signature (check link above). The other two questions require more knowledge than what I have so I'll be happy to see what other people answer to you. – Jonathan Julián Huerta May 29 '15 at 8:18