Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The motivation for the following question comes from finite model theory, but it is not a technical question about this field, and it is particularly directed at people working in other fields.

It happens in mathematics that you can state some property of finite structures (graphs, finite groups etc.) "more easily" using the assumption that the structure comes with a linear order. Often this assumption comes in disguise, e.g. when one considers only permutations of initial segments of the natural numbers instead of arbitrary finite sets. Let me give an example to explain what I mean:

Example: Parity of permutations

The parity of a permutation $\pi$ of a finite set $X$ is usually defined as the unique number modulo 2 of transpositions into which $\pi$ can be decomposed. A basic and very well known theorem states that this number is even iff for each linear order on $X$ the number of inversions of $\pi$, i.e. pairs $x,y \in X$ such that $x < y$ but $\pi(x) > \pi(y)$, is even. The number of inversions is independent of the choice of linear order on $X$, i.e. if the number of inversions is even for one linear order on $X$ then this is also the case for each other linear order. This is the crucial property in which I am interested.

Using the linear order, the original formulation which is pretty complicated from a logical view point (you have to be able to speak about all decompositions of $\pi$ into transpositions) is turned into a statement which is first-order if you admit the use of an arbitrary linear order on $X$ (and, in this particular example, a "modulo 2 counting quantifier" stating that the number of elements satisfying a formula $\phi(x)$ is even). In fact, one can show that the property "having even parity" of permutations cannot be defined by first-order logic without an order, even with the modulo 2 counting quantifier.


Do you know of any other non-trivial properties of finite structures that arise naturally in some field of mathematics, which can be stated "more easily" as in the example above using a linear order in such a way that, whether or not a structure satisfies this property is independent of the choice of linear order on this structure?

share|improve this question
Your question generalizes quite naturally: throughout all mathematics, there tends to be pleasant formulations of theory whenever you have some kind of monoidal or group-like structure around. –  Ryan Budney May 28 '13 at 9:52
While my phrasing of the question above was intentionally imprecise/non technical, I had something rather concrete on my mind. I am mostly interested in the case where some property which otherwise could not be stated in first-order logic becomes first-order definable (potentially with some generalized quantifiers as in the example above) in the presence of a linear order. For, say, second-order logic, the question becomes rather uninteresting, as you can always say "there exists some linear order such that ...". –  user34458 May 28 '13 at 10:19
The question is quite interesting for logics between first and second order. In particular, inflationary fixed-point logic characterizes classes of structures recognizable in deterministic polynomial time in the presence of a linear order, but it is strictly weaker in general, and it is an open problem whether there exist a logic characterizing polynomial time on unordered structures at all. –  Emil Jeřábek May 28 '13 at 11:45
Yes, this is of course the background of this question. As you surely now, there are rather "artificial" constructions (which embed graphs into more complicated structures in such a way that it becomes possible to simulate monadic second-order logic on the graph) which show that first-order logic with an arbitrary linear order is more expressive than first-order logic without the order. As the example above shows, for first-order logic with modulo counting, there is a very "natural" property, which can be found in nearly every basic book on algebra, which proves the analogous statement. –  user34458 May 28 '13 at 12:44
Somewhat related MO question: mathoverflow.net/questions/131255/… –  Timothy Chow May 28 '13 at 17:12
add comment

4 Answers

There are a couple of examples from combinatorics that come to mind, though I'm not sure they're of much "use" for the questions from finite model theory that you're interested in.

  1. The coefficients of the Tutte polynomial were originally defined in terms of internal/external activity, and required a labeling of the vertices, but the Tutte polynomial itself is label-independent.

  2. Manjul Bhargava's generalized factorials were originally defined using the notion of a $P$-ordering but they are independent of the choice of $P$-ordering.

share|improve this answer
Thank you, both examples fit the very general statement of my question, but you could be right that they are of no "use" to me, which does not make them less interesting. The Tutte polynomial is, in some sense, definable in monadic second-order logic with order (see: cs.technion.ac.il/~janos/RESEARCH/kotek-PhD.pdf). –  user34458 May 29 '13 at 8:12
add comment

(1) This seems to be true of vector spaces. Many properties can be derived by first taking a basis. This involves an ordering. While there are coordinate-free ways to do linear algebra, they seem to be the exception rather than the norm. (To make this example finite, consider finite vector spaces over $F_2$ for example.)

(2) Another example is the lack of distinction between the complex numbers $i,-i$. They are indistinguishable without giving them an arbitrary order. (This can be made formal using model theory. The pair $\{-i,i\}$ is definable in the language of algebraically closed fields, but the singleton $\{i\}$ is not.)

Anecdote: Back in my engineering days, I liked to believe that $j$ (what engineers call the solution to $x^2=-1$) was $-i$.

share|improve this answer
When do you have to order the basis? “Usually” you do not need an orientation in linear algebra. –  The User Jun 5 '13 at 14:46
The User, to get a basis you needed to exhaustively take linearly independent elements. This requires an order. Usually, dimension is defined using a basis (even though dimension is basis independent). Also, the determinant of a linear transformation, as defined by matrices, requires an order on the basis to determine the matrix of that linear transformation. (If you still don't believe me, try to work out a definition of determinant which doesn't rely on an ordering of a basis nor of the whole space. It can be done, but it is not the way it is usually defined.) –  Jason Rute Jun 5 '13 at 16:26
add comment

An example and a counterexample at the same time: Dowker's Theorem. (See, for example, this question: What are the applications of Dowker's theorem?.)

Dowker's theorem asserts that (the geometric realizations of) two simplicial complexes, $K$ and $L$, associated to a binary relation $R\subseteq X\times Y$ are homotopy equivalent. As I understand it, the proof of this equivalence requires a choice of ordering of the simplices; but the particular ordering used is not relevant, i.e., any total order can be used. (Please correct me if I'm wrong here!)

This is either an example, or a counterexample, depending how one looks at it. On the one hand, the equivalence of homotopy type between $K$ and $L$, as a proposition which is true, does not depend on the choice of ordering; on the other hand, in order to get a particular homotopy equivalence between $K$ and $L$, a choice of ordering is necessary: the equivalence provided by Dowker's theorem is not natural.

share|improve this answer
add comment

One more example: The main theorem on symmetric polynomials (any symmetric polynomial can be expressed as a polynomial in the elementary symmetric polynomials). Its proof uses a lexicographic order.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.