Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am having problems understanding the definition of a "structure" in universal algebra. In my course in was introduced in the following way: "A structure $S$ consists of an underlying set $\underline{S}$ together with specified operations $\underline{S}^k \rightarrow \underline{S}$ and relations $ \subseteq \underline{S}^k ,\ k\in \mathbb{N}$".

My problems with this definition are the following:

1) How can this definition be formalized ? By browsing through some books, I have encountered definitions of the type: A structure is a tuple $(A,J)$, where $A$ is a set and $J$ is a set of symbols for functions and relations. And I'm not very happy with this type of definition, which leads to question 2

2) (more of a general question) I find the notion of "set of symbols" (which I frequently encoutered while trying to find a - for me - suitable definition of a structure) very confusing. After all, a symbol is not even a mathematical object itself, it is just a way for us to denote a mathematical object, so how can we suddenly form sets of something non-mathematical ? When considering, for example, the definition of a group, as a tuple $(G,\cdot)$, no one says, that "$\cdot$" is a symbol for a mapping, it is a mapping.

P.S. I know I probably haven't understood something very fundamental, so, please, explain in as much detail as you have time and patience.

EDIT: Thanks for all your great answers; I wish I could select everybody as a "best answer"

share|improve this question
    
The $\cdot$ in $(G, \cdot)$ actually is a symbol, since the function itself is a set of pairs. The two are identified, though. –  Quinn Culver May 27 '11 at 17:42
3  
I think you're picking up on the use–mention distinction, which is something most mathematicians gloss over (if they understand it) or otherwise neglect. A symbol is a symbol. We may assign meaning to it, but philosophically a symbol (the "mention") and what it means (the "use") are distinct things. –  Zhen Lin May 27 '11 at 17:47
    
I really don't see the point for [set-theory] and [universal-algebra] for this question. I'm not 100% sure about [model-theory], but it seems fitting enough. –  Asaf Karagila May 27 '11 at 17:56
1  
@temo: “Set of symbols” formally is just any set. Such a phrase says that we have assigned the informal meaning to elements of that set in order to prop our intuitions. Likewise: elements of a vector space are called “vectors”, but if you look for the definition of a vector, it is “an element of some vector space”. Circularity? No, it's just informal labels not having any formal definition. –  beroal May 27 '11 at 18:07
    
@Asaf The question arose from a definition in universal algebra, so I think the [universal-algebra] tag is appropriate. Since providing the requested "detail" really requires formalizing model theory within set theory, I think the [set-theory] tag is appropriate. –  Quinn Culver May 27 '11 at 18:17

4 Answers 4

up vote 8 down vote accepted

temo:

The idea of symbols is easy to formalize, though whichever route you follow, the formalization may look a bit awkward while you get used to it. One way is as follows: A set of symbols consists of 3 disjoint sets $A,B,C$. We call the elements of $A$ "constant symbols". We call the elements of $B$ "function symbols", and the elements of $C$ "relation(al) symbols". Moreover, $B$ is the disjoint union of sets $B_n$, $0<n\in{\mathbb N}$, and the elements of $B_n$ are the symbols for $n$-ary functions. Similarly, $C$ is the union of sets $C_n$, and the elements of $C_n$ are the symbols for $n$-ary relations.

One can change this in several ways. For example, we can think of constant symbols as $0$-ary function symbols, and we could even make do with only relation symbols at the cost of adding some additional axioms later (indicating that some symbols represent the graph of a function). Also, one could add infinitary relation or function symbols, if one wanted, but the setting above is the most classical.

One can also be even more precise, if one so wanted. For example, you could state that a symbol is a triple $(\alpha,\beta,\gamma)$ where $\alpha=0$ or $1$, $\beta\in{\mathbb N}$, and $\gamma$ is an ordinal. We call triples of the form $(0,0,\gamma)$ constant symbols, of the form $(0,n,\gamma)$ with $n>0$ function symbols, and of the form $(1,n,\gamma)$ relation symbols, and we require that $n>0$ in the last case. A set of symbols is then just a subset of the class of triples just described.

