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

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.

       Chapter 3

       Zermelo–Fraenkel Set Theory

       3.1. Historical Context

      In 19th century, mathematicians produced a great number of sophisticated theorems and proofs. With the increasing sophistication of their techniques, an important question appeared now and again: which theorems require a proof and which facts are self-evident to a degree that no sensible mathematical proof of them is possible? What are the proper boundaries of mathematical discourse? The content of these questions is best illustrated by several contemporary examples.

      Example 3.1.1. The parallel postulate of Euclidean geometry was a subject of study for centuries. The study of geometries that fail to satisfy this postulate was considered a nonmathematical folly prior to the early 19th century, and Gauss withheld his findings in this direction for fear of public reaction. The hyperbolic geometry was discovered only in 1830 by Lobachevsky and Bolyai. Non-Euclidean geometries proved to be an indispensable tool in the general theory of relativity.

      Example 3.1.2. The Jordan Curve Theorem asserts that every non-self-intersecting closed curve divides the Euclidean plane into two regions, one bounded and the other unbounded, and any path from the bounded to the unbounded region must intersect the curve. The proof was first presented in 1887. The statement sounds self-evident, but the initial proofs were found to be confusing and unsatisfactory. The consensus formed that even statements of this kind must be proved from some more elementary properties of the real line.

      Example 3.1.3. Georg Cantor produced an exceptionally simple proof of the existence of nonalgebraic real numbers, that is, real numbers which are not roots of any polynomial with integer coefficients (1874). Proving that specific real numbers such as π or e are not algebraic is quite difficult, and the techniques for such proofs were under development at that time. On the other hand, Cantor only compared the cardinalities of the sets of algebraic numbers and real numbers, found that the first has smaller cardinality, and concluded that there must be real numbers that are not algebraic without ever producing a single definite example. Cantor’s methodology — comparing cardinalities of different infinite sets — struck many people as nonmathematical.

      As a result, the mathematical community in the late 19th century experienced an almost universally acknowledged need for an axiomatic development of mathematics modeled after the classical axiomatic treatment of geometry by Euclid. It was understood that the primitive concept must be that of a set (as opposed to a real number, for example), since the treatment of real numbers can be fairly easily reinterpreted as speaking about sets of a certain specific kind. The need for a careful choice of axioms was accentuated by several paradoxes, of which the simplest and most famous is Russell’s paradox: consider the “set”x of all sets z which are not elements of themselves. Consider the question whether x ∈ x or not. If x