# Cryptomorphisms

I am curious to collect examples of equivalent axiomatizations of mathematical structures. The two examples that I have in mind are

1. Topological Spaces. These can be defined in terms of open sets, closed sets, neighbourhoods, the Kuratowski closure axioms, etc.

2. Matroids. These can be defined via independent sets, bases, circuits, rank functions, etc.

Are there are other good examples?

Secondly, what are some advantages of multiple axiomatizations?

Obviously, one advantage is that one can work with the most convenient definition depending on the task at hand. Another is that they allow different generalizations of the object in question. For example, infinite matroids can be axiomatized by adapting the independent set axioms, but it is unknown how to axiomatize them via the circuit axioms. An acceptable answer to the second question would be an example of a proof in one axiom system that doesn't translate easily (not sure how to make this precise) into another axiom system.

-
Generally, these kinds of questions are community wiki, since you're asking for examples instead of a definitive answer to a particular question. –  Qiaochu Yuan Feb 18 '10 at 17:37
I think you're looking for examples of "cryptomorphisms." This is a bit looser (and more interesting) than equivalent axiomatizations, which would technically require the languages to be the same. –  François G. Dorais Feb 18 '10 at 18:11
Maybe You are interested in answer for my question which shares similar idea:mathoverflow.net/questions/14639/… It may be interesting for You as certain structure You want to axiomatize is a defined model for abstract axiomatization You get as output. So question how many axiomatization is possible probably fit here, and then we know that for any given structure there is infinite axiomatizations... Which are the interesting one? I have no idea;-) –  kakaz Feb 18 '10 at 20:19
@François. Indeed I am thinking of "cryptomorphisms." Thanks for the clarification. –  Tony Huynh Feb 18 '10 at 21:21
You can find some interesting examples by doing a Google books search for the phrase "take this to be the definition". –  Timothy Chow Jun 18 '10 at 22:10

The phenomenon that I think you have in mind has a name: cryptomorphism. I learned the name from the writings of Gian-Carlo Rota; Rota's favorite example was indeed matroids. Gerald Edgar informs me that the name is due to Garrett Birkhoff.

I think modern mathematics is replete with cryptomorphisms. In my class today, I presented the "Omnibus Hensel's Lemma". Part a) was: the following five conditions on a valued field are all equivalent. Part b) was: complete fields satisfy these equivalent properties. There are lots more equivalent conditions than the five I listed: see

An unfamiliar (to me) form of Hensel's Lemma

and especially Franz Lemmermeyer's answer for further characterizations.

I would say that the existence of cryptomorphisms is a sign of the richness and naturality of a mathematical concept -- it means that it has an existence which is independent of any particular way of thinking about it -- but that on the other hand the existence of not obviously equivalent cryptomorphisms tends to make things more complicated, not easier: you have to learn several different languages at once. For instance, the origin of the question I cited above was the fact that in Tuesday's class I st*p*dly chose the wrong form of Hensel's Lemma to use to try to deduce yet another version of Hensel's Lemma: it didn't work! Since we are finite, temporal beings, we often settle for learning only some of the languages, and this can make it harder for us to understand each other and also steer us away from problems that are more naturally phrased and attacked via the languages in which we are not fluent. Some further examples:

I think that the first (i.e., most elementary) serious instance of cryptomorphism is the determinant. Even the Laplace expansion definition of the determinant gives you something like $n$ double factorial different ways to compute it; the fact that these different computations are not obviously equivalent is certainly a source of consternation for linear algebra students. To say nothing of the various different ways we want students to think about determinants. It is "just" the signed change of volume of a linear transformation in Euclidean space (and the determinant over a general commutative ring can be reduced to this case). And it is "just" the induced scaling factor on the top exterior power. And it is "just" the unique scalar $\alpha(A)$ which makes the adjugate equation $A*\operatorname{adj}(A) = \alpha(A) I_n$ hold. And so forth. You have to be fairly mathematically sophisticated to understand all these things.

Other examples:

Nets versus filters for convergence of topological spaces. Most standard texts choose one and briefly allude to the other. As G. Laison has pointed out, this is a disservice to students: if you want to do functional analysis (or read works by American mathematicians), you had better know about nets. If you want to do topological algebra and/or logic (or read works by European mathematicians), you had better know about filters.

There are (at least) three axiomatizations of the concept of uniform space: (i) entourages, (ii) uniform covers, (iii) families of pseudometrics. One could develop the full theory using just one, but at various points all three have their advantages. Is there anyone who doesn't wish that there were just one definition that would work equally well in all cases?

-
Nice answer Pete. Your determinant example made me ponder if cryptomorphisms are simply different ways to think about the same thing. The latter is somehow a bit more meta than I originally intended, but I think it gets to the heart of the matter. Along these lines there is the Von Neumann bicommutant theorem, which gives one two equivalent ways to think about bounded operators on a Hilbert space (algebraically or topologically). –  Tony Huynh Feb 19 '10 at 18:50
cryptomorphism ... I heard it from Garrett Birkhoff and had the impression it was his coinage. From Wikipedia: "The word was coined by Garrett Birkhoff before 1967, for use in the third edition of his book Lattice Theory." –  Gerald Edgar Feb 19 '10 at 19:17
@Gerald: thanks. I didn't know that. I didn't quite claim that the usage was original to Rota, but still it will be an improvement to mention Birkhoff. I'll do xo. –  Pete L. Clark Feb 19 '10 at 22:26
I can't see how any of the examples in the answer fits into the concept of cryptomorphism as defined (@Gerald: "formally", contrary to what Wikipedia states at least today) in G. Birkhoff's Lattice Theory, 3rd. ed. 1967, 7th corrected printing 1993, p. 154. It appears there in the chapter on universal algebra. I wonder why this concept, or some improvement of it, is not presented more regularly in algebra texts. –  Lutz Mattner Aug 12 '14 at 14:39

