I understand that structures are means by which we know how to interpret certain languages. So for example, in the language of number theory, we might have $\displaystyle L=\left\langle 0,S,+,\cdot,E,< \right\rangle$. As I understand it, without specifying our strucutre, we do not know how to inerpret the symbols of our language. The book I am reading provides the following definition:
Fix a language $L$. An $L$-structure $\alpha$ is a nonempty set $A$,
called the universe of $\alpha$, together with:
- For each constant symbol $c$ of $L$, an element $c^\alpha$ of $A$.
- For each $n$-ary function symbol $f$ of $L$, a function $f^\alpha:A^n \to A$
- For each $n$-ary relation symbol $R$ of $L$, an n-ary relation $R^\alpha$ on $A$
A few questions regarding this definition:
- When we talk about the nonempty set $A$, is this the same as talking about "the domain" of our structure?
- Does the second point in the definition mean that our structure is "closed", i.e. that every functional relation will take $n$ elements from our universe and associate them with another element, also in the universe? So that no function can ever associate anything with an element outside the set $A$?
- What does the superscript $\alpha$ add in terms of meaning? Does it tell us that we are using the "$\alpha$-interpretation" of the symbol?
- Is this what is also called an "algebraic" structure?
The book I am reading is A Friendly Introduction to Mathematical Logic by Christopher C. Leary and Lars Kristiansen.
Best Answer
Your understanding is correct. Symbols have no meaning until they are interpreted.
Yes, $A$ is the domain of the $L$-structure $\alpha$. You specify the language $L$ and then interpret the symbols of the language in $\alpha$. That is why it is called an $L$-structure. You may encounter the notation $$\alpha:=\left(A,\{R^{\alpha}:R\in L\},\{f^{\alpha}:f\in L\},\{c^{\alpha}:c\in L\}\right)$$ Which is just notation to tell us what the $L$-structure $\alpha$ consists of, as the definition you provided.
Yes, if $f\in L$ is an $n$-ary function symbol, then its interpretation $f^{\alpha}$ is a function with domain $A^{n}$ and range always a subset of the domain of interpretation $A$. Meaning is always with respect to one domain. If the domain changes, the meaning may change. But you cannot have two different meanings within the same domain.
The superscript is notation to tell us we are talking about an element of the domain $A$. If $c\in L$ is a constant symbol, then $c^{\alpha}\in A$ is the element of a corresponding to the interpretation of $c$ in $A$. If $f$ is a function symbol, $f^{\alpha}$ is the function corresponding to the interpretation of $f$, and so on.
No, an algebraic structure consists of a nonempty set $X$ (also called the domain or underlying set), a collection of operations on $X$ (e.g addition and multiplication if applicable), and a finite set of axioms that the operations must satisfy. For example, groups, rings and vector spaces are examples of algebraic structures. However, an algebraic structure is indeed a particular type of logical structure. For example, consider the language of rings: $L=\left<\dot{0},\dot{+},\dot{-},\dot{\times}\right>$ (where I use dots to emphasize these are symbols of the language). We have not given these symbols meaning yet, and $\dot{0}$ is a constant symbol, $\dot{-}$ is a $1$-ary function symbol, and $\dot{+}$ and $\dot{\times}$ are $2$-ary function symbols. Then, a group with underlying set $G$ is an algebraic structure, and it is also an $L$-structure $\alpha:=(G,0,+,-\times)$ subject to the group axioms (here I am denoting the interpretation of the symbols of the language $L$ simply by removing the dot over them, e.g $\dot{+}^{\alpha}:=+$).
Example: Take as domain $H$ the set of all humans. The language $L$ consists of the following symbols (with their intuitive meaning in parenthesis): 1-ary function symbols $m$ (mother of) and $f$ (father of), $1$-ary relation symbols $M$ (man) and $W$ (woman), binary relation symbols $P$ (parent of), $C$ (child of), $\ell$ (loves), and constant symbols $\{\text{Adam}, \text{Mary}, \ldots\}$ (names). The $L$-structure $$\alpha=(H,m^{\alpha},f^{\alpha},M^{\alpha}, W^{\alpha}, C^{\alpha}, \ell^{\alpha}, \{\text{Mary}^{\alpha}, \text{Adam}^{\alpha},\ldots\})$$ is not algebraic. Symbols are interpreted according to their intuitive meaning. For example, $P^{\alpha}$ is the $2$-ary relation "parent of" in the domain $H$ of all humans, and $\text{Mary}^{\alpha}$ is a human named Mary.
Example: Consider the language of sets $L=\{\in\}$ (i.e. $\in$ is a binary relation symbol). The set of real numbers $\mathbb{R}$ with $\in$ interpreted in the usual way is an $L$-structure. But it does not have a defined algebraic structure. If we add to $L$ the symbols $+$, $-$, $\cdot$, $0$, $1$ defined and interpreted in the usual way (i.e. $+$, and $\cdot$ are interpreted as the usual binary operations) and we add the field axioms, then in the augmented language the $L$-structure now has an algebraic structure defined- that of a field.
A final point: For any $L$-structure $\alpha$, an assignment is a function $a:\{\text{set of variables of $L$}\}\to A$. Relative to the assignment $a$ of $\alpha$ you will see notation like $c^{\alpha}[a]$, or $f^{\alpha}[a]$ denoting the interpretation of the symbols in $A$ relative to the assignment $a$ of the variables.