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.
Read more about this topic: List Of First-order Theories
Famous quotes containing the word orders:
“There are nine orders of angels, to wit, angels, archangels, virtues, powers, principalities, dominations, thrones, cherubim, and seraphim.”
—Gregory the Great, Pope (c. 540–604)
“Selflessness is like waiting in a hospital
In a badly-fitting suit on a cold wet morning.
Selfishness is like listening to good jazz
With drinks for further orders and a huge fire.”
—Philip Larkin (1922–1986)
“He was thoughtful and grave—but the orders he gave
Were enough to bewilder a crew.
When he cried “Steer to starboard, but keep her head larboard!”
What on earth was the helmsman to do?”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)