Читать книгу Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory - Douglas Cenzer - Страница 14

In this section, we introduce the various types of partial and total orderings.

Definition 2.5.1. A relation R on A is a preorder or quasiorder if it is reflexive and transitive. A preorder is a partial ordering if it is antisymmetric. If A is a set equipped with a partial ordering, we will refer to A as a partially ordered set, or p.o. set for short. A partial ordering R is a linear ordering if it is total, that is, for any a, b ∈ A, either aRb or bRa. An ordering R is a well-ordering if it is linear and well-founded, that is, any subset B of A has a least element. A totally ordered subset of a partially ordered set is called a chain.

Note that a preorder which is symmetric is just an equivalence relation. The relation aRb if and only if card(a) ≤ card(b) for sets a and b is an example of a preorder.

Given a set A partially ordered by ≤ and a, b ∈ A, we write a < b for a ≤ b and a ≠ b. The relation < is irreflexive antisymmetric and transitive. More generally, R is a strict partial ordering if it is irreflexive, antisymmetric, and transitive. Another way to say that a partial order is total, or linear, is by the following definition.

Definition 2.5.2. The partial order ≤ on a set A has the Trichotomy Property if, for any x, y ∈ A, exactly one of the following conditions holds:

(1) x < y;

(2) y < x;

(3) x = y.

The standard ordering ≤ of the real numbers is a linear ordering, and the corresponding strict order is given by <.

The notions of minimal and maximal elements in a partially ordered set, as well as lower and upper bounds for ordered sets, are very important.

Definition 2.5.3. Let ≤ be a partial ordering on a set A and let B ⊆ A.

(1) a is a minimal element of B if a ∈ B and there is no b ∈ B with b < a.

(2) a is a maximal element of B if a ∈ B and there is no b ∈ B with b > a.

(3) a is the minimum element of B if a ∈ B and for every b ∈ B, a ≤ b.

(4) a is a lower bound for B if a ≤ b for every b ∈ B. Here a does not have to belong to B.

(5) a is an upper bound for B if b ≤ a for every b ∈ B. Again a does not have to belong to B.

(6) a is the greatest lower bound or infimum of B if a is a lower bound and c ≤ a for every lower bound c of B.

(7) a is the least upper bound or supremum of B if a is an upper bound and a ≤ c for every upper bound c of B.

We consider some examples of partial orderings and related concepts involving divisibility for natural numbers, inequality for real numbers, and inclusion for sets.

Example 2.5.4.

(1) Consider the divisibility relation on the positive integers. This relation is reflexive, since x = x · 1 so x | x for any x. To see that it is transitive, suppose a | b and b | c. Then b = ax and c = by for some positive integers x, y. It follows that xy is also a positive integer and c = axy. To see that it is antisymmetric, suppose that a|b and b|a. Then b = ax and a = by for some positive integers x, y. Then xy is a positive integer and a = axy. It follows that xy = 1 and therefore x = y = 1 and a = b. Note that we have a | −a and −a | a, so the divisibility relation is not antisymmetric on the integers.

(2) For two positive integers a, b, the maximum and the minimum under divisibility exist if one of the two divides the other and then these are just the usual max{a, b} and min{a, b} under the standard ordering ≤. The least upper bound of {a, b} is the least common multiple and the greatest lower bound of {a, b} is the greatest common denominator.

(3) Let ≤ be the standard ordering on the real numbers. A finite closed interval [a, b] has minimal element a and maximal element b. A finite open interval (a, b) has infimum a and supremum b but has no minimal or maximal elements. The half-open interval [0, ∞) has no supremum. The set {1/n : n ∈ ⁺} has infimum 0 but has no minimum.

(4) For the inclusion relation on (), let B be the family of nonempty sets. Then for any n ∈ , the singleton {n} is a minimal element of B, but B has no minimum element.

Exercises for Section 2.5

Exercise 2.5.1. Show that if ≤ is a partial ordering with strict order <, then it is linear if and only if it satisfies the so-called Trichotomy Property, that is, for any x, y, exactly one of the following conditions holds: (i) x < y; y < x; (iii) x = y.

Exercise 2.5.2. Show that if R is a preordering then R⁻¹ is a preordering.

Exercise 2.5.3. Show that if R is a preordering then R ∩ R⁻¹ is an equivalence relation.

Exercise 2.5.4.

(a) Show that if a is the minimum element in a subset B of a p.o. set A, then a is the unique minimal element of B.

(b) Give an example of a p.o. set with a unique minimal element but no minimum element.

Exercise 2.5.5.

(a) Show that a maximum element of a subset B of a p.o. set is always the supremum of B.

(b) Show that the supremum a of B is the maximum of B if and only if a ∈ B.

Exercise 2.5.6. Show that any well-founded partial ordering is a well-ordering. That is, show that such an ordering must be totally ordered.

Exercise 2.5.7. Prove that for any p.o. set A, there is an injection F : A → (A) such that a ≤ b F(A) ⊆ F(B).

Exercise 2.5.8. Let (B, ≤) be a set with a partial ordering. Let F : A → B and define a relation R on Dmn(F) by xRy F(x) ≤ F(y). Show that R is a preorder.

Exercise 2.5.9. Let F : (A, ≤A) → (B, ≤B) map one linearly ordered set onto another so that a₁ < a₂ implies F(a₁) < F(a₂). Show that F is an order isomorphism, that is, F is one-to-one and a₁ ≤ a₂ F(a₁) ≤ F(a₂).

Exercise 2.5.10. Given a preorder R on a set A, prove that there is an equivalence relation S on A and a partial ordering ≤ on A/S such that [a]S ≤ [b]S aRb.