Our cookies follow Google AdSense policy.

Theorem S.I.1 - Induction PrincipleIf (X,E) is a well ordered set, YcX and /\(x:-X) (/\(y:-X) yEx and y!=x => y:-Y) => x:-Y then X = Y.ProofLet D = X\Y. Assume to the contrary that D != O. Since (X,E) is a well ordered set, there exist t:-D such that /\(d:-D) tEd. Take any y:-X such that yEt and t!=y. It is obvious that !(y:-D). Thus y:-Y. By assumptions of this theorem we have t:-Y. Contradiction. We have shown that Y = X.Theorem S.I.2 - Recursion PrincipleIf (X,E) is a well ordered set, Y is a set, I:X->P(X) such that I(x) = {y:-X|yEx and y!=x}, D = { j:-P(XxY) | \/(x:-X) j:I(x)->Y }, and g:D->Y then there is a unique function f:X->Y such that /\(x:-X) f(x) = g(f|I(x)).Remark:Notice that if m:-X is the least element then f(m) = g(O).Proof of Theorem S.I.2If X = O there is no problem. Assume that X != O. We will write that (A,f) is a proper collection if and only if A is an initial segment of X and f:A->Y such that /\(x:-A) f(x) = g(f|I(x)). We will show that: If (A,f) and (A,g) are proper collections then f = g. Let T = {x:-A|f(x) = h(x)}. By the Induction Principle restricted to A. we get T = A. Thus f = h. We will show that: If (A,f) and (B,h) are proper collections and AcB then f c h. It is obvious that (A,h|A) is a proper collection. Thus h|A = f. So f c h. Let J(z) = {x:-X|xEz}. It is easy to show that J(z) is an initial segment of X. Let H = {z:-X | \/(f) (J(z),f) is a proper collection}. We want to use the Induction Principle to show that H = X. Take any x:-X. Assume that (/\(y:-X) yEx and y!=x => y:-H). We want to show that x:-H. Let L = {f:-P(XxY):\/(z:-I(x)) (J(z),f) is a proper collection}. It is easy to show that /\(a,b:-X) (J(a) c J(b) or J(a) c J(b)). Thus u(L) is a function by Theorem S.C.14. Let h:J(x)->Y such that /\(q:-I(x)) h(q) = u(L)(q) and h(x) = g(u(L)|I(x)). Thus (J(x),h) is a proper collection. So x:-H. By the Induction Principle H = X. Let K = {h:-P(XxY)|\/(z:-H) (J(z),h) is a proper collection}. Let f = u(K). We will show that. (1) f:X->Y, (2) /\(x:-X) f(x) = g(f|I(x)). (1) f is a function by Theorem S.C.14. f:X->Y because H = X. (2) Take any x:-X. Since x:-H we have h:J(x)->Y such that (J(x),h) is a proper collection. It is obvious that h c f. Thus f(x) = g(f|I(x)). We have shown (2). f is unique because if (X,f) (X,f1) are proper collections then f = f1.