Order-independent properties arising naturally in mathematics

Question

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.

---

Question

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?

Answer 1

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.

Answer 2

(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$.

Answer 3

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.

Answer 4

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.