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

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 Скачать книгу