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:
“Your money’s no good here. Orders of the house.”
—Stanley Kubrick (b. 1928)
“There is nothing on earth more exquisite than a bonny book, with well-placed columns of rich black writing in beautiful borders, and illuminated pictures cunningly inset. But nowadays, instead of looking at books, people read them. A book might as well be one of those orders for bacon and bran.”
—George Bernard Shaw (1856–1950)
“Really, if the lower orders don’t set us a good example, what on earth is the use of them? They seem, as a class, to have absolutely no sense of moral responsibility.”
—Oscar Wilde (1854–1900)