Editing Semiring (section)

=== Ordered semirings ===
Notions or order can be defined using strict, non-strict or [[second-order logic|second-order]] formulations. Additional properties such as commutativity simplify the axioms.

Given a [[strict total order]] (also sometimes called linear order, or [[pseudo-order]] in a constructive formulation), then by definition, the ''positive'' and ''negative'' elements fulfill <math>0<x</math> resp. <math>x<0</math>. By irreflexivity of a strict order, if <math>s</math> is a left zero divisor, then <math>s\cdot x < s\cdot y</math> is false. The ''non-negative'' elements are characterized by <math>\neg(x<0)</math>, which is then written <math>0\le x</math>.

Generally, the strict total order can be negated to define an associated partial order. The [[asymmetric relation|asymmetry]] of the former manifests as <math>x<y\to x\le y</math>. In fact in [[classical logic|classical mathematics]] the latter is a (non-strict) total order and such that <math>0\le x</math> implies <math>x=0\lor 0<x</math>. Likewise, given any (non-strict) total order, its negation is [[irreflexive relation|irreflexive]] and [[transitive relation|transitive]], and those two properties found together are sometimes called strict quasi-order. Classically this defines a strict total order – indeed strict total order and total order can there be defined in terms of one another.

Recall that "<math>\le_\text{pre}</math>" defined above is trivial in any ring. The existence of rings that admit a non-trivial non-strict order shows that these need not necessarily coincide with "<math>\le_\text{pre}</math>".

==== Additively idempotent semirings ====
A semiring in which every element is an additive [[idempotent]], that is, <math>x+x=x</math> for all elements <math>x</math>, is called an '''(additively) idempotent semiring'''.{{refn|name=Esik08}} Establishing <math>1 + 1 = 1</math> suffices. Be aware that sometimes this is just called idempotent semiring, regardless of rules for multiplication.

In such a semiring, <math>x\le_\text{pre} y</math> is equivalent to <math>x + y = y</math> and always constitutes a partial order, here now denoted <math>x\le y</math>. In particular, here <math>x \le 0\leftrightarrow x = 0</math>. So additively idempotent semirings are zerosumfree and, indeed, the only additively idempotent semiring that has all additive inverses is the trivial ring and so this property is specific to semiring theory. Addition and multiplication respect the ordering in the sense that <math>x \le y</math> implies <math>x + t \leq y + t</math>, and furthermore implies <math>s\cdot x \le s\cdot y</math> as well as <math>x\cdot s \le y\cdot s</math>, for all <math>x, y, t</math> and <math>s</math>.

If <math>R</math> is additively idempotent, then so are the polynomials in <math>R[X^*]</math>.

A semiring such that there is a lattice structure on its underlying set is '''lattice-ordered''' if the sum coincides with the meet, <math>x + y = x\lor y</math>, and the product lies beneath the join <math>x\cdot y \le x\land y</math>. The lattice-ordered semiring of ideals on a semiring is not necessarily [[distributive lattice|distributive with respect to]] the lattice structure.

More strictly than just additive idempotence, a semiring is called '''simple''' iff <math>x+1=1</math> for all <math>x</math>. Then also <math>1+1=1</math> and <math>x \le 1</math> for all <math>x</math>. Here <math>1</math> then functions akin to an additively infinite element. If <math>R</math> is an additively idempotent semiring, then <math>\{x\in R\mid x+1=1\}</math> with the inherited operations is its simple sub-semiring. 
An example of an additively idempotent semiring that is not simple is the [[tropical semiring]] on <math>{\mathbb R}\cup\{-\infty\}</math> with the 2-ary maximum function, with respect to the standard order, as addition. Its simple sub-semiring is trivial.

A '''c-semiring''' is an idempotent semiring and with addition defined over arbitrary sets.

An additively idempotent semiring with idempotent multiplication, <math>x^2=x</math>, is called '''additively and multiplicatively idempotent semiring''', but sometimes also just idempotent semiring. The commutative, simple semirings with that property are exactly the bounded distributive lattices with unique minimal and maximal element (which then are the units). [[Heyting algebras]] are such semirings and the [[Boolean algebra (structure)|Boolean algebra]]s are a special case.

Further, given two bounded distributive lattices, there are constructions resulting in commutative additively-idempotent semirings, which are more complicated than just the direct sum of structures.

