[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
http://en.wikipedia.org/wiki/Birkhoff's_representation_theorem#Functoriality
. 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