[FOM] When is it appropriate to treat isomorphism as identity?

Vaughan Pratt pratt at cs.stanford.edu
Sat Apr 18 20:14:51 EDT 2009

My recent complaint that uniqueness is too often taken for granted when 
dealing with questions of existence brought to light the ease with which 
people identify isomorphism with identity: a number of people wrote to 
remind me that uniqueness is common in many mathematical contexts, e.g. 
  the cyclic group of order 5, the least upper bound of two elements of 
a lattice, etc.

Operations of course enforce uniqueness by definition of "operation": 
the sum of two integers, the concatenation of two lists, the union of 
two sets, etc.  However in a good many of the examples, "the" was not 
enforced by some operation but instead only meant "up to isomorphism."

Sometimes it is necessary to treat isomorphism as identity, sometimes it 
is merely convenient, sometimes it is inconvenient, and sometimes it is 
inconsistent or paradoxical.  Here are examples of each.


1.  Necessary

(a) Equivalence definitions of "lattice".  A lattice can be defined as a 
poset every pair of elements of which has a least upper bound and a 
greatest lower bound, or as an algebra with operations of meet and join 
satisfying the lattice laws (idempotence, commutativity, associativity, 
absorption).  A poset or partially ordered set is a set with a reflexive 
transitive antisymmetric binary relation.  The antisymmetry requirement, 
that (in essence) isomorphic elements are equal, is *necessary for these 
two definitions to be equivalent*.  The notions of least upper bound and 
greatest lower bound continue to be meaningful for preordered sets, 
those for which the relation is only required to be reflexive and 
transitive, but preordered sets with all binary lubs and glbs do not 
form a natural class of algebras.

(b) Birkhoff duality of finite posets and distributive lattices, as per 
David Eppstein's excellent article at 
.  The monotone functions from a finite poset P to the two-element 
chain, i.e. its order filters, form a finite distributive lattice P*, 
the filters (homomorphisms to the two-element lattice) of which recover 
P up to isomorphism.  No such duality obtains for preordered sets, 
making antisymmetry necessary for Birkhoff duality.  Actually there are 
two types of isomorphism entering here, the isomorphism of elements in a 
clique within a preordered set, and the isomorphism between P and the 
poset of lattice filters of P*; regarding the latter it is convenient to 
think of the two posets as the same, but set theoretically unsound, see 
below under "4. Inconsistent".

(c) Enumeration of structures.  Neil Sloane's Encyclopedia of Integer 
Sequences counts the number A_0, A_1, A_2, ..., A_n, ... of posets, 
distributive lattices, tournaments, and many other structures of a given 
size n.  This only makes sense for structures defined up to isomorphism, 
as otherwise every A_i would be a proper class.  (There is however a 
notion of labeled structure which permits enumeration by assuming in 
effect that the n elements are the numbers from 1 to n; with that 
convention there is one labeled set of each finite cardinality, but 
three labeled posets with two elements.)

2.  Convenient

We already mentioned the convenience of identifying P with the filters 
of P* above.  While it's not necessary to identify every countable dense 
linear order with the unit interval of rationals (open, half-open, or 
closed according to which endpoints exist), it can be convenient.  The 
same goes for a great many other structures, e.g. the free group on one 
generator as the group of integers, the initial ring as the ring of 
integers, etc.  Sometimes there is no canonical object, for example the 
Boolean algebra of finite and cofinite subsets of the set N of natural 
numbers under union, intersection, and complement relative to N is 
isomorphic to that of the ultimately constant binary sequences under 
coordinate-wise Boolean combination, with no clear advantage to either. 
  The same goes for the Boolean algebra of periodic binary sequences, 
which is isomorphic to the free Boolean algebra on N as well as to the 
(unique) countably infinite atomless Boolean algebra.

3.  Inconvenient.

The forgetful functor U: Pos --> Set producing the underlying set of 
each poset in the category Pos has a left adjoint F: Set --> Pos which 
maps each set X to the corresponding discrete poset.  Inconveniently, U 
has no right adjoint.  On the other hand the category Ord of preordered 
sets, which extends Pos, has a forgetful functor U+: Ord --> Set which 
conveniently has both a left and a right adjoint.  The left adjoint F+: 
Set --> Ord yields discrete preordered sets as for Pos, while the right 
adjoint G: Set --> Ord yields codiscrete preordered sets or cliques, 
which don't exist in Pos for posets with two or more elements.

4.  Inconsistent

The powers N, N^2, N^3, N^4 of the set N of natural numbers are all 
isomorphic.  Set theory promises that we can implement N^3 as either 
Nx(NxN) or (NxN)xN.  If we use the former then the three projections are 
p, pq, and q^2, if the latter then p^2, qp, and q.  This works fine as 
long as Nx(NxN) and (NxN)xN remain distinct (albeit isomorphic) sets. 
However if we identify NxN with N then according to set theory we must 
have p = p^2, pq = qp, and q^2 = q.  But then p, pq, and q are the only 
functions that can be formed from the two projections from NxN, making 
it impossible to obtain four distinct projections from N^4 no matter how 
realized using NxN.

To make things consistent we could disallow the implementation of N^3 as 
(NxN)xN, but then it would no longer be set theory as we know it, but 
some other theory of sets that we would have to work out afresh. 
Identifying isomorphic sets is inconsistent with set theory as 
standardly defined and used.

(This adapts to set theory a similar argument by John Isbell for 
monoidal categories, see Mac Lane, Categories for the Working 
Mathematician, near the end of VII-1.)


A benefit of mathematical logic is that it makes explicit principles of 
logic that we might otherwise consider inviolable, allowing us to 
consider the consequences of violating them by replacing them with 
competing rules, thereby contributing to the ongoing undermining of the 
efficacy of pure reason.

This raises the following question.  It is clear that arguments 
purporting to show either the existence or uniqueness of any given 
entity beg the question of the necessity of the rules used in those 
arguments.  That said, is the situation entirely symmetric between 
existence and uniqueness, or is there some reason to suppose that 
existence arguments might be supportable by rules having a more 
necessary character than those supporting uniqueness arguments?  To 
demonstrate such an asymmetry would not require absolutely necessary 
rules, only some generally accepted or at least plausible ranking of 
rules by perceived necessity.

Vaughan Pratt

More information about the FOM mailing list