3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you Alex for a long descriptive answer. I've later on realized that I've mixed structures and models together. Sorry for taking up time. $\endgroup$ – Fredrik Andersson Aug 20 '18 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.