How to create models in First-order logic

Question

I'm a bit confused when it comes to defining models in First-order logic (FOL). Before I ask my question I thought I would show the semantics of how I create them and if I have understood it correctly so far.

• Signature: $\sigma$ = < c1, ..., cm ; f1, ..., fn ; R1, ..., Rk > where c are constants, f are functions and R are relations. A similar "<>" template is also created for the corresponding arity.
• Structure: $Z$ = < Z ; c1^Z, ..., cm^Z ; f1^Z, ..., fn^Z ; R1^Z, ..., Rk^Z > where c1^Z ... Rk^Z are interpretations of corresponding symbols in Z.
• Model: A structure of said signature that satisfies theory T.

With the following knowledge I'm still uncertain of the semantics of creating a model. I've seen these two examples in my books and elsewhere (the examples below are just using example values):

• $A$ = < {0,1} ; A^Z ; f^Z ; R^Z > where A^Z = 0, f^Z (n) = n + 1, R^Z (m,n) = m < n.
• $B$ = < {0,1} ; 0 ; {0, 1} ; {(0, 0), (1, 1)} >

What is the reasoning of example $B$ where if I understood it correctly, 0 is the constant, f^Z is replaced with the values that will get returned with said statement, R^Z is replaced with the values that will get returned if R^Z is true with said statement.

Is this the right way to interpret example $B$ or am I wrong?

Answer 1

Using notation in ways that make sense is really important, so I'm going to be very nitpicky here.

A = < {0,1} ; A^Z ; f^Z ; R^Z > where A^Z = 0, f^Z (n) = n + 1, R^Z (m,n) = m < n.

It looks like you're trying to describe a structure in the signature $\langle A, f, R\rangle$, where $A$ is a constant sybol, $f$ is a unary function symbol, and $R$ is a binary relation symbol. First of all, it's a really bad idea to name both the structure and the constant symbol $A$. So let's change the name of the constant symbol to $c$.

Ok, now we're in the signature $\langle c,f,R\rangle$. To define the structure $A$, you need to specify a domain and interpretations of the symbols in the signature. These interpretations are called $c^A$, $f^A$, and $R^A$, where the superscript $A$ indicates that they're the interpretations in the structure $A$. Note that in your example, you wrote $A^Z$, $f^Z$, and $R^Z$, which don't make sense (what's $Z$?).

Now you can write $A = \langle \{0,1\}; c^A; f^A; R^A\rangle$, where $c^A = 0$, $f^A(n) = n+1$, and $R^A(m,n) = m<n$. This is ok, except the way you've defined the function $f$ and relation $R$ is a bit unclear:

• According to your definition, $f^A(1) = 1+1=2$, which is not an element of $A$. Maybe you meant to add modulo $2$, so $f^A(1) = 0$? In that case, you could write $f^A(n) = n+1\mod 2$, or just list the values as $f^A(0) = 1$ and $f^A(1) = 0$. Alternatively, a function is a set of input-output ordered pairs, so you could write $f^A = \{(0,1), (1,0)\}$.
• $R^A(m,n) = m<n$ is ungrammatical. I would write "$R^A(m,n)$ if and only if $m<n$". Or just $R^A =\, <$, indicating that $R$ is interpreted as the less-than relation on $A$. Alternatively, a binary relation on $A$ is a subset of $A^2$, so you could write $R^A = \{(m,n)\mid m<n\}$ or just $R^A = \{(0,1)\}$, since there's only one ordered pair in $A^2$ satisfying the definition of $R^A$.

B = < {0,1} ; 0 ; {0, 1} ; {(0, 0), (1, 1)} >

For this to make sense, we need to know what the signature is. So let's assume we're still working with the signature $\langle c, f, R\rangle$. Then the definition specifies a structure $B$ with domain $\{0,1\}$, and interpretations of the constant symbols:

• $c^B = 0$. This is fine.
• $f^B = \{0,1\}$. This is nonsense: $\{0,1\}$ is not a function! See the tips above for correct ways to specify a function.
• $R^B = \{(0,0),(1,1)\}$. This is fine. $R$ is the equality relation on $B$.

Finally, the following thing you wrote doesn't make any sense to me: "f^Z is replaced with the values that will get returned with said statement, R^Z is replaced with the values that will get returned if R^Z is true with said statement."

The interpretation of the function symbol $f$ is a real function, which is not the same as a set of "values that will get returned". The interpretation of a relation symbol $R$ is a real relation. I don't know how to make sense of "values that will get returned if $R^Z$ is true".