ñòð. 2 |

1.1.5 The Â¯rst model we consider of this sketch is the set of natural numbers.

The value of zero is 0 and succ(i) = i + 1. The model takes nover to the empty set.

This model illustrates the fact that models are permitted to take the empty set

as value on one or more nodes. Classical model theorists have not usually allowed

sorts in a model to be empty.

1.1.6 The second model takes n to the set of integers up to and including an

upper bound N . The value at nover is a one- element set we will call 1, although

any other convenient label (including N + 1) could be used instead. As above,

1.2 The sketch for Â¯elds 3

the value of zero is 0. As for succ, it is deÂ¯ned by succ(i) = i + 1 for i < N , while

succ(N ) = 1. Note that the domain of succ does not include 1.

1.1.7 The third model takes for the value of n also the set of integers up to a

Â¯xed bound N . The value of zero is again 0 and of nover is empty. The operation

succ is deÂ¯ned by succ(i) = i + 1, for i < N while succ(N ) = 0. This is arithmetic

modulo n.

This third model could be varied by letting succ(N ) = N or, for that matter,

any intermediate value. This shows that these models really have at least two

parameters: the value of N and what happens to the successor of N .

1.1.8 Exercises

1. Construct an FD sketch whose only model is the two-element Boolean algebra.

2. Give an example of a sketch which has no models in Set. (Hint: In Set,

1 + 1 61.)

=

1.2 The sketch for Â¯elds

Another example of an FD sketch is the sketch for the mathematical structure

known as a Â¯eld. The concept of Â¯eld abstracts the properties of the arithmetic

of numbers. We will describe it in some detail here. This section is used later only

as an example in Section ES 1.3. Rather than deÂ¯ne `Â¯eld' we will describe the

sketch and say that a Â¯eld is a model of the sketch in sets.

The nodes are 1; u; f; f Â£ f and f Â£ f Â£ f . There are operations

0 : 1 Â¡ f.

!

FO{1

1 : 1 Â¡ u.

!

FO{2

+ : f Â£ f Â¡ f.

!

FO{3

Â¤ : f Â£ f Â¡ f.

!

FO{4

Â¡ : f Â¡ f.

!

FO{5

( )Â¡1 : u Â¡ u.

!

FO{6

j : u Â¡ f.

!

FO{7

The reader should note that the two 1's in FO{2 above are, of course, diÂ®erent.

One of them is the name of a node and the other of an operation. This would

normally be considered inexcusable. The reasons we do it anyway are (a) each

usage is hallowed by long tradition and (b) because they are of diÂ®erent type,

there is never any possibility of actual clash. The reader may think of it as an

early example of overloading.

The diagrams are:

FE{1 (associativity of +): + Â± (id Â£+) = + Â± (+ Â£ id) : f Â£ f Â£ f Â¡ f.

!

4 Finite discrete sketches

(associativity of Â¤): Â¤ Â± (id Â£Â¤) = Â¤ Â± (Â¤ Â£ id) : f Â£ f Â£ f Â¡ f .!

FE{2

(commutativity of +): + Â± hp2 ; p1i = + : f Â£ f Â¡ f . !

FE{3

(commutativity of Â¤): Â¤ Â± hp2 ; p1 i = Â¤ : f Â£ f Â¡ f. !

FE{4

(additive unit): + Â± hid; 0 Â± hii = + Â± h0 Â± hi; idi = id : f Â¡ f!

FE{5

(multiplicative unit): Â¤ Â± hj; j Â± 1 Â± hii = Â¤ Â± hj Â± 1 Â± hi; ji = j : u Â¡ f

!

FE{6

(additive inverse): + Â± hid; Â¡i = + Â± hÂ¡; idi = 0 Â± hi : f Â¡ f !

FE{7

(multiplicative inverse): Â¤ Â± (j Â£ j) Â± hid; ()Â¡1 i = Â¤ Â± (j Â£ j) Â± h()Â¡1; idi = 1 Â±

FE{8

hi : u Â¡ u

!

FE{9 (distributive): + Â± (Â¤ Â£ Â¤) Â± hp1 ; p2; p1 ; p3 i = Â¤ Â± (id Â£+);

+ Â± (Â¤ Â£ Â¤) Â± hp1; p3 ; p2 ; p3i = Â¤ Â± (+ Â£ id) : f Â£ f Â£ f Â¡ f.

!

There are cones deÂ¯ned implicitly and one cocone:

1 u

@ Â¡

0@ Â¡j

@ Â¡

R

@ Â¡

Âª

f

Intuitively, this says that each element of a Â¯eld is either zero or else is an element

of u. u is interpreted as the set of multiplicatively invertible elements in a model.

1.2.1 An example of a Â¯eld is the set of ordinary rational numbers. Expressed

as a model M of the sketch, the numbers M (0) and M (1) are the usual ones,

M (f ) and M (u) are the sets of all rationals and nonzero rationals, respectively,

and M (j) is the inclusion. The arithmetic operations are the usual ones. Other

familiar examples are the real and complex numbers.

1.2.2 In building a model of this sketch, we would have to start with the ele-

ments 0 and 1 and then begin adding and multiplying them to get new elements.

For example, we could let 2 = 1 + 1. Now since M (f) = M (u) + f0g, we have

to decide whether 2 2 M (u) or 2 2 f0g, that is, whether or not 2 = 0. Quite

possibly, the only Â¯elds the reader has seen have the property that 2 60. Even

=

so, one cannot exclude out of hand the possibility that 2 = 0 and it is in fact

possible: there is a model of this sketch whose value at f is f0; 1g with the values

of the operations being given by the tables:

Â¤

+ 01 01

0 01 0 00

1 10 1 01

(These tables are addition and multiplication (mod 2).) If, on the other hand,

2 60, we can form 3 = 1 + 2. The same question arises: is 3 = 0 or not? It is not

=

hard to write down a Â¯eld in which 3 = 0.

1.3 Term algebras for FD sketches 5

Suppose that neither 2 nor 3 is 0? We would deÂ¯ne 4 = 1 + 3 (and prove, by

the way, that 2 + 2 = 2 Â¤ 2 = 4) and ask whether 4 = 0. It turns out that if 2 60

=

then 4 60. In fact, it is not hard to show that any product of elements of u also

=

lies in u. Thus the Â¯rst instance of an integer being 0 must happen at a prime.

But, of course, it need never happen, since no number gotten by adding 1 to itself

a number of times is zero in the rational, real or complex Â¯eld.

1.2.3 A homomorphism between Â¯elds must preserve all operations. Since it

preserves the operation ( )Â¡1 , no nonzero element can be taken to zero. Conse-

quently, two distinct elements cannot go to the same element since their diÂ®erence

would be sent to zero. Thus Â¯eld homomorphisms are injective.

From this, it follows that there can be no Â¯eld that has a homomorphism

both to the Â¯eld of two elements and to the rationals, since in the Â¯rst 1 + 1 = 0,

which is not true in the second. This implies that the category of Â¯elds and Â¯eld

homomorphisms does not have products.

1.2.4 Exercises

1. Prove that in a Â¯eld, if two elements each have multiplicative inverses, then so

does their product. Deduce that if 4 = 0, then 2 = 0.

2. Prove that the next to last sentence of ES 1.2.3 implies that the category of

Â¯elds and Â¯eld homomorphisms does not have products.

1.3 Term algebras for FD sketches

A complication arises in trying to extend the construction of initial term algebras

to FD sketches. As we see from the examples of natural numbers and Â¯elds, an

ñòð. 2 |