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:
“Let’s start with the three fundamental Rules of Robotics.... We have: one, a robot may not injure a human being, or, through inaction, allow a human being to come to harm. Two, a robot must obey the orders given it by human beings except where such orders would conflict with the First Law. And three, a robot must protect its own existence as long as such protection does not conflict with the First or Second Laws.”
—Isaac Asimov (1920–1992)
“The newspapers, especially those in the East, are amazingly superficial and ... a large number of news gatherers are either cynics at heart or are following the orders and the policies of the owners of their papers.”
—Franklin D. Roosevelt (1882–1945)
“I’ve got orders to obey, thank God.”
—Robert Bolt (1924–1995)