Skip to content

Structures

Structures (or Models)

Given a signature \(\sigma\), a \(\sigma\)-structure \(\mathcal{A}\) consists of the following:

  1. A non-empty set called the domain of \(\mathcal{A}\). Elements of the domain are called elements of \(\mathcal{A}\). We write \(|\mathcal{A}|\) for the domain of \(\mathcal{A}\).

  2. For each constant symbol \(c\) of \(\sigma\), an element of the domain \(c_\mathcal{A}\).

  3. For each function symbol \(F\) of \(\sigma\) with arity \(n\) (i.e., \(r(F)=n\)), an \(n\)-ary function on the domain, denoted \(F_\mathcal{A}\). So, \(F_\mathcal{A}:|\mathcal{A}|^n\rightarrow |\mathcal{A}|\).

  4. For each relation symbol \(R\) of \(\sigma\) with arity \(n\) (i.e., \(r(R)=n\)), an \(n\)-ary relation on the domain, denoted \(R_\mathcal{A}\). So, \(R_\mathcal{A}\subseteq |\mathcal{A}|^n\).

Examples of Structures

Let \(\mathcal{N}\) be the following \(\sigma_{arith}\)-structure:

  1. \(|\mathcal{N}| = \mathbb{N}\)
  2. \(\bar{0}_\mathcal{N}\) is \(0\)
  3. \(\bar{S}_\mathcal{N}\) is the successor function, i.e., \(n\mapsto n+1\)
  4. \(\bar{+}_\mathcal{N}\) is \(+\), i.e., \((m,n)\mapsto m+n\)
  5. \(\bar{\times}_\mathcal{N}\) is \(\times\), i.e., \((m,n)\mapsto m\times n\)

Let \(\mathcal{N}_3\) be the following \(\sigma_{arith}\)-structure:

  1. \(|\mathcal{N}_3| = \mathbb{N}/3\mathbb{N}= \{0, 1, 2\}\)
  2. \(\bar{0}_{\mathcal{N}_3}\) is \(0\)
  3. \(\bar{S}_{\mathcal{N}_3}\) is the function \(\bar{S}_{\mathcal{N}_3}(n) = \begin{cases} n+1 & n<2 \\ 0 & n=2\end{cases}\)
  4. \(\bar{+}_{\mathcal{N}_3}\) is the function that maps pairs of numbers \((x,y)\) to the remainder when \(x+y\) is divided by \(3\).
  5. \(\bar{\times}_{\mathcal{N}_3}\) is the function that maps pairs of numbers \((x,y)\) to the remainder when \(xy\) is divided by \(3\).

Structures

Often, the same name is used for the domain of a structure and the structure. For instance, in the Chiswell & Hodges book, they use \(\mathbb{N}\) for the standard structure (called \(\mathcal{N}\) above).

Observations about Structures

  • There can be different structures of the same signature.
  • The same formula can be true in one structure but false in another. For example, \(\bar{S}(\bar{0}) = \bar{S}\bar{S}\bar{S}\bar{S}(\bar{0})\) is false in \(\mathcal{N}\) but this formula is true in \(\mathcal{N}_3\).
  • Sometimes the same element is named by many different terms. For example, in \(\mathcal{N}_3\), the element \(1\) is picked out by the following terms:
\[\bar{S}(\bar{0}), \bar{S}\bar{S}\bar{S}\bar{S}(\bar{0}), \bar{S}\bar{S}\bar{S}\bar{S}\bar{S}\bar{S}\bar{S}(\bar{0}), \ldots \]

  • There may be structures for a signature with elements of the domain that are not named by any term in the language. For instance, Let \(\mathcal{N}^*\) be the following structure:

    1. \(|\mathcal{N}^*| = \mathbb{N}\cup \{a,b\}\)
    2. \(\bar{0}_{\mathcal{N}^*}\) is \(0\)

    3. \(\bar{S}_{\mathcal{N}^*}\) is the function \(S^*:\mathbb{N}\cup\{a,b\}\rightarrow\mathbb{N}\cup\{a,b\}\) defined as follows: For all \(x\in\mathbb{N}\cup\{a,b\}\):

      \[S^*(x) = \begin{cases} x+1 & x\in\mathbb{N}\\ a & x=a\\ b & x=b\end{cases}\]

    4. \(\bar{+}_{\mathcal{N}^*}\) is the function \(+^*:|\mathcal{N}^*|\times |\mathcal{N}^*|\rightarrow |\mathcal{N}^*|\) defined as follows: For all \(x,y\in\mathbb{N}\cup\{a,b\}\):

      \[+^*(x,y) = \begin{cases} x + y & x,y\in\mathbb{N}\\ a & x = a\mbox{ and } y\in\mathbb{N}\\ b & x = b\mbox{ and } y\in\mathbb{N}\\ b & y = a\mbox{ and } x\in\mathbb{N}\cup\{a,b\}\\ a & y = b\mbox{ and } x\in\mathbb{N}\cup\{a,b\}\end{cases}\]

    Note

    The above is only part of a definition of a structure for \(\sigma_{arith}\). To complete the definition, an interpretation of \(\bar{\times}\) must be provided.