The above is simply a pedantic way of emphasizing that there is nothing "non-mathematical" in the concept of "symbol".

Now, given a set $S$ of symbols, a structure of type $S$ (or "in language $S$") is a tuple $M=(A,F)$ where $A$ is a non-empty set, and $F$ is a function with domain $S$. We have that

  • $F(0,0,\alpha)\in A$ for all $(0,0,\alpha)\in S$,
  • $F(0,n,\alpha)$ is a function $A^n\to A$ for all $(0,n,\alpha)\in S$ with $n>0$, and
  • $F(1,n,\alpha)\subseteq A^n$ for all $(1,n,\alpha)\in S$.

Of course, one never writes things this way. Given a symbol $c$, we write $c^M$ for $F(c)$, so $c^M$ is a constant (an element of $A$) if $c$ is a constant symbol, and similarly, $f^M$ is a function (an $n$-ary function, in fact, if $f$ is of the form $(0,n,\alpha)$), and $R^M$ is an $n$-ary relation if $R$ is a relation symbol of the form $(1,n,\alpha)$.

Still the above looks ridiculously convoluted. Note that different symbols $c$ and $d$ may have the same interpretation $c^M=d^M$, for example.

The question is then, independently of how one ends up formalizing the concept of "symbol", why do we use it at all instead of just using the functions, etc, directly.

One of the points here is that we may want, for example, to talk about certain structures defined by axioms. Say, groups. We need a language to write down these axioms. The language consists of some logical symbols and some non-logical ones. The non-logical ones typically consist of a constant symbol $e$, a unary function symbol $i$, and a binary function symbol $f$. We could set $e=(0,0,0)$, $i=(0,1,0)$, and $f=(0,2,0)$ if we wanted.

We write the axioms saying that $e$ is to be interpreted as the identity of $f$: For all $a$, $f(a,e)=f(e,a)=a$; that $f$ is associative: For all $a,b,c$, $f(a,f(b,c))=f(f(a,b),c)$; and $i$ is an inverse for $f$: For all $a$, $f(a,i(a))=f(i(a),a)=e$.

Again, we may write this in more palatable ways, $a*(b*c)=(a*b)*c$, etc.

A group is then a structure $M$ in the language of groups, that satisfies the three axioms above when $e,i,f$ are understood to mean $e^M,i^M,f^M$, respectively.

Note that the same language allows us to talk about many different classes of structures, not just groups. Using symbols allows us to be able, in a uniform way, to refer to these structures, to define what a homomorphism between structures is, to explain how a structure of a certain kind can be transformed into a structure of another kind, etc, without having to go into the details of what the structures actually are or what properties they satisfy.

Of course, one may very well argue directy in terms of structures, and never mention symbols. Neither approach is better than the other. We use the formal format above because it makes certain details easier, but at least at an introductory level, not much would be lost if we never used symbols directly. But it is a good idea to invest some time in working with them.

Here is an example: Say we have a binary relation symbol $R$. A typical example would be a structure $M$ where the interpretation $R^M$ is a linear order $<$. But there are many different possibilities: $R$ could be a partial order, the edge relation in a directed graph, or something else entirely. The statement "For all $a$ there is a $b$ with $aRb$" is true in some of these structures and false in others. But to even say this would be awkward without symbols, because you need to talk about what $R$ means in each specific structure otherwise, and you would end up referring to the interpretation of $R$ in each case anyway.

A word about your final comment: A group $(G,\cdot)$ is a tuple, where $\cdot$ is a mapping. This mapping is the interpretation of a symbol for a mapping. When you discuss the axioms of groups or specific properties you want to study, you use a symbol for a mapping. When discussing groups that may or may not have the properties you are looking for, you use mappings that interpret these symbols.

