Theory and Applications of Categories, Vol. 3, No. 3, 1997, pp. 45–49.

NOTE ON A THEOREM OF PUTNAM’S

MICHAEL BARR

Transmitted by F. William Lawvere

ABSTRACT. In a 1981 book, H. Putnam claimed that in a pure relational language without equality, for any model of a relation that was neither empty nor full, there was another model that satisfies the same first order sentences. Ed Keenan observed that this was false for finite models since equality is a definable predicate in such cases. This note shows that Putnam’s claim is true for infinite models, although it requires a more sophisticated proof than the one outlined by Putnam.

1. Introduction

In an appendix to his 1981 book, Putnam made the following claim.

1.1. Theorem. Let L be a language with predicates F_{1}, F_{2}, …, F_{k} (not necessarily monadic [unary]). Let I be an interpretation, in the sense of an assignment of an intension to every predicate of L. Then if I is non-trivial in the sense that at least one predicate has an extension which is neither empty nor universal in at least one possible world, there exists a second interpretation J which disagrees with I, but which makes the same sentences true in every possible world as I does.

In more familiar language, he is claiming that in for any relational theory in a first order language (without equality as a built-in predicate), there are distinct models that satisfy the same first order sentences. This will true if and only if it is true for a single predicate, so we stick to that case here. Thus we can rephrase his assertion as follows.

1.2. Theorem. Let U be a set and R ⊆ U^{n} an n-ary relation on U. Then either R = ∅ or R = U^{n} or there is a R′ ≠ R in U^{n} that satisfies the same first order sentences as R.

Ed Keenan showed that the equality relation on a two element set is a counter-example and asserted that a similar example could be given on any finite set U ([Keenan, 1995]). He also raised (privately) the question about what was true for infinite sets. The purpose of this note is to show that Theorem 1.2 is true when U is infinite. Of course, Putnam’s proof remains invalid because of the finite counter-example. Putnam does not make it clear whether he is limiting himself to finite models or infinite models or not at all.

In the preparation of this paper, I have been assisted by a grant from the NSERC of Canada and the FCAR du Québec.

Received by the editors 1996 December 15 and, in revised form, 1997 January 14.

Published on 1997 February 20

1991 Mathematics Subject Classification : 03C52, 18B99.

Key words and phrases: model, relational theory, back and forth lemma.

\begin{matrix}c \\ ◯ \end{matrix} Michael Barr 1997. Permission to copy for private use granted.

2. Permutation invariant relations

For a set U and a finite ordinal n = {0, 1,…, n−1}, we view U^{n} as the set of all functions a : n ⟶ U. If a ∈ U^{n}, the kernel pair of a, denoted kerp(a) is the equivalence relation on n defined by kerp(a) = {(i, j) ∈ n × n | a_{i} = a_{j}}.

2.1. Proposition. Let a, b : n ⟶ U. Then there is a permutation σ of U such that a = σ^{∘} b if and only if kerp(a) = kerp(b).

Proof. Since σ is a bijection, we see from a = σ^{∘} b that a_{i} = a_{j} if and only if (σ^{∘} b)_{i} = (σ^{∘} b)_{j} if and only if b_{i} = b_{j}. Thus a and b have the same kernel pair. Conversely, suppose kerp(a) = kerp(b) = α ⊆ n × n. From the diagram

[figure: n; n/α; n; n/α; =; =; U; \overline{b}; U; \overline{a}]

We see that a and b have isomorphic images. Since n is finite, their images also have isomorphic complements.

For an equivalence relation α on n, let R_{α} ⊆ U^{n} denote the set of all functions n ⟶ U whose kernel pair is α. Since each function has a unique kernel pair, it follows that U^{n} = ∑ R_{α}, the sum taken over the equivalence relations on n.

Say that a subset R ⊆ U^{n} is permutation invariant (PI), if a ∈ R and σ a permutation of U implies that σ^{∘} a ∈ R. The preceding proposition implies that,

2.2. Corollary. A subset R ⊆ U^{n} is PI if and only if it is a union of sets of the form R_{α}.

