8
$\begingroup$

This is basically a reference request, but the post is going to be relatively long (and a little bit verbose): I apologize in advance for that.

Premise. There are several examples of "ordered structures" appearing in nature (at least for the moment, let me be vague with the actual meaning of various terms I'm using): ordered groups, ordered rings, ordered vector spaces, etc. All of these have something in common: They are algebraic structures, where each operation is compatible, in some sense and in some way, with a (partial) order. Thus, I find it reasonable to ask:

What about a fully formal definition of an ordered structure, in general?

For simplicity, I'm not seeking a definition worded in the language of categories, and I'm looking at the case where "structure" means whatever can be understood as a (classical) model of a finitary, single-sorted, first-order algebraic theory in the frame of model theory (in principle, I'm also interested in possibly non-finitary or many-sorted structures, but the general case would probably make things look more complicated than they are and overshadow some relevant details).

The most basic, non-trivial example is provided by structures with one operation. For instance, an ordered semigroup is a triple $\mathbb A = (A, {\cdot}\,, \preceq)$, where $(A, \cdot)$ is a semigroup (written multiplicatively) and $\preceq$ an order on $A$ with the property that $xz \preceq yz$ and $zx \preceq zy$ for all $x,y,z \in A$ such that $x \preceq y$.

Of course, the axiom of associativity doesn't play any role in these definitions, so from a fundamental point of view it would have been morally better to replace "semigroups" with "magmas" in the previous paragraph, but on the other hand, that doesn't really matter, insofar as I'm just using ordered semigroups as a guiding example to forge a tentative answer to my question along the following lines.

Naive (and "wrong") approach. Let $T$ be a finitary, single-sorted, first-order theory, which, to me, means a triple $(\sigma, \Xi, V)$, where:

  1. $V$ is an infinite countable set of (logical) variables from the formal language, $\mathcal L$, underlying the axiomatic theory used to lay out the foundations (say, Tarski-Grothendieck set theory, as oversized as it may appear);
  2. $\sigma$ is a (single-sorted) signature, namely a triple $(\Sigma_{\rm f}, \Sigma_{\rm r}, \varrho)$ consisting of a set of function symbols $\Sigma_{\rm f}$, a set of relation symbols $\Sigma_{\rm r}$, and a function $\varrho: \Sigma_{\rm f} \cup \Sigma_{\rm r} \to \mathbf N^+$ such that $\Sigma_{\rm f}$, $\Sigma_{\rm r}$, and the set of (logical and non-logical) symbols of $\mathcal L$ are pairwise disjoints (the function $\varrho$ assigns to each function or relation symbol of $\sigma$ an ariety; in particular, an $n$-ary function symbol will correspond, in any model of the theory, to a function $A^{n-1} \to A$ (for some set $A$), and an $n$-ary relation symbol to a subset of $A^n$);
  3. $\Xi$ is a (possibly empty) subset of $\langle V; \sigma \rangle$, the set of all (well-formed) formulas generated by combining, according to the formation rules of first-order logic, the variables in $V$, the (function and relation) symbols of $\sigma$, and those of $\mathcal L$ which are not logical variables.

(The role of $V$ is meaningless here, as we could assume that $V$ includes all the variables in $\mathcal L$; however, it starts being meaningful in the case of many-sorted theories, and that's why I beg your indulgence for being redundant in this respect.)

Now, $T$ is called an algebraic theory if $\Sigma_{\rm r}$ is empty (in which case $\sigma$ is referred to as an algebraic signature), and since we are interested in structures that are algebraic except for the fact of being endowed with an order, we may refer to $T$ as a quasi-algebraic theory if

  1. $\Sigma_{\rm r}$ consists of one relation symbol $R$, subjected to the axioms of reflexivity, antisymmetry, and transitivity (for binary relations), which are hence comprised among the formulas in $\Xi$ (so that $R$ is interpreted as a partial order in any possible model of $T$);
  2. $\Xi$ includes basic formulas encoding the compatibility between each function symbol of $\sigma$ and the relation $R$, which can be phrased as follows: If $\varsigma$ is a function symbol in $\Sigma_{\rm f}$ of ariety $n := \varrho(\varsigma)$, then the formula $$ \forall \vec{x}, \vec{y} \in V^{n-1}: R^{(2n-2)}(\vec{x}, \vec{y}) \implies R(\varsigma(\vec{x}), \varsigma(\vec{y}))\qquad\qquad(\star) $$ belongs to $\Xi$. (The notation should be self-explanatory, but let me note that the formula in the case of constant symbols is redundant, in the sense that it is implied, in any model of theory, by the very fact that $R$ is reflexive; yet, having it there makes the approach look more "uniform" than otherwise, in the same spirit of Joel David Hamkins' comment below.)

An ordered structure would then be any model of a quasi-algebraic theory.

Unfortunately, the above doesn't work even in the case of (the theory of) groups, where $\Sigma_{\rm f}$ consists, say, of the symbols $\cdot$ (binary symbol for "multiplication"), ${}^{-1}$ (unary symbol for "inversion"), and $1$ (constant symbol for "identity"). In fact, the naive approach would suggest to assume one binary relation symbol, say $\preceq$, in $\Sigma_{\rm r}$ and the following axioms in $\Xi$: $$ \begin{split} (1)\ & \forall x, y, z \in V: x \cdot (y \cdot z) = (x \cdot y) \cdot z \\ (2)\ & \forall x \in V: x \cdot 1 = 1 \cdot x = x \\ (3)\ & \forall x,y \in V: x \cdot x^{-1} = x^{-1} \cdot x = 1 \\ (4)\ & \forall x,y,z \in V: (x \preceq x) \land (((x \preceq y) \land (y \preceq y) \implies (x=y))) \land (((x \preceq y) \land (y \preceq z) \implies (x \preceq z))) \\ (5)\ & \forall x,y \in V: (x \preceq y) \implies (x^{-1} \preceq y^{-1}) \\ (6)\ & \forall x,y,z \in V: (x \preceq y) \implies ((x \cdot z \preceq y \cdot z) \land (z \cdot x \preceq z \cdot y)) \\ \end{split} $$ The problem is that the 5th axiom is essentially incompatible with the 6th, as the latter yields that, in every model $(A; +, \cdot\,,1;\preceq)$ of $T$, we have $x \preceq y$ iff $y^{-1} \preceq x^{-1}$.

Remedies. One may argue that the "mistake" lies in the fact of including the function symbol ${}^{-1}$ in the signature of the theory, while an alternative could be to avoid it and replace the 3th axiom above with:

$$ \forall x \in V, \exists\, \tilde{x} \in V: x \cdot \tilde{x} = \tilde{x} \cdot x = 1. $$ This is certainly a possibility (as long as $\mathcal L$ includes both $\forall$ and $\exists$ among the logical symbols), but I find it rather "artificial" (whatever it may mean), all the more that the same strategy fails if we try to use the naive approach outlined in the above to recover as a special case the common definition of an ordered ring, for which the compatibility between multiplication and order is "restricted to nonnegative factors", which has no hope to fit in the paradigm implied by condition $(\star)$.

So, putting it all together, my (second) question is:

Where should I look up for a sufficiently general definition of "ordered structure", which copes with the kind of issues that I've tried to point out in this post?

I've my own ideas on what to do, but there may be a much better way on how to proceed, which is what I'm looking for. In particular, one solution could be as follows:

  1. Start with a finitary, single-sorted, first-order theory $T = (\sigma, \Xi, V)$, whose signature is of the form $((\varsigma_i)_{i \in I}, (R_i)_{i \in I \,\cup\, \{\infty\}}, \varrho)$ for some index set $I$ and $\infty \notin I$, so that each function symbol $\varsigma$ has one corresponding relation symbol of ariety $2\varrho(\varsigma)-2$, and we have an extra relation symbol $R_\infty$.
  2. Make $\Xi$ include, for each relation symbol $R$ of $\sigma$, the axioms of reflexivity, antisymmetry, and transitivity (extended, as appropriate, from binary to $2n$-ary relations), so that, in particular, $R_\infty$ is interpreted as an order in any possible model of the theory.
  3. Rewrite condition ($\star$) so as to replace, for each function symbol $\varsigma$ of $\sigma$, the symbol "$R^{(2n-2)}$" to the left of the connective "$\implies$" with the (unique) relation corresponding to the function symbol $\varsigma$, and the symbol "$R$" to the right with "$R_\infty$".

These conditions together describe a paradigm I will refer to as (P), the last condition encoding the naive idea that the relations $R_i$ must be glued together in a "consistent way" (and can't be "completely independent" from each other, which otherwise would result into something exceedingly general, I feel).

An example. Assume the (algebraic) theory of unital rings is encoded by the (algebraic) signature whose set of function symbols is given by $\Sigma_{\rm ring} := \{+, \cdot\,, -\,, 0, 1\}$, where $+$ and $\cdot$ are, respectively, the binary symbols for "addition" and "multiplication", $-$ is the unary symbol for "additive inverse", and $0$ and $1$ are, respectively, the constant symbols for "additive identity" and "multiplicative identity". The axioms of the theory are the usual ones: $$ \begin{split} (1)\ & \forall x, y, z \in V: (x+(y+z) = (x+y)+z) \land (x \cdot (y \cdot z) = (x \cdot y) \cdot z) \\ (2)\ & \forall x \in V: (x+0 = 0 + x = x) \land (x \cdot 1 = 1 \cdot x = x) \\ (3)\ & \forall x,y \in V: x + (-x) = (-x) + x = 0 \\ (4)\ & \forall x,y,z \in V: (x \cdot (y+z) = (x \cdot y) + (x \cdot z)) \land ((y+z) \cdot x = (y \cdot x) + (z \cdot x)) \\ \end{split} $$ Now, according to the paradigm (P), the theory of ordered rings would have a signature of the form $(\Sigma_{\rm ring}, \Sigma_{\rm r}, \varrho)$, where $\Sigma_{\rm r}$ is a set of relation symbols of the form $\{R_{(+)}, R_{(\cdot)}, R_{(-)}, R_{(0)}, R_{(1)}, \preceq\}$, with each relation symbol subjected to the axioms of reflexivity, antisymmetry, and transitivity, all the relation symbols glued together by the 4th condition of (P), and each function symbol $\varsigma$ in $\Sigma_{\rm ring}$ "bound" to the corresponding relation symbol $R_{(\varsigma)} \in \Sigma_{\rm r}$ by the formula: $$ \forall (\vec{x}, \vec{y}) \in V^{n-1} \times V^{n-1}: R_{(\varsigma)}(\vec{x}, \vec{y}) \implies (\varsigma(\vec{x}) \preceq \varsigma(\vec{y})), $$ where $n$ is the ariety of $\varsigma$.

In particular, this paradigm fits with the usual notion of an ordered ring, which is then a tuple $\mathbb A = (A; +, \cdot\,,-\,,0,1; R_{(+)}, R_{(\cdot)}, R_{(-)}, \preceq)$, where $\preceq$ is a partial order on $A$, $R_{(+)}$ the subset of $A^2 \times A^2$ consisting of those pairs $((x,y),(x,z))$ or $((y,x),(z,x))$ with $y \preceq z$, $R_{(\cdot)}$ the subset of $A^2 \times A^2$ consisting of those pairs $((x,y),(x,z))$ or $((y,x),(z,x))$ such that $0 \preceq x$ and $y \preceq z$, and $R_{(-)} = \{(x,x): x \in A\}$. (I'm intentionally omitting any explicit reference in models to the relations associated with constants, for they don't add any information, as a result of considerations already made in the above.)

$\endgroup$
8
  • $\begingroup$ Surely you mean to say $\forall x,y \in V: (x \preceq y) \implies (y^{-1} \preceq x^{-1}).$ Try any example of what you would consider an ordered group. Of course you can also derive this easily from $xz \preceq yz$ and $zx \preceq zy$ for all $x,y,z \in A$ such that $x \preceq y$ $\endgroup$ Dec 23, 2015 at 22:12
  • 1
    $\begingroup$ No, I mean what I wrote, but wasn't probably clear, sorry about that. What I'm saying is: If I should stick to the naive approach outlined in the OP, then condition $(\star)$ specialized to the unary operation ${}^{-1}$ would translate into: $\forall x, y \in V: (x \preceq y) \implies (x^{-1} \preceq y^{-1})$, with the result that all and the only ordered groups would be trivial. Therefore, the naive idea of using one "global" relation to encode the interplay between the algebraic and order-theoretic "components" of the theory is "wrong", and something different is needed. $\endgroup$ Dec 23, 2015 at 22:28
  • 3
    $\begingroup$ I suppose the point is that in groups, we think of the unary inverse operation as order-reversing, which is Aaron's point, but in an abstract first-order structure, which is to be regarded as an "ordered" structure, one might naively expect that the unary operation respects the order. But perhaps the solution is that for any function or relation, we should specify whether the order is meant to be order respecting or reversing with respect to each specific variable? I guess that would be a uniform solution that gives rise to the main cases? $\endgroup$ Dec 23, 2015 at 22:54
  • $\begingroup$ @JDH. Yes, that's precisely my point with the naive approach to the question described in the OP. On the other hand, the main problem I see with the idea you're suggesting is that, AFAICS, it wouldn't fix the issue with the case of ordered rings, where, if we look at what is expected to happen from the side of models, we have one binary relation, that behaves differently (i.e., in a non-uniform way, if you let me borrow your words) depending on whether we focus on the interplay between the order and either the additive or the multiplicative structure of the ring. $\endgroup$ Dec 23, 2015 at 23:37
  • 1
    $\begingroup$ If one is interested in ordered topological spaces, Guram Bezhanishvili and Patrick Morandi have studied topological spaces in which there is a compatible partial order. See my answer at mathoverflow.net/a/140625/22277 for more detail on how such compatibility is formalizable. $\endgroup$ Dec 24, 2015 at 3:15

2 Answers 2

5
$\begingroup$

You might be interested in a universal algebraic perspective.

There is a concept called polarity based on the relation "algebraic operation f preserves or respects n-ary relation (subuniverse) R". If you have picked a partial, pre, quasi, or total order R, you might consider studying the structure with all functions preserving that order. Similarly, given an operation f, consider all subuniverses of product of the algebra which f respects, and see which of those are the kind you wish to have as an order. If preservation is important to you, you might consider this type of approach.

In my limited experience, an ordered algebraic structure is an algebraic structure equipped with a partial order such that there is an interesting interplay that results in useful theorems about such structures. Often one or more of the operations preserve the order, but not all of them, as you have observed. I suspect your attempt at generalization will be more successful if you have a target theorem, to make up an example: "an algebraic structure can be equipped with an (interesting) partial order iff the algebra generates a congruence permutable variety". If you want examples of target theorems, you might browse the journal 'Order' for some inspiration.

Gerhard "What Uses Are You Intending?" Paseman, 2015.12.24

$\endgroup$
2
  • $\begingroup$ That sounds promising, insofar as I'm interested in a kind of structures that are somehow derived from ordered structures (which involves some sort of preservation of orders): this is roughly the use I'm intending. Yet, I don't get how an approach along the lines of what you write could encode, say, the (usual) notion of ordered ring. Would you mind to work it out in details? On the other hand, I beg to disagree with the principle underlying the 2nd part of your answer (though, of course, I agree with its significance): I don't think they had in mind any particularly useful theorem (...) $\endgroup$ Dec 24, 2015 at 22:28
  • $\begingroup$ (...) when they first worded the general notions of function, topology, algebraic structure, etc. we are still using in the present days (in classical mathematics). To the contrary, I believe they rather had a vague (?) idea of some specific features these notions should have captured, and a number of "natural examples" they would have liked to recover as a special case. $\endgroup$ Dec 24, 2015 at 22:29
4
$\begingroup$

I agree with Gerhard about the value of a universal algebraic approach. There is one insight I can offer, that comes from a paper I wrote 25 years ago, as an undergraduate. It is simply that the defining sentences ought to have the form (universal closure of) $$\left(\bigwedge \Psi_i\right) \to \Phi$$ where the $\Psi_i$ are atomic inequalities and $\Phi$ is an atomic equality or inequality. E.g., $(x \geq 0 \wedge y \geq z) \to xy \geq xz$. Properties like associativity or distributivity involve an empty premise. We have a Birkhoff-type theorem which says that a class of structures is definable in this way if and only if it is closed under the formation of products, substructures, and "$*$-homomorphic" images --- an odd choice of terminology which somehow anticipated my later interest in C*-algebras. Of course, this doesn't address your main question of why your axiom (5) for ordered groups shouldn't be included, but maybe it could help in some way. The reference is Generalized varieties, Algebra Universalis 30 (1993), 27–52 if you are interested.

$\endgroup$
7
  • $\begingroup$ What would be a non-atomic inequality? $\endgroup$ Dec 29, 2015 at 14:58
  • $\begingroup$ @LutzMattner: an atomic formula can be either an equality or an inequality, so I use the terms "atomic equality" and "atomic inequality". I guess it is slightly redundant. $\endgroup$
    – Nik Weaver
    Dec 29, 2015 at 16:53
  • $\begingroup$ Sorry for the delay in replying, and thanks for sharing your thoughts. While I agree that there is some value (I can't really quantify it) in the insights coming from universal algebra, I'm not convinced that an approach along the lines you are suggesting can answer the question in the OP (as vague as it may sound): Fields, for one thing, don't fall in the scope of universal algebra, and that's more than enough for me to advocate for a different approach. $\endgroup$ Jan 27, 2016 at 5:58
  • $\begingroup$ @SalvoTringali: Do simple groups "fall in the scope of universal algebra"? A field is a simple ring (okay, a simple commutative ring with unit). $\endgroup$
    – Nik Weaver
    Jan 27, 2016 at 6:23
  • $\begingroup$ @NikWeaver. I don't know, should check. But what's the point of your question? The OP makes explicit reference to ordered vector spaces. For that, you need a notion of ordered field, and you can't frame it in the language of universal algebra, can you? That's my point. Of course, there is no issue with the definition of an ordered ring (either unital or not, or commutative or not). But that's a different notion, which leads to a different class of widgets. (I feel as I'm misunderstanding what you wanted to mean.) $\endgroup$ Jan 27, 2016 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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