:: Introduction to Trees :: by Grzegorz Bancerek :: :: Received October 25, 1989 :: Copyright (c) 1990-2021 Association of Mizar Users :: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland). :: This code can be distributed under the GNU General Public Licence :: version 3.0 or later, or the Creative Commons Attribution-ShareAlike :: License version 3.0 or later, subject to the binding interpretation :: detailed in file COPYING.interpretation. :: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these :: licenses, or see http://www.gnu.org/licenses/gpl.html and :: http://creativecommons.org/licenses/by-sa/3.0/. environ vocabularies NUMBERS, XBOOLE_0, SUBSET_1, FUNCT_1, FINSEQ_1, TARSKI, RELAT_1, NAT_1, ORDINAL4, ARYTM_3, FINSET_1, CARD_1, XXREAL_0, ORDINAL1, TREES_1, AMISTD_3, FINSEQ_2; notations TARSKI, XBOOLE_0, ENUMSET1, SUBSET_1, CARD_1, XCMPLX_0, ORDINAL1, NAT_1, NUMBERS, RELAT_1, FUNCT_1, FINSEQ_1, FINSEQ_2, FUNCT_2, FINSET_1, XXREAL_0; constructors ENUMSET1, WELLORD2, XXREAL_0, XREAL_0, NAT_1, FINSEQ_1, FINSEQ_2, FUNCOP_1, FUNCT_2, RELSET_1, NUMBERS; registrations XBOOLE_0, RELAT_1, FUNCT_1, ORDINAL1, FINSET_1, XXREAL_0, XREAL_0, NAT_1, FINSEQ_1, CARD_1, RELSET_1, FINSEQ_2; requirements NUMERALS, REAL, BOOLE, SUBSET, ARITHM; begin reserve:: D for non empty set, X,x,y,z for set, k,n,m for Nat , f for Function, p,q,r for FinSequence of NAT; :: :: Relations "is a prefix of", "is a proper prefix of" and :: "are comparable" of finite sequences :: notation let p,q be FinSequence; synonym p is_a_prefix_of q for p c= q; end; definition let p,q be FinSequence; redefine pred p is_a_prefix_of q means :: TREES_1:def 1 ex n st p = q|Seg n; end; theorem :: TREES_1:1 for p,q being FinSequence holds p is_a_prefix_of q iff ex r being FinSequence st q = p^r; ::$CT theorem :: TREES_1:3 <*x*> is_a_prefix_of <*y*> implies x = y; notation let p,q be FinSequence; synonym p is_a_proper_prefix_of q for p c< q; end; theorem :: TREES_1:4 for p,q being finite set st p,q are_c=-comparable & card p = card q holds p = q; reserve p1,p2,p3 for FinSequence; theorem :: TREES_1:5 <*x*>,<*y*> are_c=-comparable implies x = y; theorem :: TREES_1:6 for p,q being finite set st p c< q holds card p < card q; theorem :: TREES_1:7 p1^<*x*> is_a_prefix_of p2 implies p1 is_a_proper_prefix_of p2; theorem :: TREES_1:8 p1 is_a_prefix_of p2 implies p1 is_a_proper_prefix_of p2^<*x*>; theorem :: TREES_1:9 p1 is_a_proper_prefix_of p2^<*x*> implies p1 is_a_prefix_of p2; theorem :: TREES_1:10 {} is_a_proper_prefix_of p2 or {} <> p2 implies p1 is_a_proper_prefix_of p1^p2; :: :: The set of proper prefixes of a finite sequence :: definition let p be FinSequence; func ProperPrefixes p -> set means :: TREES_1:def 2 for x being object holds x in it iff ex q being FinSequence st x = q & q is_a_proper_prefix_of p; end; theorem :: TREES_1:11 for p being FinSequence st x in ProperPrefixes p holds x is FinSequence; theorem :: TREES_1:12 for p,q being FinSequence holds p in ProperPrefixes q iff p is_a_proper_prefix_of q; theorem :: TREES_1:13 for p,q being FinSequence st p in ProperPrefixes q holds len p < len q; theorem :: TREES_1:14 for p,q,r being FinSequence st q^r in ProperPrefixes p holds q in ProperPrefixes p; theorem :: TREES_1:15 ProperPrefixes {} = {}; theorem :: TREES_1:16 ProperPrefixes <*x*> = { {} }; theorem :: TREES_1:17 for p,q being FinSequence st p is_a_prefix_of q holds ProperPrefixes p c= ProperPrefixes q; theorem :: TREES_1:18 for p,q,r being FinSequence st q in ProperPrefixes p & r in ProperPrefixes p holds q,r are_c=-comparable; :: :: Trees and their properties :: definition let X; attr X is Tree-like means :: TREES_1:def 3 X c= NAT* & (for p st p in X holds ProperPrefixes p c= X) & for p,k,n st p^<*k*> in X & n <= k holds p^<*n*> in X; end; registration cluster { {} } -> Tree-like; end; registration cluster non empty Tree-like for set; end; definition mode Tree is Tree-like non empty set; end; reserve T,T1 for Tree; theorem :: TREES_1:19 x in T implies x is FinSequence of NAT; definition let T; redefine mode Element of T -> FinSequence of NAT; end; theorem :: TREES_1:20 for p,q being FinSequence st p in T & q is_a_prefix_of p holds q in T; theorem :: TREES_1:21 for r being FinSequence st q^r in T holds q in T; theorem :: TREES_1:22 {} in T & <*> NAT in T; theorem :: TREES_1:23 { {} } is Tree; registration let T,T1; cluster T \/ T1 -> Tree-like; cluster T /\ T1 -> Tree-like non empty; end; theorem :: TREES_1:24 T \/ T1 is Tree; theorem :: TREES_1:25 T /\ T1 is Tree; :: :: Finite trees and their properties :: registration cluster finite for Tree; end; reserve fT,fT1 for finite Tree; theorem :: TREES_1:26 fT \/ fT1 is finite Tree; theorem :: TREES_1:27 fT /\ T is finite Tree; :: :: Elementary trees :: definition let n; func elementary_tree n -> Tree equals :: TREES_1:def 4 { <*k*> : k < n } \/ { {} }; end; registration let n; cluster elementary_tree n -> finite; end; theorem :: TREES_1:28 k < n implies <*k*> in elementary_tree n; theorem :: TREES_1:29 elementary_tree 0 = { {} }; theorem :: TREES_1:30 p in elementary_tree n implies p = {} or ex k st k < n & p = <*k*>; :: :: Leaves and subtrees :: definition let T; func Leaves T -> Subset of T means :: TREES_1:def 5 p in it iff p in T & not ex q st q in T & p is_a_proper_prefix_of q; let p such that p in T; func T|p -> Tree means :: TREES_1:def 6 :: subtree of T, which root is in p q in it iff p^q in T; end; theorem :: TREES_1:31 T|(<*> NAT) = T; registration let T be finite Tree; let p be Element of T; cluster T|p -> finite; end; definition let T; assume Leaves T <> {}; mode Leaf of T -> Element of T means :: TREES_1:def 7 it in Leaves T; end; definition let T; mode Subtree of T -> Tree means :: TREES_1:def 8 ex p being Element of T st it = T|p; end; reserve t for Element of T; definition let T,p,T1; assume p in T; func T with-replacement (p,T1) -> Tree means :: TREES_1:def 9 q in it iff q in T & not p is_a_proper_prefix_of q or ex r st r in T1 & q = p^r; end; theorem :: TREES_1:32 p in T implies T with-replacement (p,T1) = { t1 where t1 is Element of T : not p is_a_proper_prefix_of t1 } \/ the set of all p^s where s is Element of T1; theorem :: TREES_1:33 p in T implies T1 = T with-replacement (p,T1)|p; registration let T be finite Tree, t be Element of T; let T1 be finite Tree; cluster T with-replacement (t,T1) -> finite; end; reserve w for FinSequence; theorem :: TREES_1:34 for p being FinSequence holds ProperPrefixes p,dom p are_equipotent; registration let p be FinSequence; cluster ProperPrefixes p -> finite; end; theorem :: TREES_1:35 for p being FinSequence holds card ProperPrefixes p = len p; :: :: Height and width of finite trees :: definition let IT be set; attr IT is AntiChain_of_Prefixes-like means :: TREES_1:def 10 (for x st x in IT holds x is FinSequence) & for p1,p2 st p1 in IT & p2 in IT & p1 <> p2 holds not p1,p2 are_c=-comparable; end; registration cluster AntiChain_of_Prefixes-like for set; end; definition mode AntiChain_of_Prefixes is AntiChain_of_Prefixes-like set; end; theorem :: TREES_1:36 { w } is AntiChain_of_Prefixes-like; theorem :: TREES_1:37 not p1,p2 are_c=-comparable implies { p1,p2 } is AntiChain_of_Prefixes-like; definition let T; mode AntiChain_of_Prefixes of T -> AntiChain_of_Prefixes means :: TREES_1:def 11 it c= T; end; reserve t1,t2 for Element of T; theorem :: TREES_1:38 {} is AntiChain_of_Prefixes of T & { {} } is AntiChain_of_Prefixes of T; theorem :: TREES_1:39 { t } is AntiChain_of_Prefixes of T; theorem :: TREES_1:40 not t1,t2 are_c=-comparable implies { t1,t2 } is AntiChain_of_Prefixes of T; registration let T be finite Tree; cluster -> finite for AntiChain_of_Prefixes of T; end; definition let T be finite Tree; func height T -> Nat means :: TREES_1:def 12 (ex p st p in T & len p = it) & for p st p in T holds len p <= it; func width T -> Nat means :: TREES_1:def 13 ex X being AntiChain_of_Prefixes of T st it = card X & for Y being AntiChain_of_Prefixes of T holds card Y <= card X; end; theorem :: TREES_1:41 1 <= width fT; theorem :: TREES_1:42 height elementary_tree 0 = 0; theorem :: TREES_1:43 height fT = 0 implies fT = elementary_tree 0; theorem :: TREES_1:44 height elementary_tree(n+1) = 1; theorem :: TREES_1:45 width elementary_tree 0 = 1; theorem :: TREES_1:46 width elementary_tree(n+1) = n+1; theorem :: TREES_1:47 for t being Element of fT holds height(fT|t) <= height fT; theorem :: TREES_1:48 for t being Element of fT st t <> {} holds height(fT|t) < height fT; scheme :: TREES_1:sch 1 TreeInd { P[Tree] }: for fT holds P[fT] provided for fT st for n being Element of NAT st <*n*> in fT holds P[fT|<*n*>] holds P[fT]; begin :: Addenda :: from MODAL_1, 2007.03.14, A.T. reserve s,t for FinSequence; theorem :: TREES_1:49 w^t is_a_proper_prefix_of w^s implies t is_a_proper_prefix_of s; theorem :: TREES_1:50 n <> m implies not <*n*> is_a_prefix_of <*m*>^s; theorem :: TREES_1:51 elementary_tree 1 = {{},<*0*>}; theorem :: TREES_1:52 not <*n*> is_a_proper_prefix_of <*m*>; theorem :: TREES_1:53 elementary_tree 2 = {{},<*0*>,<*1*>}; :: from BINTREE1 theorem :: TREES_1:54 for T being Tree, t being Element of T holds t in Leaves T iff not t^<*0*> in T; theorem :: TREES_1:55 for T being Tree, t being Element of T holds t in Leaves T iff not ex n being Nat st t^<*n*> in T; definition func TrivialInfiniteTree -> set equals :: TREES_1:def 14 the set of all k |-> 0 where k is Nat; end; registration cluster TrivialInfiniteTree -> non empty Tree-like; end; theorem :: TREES_1:56 NAT,TrivialInfiniteTree are_equipotent; registration cluster TrivialInfiniteTree -> infinite; end;