Defining Structures

Now the plot begins to thicken. The previous handout, ``Defining a Language,'' was exclusively concerned with the syntax of a language $\mathcal{L}$. That is, we defined a language by carefully delimiting which strings of basic symbols in $\mathcal{L}$ are formulas (or what logicians sometimes call ``well-formed formulas'' or ``wffs'' for short). But we haven't said anything yet about what these formulas mean. We need a way to specify not only the syntax of a language, but also its semantics; not only which strings are grammatical, but also what their content is. This is what structures are for.

Meaning or semantics has to do with the relation between language and the world, between language and what it represents. The only nonlogical parts of a first-order language, i.e. the only items that can vary from one first-order language to another, are the constant symbols, relation symbols, and function symbols. A semantics for such a language will need to specify what these symbols express. Intuitively, constants represent particular things; function symbols represent functions; and relation symbols represent relations. (Recall the set-theoretic analysis of relations, according to which an $n$-place relation is a set of ordered $n$-tuples, and an $n$-place function is an $n + 1$-place relation that satisfies the condition that no two tuples differ only in their last place.)

So there shouldn't be anything too surprising in the definition of a structure (Leary's Definition 1.6.1, p. 26):

Definition: Fix a language $\mathcal{L}$. An $\mathcal{L}$-structure $\mathfrak{A}$ is a nonempty set $A$, called the universe of $\mathfrak{A}$, together with:

1. For each constant cymbol $c$, of $\mathcal{L}$, an element $c^\mathfrak{A}$ of $A$
2. For each $n$-ary function symbol $f$ of $\mathcal{L}$, a fnction $f^\mathfrak{A} : A^n\to A$
3. For each $n$-ary relation symbol $R$ of L, an $n$-ary relation $R^\mathfrak{A}$ on $A$ (i.e., a subset of $A^n$)

A couple of comments on the notation here may be in order. I don't see that Leary explains the expressions $A^n$ or $f^\mathfrak{A} : A^n\to A$. No doubt he assumes that his readers are already familiar with these notational devices. $A^n$ is simply the set of all the ordered $n$-tuples whose elements are elements of $A$. (Another way to put this involves the notion of the Cartesian product of sets. The Cartesian product $A \times B$ is the set of ordered pairs $(x, y)$ where $x \in A$ and $y \in B$. So $A \times A$ is the set of ordered pairs both of whose members are elements of $A$. Similarly, $A \times A \times A$ is the set of ordered triples all of whose members are elements of $A$. Then $A^n$ is the general case: $A^n$ is $A \times A \times \ldots \times A$ where $A$ occurs $n$ times.) To describe a function $f^\mathfrak{A}$ as $f^\mathfrak{A} : A^n\to A$ is to say that it is a function from $A^n$ to $A$ -- that is, that the domain of the function is $A^n$ and its range is $A$.

A simple example: suppose that $A$ is ${1, 2}$. Then $A^n$ is

$$\{(1,1), (1,2), (2,1), (2,2)\}$$

We can define a binary function $\heartsuit$ that has $A^n$ as its domain: that is, the possible pairs of arguments for the function $x \heartsuit y$ are $(1,1), (1,2), (2,1),$ and $(2,2)$. Similarly, the function has $A$ as its range - that is, the possible values of the function (relative to the universe $A$) are 1 and 2. (For example, $\heartsuit$ might be the max function; in that case $x \heartsuit y$ takes the value 1 for the argument pair (1,1) and takes the value 2 for the other three argument pairs.)