Thm* For any graph
p:V List. 1 < ||p||  path(the_graph;p)  path(the_graph;tl(p)) | [path-tl] |
Thm* k: , L: List. 0 < ||L||  ( r: . r- > L^k) | [Ramsey] |
Thm* r,k: , L,R: List. 2 k  ||R|| = ||L||  ( i: ||L||. 0 < L[i]  R[i]- > L[i--]^k)  r- > R^k-1  r+1- > L^k | [Ramsey-recursion] |
Thm* L: List, i,j: ||L||. 0 < L[i]  L[i--][j] = if j= i L[j]-1 else L[j] fi | [list-dec-select] |
Thm* L: List, i: ||L||. 0 < L[i]  ||L[i--]|| = ||L||  | [list-dec-length] |
Thm* L: List, i: ||L||. 0 < L[i]  L[i--] List | [list-dec_wf] |
Thm* L: List. sum(L[i]-1 | i < ||L||)+1- > L^1 | [Ramsey-base-case] |
Thm* k: , L: List. k-1- > L^k  ( i: ||L||. L[i] < k) | [trivial-arrows] |
Thm* n,k: , c:( n  k). p:( k ( List)). sum(||p(j)|| | j < k) = n & ( j: k, x,y: ||p(j)||. x < y  (p(j))[x] > (p(j))[y]) & ( j: k, x: ||p(j)||. (p(j))[x] < n & c((p(j))[x]) = j) | [finite-partition] |
Def path(the_graph;p) == 0 < ||p|| & ( i: (||p||-1). p[i]-the_graph- > p[(i+1)]) | [path] |
Def paren(T;s) == s = nil (T+T) List ( t:T, s':(T+T) List. s = ([inl(t)] @ s' @ [inr(t)]) & paren(T;s')) ( s',s'':(T+T) List. ||s'|| < ||s|| & ||s''|| < ||s|| & s = (s' @ s'') & paren(T;s') & paren(T;s'')) (recursive) | [paren] |
Def L[i--] == mklist(||L||; j.if j= i L[j]-1 else L[j] fi) | [list-dec] |
Def r- > L^k == n: . r n  ( G:({s:( n List)| ||s|| = k & ( x,y: ||s||. x < y  s[x] < s[y]) }  ||L||). c: ||L||, f:( L[c]  n). increasing(f;L[c]) & ( s: L[c] List. ||s|| = k  ( x,y: ||s||. x < y  s[x] < s[y])  G(map(f;s)) = c)) | [arrows] |