==== Number lines ====
In a model of the ring <math>{\mathbb R}</math>, one can define a non-trivial positivity predicate <math>0<x</math> and a predicate <math>x<y</math> as <math>0<(y-x)</math> that constitutes a strict total order, which fulfills properties such as <math>\neg(x<0 \lor 0<x) \to x=0</math>, or classically the [[law of trichotomy]]. With its standard addition and multiplication, this structure forms the strictly [[ordered field]] that is [[Dedekind-complete]]. [[elementary equivalence|By definition]], all [[first-order logic|first-order properties]] proven in the theory of the reals are also provable in the [[Decidability (logic)#Decidability of a theory|decidable theory]] of the [[real closed field]]. For example, here <math> x < y </math> is mutually exclusive with <math>\exists d. y + d^2 = x</math>.

But beyond just ordered fields, the four properties listed below are also still valid in many sub-semirings of <math>{\mathbb R}</math>, including the rationals, the integers, as well as the non-negative parts of each of these structures. In particular, the non-negative reals, the non-negative rationals and the non-negative integers are such a semirings.
The first two properties are analogous to the property valid in the idempotent semirings: Translation and scaling respect these [[ordered ring]]s, in the sense that addition and multiplication in this ring validate
* <math>(x<y)\,\to\,x+t<y+t</math>
* <math>(x<y\land 0<s)\,\to\,s\cdot x < s\cdot y</math>
In particular, <math>(0<y\land 0<s)\to 0 < s\cdot y</math> and so squaring of elements preserves positivity.

Take note of two more properties that are always valid in a ring. Firstly, trivially <math>P\,\to\,x \le_\text{pre} y</math> for any <math>P</math>. In particular, the ''positive'' additive difference existence can be expressed as
* <math>(x<y)\,\to\,x \le_\text{pre} y</math>
Secondly, in the presence of a trichotomous order, the non-zero elements of the additive group are partitioned into positive and negative elements, with the inversion operation moving between them. With <math>(-1)^2=1</math>, all squares are proven non-negative. Consequently, non-trivial rings have a positive multiplicative unit,
* <math>0<1</math>
Having discussed a strict order, it follows that <math>0\neq 1</math> and <math>1\neq 1+1</math>, etc.

==== Discretely ordered semirings ====
There are a few conflicting notions of discreteness in order theory. Given some strict order on a semiring, one such notion is given by <math>1</math> being positive and [[Covering relation|covering]] <math>0</math>, i.e. there being no element <math>x</math> between the units, <math>\neg(0<x \land x<1)</math>. Now in the present context, an order shall be called '''discrete''' if this is fulfilled and, furthermore, all elements of the semiring are non-negative, so that the semiring starts out with the units.

Denote by <math>{\mathsf {PA}}^-</math> the theory of a commutative, discretely ordered semiring also validating the above four properties relating a strict order with the algebraic structure. All of its models have the model <math>\N</math> as its initial segment and [[Gödel's theorems|Gödel incompleteness]] and [[Tarski undefinability theorem|Tarski undefinability]] already apply to <math>{\mathsf {PA}}^-</math>. The non-negative elements of a commutative, [[Ordered ring#Discrete ordered rings|discretely ordered ring]] always validate the axioms of <math>{\mathsf {PA}}^-</math>. So a slightly more exotic model of the theory is given by the positive elements in the [[polynomial ring]] <math>{\mathbb Z}[X]</math>, with positivity predicate for <math> p={\textstyle\sum}_{k=0}^n a_k X^k </math> defined in terms of the last non-zero coefficient, <math>0 < p := (0 < a_n) </math>, and <math>p < q := (0 < q - p)</math> as above. While <math>{\mathsf {PA}}^-</math> proves all [[Arithmetical hierarchy|<math>\Sigma_1</math>-sentences]] that are true about <math>\N</math>, beyond this complexity one can find simple such statements that are [[logical independence|independent]] of <math>{\mathsf {PA}}^-</math>. For example, while <math>\Pi_1</math>-sentences true about <math>\N</math> are still true for the other model just defined, inspection of the polynomial <math>X</math> demonstrates <math>{\mathsf {PA}}^-</math>-independence of the <math>\Pi_2</math>-claim that all numbers are of the form <math>2q</math> or <math>2q+1</math> ("[[Parity (mathematics)#Definition|odd or even]]"). Showing that also <math>{\mathbb Z}[X,Y]/(X^2-2Y^2)</math> can be discretely ordered demonstrates that the <math>\Pi_1</math>-claim <math>x^2\neq 2y^2</math> for non-zero <math>x</math> ("no rational squared equals <math>2</math>") is independent. Likewise, analysis for <math>{\mathbb Z}[X,Y,Z]/(XZ-Y^2)</math> demonstrates independence of some statements about [[factorization]] true in <math>\N</math>. There are <math>{\mathsf {PA}}</math> characterizations of primality that <math>{\mathsf {PA}}^-</math> does not validate for the number <math>2</math>.

In the other direction, from any model of <math>{\mathsf {PA}}^-</math> one may construct an ordered ring, which then has elements that are negative with respect to the order, that is still discrete the sense that <math>1</math> covers <math>0</math>. To this end one defines an equivalence class of pairs from the original semiring. Roughly, the ring corresponds to the differences of elements in the old structure, generalizing the way in which the [[initial object|initial]] ring <math>\Z</math> [[Integer#Equivalence classes of ordered pairs|can be defined from]] <math>\N</math>. This, in effect, adds all the inverses and then the preorder is again trivial in that <math>\forall x. x\le_\text{pre} 0</math>.

Beyond the size of the two-element algebra, no simple semiring starts out with the units. Being discretely ordered also stands in contrast to, e.g., the standard ordering on the semiring of non-negative rationals <math>{\mathbb Q}_{\ge 0}</math>, which is [[dense order|dense]] between the units. For another example, <math>{\mathbb Z}[X]/(2X^2-1)</math> can be ordered, but not discretely so.

==== Natural numbers ====
<math>{\mathsf {PA}}^-</math> plus [[mathematical induction]] gives [[Peano axioms#Equivalent axiomatizations|a theory equivalent to]] first-order [[Peano arithmetic]] <math>{\mathsf {PA}}</math>. The theory is also famously not [[categorical theory|categorical]], but <math>\N</math> is of course the intended model. <math>{\mathsf {PA}}</math> proves that there are no zero divisors and it is zerosumfree and so no [[Non-standard model of arithmetic|model of it]] is a ring.

The standard axiomatization of <math>{\mathsf {PA}}</math> is more concise and the theory of its order is commonly treated in terms of the non-strict "<math>\le_\text{pre}</math>". However, just removing the potent induction principle from that axiomatization does not leave a workable algebraic theory. Indeed, even [[Robinson arithmetic]] <math>{\mathsf {Q}}</math>, which removes induction but adds back the predecessor existence postulate, does not prove the monoid axiom <math>\forall y. (0 + y = y)</math>.