Proof. Since a has the same kernel pair as σ^{∘} a for any permutation σ, it follows that R_{α} is PI. On the other hand, if R is PI, then for any a ∈ R any b ∈ R_{α} has the form b = σ^{∘} a for some permutation σ. Thus if α is the kernel pair of a, we must have R_{α} ⊆ R. Since the R_{α} partition U^{n} the subset R is a union of R_{α}. If we let Γ(R) = {α | R_{α} ⊆ R} we can write that

R = ⋃_{α∈Γ(R)} R_{α}

2.3. Definable sets. Say that a set R ⊆ U^{n} is first order definable (or simply definable) if there is a set of first order sentences (not using equality) that are satisfied by R and by no other subset of U^{n}. Putnam claimed in his proof that the only definable sets are the empty set and U^{n}. He then observed that a definable is PI and seems to have assumed that the only PI sets are the empty set and U^{n}. We have just seen that all the R_{α} are PI. As mentioned, Keenan showed that equality on a finite set was definable. In fact, on a finite set, every PI relation is definable.

2.4. Theorem. Every PI relation on a finite set is definable. Proof. We first show that equality is definable. In fact, if U is an n element set, then equality is the unique binary relation E such that Eq–1. ∀x, xEx;

Eq–2. ∀x, ∀y, xEy ⇒ yEx;

Eq–3. ∀x, ∀y, ∀z(xEy) ∧ (yEz) ⇒ xEz;

Eq–4. ∀x_{1},…, ∀x_{n−1}, ∃x_{n}, ¬(x_{1}Ex_{n}) ∧… ∧ ¬(x_{n−1}Ex_{n}). Next we see that any R_{α} is definable. In fact, R_{α} is definable by the following first order sentence

∀x_{1},…, ∀x_{n}, ((x_{1},…, x_{n}) ∈ R_{α}) ⟺ ((⋀_{iαj} x_{i} = x_{j}) ∧ ( ⋀_{¬iαj} ¬(x_{i} = x_{j})))

Since each R_{α} is definable, so is each finite union of R_{α}, that is, each PI set.

3. The infinite case

We now consider the case of an infinite universe U. We will show that in this case, only the empty and total relations are definable.

Let E be an equivalence relation on U. For an equivalence relation α on n, let E(R_{α}) denote the subset of U^{n} consisting of all a : n ⟶ U for which the kernel pair of the composite n \underrightarrow{a} U ⟶ U/E is exactly α. We note that in general E(R_{α}) neither includes nor is included in R_{α}. For example, suppose that E is not the equality. Then when α is the equality relation, R_{α} consists of the all the injective functions a : n ⟶ U, while E(R_{α}) is the proper subset consisting of all those for which the composite n ⟶ U ⟶ U/E is injective. On the other hand, when α is the trivial relation (all pairs), then R_{α} is just the set of constant functions, while E(R_{α}) is the superset consisting of those for which n ⟶ U ⟶ U/E is constant.

If R is a PI subset of U^{n}, then R = ⋃_{α∈Γ(R)} R_{α}. Define E(R) = ⋃_{α∈Γ(R)} E(R_{α}). We do not define E(R) unless R is PI. Then the following two propositions will demonstrate the claim that only the empty set and U^{n} are first order definable. 3.1. Proposition. Let R ⊆ U^{n} be a PI relation and E be an equivalence relation on U such that each equivalence class is infinite and E(R) = R. Then R = ∅ or R = U^{n}. 3.2. Proposition. Suppose U is an infinite set and E is an equivalence relation U for which there are infinitely many equivalence classes. Then for any R ⊆ U^{n}, the first order theory of R and of E(R) are the same.

Assuming these are proven and that U is infinite, let E be an equivalence relation on U such that there are infinitely many equivalence classes and infinitely many elements in each class. Then if R ∈ U^{n} is definable, it is PI. Since R and E(R) satisfy the same first order sentences, we must also have that R = E(R) and then either R = ∅ or R = U^{n}.

4. Proofs

