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

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 . Then for a natural number n, Σn denotes the set of strings σ = (σ(0), σ(1), . . . , σ(n − 1)) of n letters from Σ; the length n of σ is denoted by |σ|. The empty string has length 0 and will be denoted by ϵ. Σ^∗ (or sometimes Σ^<ω) denotes the set ⋃_n∈ Σn and Σω, or Σ, denotes the set of infinite sequences.

A constant string σ of length n consisting of the symbol k will be denoted kn. For m < |σ|, σ ↾ m is the string (σ(0), . . . , σ(m − 1)); σ is an initial segment of τ (written σ ⊑ τ) if σ = τ ↾ m for some m. Initial segments are also referred to as prefixes. Similarly, τ is said to be a suffix of σ if |τ| ≤ |σ| and, for all i < |τ|, σ(|σ| − |τ| + i) = τ(i). The concatenation σ⌢τ (or sometimes σ ∗ τ or just στ) is defined by σ⌢τ = (σ(0), σ(1), . . . , σ(m−1), τ(0), τ(1), . . . , τ(n−1)), where |σ| = m and |τ| = n; in particular we write σ⌢a for σ⌢(a) and a⌢ σ for (a)⌢σ. Thus we may also say that σ is a prefix of τ if and only if τ = σ⌢ρ for some ρ and that τ is a suffix of σ if and only if σ = ρ⌢τ for some ρ.

For any x ∈ Σ and any finite n, the initial segment x ↾ n of x is (x(0), . . . , x(n − 1)). We write σ ⊑ x if σ = x ↾ n for some n. For any σ ∈ Σn and any x ∈ Σ, we have σ⌢x = (σ(0), . . . , σ(n − 1), x(0), x(1), . . . ). The lexicographic, or dictionary ordering on Σ^∗, is defined so that σ τ if either σ ⊑ τ or if σ(n) < τ(n), where n is the least such that σ(n) ≠ τ(n).

Proposition 2.6.2. The relation ⊑ is a partial ordering.

The proof is left as an exercise.

Finite strings in {0, 1}^∗ can be viewed as representing dyadic rational numbers.

Definition 2.6.3. For σ ∈ {0, 1}^∗, let qσ = ∑_i<|σ| 2⁻ⁱ⁻¹σ(i).

For example, q₁₁₀₁ represents Note here that the number 13 in base two is just 1101, that is, 13 = 8 + 4 + 1.

A similar definition can be given for numbers in base k when the alphabet Σ = {0, 1, . . . , k − 1}. We can now define the lexicographic order on {0, 1}^∗.

Definition 2.6.4. Let σ τ if and only if either σ ⊏ τ or qσ < qτ.

The following facts are left as exercises.

Fact 2.6.5. For any σ, τ ∈ {0, 1}^∗,

• qσ = qτ if and only if either σ ⊑ τ or τ ⊑ σ;

• if σ τ, then qσ ≤ qτ.

There is another way to state that qσ < qτ.

Lemma 2.6.6. For any σ, τ ∈ {0, 1}^∗, qσ < qτ if and only if there exists n such that σ ↾ n = τ ↾ n and σ(n) < τ(n).

Proof. Suppose first that σ ↾ n = τ ↾ n and σ(n) < τ(n) (that is, σ(n) = 0 and τ(n) = 1), and let ρ = σ ↾ n. Let |σ| = k. Then

This can be used to define the lexicographic order over any well-ordered alphabet Σ, by having σ τ if and only if either σ ⊏ τ or there exists n such that σ ↾ n = τ ↾ n and σ(n) < τ(n).

Proposition 2.6.7. The lexicographic order on Σ^∗ is a linear ordering.

Proof. Reflexive: σ ⊑ σ, so that σ σ.

Antisymmetric: Suppose that σ τ and τ σ. There are two cases.

Case 1: σ ⊆ τ. In this case, qσ = qτ, so that τ σ implies that τ ⊑ σ. Therefore σ = τ, since ⊑ is antisymmetric.

Case 2: qσ < qτ. In this case, τ σ is not possible.

Transitive: Suppose that σ τ and τ ρ. There are two cases.

Case 1: σ ⊏ τ. In this case, qσ = qτ. Now, there are two subcases.

• In the first case, if τ ⊏ ρ, then σ ⊏ ρ and therefore σ ρ.

• In the second case, if qτ < qρ, then qσ < qρ and thus σ ρ as desired.

Case 2: qσ < qτ. Now τ ρ implies that qτ ≤ qρ and therefore qσ < qρ. Thus σ ρ.

Total: This is left as an exercise.

A tree T over Σ is a set of finite strings from Σ^∗ which is closed under initial segments. Then τ ∈ T is an immediate successor of a string σ ∈ T if τ = σ⌢a for some a ∈ Σ.

We will generally assume that T ⊆ ^∗. That is, the nodes of T are finite sequences of natural numbers. Such a tree defines a subset [T] of the so-called Baire space , where [T] is the set of infinite paths through the tree T, that is,

Example 2.6.8. The full binary tree is {0, 1}^∗. Here, every node σ has exactly two successors, σ0 and σ1. The set of infinite paths through the full tree is the so-called Cantor space {0, 1}.

A tree T is said to be a shift if it is also closed under suffixes.

Example 2.6.9. Define T ⊆ {0, 1}^∗ so that σ ∈ T if and only if σ does not have three consecutive 0’s, that is, if σ has no consecutive substring of the form (000). Clearly if σ does not have three consecutive 0’s then no initial segment of σ can have three consecutive 0’s either. Furthermore, if σ has no consecutive substring (000), then no suffix of σ can have a consecutive substring (000). Thus T is a shift.

We say that a tree T is finite-branching if, for every σ ∈ T, there are only finitely many immediate successors of σ in T. Certainly, any tree T over a finite alphabet is finite-branching.

Example 2.6.10. Define the tree T ⊆ ω^∗ so that, for any string σ and any i < |σ|, σ(i) ≤ i. Then, for any σ ∈ T of length n, σ has exactly n + 1 successors.

Exercises for Section 2.6

Exercise 2.6.1. Show that the relation ⊑ is a partial ordering.

Exercise 2.6.2. For any σ, τ ∈ {0, 1}^∗,

• qσ = qτ if and only if either σ ⊑ τ or τ ⊑ σ;

• if σ τ, then qσ ≤ qτ.

Exercise 2.6.3. Show that the lexicographic ordering on {0, 1}^∗ is not well-founded.

Hint: The ordering on the dyadic rational numbers is not well-founded.

Exercise 2.6.4. Show that the lexicographic ordering {0, 1}^∗ is total (and therefore a linear ordering).

Exercise 2.6.5. Show that there is no cycle in the full tree ω^∗.

Exercise 2.6.6. For any abstract tree T = (V, E), and any node u of T, let T(u) be the set of nodes v such that there is a path from u to v. Show that T(u) is also a tree, that is, T(u) does not contain any cycle.