Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory. Douglas Cenzer

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.

2.6. Trees

      Trees play a very important role in many areas of mathematics, set theory and logic in particular. There are many ways to present the notion of a tree. In graph theory, a tree is a connected, acyclic directed graph; that is, there is no cycle of directed edges (v₀, v₁), (v₁, v₂), . . . , (v_n−1, vn), (vn, v₀).

      We are interested in rooted trees, where there is a special node called the root and a directed path from the root to every node, where a directed path from node v₀ to node vn is a sequence (v₀, v₁), (v₁, v₂), . . . , (v_n−1, vn) of directed edges. (Note that the empty sequence may be viewed as a path from v to itself.)

      When there is a directed edge from u to v, we say that v is a successor of u and v is the (unique) predecessor of v. There is a natural partial ordering on a tree, defined so that u ≤ v if and only if there is a path from u to v.

      Example 2.6.1. For example, let T =

and let mEn if and only if n = m + 1. Then 0 is the root and each number m has unique successor m + 1. The partial ordering given by this tree is simply the standard ≤ ordering on

.

      

      We want to consider trees with strings as vertices. Let Σ be a set of symbols (an alphabet), usually an initial segment of Скачать книгу