Model Theory

1. Terminology

Given a language \(L\) and a sentence \(S\) in the language, an interpretation \(I\) is a structure that consists of:

an assignment of values to the references in \(S\) and
an assignment of classes to what the quantifiers in \(S\) range over

such that \(S\) is true in \(I\). Then we say:

\(I \models S\)
\(I\) models \(S\)
\(S\), when interpreted in \(I\), is true
\(I\) satisfies \(S\)

1.1. Example:

Our language could be English, and our sentence may be: "He ate all of it for lunch". Then, an interpretation for the sentence may be the structure that specifies that:

"He" refers to "John"
"all of it" ranges over the class of leftovers in the fridge

2. Model-theoretic handlings of "definitions"

These are 4 different ways that the concept of "definition" appear in model-theory discussion

2.1. typical model-theoretic definition

A set of sentences \(T\) in a language together are called a theory. Then \(\text{Mod}(T)\) is the class of all structures that are models of \(T\).

2.1.1. Example

Consider the following set of sentences in first-order logic:

\(\forall x \forall y \forall z((x+y)+z) = x+(y+z))\)
\(\forall x (x+0 = x)\)
\(\forall x (x + (-x) = 0\)
\(\forall x \forall y (x+y = y+x)\)

Here, the labels that an interpretation must specify are: (+,-). An interpretation must also specify the domain that the quantifiers range over.

The models of these sentences are abelian groups if they also:

Contain an interpretation of the constant label 0
Are closed under (+) and (-)

Phrased another way: any structure that is an abelian group, e.g. the integers, is a model for the above axioms.

2.1.2. Some more terminology

A structure (read: "model" or "interpretation") contains interpretations for certain:

predicate symbols of a particular arity
function symbols of a particular arity
constant symbols

The set of the above symbols is called a signature \(K\). Similarly, languages can also have signatures.

So in the previous example, an abelian group is a model of signature \((+,-,0)\) that satisfies the given sentences.

2.2. defining relations inside a structure

In the previous example, there were 3 types of symbols:

There was the logical symbol "="
There were the symobls in the signature, i.e. (+,-,0) and the quantifier symbols. These are called nonlogical constants
There were the variables \(x\), \(y\), and \(z\)

In the previous discussion, we looked for interpretations of the nonlogical constants that satisfied a given sentence. Instead, let's fix a structure \(A\) and look for assignments of elements of \(A\) to variables that make a given formula true.

2.2.1. Example

Let's talk about the structure \(\mathbf{Z}\) which consists of the integers \(\mathbb{Z}\) and the symbols \((+,-,0)\) with their usual meanings. Consider the formula: \[x+x=y\]

Assigning \(3\) to \(x\) and \(6\) to \(y\) satisfies this formula in \(\mathbf{Z}\). Other satisfying pairs include \((2,4)\), \((4,8)\), etc. In this way, the formula defines a binary relation in \(\mathbf{Z}\).

2.3. "interpretation"

We can interpret a structure \(B\) in a structure \(A\). Or, think of it as: representing \(B\) in \(A\). Or, think of it as: finding some isomorphism from the relationships and elements in \(A\) to the relationships and elements in \(B\).

The general procedure:

Start with a structure \(A\). We will be representing \(B\) in \(A\)
Define the domain of \(B\) to be \(X\) in \(A\)

2a. Here, we might also define equivalence classes in \(X\), and take the domain of \(B\) to be the set of these equivalence classes

Define the relations on \(B\) to in terms of relations that are definable in \(A\)

2.3.1. Example

For example, let's represent the integers \(\mathbb{Z}\) in the natural numbers \(\mathbb{N}\). Let's define the following equivalence relation on pairs of natural numbers: \[(a,b) \sim (c,d) \Leftrightarrow a+d = c+b\] Then, let's take the domain to be the equivalence classes on tuples \((x,y)\). Now, we can define addition in \(\mathbb{Z}\) as: \[(a,b) + (c,d) = (e,f) \Leftrightarrow a+c+f = b+d+e\] Finally, we interpret the equivalence class \((a,b)\) as the integer \(a-b\).

Here's how I understand this example: Using the language from the previous discussion, we have created a certain structure using the pieces of \(\mathbb{N}\), we can give meaning to this structure by assigning the elements to pieces of \(\mathbb{Z}\). So, \(\mathbb{Z}\) provides the interpretation.

This is similar to the technique of reduction: in which a problem \(A\) can be phrased in terms of another problem \(P\) to show that \(P\) is at least hard as \(A\).

2.4. implict definiability and explicit definiability

3. Model-theoretic handling of "consequence"

Let \(L\) be a language with signature \(K\). Let \(T\) be a theory in \(L\) and \(\phi\) be a sentence in \(L\). Then: \[ \text{Mod}(T) \subseteq \text{Mod}(\phi) \] means that every structure of signature \(K\) that is a model of \(T\) is also a model of \(\phi\).

How do we talk about the validity of an argument in model-theoretic terms? We might say that our premises are part of \(T\) and our conclusion is \(\phi\).

There is a related (possibly identical?) procedure: paraphrase an argument in terms of set-theory and check if the conclusion is valid in the set-theoretic sense. I am still a little unclear as to how this procedure is related to the model-theoretic handling of "consequence"

I think the model-theoretic version of "consequence" is supposed to capture the idea: "your conclusion follows from your premises, if your conclusion holds in all possible domains that your premises axiomatize". For example your premises could axiomatize the class of abelian groups. If your conclusion is supported by these axioms, then they should hold in all possible structures that are abelian groups.

4. Model-theoretic handling of "expressivity"

Consider two languages \(L\) and \(L'\). We say that \(L'\) is at least as expressive of \(L\) if for every class \(\text{Mod}(S)\), where \(S\) is a sentence in \(L\), there is a sentence \(S'\) in \(L'\) such that \(\text{Mod}(S) = \text{Mod}(S')\). Then, we say that \(L\) is reducible to \(L'\).

Note: here we say that \(L'\) is at least as expressive as \(L\) when \(L\) is reduced to \(L'\). (See Reduction). I think of it this way: "I claim that \(L'\) is as expressive as \(L\). Alright, let's try to represent every sentence in \(L\) in \(L'\). What does it mean to 'represent' \(S\) as \(S'\)? It means that \(S'\) should pick out the same class of models as \(S\)."

When we are talking about query languages, we can think about the possible database states as structures. Then, we say that a sentence \(S\) in a query language \(L\) has a class of database states which are models of that sentence. If \(L'\) can represent all the same queries as \(L\), then there is some query \(S'\) that can pick out the same set of states.

5. What do scientists mean when they talk about "modelling"?

It's a little fuzzy. Consider what we mean when we say that we are modelling a phenomenon, e.g. heat transfer, using formulas, e.g. a set of differential equations. There are two things that could be going on:

There is an abstract phenomenon, call it Heat Transfer, of which the solution \(S\) to the differential equations is a model, in the sense that we discussed above. That is, the terms of Heat Transfer can be concretely interpreted as being the relations that hold in the solution \(S\). Or in other words, \(S\) is just an instantiation of the phenomenon Heat Transfer, of which heat transfer is also an instantion. Think of the way that a toy boat is a model boat, in that it is also an instantiation of the Boat class.
The differential equations are the theory, of which heat transfer is a model. Here, "theory" and "model" are used in the same sense as in the previous discussion. That is, the differential equations specify axioms, of which heat transfer is a concrete instantiation.