Interpreting Sentences

Closed Terms/Sentences

A term or a quantifier-free formula of \(LR(\sigma)\) is closed if it has no variables in it. A closed qf formula is called a sentence.

Interpreting Closed Terms

Suppose that \(\sigma\) is a signature and \(A\) is a \(\sigma\)-structure. Then for each closed term \(t\) of \(LR(\sigma)\) we define the element \(t_A\) of the domain of \(A\) by:

  1. If \(t\) is a constant symbol \(c\), then \(t_A=c_A\); and

  2. If \(F\) is an \(n\)-ary function symbole of \(\sigma\), and \(t_1,\ldots, t_n\) are closed terms, then

    \[(F(t_1,\ldots, t_n))_A = F_A((t_1)_A,\ldots, (t_n)_A)\]

Truth in a Structure

Suppose that \(\sigma\) is a signature, \(A\) is a \(\sigma\)-structure, and \(\chi\) is a sentence of \(LR(\sigma)\). Then \(\chi\) is true in \(A\), denoted \(\models_A\chi\), is defined as follows:

  1. If \(\chi\) is \(R(t_1,\ldots, t_n)\), where \(R\) is an \(n\)-ary relation symbol of \(\sigma\) and \(t_1,\ldots, t_n\) are terms (which must be closed), then

    \[\models_A\chi \text{ if and only if } ((t_1)_A,\ldots, (t_n)_A)\in R_A\]

  2. If \(\chi\) is \((s=t)\), where \(s\) and \(t\) are closed terms, then

    \[\models_A \chi \text{ if and only if } s_A=t_A\]

  3. If \(\chi\) is \(\bot\), then \(\models_A\chi\) does not hold

  4. If \(\chi\) is \((\neg\varphi)\), then

    \[\models_A \chi \text{ if and only if it is not true that } \models_A\varphi\]

  5. If \(\chi\) is \((\varphi\wedge\psi)\), then

    \[\models_A \chi \text{ if and only if }\models_A\varphi\text{ and }\models_A\psi\]

  6. The definitions of the other Boolean connectives are similar (i.e., when \(\chi\) is \((\varphi\vee\psi)\), \((\varphi\rightarrow\psi)\) or \((\varphi\leftrightarrow\psi)\))

If \(\models_A\chi\), then we say that \(A\) is a model of \(\varphi\).

Terminology

Suppose that \(\sigma\) is a signature and \(\varphi\) is a qf sentence of \(LR(\sigma)\).

  1. We say that \(\varphi\) is valid, denoted \(\models_\sigma\varphi\), if for every \(\sigma\)-structure \(A\), we have that \(\models_A\varphi\).

  2. We say that \(\varphi\) is satisfiable if there is some \(\sigma\)-structure \(A\) such that \(\models_A\varphi\).

  3. We say that \(\varphi\) is a contradiction if there is no \(\sigma\)-structure \(A\) such that \(\models_A\varphi\).

  4. If \(\Gamma\) is a set of qf sentences of \(LR(\sigma)\), then we say that a \(\sigma\)-structure \(A\) is a model of \(\Gamma\), denoted \(\models_A\Gamma\), when \(\models_A\chi\) for all \(\chi\in\Gamma\). Then,

    \[\Gamma\models_\sigma\varphi\text{ if and only if, for every }\sigma\text{-structure }A\text{, if }\models_A\Gamma\text{ then }\models_A\varphi.\]

Exercises

Complete the tutorial questions.