3
$\begingroup$

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:

  1. For each constant symbol $c$ of $L$, an element $c^\alpha$ of $A$.
  2. For each $n$-ary function symbol $f$ of $L$, a function $f^\alpha:A^n \to A$
  3. For each $n$-ary relation symbol $R$ of $L$, an n-ary relation $R^\alpha$ on $A$

A few questions regarding this definition:

  1. When we talk about the nonempty set $A$, is this the same as talking about "the domain" of our structure?
  2. 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$?
  3. What does the superscript $\alpha$ add in terms of meaning? Does it tell us that we are using the "$\alpha$-interpretation" of the symbol?
  4. 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.

$\endgroup$
2
  • 1
    $\begingroup$ Is it the first edition? There is a second edition coauthored with Lars Kristiansen. $\endgroup$
    – John
    Mar 2 at 18:44
  • 1
    $\begingroup$ Since some of your other questions concern nonstandard analysis and the transfer principle, I would guess that part of the motivation for this question comes from trying to understand the meaning of the transfer principle. If so, Goldblatt does a great job of explaining the necessary logical background (including languages and structures) in his book on the hyperreals: Goldblatt, Robert. Lectures on the hyperreals. An introduction to nonstandard analysis. Graduate Texts in Mathematics, 188. Springer-Verlag, New York, 1998. $\endgroup$ Mar 3 at 12:13

1 Answer 1

4
$\begingroup$

Your understanding is correct. Symbols have no meaning until they are interpreted.

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

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

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

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

$\endgroup$
12
  • $\begingroup$ Thank you for the great answer! Just to clarify: are all algebraic structures L-structures, but no the other way around? And also, would another example of an algebraic structure be $[\mathbb{R},+,\cdot]$? $\endgroup$
    – naytte2
    Mar 2 at 14:47
  • 1
    $\begingroup$ Yes, all algebraic structures are logical structures, but not the other way around. Plenty of examples. I have added one to my answer. As for $[\mathbb{R},+,\cdot]$ If you mean the domain of discourse to be the set of real numbers and the language to consist of two binary functions symbols that you interpret as the usual addition $+$ and product $\cdot$ in the set of real numbers, it would be an algebraic structure. However, if you change the interpretation of the symbols, it may not be the case. $\endgroup$
    – John
    Mar 2 at 17:33
  • 1
    $\begingroup$ You may want to add the reference of the book you're reading to your question. $\endgroup$
    – John
    Mar 2 at 17:42
  • 1
    $\begingroup$ I have updated the post now! Also, is the reason that the example you provided is not algebraic that we have not associated any axioms with the $L$-structure? $\endgroup$
    – naytte2
    Mar 2 at 18:16
  • 1
    $\begingroup$ There are no binary operations $H\times H\to H$ in the example and adding the axiom does not yield an algebraic structure. An algebraic structure is not just a set with some binary operations and some axioms. We want these operations and axioms to be arithmetic-like in the sense that they abstract familiar operations like addition, multiplication, division and the like. Think groups, rings, fields. In the language $L=\{\in\}$ of sets a set $A$ is certainly an $L$-structure, but it may not have an algebraic structure (or any other structure). The set of all humans is an example. $\endgroup$
    – John
    Mar 2 at 19:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .