هياكل متقطعةII + orderd sets

[O2 ]  (Antisymmetric)   If aRb and bRa, then a = b.

[O3 ]  (Transitive)   If aRb and bRc, then aRc.

Then R is called a partial order or, simply an order relation, and R is said to de?ne a partial ordering of S. The set S with the partial order is called a partially ordered set or, simply, an ordered set or poset. We write (S, R) when we want to specify the relation R.

The most familiar order relation, called the usual order, is the relation ? (read “less than or equal”) on the

positive integers N or, more generally, on any subset of the real numbers R. For this reason, a partial order relation

is usually denoted by    ; and

is read “a precedes b.” In this case we also write:

a    b

a ? b means a    b and a = b;     read “a strictly precedes b.”

b    a means a    b;                         read “b succeeds a.”

b . a means a ? b;                        read “b strictly succeeds a.”

 / , ?/ , / , and . are self-explanatory.

When there is no ambiguity, the symbols ?, <, >, and ? are frequently used instead of  , ?, ., and    ,

respectively.

EXAMPLE  1

(a)  Let S be any collection of sets. The relation ? of set inclusion is a partial ordering of S. Speci?cally, A ? A

for any set A; if A ? B and B ? A then A = B ; and if A ? B and B ? C then A ? C.

(b)  Consider the set N of positive integers. We say “a divides b,” written a | b, if there exists an integer c such that ac = b. For example, 2 | 4, 3 | 12, 7 | 21, and so on. This relation of divisibility is a partial ordering of N.

(c)  The relation “|” of divisibility is not an ordering of the set Z of integers. Speci?cally, the relation is not antisymmetric. For instance, 2 | ?2 and ?2 | 2, but 2 = ?2.

(d)  Consider the set Z of integers. De?ne aRb if there is a positive integer r such that b = ar . For instance, 2 R 8 since 8 = 23 . Then R is a partial ordering of Z.

Dual Order

Let    be any partial ordering of a set S. The relation    , that is, a succeeds b, is also a partial ordering of S;

it is called the dual order. Observe that a    b if and only if b    a; hence the dual order     is the inverse of the relation    , that is,     =   ?1 .

Ordered Subsets

Let A be a subset of an ordered set S, and suppose a, b ? A. De?ne a    b as elements of A whenever a    b as elements of S. This de?nes a partial ordering of A called the induced order on A. The subset A with the induced order is called an ordered subset of S. Unless otherwise stated or implied, any subset of an ordered set S will be treated as an ordered subset of S.

Quasi-order

Suppose ? is a relation on a set S satisfying the following two properties: [Q1 ]  (Irre?exive)   For any a ? A, we have a ?/ a.

[Q2 ]  (Transitive)   If a ? b, and b ? c, then a ? c.

Then ? is called a quasi-order on S.

There is a close relationship between partial orders and quasi-orders. Speci?cally, if     is a partial order on a set S and we de?ne a ? b to mean a    b but a = b, then ? is a quasi-order on S. Conversely, if ? is a quasi-order on a set S and we de?ne a    b to mean a ? b or a = b, then     is a partial order on S. This allows

us to switch back and forth between a partial order and its corresponding quasi-orders using whichever is more convenient.