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

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

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