2. If A is not finite, it is infinite The following theorem is a base on syntax of logic Theorem 7. Let a be a countable set. The set of all finite sequence of elements in a is also countable Proof. We can formalize it as S=UnENA=AUAU. UA"U.. Then we can construct a mapping from A" to M 5 Tree In the last semester, we have learned tree in the way of graph. And we have already known that a relation and a graph can represent each other. Here, we will represent a tree with a partial order We can define a tree based on a partial order as follows Definition 8(Tree). A tree is a set T(whose elements are called nodes) partially ordered by <t, with a unique least element called the root, in which the predecessors of every node are well ordered From now on, we will redefine the concepts and discuss its properties in an order approach Definition 9(Path). A path on a tree T is a maximal linearly ordered subset ofT Definition 10(Properties of tree). 1. The levels of a tree T are defined by induction 2. The 0 level of T consists precisely of the root ofT. 3. The k+1 level of f consists of the immediate successors of the nodes on the k level of t. 4. If each node has at most n immediate successors, the tree is n-ary or n-branching 5. If each node has finitely many immediate successors, we say that the tree is finitely branching A node with no successors is called a leaf or a terminal node. Theorem 11(Konig's lemma). If a finitely branching tree T is infinite, it has an infinite path sketch. If there is no infinite path, the tree would be finite. Split the successors of the node into two parts. One with infinite successors and the other with finite successors 6 Extensions on tree Definition 12(Segment). 1. o is an initial segment of r ifa CT oro=T 2. o is an proper initial segment ofT if CT2. If A is not finite, it is infinite. The following theorem is a base on syntax of logic. Theorem 7. Let A be a countable set. The set of all finite sequence of elements in A is also countable. Proof. We can formalize it as S = ∪n∈N An = A1 ∪ A2 ∪ · · · ∪ An ∪ · · · . Then we can construct a mapping from An to N . 5 Tree In the last semester, we have learned tree in the way of graph. And we have already known that a relation and a graph can represent each other. Here, we will represent a tree with a partial order. We can define a tree based on a partial order as follows: Definition 8 (Tree). A tree is a set T(whose elements are called nodes) partially ordered by <T , with a unique least element called the root, in which the predecessors of every node are well ordered by <T . From now on, we will redefine the concepts and discuss its properties in an order approach. Definition 9 (Path). A path on a tree T is a maximal linearly ordered subset of T. Definition 10 (Properties of tree). 1. The levels of a tree T are defined by induction. 2. The 0 th level of T consists precisely of the root of T. 3. The k + 1th level of T consists of the immediate successors of the nodes on the k th level of T. 4. If each node has at most n immediate successors, the tree is n-ary or n-branching. 5. If each node has finitely many immediate successors, we say that the tree is finitely branching. 6. A node with no successors is called a leaf or a terminal node. Theorem 11 (K¨onig’s lemma). If a finitely branching tree T is infinite, it has an infinite path. sketch. If there is no infinite path, the tree would be finite. Split the successors of the node into two parts. One with infinite successors and the other with finite successors. 6 Extensions on Tree Definition 12 (Segment). 1. σ is an initial segment of τ if σ ⊂ τ or σ = τ . 2. σ is an proper initial segment of τ if σ ⊂ τ . 4