[Prev][Next][Index][Thread]

Penultimate algebras

Date: Sat, 12 Nov 88 23:06:09 PST

To: meyer@theory.LCS.MIT.EDU
Cc: coraki!pratt@sun.com

In my previous message I remarked parenthetically that I did not have a
formalization of the notion of "close-to-final."  This message proposes
one such formalization.  To distinguish it from other formalizations I
suggest the term "penultimate."

Definition.  An algebra A is *penultimate* in a class C of algebras of
a given similarity type when for every algebra B in C there exists an
epimorphism (onto homomorphism) from B onto A.

Proposition X.  Penultimate algebras are isomorphic.

Proposition X is clearly a theorem for finite penultimate algebras, and
also for the empty signature, i.e. sets, by the dual of
Cantor-Schroeder-Bernstein.  It can fail for uncountable penultimate
algebras [Hanf, Math. Scand. 5, 1957].  It seems to be open for
countable algebras in general, but (unless I've misinterpreted
something) it does hold between any two algebras when one of the two
epimorphisms between them is of finite index (at most finitely many
elements sent to the same element) [McKenzie, Fund.  Math. 70, 1971,
see also McKenzie,McNulty,Taylor, "Algebras, Lattices, Varieties," Vol
I, Wadsworth & Brooks/Cole, 1987, section 5.7].

Hanf's uncountable counterexample cannot arise as a penultimate algebra
in the sort of formal specification considered thus far, unless one of
the given algebras is uncountable, which it won't be if the given
algebras are themselves defined as either initial or penultimate
algebras with countable signatures.  And in general counterexamples to
Proposition X seem to be hard to construct.  Hence:

Conjecture.  For any class of algebras arising as the class of models
of an algebraic specification, Proposition X is a theorem.

This conjecture is of course parametrized by the details of the
specification methodology, in particular by the permitted specification
language:  pure equations, universal Horn clauses, general Horn
clauses, first order sentences, first order theories, theories with
various generalized quantifiers, etc.  I'd be happy to see the outcome
for the case of pure equations, as typified by Albert's and my
examples.  However I strongly conjecture it for everything up to at
least first order theories.

Where Proposition X does hold, penultimate algebras are just as blessed
as final algebras.  The difference is that there may be more than one
isomorphism from any given penultimate algebra to another.  In view of
the existence of useful algebras with nontrivial automorphisms but
specifiable as penultimate algebras, this would seem to make
penultimate algebras more useful than final algebras.  After all, the
main point of finality is surely uniqueness of the final object up to
isomorphism, not uniqueness of the isomorphism itself, which we now see
can actually get in the way.  (Cf. Mac Lane's question in CFTWM, p.57:
"The general fact of the uniqueness of the universal arrow implies the
uniqueness of the completed object, up to a unique isomormorphism (who
wants more?)."  Here we actually want less!)

As with final algebras it is natural to generalize "penultimate
algebra" to "penultimate object."  The obvious abstraction generalizes
epimorphism (onto homomorphism) to epi morphism (morphism f is epi when
for all g,h, gf=hf implies g=h). 

Proposition Y.  Penultimate objects are isomorphic.

As with Proposition X, Proposition Y holds in the finite case but may
fail in the infinite case, rather more simply than Proposition X
however.  First a handy lemma.

Lemma 1.  Let a,b be objects of a category C with epis f:a->b, g:b->a,
and let C' be the subcategory of C generated by f and g.  Then a and b
are isomorphic in C' if and only if C' is not freely generated by f and
g.

Proof.  (Only if) Free categories are skeletal (distinct objects are not
isomorphic). 

	(If) For the subcategory not to be freely generated we must
	 i       j
have (fg)  = (fg)  for i>j (or similar depending on which of the 4
homsets the identification arises in).  But by cancelling on the
                    i-j                        i-j-1
right we obtain (fg)    = 1, whence f and g(fg)      constitute a pair of
isomorphisms.

Now, first a case where Proposition Y holds.

Theorem 2.  Penultimate objects are isomorphic when C has finite
homsets.

Proof.  If a and b are penultimate then there is an epi between them in
each direction.  By Lemma 1, if a and b are not isomorphic then those
epis must generate a free category C'.  Since the epis form a cycle the
generated homsets of C' (a subcategory of C) must be infinite, whence
so must those of C.

Next, a countable counterexample to Proposition Y.

Theorem 3.  In the free category generated by a strongly connected
graph (one having a path from any object to any other), every object is
penultimate yet no two objects are isomorphic.

Proof.  Every object is penultimate because every morphism of a free
category is an epi (as well as a monic) and the strongly-connected
condition ensures that every homset is nonempty.   No two objects are
isomorphic in a free category.

Since countably generated free categories have countable homsets this
provides us with a ready supply of countable counterexamples to
Proposition Y.

However categories of algebras enjoying the usual sorts of closure
properties such as HSP associated with algebraically defined classes
are far from free, suggesting the following.

Problem.  Give reasonable conditions on C sufficient to ensure that the
penultimate objects of C are isomorphic.

Ideally these conditions should allow all categories that arise as the
class of solutions of an equational specification, in which case one
might end up with a simple categorical solution to my conjecture above,
just as the uniqueness up to isomorphism of final algebras is most
simply understood categorically.
-v