Let me close with a comment that this idea of distinguishing between symbols and their interpretations actually becomes very important in some contexts. For example, in logic, we have Gödel's famous incompleteness theorem that tells you, in particular, that the basic axioms for (first order) number theory cannot prove all truths about numbers. The first step in the proof of this result consists in coding the statements of number theory using number theory. Note this is a bit of a problem: Number theory is about numbers, not about logical formulas that talk about numbers. What we do first is to code the symbols of number theory using numbers, so "2+3=5" could be coded by, say, a number of the form $2^a3^b5^c7^d11^e$ where $a$ is a number that codes the symbol 2, $b$ is a number that codes the symbol $+$, $c$ is a number that codes the symbol $3$, etc, and here it becomes clear that it is important to distinguish, for example, between the actual number 2 and the code for it.

share|improve this answer

Such details matter more in model theory than in universal algebra (where notational abuse abounds). So it's not too surprising to see more attention to such details in model theory textbooks. For example, it is explained nicely on the first page of Hodges' excellent textbook Model theory. Below is an excerpt. enter image description here enter image description here enter image description here

And on how the structure is explicitly represented

enter image description here

Finally, note that one chooses the named operations in the signature so that the universal notions of homomorphism and substructure agree with the classical notions - see here.

share|improve this answer
1  
I'm quite curious to know the reason for the downvote. –  Bill Dubuque May 28 '11 at 17:34

I am not sure what you mean by "formalized." The definition, as it was introduced in your course, has to me the same look and feel as other definitions that we make in mathematics.

The definition, implicitly and explicitly, used set-theoretic language. We can make the definition more formal by using explicitly a formalized set theory, such as ZFC. For most purposes, this does not add enough to be worth doing.

You are perfectly correct in observing that for a structure, we need honest to goodness functions (which can be defined set-theoretically, if necessary) and subsets, not "symbols."

When we do Model Theory, which in some sense is the logician's version of Universal Algebra, we do introduce a language. We have the usual logical symbols, parentheses, a symbol for equality, symbols for variables (or a method for generating such symbols), quantifiers, as well as the following kinds of symbols, appropriate to the "algebra" under study.

(1) function symbols

(2) relation symbols

(3) constant symbols (which can be thought of as $0$-ary function symbols)

We then define, after a while, what one means by a (well-formed) formula.

All this is at the language level. But a language is for talking about things. So for any language $L$, one defines what one means by an $L$-structure. This is, essentially exactly, what was called a "structure" in your course.

Model Theory, in the main, deals with the interaction between linguistic objects (sentences, formal proofs) and structures. While studying these interactions, it is highly desirable to remain constantly aware of the fact that languages and structures are different.

To sum up, your objection to the use of the term "symbol" for real objects is absolutely correct. If $f$ is a (say unary) function symbol of the language $L$, and $G$ is an $L$-structure, the interpretation of $f$ in $G$ is an honest to goodness function from the underlying set of $G$ to itself. In Model Theory, the usual notation for this function would be $f_G$.

Note that $f$ and $f_G$ are very different kinds of things. In another $L$-structure $H$, the interpretation of $f$ in $H$ should be called $f_H$.

However, this all can be a bit of a nuisance, and can make mathematical writing look awful, so the formal distinction is often not observed in practice. Sometimes a bit of deliberate notational sloppiness can be useful!

share|improve this answer

The notion of a structure comes up in algebra and mathematical logic exactly when we want to distinguish different interpretations of the same syntactic elements.

For example, we could make one algebraic structure whose elements are natural numbers and in which $a \odot b$ means $a + b$. We can make another structure with the same elements but in which $a \odot b$ means $a + 3b$. Both of these use the same symbol, $\odot$, to refer to their operation. But the operation itself is not the same, just the symbol.

So abstracting this, suppose that we want to talk about all algebraic structures in which there is just one binary operation symbol, $\odot$. Well, such a structure must have some set of elements, and it must have some actual binary operation that is assigned to the symbol $\odot$. This is where the definition of a structure comes from.

If you are worried about making the symbol a mathematical object, you could just make some arbitrary definition such as "the symbol $\odot$ is just an abbreviation for the number 1". But this gets confusing because you might have a structure that has 1 as an element, so now 1 is playing double duty. That doesn't lead to any mathematical problems, but it's easier to treat the symbol $\odot$ as a mathematical object itself rather than to try to formally replace it with some arbitrarily-chosen mathematical object.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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