Order (relation): Difference between revisions
imported>Richard Pinch (added associated concepts intervals, cover) |
imported>Richard Pinch (→Associated concepts: Upper and lower bound, maximum and minimum) |
||
Line 27: | Line 27: | ||
We say that ''b'' ''covers'' ''a'' if the interval <math>[a,b] = \{a,b\}</math>: that is, there is no ''x'' strictly between ''a'' and ''b''. | We say that ''b'' ''covers'' ''a'' if the interval <math>[a,b] = \{a,b\}</math>: that is, there is no ''x'' strictly between ''a'' and ''b''. | ||
Let ''S'' be a subset of a ordered set (''X'',<). An ''upper bound'' for ''S'' is an element ''u'' of ''X'' such that <math>u \ge s</math> for all elements <math>s \in S</math>. A ''lower bound'' for ''S'' is an element ''l'' of ''X'' such that <math>\ell \ge s</math> for all elements <math>s \in S</math>. In general a set need not have either an upper or a lower bound. | |||
A ''maximum'' for ''S'' is an upper bound which is in ''S''; a ''minimum'' for ''S'' is a lower bound which is in ''S''. |
Revision as of 15:07, 29 November 2008
In mathematics, an order relation is a relation on a set which generalises the notion of comparison between numbers and magnitudes, or inclusion between sets or algebraic structures.
Throughout the discussion of various forms of order, it is necessary to distinguish between a strict or strong form and a weak form of an order: the difference being that the weak form includes the possibility that the objects being compared are equal. We shall usually denote a general order by the traditional symbols < or > for the strict form and ≤ or ≥ for the weak form, but notations such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\subset},{\supset}} ,; ,; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\sqsubset},{\sqsupset}} ,Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\sqsubseteq},{\sqsupseteq}} are also common. We also use the traditional notational convention that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y \Leftrightarrow y > x} .
Partial order
The most general form of order is the (strict) partial order, a relation < on a set satisfying:
- Irreflexive: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \not< x ; \,}
- Antisymmetric: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y \Rightarrow y \not< x ; \,}
- Transitive: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y, y < z \Rightarrow x < z . \,}
The weak form ≤ of an order satisfies the variant conditions:
- Reflexive: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le x ; \,}
- Antisymmetric: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le y, y \le x \Rightarrow x=y ; \,}
- Transitive: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le y, y \le z \Rightarrow x \le z . \,}
Total order
A total or linear order is one which has the trichotomy property: for any x, y exactly one of the three statements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = y} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x > y} holds.
Associated concepts
If a ≤ b in an ordered set (X,<) then the interval
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a,b] = \{ x \in X : a \le x \le b \}.\,}
We say that b covers a if the interval : that is, there is no x strictly between a and b.
Let S be a subset of a ordered set (X,<). An upper bound for S is an element u of X such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u \ge s} for all elements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s \in S} . A lower bound for S is an element l of X such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell \ge s} for all elements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s \in S} . In general a set need not have either an upper or a lower bound.
A maximum for S is an upper bound which is in S; a minimum for S is a lower bound which is in S.