5 Extensions on tree Definition 12(Segment). 1. o is an initial segement of T ifa o 2. o is an proper initial segement of t if CT Definition 13 (Lexicographic ordering). For two sequences o and T we say that o <LT ifo CT or if o(n), the nn entry in a, is less than (n)where n is the first entry at which the sequences diffe Given a tree, we can define a linear order like this, which is also a special type of lexicographic Definition 14 (left to right ordering). Given two nodes a and y 1. If r <r y, we say that <L y 2. If a and y are incomparable in the tree ordering, find the largest predecessors of a and y, say and y (a) Ifa' equals y, a sy if and only if a is left to y relative to a (b)Otherwise a<L y if and only if r'<l y Exercise Hints: Tree is now a set T with partial order <T. You should prove the problem based on this definition other its definition in Graph theory 1. Show that antisymmetric can be implied by new definition of partial order 2. Given an example of a finitely branching tree that is not n-branching for any n 3. Prove that the notion of the level of a node in a tree is well defined, i.e every node of a tree T is on exactly one level 4. Prove that every node of a tree other than the root has exactly one immediate predecessor 5. Consider the set of all finite sequences of natural numbers. Define an ordering as follows o<T iff(if and only if) either o is shorter than T or, if not, O <L T, which means that o CT or a(n), the nth entry in o, is less than (n) where n is the first entry at which the sequences differ. Prove that is a well ordering 6. Prove that 2. all integer number, with is not well ordered. Define a order such that <2<l> is well ordered 7. Find some ways to make a tree linear other than lexicographic orderin5 Extensions on Tree Definition 12 (Segment). 1. σ is an initial segement of τ if σ ⊂ τ or σ = τ . 2. σ is an proper initial segement of τ if σ ⊂ τ . Definition 13 (Lexicographic ordering). For two sequences σ and τ we say that σ <L τ if σ ⊂ τ or if σ(n), the n th entry in σ, is less than τ (n) where n is the first entry at which the sequences differ. Given a tree, we can define a linear order like this, which is also a special type of lexicographic ordering. Definition 14 (left to right ordering). Given two nodes x and y, 1. If x <T y, we say that x <L y. 2. If x and y are incomparable in the tree ordering, find the largest predecessors of x and y, say x 0 and y 0 (a) If x 0 equals y 0 , x ≤ y if and only if x is left to y relative to x 0 . (b) Otherwise x <L y if and only if x 0 <L y 0 . Exercise Hints: Tree is now a set T with partial order <T . You should prove the problem based on this definition other its definition in Graph theory. 1. Show that antisymmetric can be implied by new definition of partial order. 2. Given an example of a finitely branching tree that is not n-branching for any n. 3. Prove that the notion of the level of a node in a tree is well defined, i.e., every node of a tree T is on exactly one level. 4. Prove that every node of a tree other than the root has exactly one immediate predecessor. 5. Consider the set of all finite sequences of natural numbers. Define an ordering < as follows: σ < τ iff(if and only if) either σ is shorter than τ or, if not, σ <L τ , which means that σ ⊂ τ or σ(n), the n th entry in σ, is less than τ (n) where n is the first entry at which the sequences differ. Prove that < is a well ordering. 6. Prove that Z, all integer number, with < is not well ordered. Define a order <0 such that < Z, <0> is well ordered. 7. Find some ways to make a tree linear other than lexicographic ordering. 4