List of First-order Theories - Orders

Orders

The signature of orders has no constants or functions, and one binary relation symbols ≤. (It is of course possible to use ≥, < or > instead as the basic relation, with the obvious minor changes to the axioms.) We define x ≥ y, x < y, x > y as abbreviations for y ≤ x, x ≤ y ∧¬y ≤ x, y < x,

Some first-order properties of orders:

• Transitive: ∀x ∀y ∀z x ≤ y∧y ≤ z → x ≤ z
• Reflexive: ∀x x ≤ x
• Antisymmetric: ∀x ∀y x ≤ y ∧ y ≤ x → x = y
• Partial: Transitive∧Reflexive∧Antisymmetric;
• Linear (or total): Partial ∧ ∀x ∀y x≤y ∨ y≤x
• Dense ∀x ∀z x < z → ∃y x < y ∧ y < z ("Between any 2 distinct elements there is another element")
• There is a smallest element: ∃x ∀y x ≤ y
• There is a largest element: ∃x ∀y y ≤ x
• Every element has an immediate successor: ∀x ∃y ∀z x < z ↔ y ≤ z

The theory DLO of dense linear orders without endpoints (i.e. no smallest or largest element) is complete, ω-categorical, but not categorical for any uncountable cardinal. There are 3 other very similar theories: the theory of dense linear orders with a:

• Smallest but no largest element;
• Largest but no smallest element;
• Largest and smallest element.

Being well ordered ("any non-empty subset has a minimal element") is not a first-order property; the usual definition involves quantifying over all subsets.