For one take, see Feynman's lectures at Cornell. Among other things, he talks about how there are many equivalent axiomatizations for physics. Although the different axiomatizations are mathematically equivalent, they suggest different understandings of the world, and hence different experiments on the one hand and different metaphysics on the other.

-

There are nice examples in geometry. For example, the Euclidean plane can be characterized on the one hand by Hilbert's axioms, on the other hand by axioms for complete ordered field $+$ vector space $+$ inner product.

Another example is that of a Pappian plane, characterized on the one hand by the three projective plane axioms $+$ Pappus theorem, on the other hand by the field axioms (from which the plane may be constructed via homogeneous coordinates).

-

Here is one example that I always found fascinating.

• Frames are complete lattices which satisfy the infinite distributive law $$U \wedge \bigvee_{i \in I} V_i = \bigvee_{i \in I} U \wedge V_i.$$ In pointfree topology, these are used to abstract the lattice of open sets of a topological space.

• Complete Heyting algebras are complete lattices which have a binary operation ${\Rightarrow}$ that satisfies $$U \wedge V \leq W \quad\mbox{iff}\quad U \leq V \Rightarrow W.$$ These are primarily used to interpret intuitionistic logic.

The fact that these two types of lattices are cryptomorphic is essentially the Adjoint Functor Theorem (when viewing the underlying partial order as a category).

-
Don't forget locales. But although these are "the same objects", they form different categories since they have different morphisms (even the wikipedia page on Complete Heyting Algebras mentions this). –  Jacques Carette Mar 20 '10 at 21:44

If you don't mind working in equational logic (no relation symbols besides equality, and focusing only on universally quantified equations), then there are many examples in universal algebra. Groups have axiomatizations with and without a symbol for inverse, and even within the same language there is interest in alternative axiomatizations for the same theory, e.g. Boolean algebras, Heyting algebras, lattices.

If you want logics with more expressive power, you may consider interpretability results as well, which are ways of "encoding" one theory into another. I only know of applications of this to show undecidability of theories, but there is a study of other objects around the notion of interpretability that Ralph McKenzie and others have created/discovered.

Gerhard "Ask Me About System Design" Paseman, 2010.02.18

-
If the group example in the second sentence was intended to connect with "If you don't mind working in equational logic" in the first sentence, then I disagree. It seems to me that, in order to axiomatize groups in a language with only multiplication and identity (no inverse), one needs sentences that contain both universal and existential quantifiers, like $\forall x\exists y\,(xy=e)$. The point is that, in this restricted language, a subalgebra (in the sense of universal algebra) of a group need not be a group (but merely a monoid). –  Andreas Blass Nov 26 '10 at 17:26
Andreas, you may choose the axiomatization you prefer. I do not recall an equational characterization which has only multiplication and identity for groups, but I do know that there are those with a constant symbol for the identity, as well as one without, which will characterize groups, and I believe that there is an equational characterization of groups using just the similarity type <2,0>. So if you are disagreeing with my preference, that is your perogative; be careful that you are not disagreeing with fact. Gerhard "Austin Identities Come To Mind" Paseman, 2010.11.26 –  Gerhard Paseman Nov 26 '10 at 22:29
I was writing about fact, not preference. I believe the last sentence of my previous comment suffices to show that there is no axiomatization of the notion of group that simultaneously (1) uses only multiplication and identity element (not inversion) and (2) consists entirely of universally quantified equations. If you know of such an axiomatization, I'd like to see it, so that I can track down where my argument goes wrong. –  Andreas Blass Nov 28 '10 at 23:00
Since the subject was about cryptomorphisms, I thought alternate characterizations (e.g. ternary operations used to represent Abelian groups, single functions that encode mutliplication and inverse) were of interest. With a symbol that again represents the group multiplication, I too know of no pure equational characterization without another function symbol. If you only intend to say such a characterization does not have the same multiplication because it includes monoids, I agree, but think such reading of this answer misses the point. Gerhard Paseman, 2010.11.28 –  Gerhard Paseman Nov 29 '10 at 5:12

A very familiar example is given by the different ways to express the completeness property of the real line --- Cauchy sequences converge, bounded nonempty sets have suprema, etc.

-

Theodore Hailperin found a finite set of axioms for Quine's NF set theory. This finite axiomatization consists of a short list of particular instances of the NF axiom scheme of "stratefied comprehension." The advantage of Hailperin's alternate axiomatization is that it eliminates the necessity of referring to the concept of type in the definition of NF. See Hailperin's article "A set of axioms for logic" [Journal of Symbolic Logic, Volume 9, Issue 1 (1944), pp. 1-19].

-

Does the Cardinal Equivalence interest you? Satisfying assignments have lower level semantics than valid quantifications, but their cardinalities are equivalent:

Boolean formulas: |valid quantifications| = |satisfying assignments|.

That is, for formula B(x1,..xn), variables ordered from 1 to n: the number of valid quantification prefixes (q1..qn, over x1 to xn) of B, is Equivalent to the number of satisfying assignments of B. The cardinality range is from zero for contradictions through 2^n for tautologies (technical notice: n+1 bits are needed to represent these cardinality for tautologies; thus, there is some practical difficulty about finite propositional formulas performing logic with their own number of solutions).

I only know this theorem for finite propositional boolean formulas; higher order extensions of the equivalence merely seem plausible, with some effort. So, if you "axiomatize" counting propositional assignments, you would also be solving the higher level problem, counting valid QBFs. (Cardinal Equivalence is the only known equivalence in the boolean hierarchy; manifestations elsewhere seem "likely", but also "omh" (over my head).)

-