Proof. [of 3.1] Let a : n ⟶ U be an element of R. Let the image of a consist of the distinct elements u_{1},…, u_{k}. Choose distinct elements v_{1},…, v_{k} ∈ U that are all equivalent mod E. Let σ be any automorphism of U such that σ(u_{i}) = v_{i}, i = 1,…, k. Since R is PI, it follows that σ^{∘} a ∈ R. Since E(R) = R, then σ^{∘} a ∈ E(R), which implies that σ^{∘} a ∈ E(R_{α}) for some equivalence relation α on n. But since a_{i}Ea_{j} for all i, j ∈ n, the only equivalence relation on n such that σ^{∘} a ∈ E(R_{α}) is the total relation n×n. Thus R_{n×n} meets E(R) = R. But R is the disjoint union of R_{α} so this implies that R_{n×n} ⊆ R. Let α be an arbitrary equivalence relation on n and suppose that a : n ⟶ U belongs to R_{α}. Repeat the above construction to get a b : n ⟶ U such that b ∈ R_{α}, and all the values of b are equivalent mod E. This means that b ∈ E(R_{n×n}) ⊆ R and clearly b ∈ R_{α}. Thus R_{α} meets R_{n×n} so that it meets and hence is included in R. Since α was arbitrary, this shows that R = U^{n}.

Proof. [of 3.2] There is a standard method used in logic to prove that two models are isomorphic. It is called the back and forth method since you begin by well-ordering the carriers and then alternate between defining the function and its inverse at the earliest place they are not defined. In this way, you guarantee surjectivity, as well as injectivity. For more details, see [Chang & Keisler], especially the definition on page 114 and Proposition 2.2.4 (ii) on page 115. Define P_{E} : U ⟶ U/E as the projection on the equivalence classes mod E. To apply the back and forth method, we have to define relations I_{m} ⊆ U^{m} × U^{m} by a I_{m} b if kerp(a) = kerp(p_{E} ^{∘} b) and show that

B&F–1. () I_{0} ();

B&F–2. If f : n ⟶ m is an injective function and a I_{m} b, then a^{∘} f I_{n} b^{∘} f

B&F–3. If a I_{m} b and a′ : m + 1 ⟶ U extends a, then there is a b′ : m + 1 ⟶ U that extends b for which a′ I_{m+1} b′.

B&F–1 is vacuously true. B&F–2 is immediate (even if f is not injective) since both squares of

[figure: kerp(a); m × m; kerp(a^{∘} f); n × n; f × f; kerp(p_{E} ^{∘} b); kerp(p_{E} ^{∘} b^{∘} f)]

are pullbacks.

Finally, we show B&F–3. If a′ extends a, there is a new value, a′(m), while a′(i) = a(i) for i = 0,…, m − 1. It may happen that a′(m) = a(i) for some i < m. In that case, just let b′(m) = b(i). Then the kernel pair of a′ is generated by that of a and the additional element (i, m) and the same will be true of p_{E} ^{∘} b′. The other possibility is that a′(m) is distinct from the image of a. In that case, the kernel pair of a′ is generated by that of a. Since there are infinitely many equivalence classes mod E, we can find an element b′(m) ∈ U that is inequivalent mod E to all b(i), i = 1,…, m, in which case the kernel pair of p_{E} ^{∘} b′ will also be generated by the kernel pair of b.

References

[1] C. C. Chang and H. J. Keisler (1990), Model Theory, (3rd edition). North Holland.

[2] E. L. Keenan (1995), Logical objects. Preprint.

[3] H. Putnam (1981), Reason, Truth and History, Cambridge University Press.

Department of Mathematics and Statistics McGill University Montreal, Quebec, Canada

Email: barr@triples.math.mcgill.ca

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/1997/n3/n3.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi and Postscript format. Details will be e-mailed to new subscribers and are available by WWW/ftp. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and LaTEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@triples.math.mcgill.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, University of Genoa: carboni@vmimat.mat.unimi.it P. T. Johnstone, University of Cambridge: ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney: kelly m@maths.su.oz.au Anders Kock, University of Aarhus: kock@mi.aau.dk F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.ruu.nl Susan Niefield, Union College: niefiels@gar.union.edu Robert Paré, Dalhousie University: pare@cs.dal.ca Andrew Pitts, University of Cambridge: ap@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@charlie.math.unc.edu Ross Street, Macquarie University: street@macadam.mpce.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Sydney: walters b@maths.su.oz.au R. J. Wood, Dalhousie University: rjwood@cs.da.ca