Copyright (c) 1989 Association of Mizar Users
environ vocabulary ZF_LANG, FUNCT_1, ORDINAL1, ZF_MODEL, TARSKI, BOOLE, FINSEQ_1, MCART_1, RELAT_1, ZFMODEL1; notation TARSKI, XBOOLE_0, ENUMSET1, ZFMISC_1, SUBSET_1, XREAL_0, NAT_1, RELAT_1, FUNCT_1, FINSEQ_1, ZF_LANG, RELSET_1, FUNCT_2, ORDINAL1, ZF_MODEL, MCART_1; constructors NAT_1, ENUMSET1, ZF_MODEL, MCART_1, XREAL_0, MEMBERED, XBOOLE_0; clusters ZF_LANG, RELSET_1, SUBSET_1, MEMBERED, ZFMISC_1, XBOOLE_0; requirements NUMERALS, SUBSET, BOOLE, ARITHM; definitions TARSKI, ORDINAL1, ZF_MODEL, ZF_LANG, RELAT_1, FUNCT_1, XBOOLE_0; theorems TARSKI, ZF_LANG, ZF_MODEL, ZFMISC_1, MCART_1, FUNCT_1, FUNCT_2, ENUMSET1, ORDINAL1, RELAT_1, RELSET_1, XBOOLE_0; schemes NAT_1, ZF_LANG, XBOOLE_0; begin reserve x,y,z for Variable, H for ZF-formula, E for non empty set, a,b,c,X,Y,Z for set, u,v,w for Element of E, f,g,h,i,j for Function of VAR,E, k,n for Nat; set x0 = x.0, x1 = x.1, x2 = x.2, x3 = x.3, x4 = x.4; Lm1: x0 = 5 + 0 & x1 = 5 + 1 & x2 = 5 + 2 & x3 = 5 + 3 & x4 = 5 + 4 by ZF_LANG:def 2; theorem E is epsilon-transitive implies E |= the_axiom_of_extensionality proof assume A1: X in E implies X c= E; A2: the_axiom_of_extensionality = All(x0,All(x1,All(x2,x2 'in' x0 <=> x2 'in' x1) => x0 '=' x1)) by ZF_LANG:23,ZF_MODEL:def 6; E |= All(x2,x2 'in' x0 <=> x2 'in' x1) => x0 '=' x1 proof let f; now assume A3: E,f |= All(x2,x2 'in' x0 <=> x2 'in' x1); f.x0 = f.x1 proof thus a in f.x0 implies a in f.x1 proof assume A4: a in f.x0; f.x0 c= E by A1; then reconsider a' = a as Element of E by A4; consider g such that A5: g.x2 = a' & for x st x <> x2 holds g.x = f.x by ZF_MODEL:21; for x st g.x <> f.x holds x2 = x by A5; then E,g |= x2 'in' x0 <=> x2 'in' x1 by A3,ZF_MODEL:16; then A6: E,g |= x2 'in' x0 iff E,g |= x2 'in' x1 by ZF_MODEL:19; g.x0 = f.x0 & g.x1 = f.x1 by A5,Lm1; hence thesis by A4,A5,A6,ZF_MODEL:13; end; let a such that A7: a in f.x1; f.x1 c= E by A1; then reconsider a' = a as Element of E by A7; consider g such that A8: g.x2 = a' & for x st x <> x2 holds g.x = f.x by ZF_MODEL:21; for x st g.x <> f.x holds x2 = x by A8; then E,g |= x2 'in' x0 <=> x2 'in' x1 by A3,ZF_MODEL:16; then A9: E,g |= x2 'in' x0 iff E,g |= x2 'in' x1 by ZF_MODEL:19; g.x0 = f.x0 & g.x1 = f.x1 by A8,Lm1; hence thesis by A7,A8,A9,ZF_MODEL:13; end; hence E,f |= x0 '=' x1 by ZF_MODEL:12; end; hence E,f |= All(x2,x2 'in' x0 <=> x2 'in' x1) => x0 '=' x1 by ZF_MODEL:18; end; then E |= All(x1,All(x2,x2 'in' x0 <=> x2 'in' x1) => x0 '=' x1) by ZF_MODEL:25; hence thesis by A2,ZF_MODEL:25; end; theorem Th2: E is epsilon-transitive implies (E |= the_axiom_of_pairs iff for u,v holds { u,v } in E) proof assume A1: X in E implies X c= E; A2: a in u implies a is Element of E proof assume A3: a in u; u c= E by A1; hence a is Element of E by A3; end; A4: (E |= All(x0,All(x1,Ex(x2, All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) ))) iff E |= All(x1,Ex(x2,All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) )) ) & (E |= All(x1,Ex(x2,All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) )) iff E |= Ex(x2,All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) ) ) by ZF_MODEL:25; thus E |= the_axiom_of_pairs implies for u,v holds { u,v } in E proof assume A5: E |= the_axiom_of_pairs; let u,v; consider fv being Function of VAR,E; consider g such that A6: g.x0 = u & for x st x <> x0 holds g.x = fv.x by ZF_MODEL:21; consider f such that A7: f.x1 = v & for x st x <> x1 holds f.x = g.x by ZF_MODEL:21; A8: f.x0 = u by A6,A7,Lm1; E,f |= Ex(x2,All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) ) by A4,A5,ZF_LANG:23,ZF_MODEL:def 5,def 7; then consider h such that A9: (for x st h.x <> f.x holds x2 = x) & E,h |= All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) by ZF_MODEL:20; for a holds a in h.x2 iff a = u or a = v proof let a; thus a in h.x2 implies a = u or a = v proof assume A10: a in h.x2; then reconsider a' = a as Element of E by A2; consider f3 being Function of VAR,E such that A11: f3.x3 = a' & for x st x <> x3 holds f3.x = h.x by ZF_MODEL:21; for x st f3.x <> h.x holds x3 = x by A11; then E,f3 |= x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1 by A9,ZF_MODEL:16; then A12: E,f3 |= x3 'in' x2 iff E,f3 |= x3 '=' x0 'or' x3 '=' x1 by ZF_MODEL:19; f3.x2 = h.x2 by A11,Lm1; then E,f3 |= x3 '=' x0 or E,f3 |= x3 '=' x1 by A10,A11,A12, ZF_MODEL:13,17; then A13: f3.x3 = f3.x0 or f3.x3 = f3.x1 by ZF_MODEL:12; f3.x0 = h.x0 & h.x0 = f.x0 & f3.x1 = h.x1 & h.x1 = f.x1 by A9,A11,Lm1; hence thesis by A6,A7,A11,A13; end; assume A14: a = u or a = v; then reconsider a' = a as Element of E; consider f3 being Function of VAR,E such that A15: f3.x3 = a' & for x st x <> x3 holds f3.x = h.x by ZF_MODEL:21; for x st f3.x <> h.x holds x3 = x by A15; then E,f3 |= x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1 by A9,ZF_MODEL:16; then A16: E,f3 |= x3 'in' x2 iff E,f3 |= x3 '=' x0 'or' x3 '=' x1 by ZF_MODEL:19; f3.x0 = h.x0 & h.x0 = f.x0 & f3.x1 = h.x1 & h.x1 = f.x1 by A9,A15,Lm1; then E,f3 |= x3 '=' x0 or E,f3 |= x3 '=' x1 by A7,A8,A14,A15, ZF_MODEL:12; then f3.x3 in f3.x2 by A16,ZF_MODEL:13,17; hence thesis by A15,Lm1; end; then h.x2 = { u,v } by TARSKI:def 2; hence thesis; end; assume A17: for u,v holds { u,v } in E; let f; now let g such that for x st g.x <> f.x holds x0 = x or x1 = x; reconsider w = { g.x0,g.x1 } as Element of E by A17; consider h such that A18: h.x2 = w & for x st x <> x2 holds h.x = g.x by ZF_MODEL:21; now let m be Function of VAR,E; assume for x st m.x <> h.x holds x3 = x; then A19: h.x0 = g.x0 & m.x0 = h.x0 & h.x1 = g.x1 & m.x1 = h.x1 & m.x2 = h .x2 by A18,Lm1; ( E,m |= x3 'in' x2 iff m.x3 in m.x2 ) & ( E,m |= x3 '=' x0 iff m.x3 = m.x0 ) & ( E,m |= x3 '=' x1 iff m.x3 = m.x1 ) & ( E,m |= x3 '=' x0 'or' x3 '=' x1 iff E,m |= x3 '=' x0 or E,m |= x3 '=' x1 ) by ZF_MODEL:12,13,17; hence E,m |= x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1 by A18,A19,TARSKI:def 2,ZF_MODEL:19; end; then A20: E,h |= All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) by ZF_MODEL:16; for x st h.x <> g.x holds x2 = x by A18; hence E,g |= Ex(x2,All(x3,x3 'in' x2 <=> x3 '=' x0 'or' x3 '=' x1) ) by A20,ZF_MODEL:20; end; hence E,f |= the_axiom_of_pairs by ZF_MODEL:22,def 7; end; theorem E is epsilon-transitive implies (E |= the_axiom_of_pairs iff for X,Y st X in E & Y in E holds { X,Y } in E) proof assume A1: E is epsilon-transitive; hence E |= the_axiom_of_pairs implies for X,Y st X in E & Y in E holds { X,Y } in E by Th2; assume for X,Y st X in E & Y in E holds { X,Y } in E; then for u,v holds { u,v } in E; hence E |= the_axiom_of_pairs by A1,Th2; end; theorem Th4: E is epsilon-transitive implies (E |= the_axiom_of_unions iff for u holds union u in E) proof assume A1: X in E implies X c= E; thus E |= the_axiom_of_unions implies for u holds union u in E proof assume E |= the_axiom_of_unions; then A2: E |= Ex(x1,All(x2,x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) )) by ZF_MODEL:25,def 8; let u; consider f0 being Function of VAR,E; consider f such that A3: f.x0 = u & for x st x <> x0 holds f.x = f0.x by ZF_MODEL:21; E,f |= Ex(x1,All(x2,x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) ) ) by A2,ZF_MODEL:def 5; then consider g such that A4: (for x st g.x <> f.x holds x1 = x) & E,g |= All(x2,x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) ) by ZF_MODEL:20; a in g.x1 iff ex X st a in X & X in u proof thus a in g.x1 implies ex X st a in X & X in u proof assume A5: a in g.x1; g.x1 c= E by A1; then reconsider a' = a as Element of E by A5; consider h such that A6: h.x2 = a' & for x st x <> x2 holds h.x = g.x by ZF_MODEL:21; h.x1 = g.x1 by A6,Lm1; then A7: E,h |= x2 'in' x1 by A5,A6,ZF_MODEL:13; for x st h.x <> g.x holds x2 = x by A6; then E,h |= x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) by A4,ZF_MODEL:16; then E,h |= Ex(x3,x2 'in' x3 '&' x3 'in' x0) by A7,ZF_MODEL:19; then consider m being Function of VAR,E such that A8: (for x st m.x <> h.x holds x3 = x) & E,m |= x2 'in' x3 '&' x3 'in' x0 by ZF_MODEL:20; A9: E,m |= x2 'in' x3 & E,m |= x3 'in' x0 by A8,ZF_MODEL:15; reconsider X = m.x3 as set; take X; m.x0 = h.x0 & h.x0 = g.x0 & g.x0 = f.x0 & m.x2 = h.x2 by A4,A6,A8,Lm1; hence a in X & X in u by A3,A6,A9,ZF_MODEL:13; end; given X such that A10: a in X & X in u; u c= E by A1; then reconsider X as Element of E by A10; X c= E by A1; then reconsider a' = a as Element of E by A10; consider h such that A11: h.x2 = a' & for x st x <> x2 holds h.x = g.x by ZF_MODEL:21; consider m being Function of VAR,E such that A12: m.x3 = X & for x st x <> x3 holds m.x = h.x by ZF_MODEL:21; A13: for x st m.x <> h.x holds x3 = x by A12; m.x2 = h.x2 & m.x0 = h.x0 & h.x0 = g.x0 & g.x0 = f.x0 by A4,A11,A12,Lm1; then E,m |= x2 'in' x3 & E,m |= x3 'in' x0 by A3,A10,A11,A12, ZF_MODEL:13 ; then E,m |= x2 'in' x3 '&' x3 'in' x0 by ZF_MODEL:15; then A14: E,h |= Ex(x3,x2 'in' x3 '&' x3 'in' x0) by A13,ZF_MODEL:20; for x st h.x <> g.x holds x2 = x by A11; then E,h |= x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) by A4,ZF_MODEL:16; then E,h |= x2 'in' x1 by A14,ZF_MODEL:19; then h.x2 in h.x1 by ZF_MODEL:13; hence thesis by A11,Lm1; end; then g.x1 = union u by TARSKI:def 4; hence union u in E; end; assume A15: for u holds union u in E; now let f; reconsider v = union(f.x0) as Element of E by A15; consider g such that A16: g.x1 = v & for x st x <> x1 holds g.x = f.x by ZF_MODEL:21; A17: for x st g.x <> f.x holds x1 = x by A16; now let h; assume A18: for x st h.x <> g.x holds x2 = x; then A19: h.x1 = g.x1 by Lm1; E,h |= x2 'in' x1 iff E,h |= Ex(x3,x2 'in' x3 '&' x3 'in' x0) proof thus E,h |= x2 'in' x1 implies E,h |= Ex(x3,x2 'in' x3 '&' x3 'in' x0) proof assume E,h |= x2 'in' x1; then h.x2 in h.x1 by ZF_MODEL:13; then consider X such that A20: h.x2 in X & X in f.x0 by A16,A19,TARSKI:def 4; f.x0 c= E by A1; then reconsider X as Element of E by A20; consider m being Function of VAR,E such that A21: m.x3 = X & for x st x <> x3 holds m.x = h.x by ZF_MODEL:21; A22: for x st m.x <> h.x holds x3 = x by A21; m.x0 = h.x0 & h.x0 = g.x0 & g.x0 = f.x0 & m.x2 = h.x2 by A16,A18,A21,Lm1; then E,m |= x2 'in' x3 & E,m |= x3 'in' x0 by A20,A21,ZF_MODEL:13; then E,m |= x2 'in' x3 '&' x3 'in' x0 by ZF_MODEL:15; hence thesis by A22,ZF_MODEL:20; end; assume E,h |= Ex(x3,x2 'in' x3 '&' x3 'in' x0); then consider m being Function of VAR,E such that A23: (for x st m.x <> h.x holds x3 = x) & E,m |= x2 'in' x3 '&' x3 'in' x0 by ZF_MODEL:20; E,m |= x2 'in' x3 & E,m |= x3 'in' x0 by A23,ZF_MODEL:15; then m.x2 in m.x3 & m.x3 in m.x0 by ZF_MODEL:13; then A24: m.x2 in union(m.x0) by TARSKI:def 4; m.x2 = h.x2 & m.x0 = h.x0 & h.x0 = g.x0 & g.x0 = f.x0 & h.x1 = g.x1 by A16,A18,A23,Lm1; hence E,h |= x2 'in' x1 by A16,A24,ZF_MODEL:13; end; hence E,h |= x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) by ZF_MODEL:19; end; then E,g |= All(x2,x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) ) by ZF_MODEL:16; hence E,f |= Ex(x1,All(x2,x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) )) by A17,ZF_MODEL:20; end; then E |= Ex(x1,All(x2,x2 'in' x1 <=> Ex(x3,x2 'in' x3 '&' x3 'in' x0) )) by ZF_MODEL:def 5; hence E |= the_axiom_of_unions by ZF_MODEL:25,def 8; end; theorem E is epsilon-transitive implies (E |= the_axiom_of_unions iff for X st X in E holds union X in E) proof assume A1: E is epsilon-transitive; hence E |= the_axiom_of_unions implies for X st X in E holds union X in E by Th4; assume for X st X in E holds union X in E; then for u holds union u in E; hence thesis by A1,Th4; end; theorem Th6: E is epsilon-transitive implies (E |= the_axiom_of_infinity iff ex u st u <> {} & for v st v in u ex w st v c< w & w in u) proof assume A1: X in E implies X c= E; thus E |= the_axiom_of_infinity implies ex u st u <> {} & for v st v in u ex w st v c< w & w in u proof consider f; assume E,g |= the_axiom_of_infinity; then E,f |= the_axiom_of_infinity; then consider g such that A2: (for x st g.x <> f.x holds x0 = x or x1 = x) & E,g |= x1 'in' x0 '&' All(x2,x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) )) by ZF_MODEL:23,def 9; take u = g.x0; E,g |= x1 'in' x0 by A2,ZF_MODEL:15; hence u <> {} by ZF_MODEL:13; let v such that A3: v in u; consider h such that A4: h.x2 = v & for x st x <> x2 holds h.x = g.x by ZF_MODEL:21; A5: for x st h.x <> g.x holds x2 = x by A4; E,g |= All(x2,x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) )) by A2,ZF_MODEL:15; then A6: E,h |= x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) ) by A5,ZF_MODEL:16; h.x0 = g.x0 by A4,Lm1; then E,h |= x2 'in' x0 by A3,A4,ZF_MODEL:13; then E,h |= Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) ) by A6,ZF_MODEL:18; then consider f such that A7: (for x st f.x <> h.x holds x3 = x) & E,f |= x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) by ZF_MODEL:20; take w = f.x3; A8: E,f |= x3 'in' x0 '&' 'not' x3 '=' x2 & E,f |= All(x4,x4 'in' x2 => x4 'in' x3) by A7,ZF_MODEL:15; thus v c= w proof let a such that A9: a in v; v c= E by A1; then reconsider a' = a as Element of E by A9; consider m being Function of VAR,E such that A10: m.x4 = a' & for x st x <> x4 holds m.x = f.x by ZF_MODEL:21; for x st m.x <> f.x holds x4 = x by A10; then A11: E,m |= x4 'in' x2 => x4 'in' x3 by A8,ZF_MODEL:16; m.x2 = f.x2 & f.x2 = h.x2 by A7,A10,Lm1; then E,m |= x4 'in' x2 by A4,A9,A10,ZF_MODEL:13; then E,m |= x4 'in' x3 by A11,ZF_MODEL:18; then m.x4 in m.x3 by ZF_MODEL:13; hence thesis by A10,Lm1; end; A12: E,f |= x3 'in' x0 & E,f |= 'not' x3 '=' x2 by A8,ZF_MODEL:15; then not E,f |= x3 '=' x2 by ZF_MODEL:14; then f.x3 <> f.x2 & f.x2 = h.x2 by A7,Lm1,ZF_MODEL:12; hence v <> w by A4; f.x0 = h.x0 & h.x0 = g.x0 by A4,A7,Lm1; hence thesis by A12,ZF_MODEL:13; end; given u such that A13: u <> {} and A14: for v st v in u ex w st v c< w & w in u; consider a being Element of u; u c= E by A1; then reconsider a as Element of E by A13,TARSKI:def 3; let f0 be Function of VAR,E; consider f1 being Function of VAR,E such that A15: f1.x0 = u & for x st x <> x0 holds f1.x = f0.x by ZF_MODEL:21; A16: for x st f1.x <> f0.x holds x0 = x by A15; consider f2 being Function of VAR,E such that A17: f2.x1 = a & for x st x <> x1 holds f2.x = f1.x by ZF_MODEL:21; A18: for x st f2.x <> f1.x holds x1 = x by A17; now let f such that A19: for x st f.x <> f2.x holds x2 = x; now assume E,f |= x2 'in' x0; then f.x2 in f.x0 & f.x0 = f2.x0 & f2.x0 = f1.x0 by A17,A19,Lm1,ZF_MODEL:13; then consider w such that A20: f.x2 c< w & w in u by A14,A15; A21: f.x2 c=w & f.x2 <> w by A20,XBOOLE_0:def 8; consider g such that A22: g.x3 = w & for x st x <> x3 holds g.x = f.x by ZF_MODEL:21; A23: for x st g.x <> f.x holds x3 = x by A22; g.x0 = f.x0 & f.x0 = f2.x0 & f2.x0 = f1.x0 & g.x2 = f.x2 by A17,A19,A22,Lm1; then A24: E,g |= x3 'in' x0 & not E,g |= x3 '=' x2 by A15,A20,A22,ZF_MODEL:12,13; then E,g |= 'not' x3 '=' x2 by ZF_MODEL:14; then A25: E,g |= x3 'in' x0 '&' 'not' x3 '=' x2 by A24,ZF_MODEL:15; now let h such that A26: for x st h.x <> g.x holds x4 = x; now assume E,h |= x4 'in' x2; then h.x4 in h.x2 & h.x2 = g.x2 & g.x2 = f.x2 by A22,A26,Lm1,ZF_MODEL:13; then h.x3 = g.x3 & h.x4 in w by A21,A26,Lm1; hence E,h |= x4 'in' x3 by A22,ZF_MODEL:13; end; hence E,h |= x4 'in' x2 => x4 'in' x3 by ZF_MODEL:18; end; then E,g |= All(x4,x4 'in' x2 => x4 'in' x3) by ZF_MODEL:16; then E,g |= x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) by A25,ZF_MODEL:15; hence E,f |= Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) ) by A23,ZF_MODEL:20; end; hence E,f |= x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) ) by ZF_MODEL:18; end; then A27: E,f2 |= All(x2,x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) )) by ZF_MODEL:16; f2.x0 = f1.x0 by A17,Lm1; then E,f2 |= x1 'in' x0 by A13,A15,A17,ZF_MODEL:13; then E,f2 |= x1 'in' x0 '&' All(x2,x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) )) by A27,ZF_MODEL:15; then E,f1 |= Ex(x1,x1 'in' x0 '&' All(x2,x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) ))) by A18,ZF_MODEL:20; then E,f0 |= Ex(x0,Ex(x1,x1 'in' x0 '&' All(x2,x2 'in' x0 => Ex(x3,x3 'in' x0 '&' 'not' x3 '=' x2 '&' All(x4,x4 'in' x2 => x4 'in' x3) )))) by A16,ZF_MODEL:20; hence thesis by ZF_LANG:23,ZF_MODEL:def 9; end; theorem E is epsilon-transitive implies (E |= the_axiom_of_infinity iff ex X st X in E & X <> {} & for Y st Y in X ex Z st Y c< Z & Z in X) proof assume A1: E is epsilon-transitive; thus E |= the_axiom_of_infinity implies ex X st X in E & X <> {} & for Y st Y in X ex Z st Y c< Z & Z in X proof assume E |= the_axiom_of_infinity; then consider u such that A2: u <> {} & for v st v in u ex w st v c< w & w in u by A1,Th6; reconsider X = u as set; take X; thus X in E & X <> {} by A2; let Y such that A3: Y in X; X c= E by A1,ORDINAL1:def 2; then reconsider v = Y as Element of E by A3; consider w such that A4: v c< w & w in u by A2,A3; reconsider w as set; take w; thus thesis by A4; end; given X such that A5: X in E & X <> {} & for Y st Y in X ex Z st Y c< Z & Z in X; ex u st u <> {} & for v st v in u ex w st v c< w & w in u proof reconsider u = X as Element of E by A5; take u; thus u <> {} by A5; let v; assume v in u; then consider Z such that A6: v c< Z & Z in X by A5; X c= E by A1,A5,ORDINAL1:def 2; then reconsider w = Z as Element of E by A6; take w; thus thesis by A6; end; hence thesis by A1,Th6; end; theorem Th8: E is epsilon-transitive implies (E |= the_axiom_of_power_sets iff for u holds E /\ bool u in E) proof assume A1: X in E implies X c= E; thus E |= the_axiom_of_power_sets implies for u holds E /\ bool u in E proof assume E |= the_axiom_of_power_sets; then A2: E |= Ex(x1,All(x2,x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) )) by ZF_MODEL:25,def 10; let u; consider f0 being Function of VAR,E; consider f such that A3: f.x0 = u & for x st x <> x0 holds f.x = f0.x by ZF_MODEL:21; E,f |= Ex(x1,All(x2,x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) ) ) by A2,ZF_MODEL:def 5; then consider g such that A4: (for x st g.x <> f.x holds x1 = x) & E,g |= All(x2,x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) ) by ZF_MODEL:20; g.x1 = E /\ bool u proof thus a in g.x1 implies a in E /\ bool u proof assume A5: a in g.x1; g.x1 c= E by A1; then reconsider a' = a as Element of E by A5; consider h such that A6: h.x2 = a' & for x st x <> x2 holds h.x = g.x by ZF_MODEL:21; for x st h.x <> g.x holds x2 = x by A6; then A7: E,h |= x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) by A4,ZF_MODEL:16; h.x1 = g.x1 by A6,Lm1; then E,h |= x2 'in' x1 by A5,A6,ZF_MODEL:13; then A8: E,h |= All(x3,x3 'in' x2 => x3 'in' x0) by A7,ZF_MODEL:19; a' c= u proof let b such that A9: b in a'; a' c= E by A1; then reconsider b' = b as Element of E by A9; consider m being Function of VAR,E such that A10: m.x3 = b' & for x st x <> x3 holds m.x = h.x by ZF_MODEL:21; for x st m.x <> h.x holds x3 = x by A10; then A11: E,m |= x3 'in' x2 => x3 'in' x0 by A8,ZF_MODEL:16; m.x2 = h.x2 by A10,Lm1; then E,m |= x3 'in' x2 by A6,A9,A10,ZF_MODEL:13; then A12: E,m |= x3 'in' x0 by A11,ZF_MODEL:18; m.x0 = h.x0 & h.x0 = g.x0 & g.x0 = f.x0 by A4,A6,A10,Lm1; hence b in u by A3,A10,A12,ZF_MODEL:13; end; hence thesis by XBOOLE_0:def 3; end; let a; assume A13: a in E /\ bool u; then A14: a in E & a in bool u by XBOOLE_0:def 3; reconsider a as Element of E by A13,XBOOLE_0:def 3; consider h such that A15: h.x2 = a & for x st x <> x2 holds h.x = g.x by ZF_MODEL:21; for x st h.x <> g.x holds x2 = x by A15; then A16: E,h |= x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) by A4,ZF_MODEL:16; now let m be Function of VAR,E such that A17: for x st m.x <> h.x holds x3 = x; now assume E,m |= x3 'in' x2; then m.x3 in m.x2 & m.x2 = h.x2 & a c= u by A14,A17,Lm1,ZF_MODEL:13; then m.x3 in u & m.x0 = h.x0 & h.x0 = g.x0 & g.x0 = f.x0 by A4,A15,A17,Lm1; hence E,m |= x3 'in' x0 by A3,ZF_MODEL:13; end; hence E,m |= x3 'in' x2 => x3 'in' x0 by ZF_MODEL:18; end; then E,h |= All(x3,x3 'in' x2 => x3 'in' x0) by ZF_MODEL:16; then E,h |= x2 'in' x1 by A16,ZF_MODEL:19; then h.x2 in h.x1 & h.x1 = g.x1 by A15,Lm1,ZF_MODEL:13; hence thesis by A15; end; hence thesis; end; assume A18: for u holds E /\ bool u in E; E |= Ex(x1,All(x2,x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) )) proof let f; reconsider v = E /\ bool(f.x0) as Element of E by A18; consider g such that A19: g.x1 = v & for x st x <> x1 holds g.x = f.x by ZF_MODEL:21; now let h such that A20: for x st h.x <> g.x holds x2 = x; now thus E,h |= x2 'in' x1 implies E,h |= All(x3,x3 'in' x2 => x3 'in' x0) proof assume E,h |= x2 'in' x1; then A21: h.x2 in h.x1 by ZF_MODEL:13; h.x1 = v by A19,A20,Lm1; then A22: h.x2 in bool(f.x0) by A21,XBOOLE_0:def 3; now let m be Function of VAR,E such that A23: for x st m.x <> h.x holds x3 = x; now assume E,m |= x3 'in' x2; then m.x3 in m.x2 & m.x2 = h.x2 by A23,Lm1,ZF_MODEL:13; then m.x3 in f.x0 & f.x0 = g.x0 & g.x0 = h.x0 & h.x0 = m.x0 by A19,A20,A22,A23,Lm1; hence E,m |= x3 'in' x0 by ZF_MODEL:13; end; hence E,m |= x3 'in' x2 => x3 'in' x0 by ZF_MODEL:18; end; hence thesis by ZF_MODEL:16; end; assume A24: E,h |= All(x3,x3 'in' x2 => x3 'in' x0); h.x2 c= f.x0 proof let a such that A25: a in h.x2; h.x2 c= E by A1; then reconsider a' = a as Element of E by A25; consider m being Function of VAR,E such that A26: m.x3 = a' & for x st x <> x3 holds m.x = h.x by ZF_MODEL:21; (for x st m.x <> h.x holds x3 = x) & m.x2 = h.x2 by A26,Lm1; then E,m |= x3 'in' x2 => x3 'in' x0 & E,m |= x3 'in' x2 by A24,A25,A26,ZF_MODEL:13,16; then E,m |= x3 'in' x0 by ZF_MODEL:18; then m.x3 in m.x0 & m.x0 = h.x0 & h.x0 = g.x0 & g.x0 = f.x0 by A19,A20,A26,Lm1,ZF_MODEL:13; hence a in f.x0 by A26; end; then h.x2 in bool(f.x0) & h.x1 = g.x1 by A20,Lm1; then h.x2 in h.x1 by A19,XBOOLE_0:def 3; hence E,h |= x2 'in' x1 by ZF_MODEL:13; end; hence E,h |= x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) by ZF_MODEL:19; end; then A27: E,g |= All(x2,x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) ) by ZF_MODEL:16; for x st g.x <> f.x holds x1 = x by A19; hence E,f |= Ex(x1,All(x2,x2 'in' x1 <=> All(x3,x3 'in' x2 => x3 'in' x0) ) ) by A27,ZF_MODEL:20; end; hence thesis by ZF_MODEL:25,def 10; end; theorem E is epsilon-transitive implies (E |= the_axiom_of_power_sets iff for X st X in E holds E /\ bool X in E) proof assume A1: E is epsilon-transitive; hence E |= the_axiom_of_power_sets implies for X st X in E holds E /\ bool X in E by Th8; assume for X st X in E holds E /\ bool X in E; then for u holds E /\ bool u in E; hence thesis by A1,Th8; end; defpred Lm2[Nat] means for x,E,H,f st len H = $1 & not x in Free H & E,f |= H holds E,f |= All(x,H); Lm2: for n st for k st k < n holds Lm2[k] holds Lm2[n] proof let n such that A1: for k st k < n for x,E,H,f st len H = k & not x in Free H & E,f |= H holds E,f |= All(x,H); let x,E,H,f such that A2: len H = n and A3: not x in Free H & E,f |= H; A4: now assume H is_equality; then A5: H = (Var1 H) '=' Var2 H & Free H = { Var1 H,Var2 H } by ZF_LANG:53,ZF_MODEL:1; then A6: f.(Var1 H) = f.(Var2 H) & x <> Var1 H & x <> Var2 H by A3,TARSKI:def 2,ZF_MODEL:12; now let g; assume for y st g.y <> f.y holds x = y; then g.(Var1 H) = f.(Var1 H) & g.(Var2 H) = f.(Var2 H) by A6; hence E,g |= H by A5,A6,ZF_MODEL:12; end; hence thesis by ZF_MODEL:16; end; A7: now assume H is_membership; then A8: H = (Var1 H) 'in' Var2 H & Free H = { Var1 H,Var2 H } by ZF_LANG:54,ZF_MODEL:1; then A9: f.(Var1 H) in f.(Var2 H) & x <> Var1 H & x <> Var2 H by A3,TARSKI:def 2,ZF_MODEL:13; now let g; assume for y st g.y <> f.y holds x = y; then g.(Var1 H) = f.(Var1 H) & g.(Var2 H) = f.(Var2 H) by A9; hence E,g |= H by A8,A9,ZF_MODEL:13; end; hence thesis by ZF_MODEL:16; end; A10: now assume A11: H is negative; then A12: H = 'not' the_argument_of H & Free H = Free the_argument_of H by ZF_LANG:def 30,ZF_MODEL:1; assume not thesis; then consider g such that A13: for y st g.y <> f.y holds x = y and A14: not E,g |= H by ZF_MODEL:16; A15: E,g |= the_argument_of H by A12,A14,ZF_MODEL:14; the_argument_of H is_immediate_constituent_of H by A12,ZF_LANG:def 39 ; then len the_argument_of H < len H & not x in Free the_argument_of H by A3,A11,ZF_LANG:81,ZF_MODEL:1; then E,g |= All(x,the_argument_of H) by A1,A2,A15; then E,f |= the_argument_of H & not E,f |= the_argument_of H by A3,A12,A13,ZF_MODEL:14,16; hence contradiction; end; A16: now assume H is conjunctive; then A17: H = (the_left_argument_of H) '&' the_right_argument_of H & Free H = Free the_left_argument_of H \/ Free the_right_argument_of H by ZF_LANG:58,ZF_MODEL:1; then A18: E,f |= the_left_argument_of H & E,f |= the_right_argument_of H & not x in Free the_left_argument_of H & not x in Free the_right_argument_of H by A3,XBOOLE_0:def 2,ZF_MODEL:15; the_left_argument_of H is_immediate_constituent_of H & the_right_argument_of H is_immediate_constituent_of H by A17,ZF_LANG:def 39; then len the_left_argument_of H < len H & len the_right_argument_of H < len H by ZF_LANG:81; then A19: E,f |= All(x,the_left_argument_of H) & E,f |= All(x,the_right_argument_of H) by A1,A2,A18; now let g; assume for y st g.y <> f.y holds x = y; then E,g |= the_left_argument_of H & E,g |= the_right_argument_of H by A19,ZF_MODEL:16; hence E,g |= H by A17,ZF_MODEL:15; end; hence thesis by ZF_MODEL:16; end; now assume H is universal; then A20: H = All(bound_in H,the_scope_of H) & Free H = Free the_scope_of H \ { bound_in H } by ZF_LANG:62,ZF_MODEL:1; A21: now assume A22: x = bound_in H; now let g; assume for y st g.y <> f.y holds x = y or bound_in H = y; then for y st g.y <> f.y holds bound_in H = y by A22; hence E,g |= the_scope_of H by A3,A20,ZF_MODEL:16; end; then E,f |= All(x,bound_in H,the_scope_of H) by ZF_MODEL:22; hence thesis by A20,ZF_LANG:23; end; A23: not x in Free the_scope_of H or x in { bound_in H } by A3,A20,XBOOLE_0:def 4; now assume A24: x <> bound_in H; assume not thesis; then consider g such that A25: for y st g.y <> f.y holds x = y and A26: not E,g |= H by ZF_MODEL:16; consider h such that A27: for y st h.y <> g.y holds bound_in H = y and A28: not E,h |= the_scope_of H by A20,A26,ZF_MODEL:16; consider m being Function of VAR,E such that A29: m.(bound_in H) = h.(bound_in H) & for y st y <> bound_in H holds m.y = f.y by ZF_MODEL:21; (for y st m.y <> f.y holds bound_in H = y) & the_scope_of H is_immediate_constituent_of H by A20,A29,ZF_LANG:def 39; then len the_scope_of H < len H & E,m |= the_scope_of H by A3,A20,ZF_LANG:81,ZF_MODEL:16; then A30: E,m |= All(x,the_scope_of H) by A1,A2,A23,A24,TARSKI:def 1; now let y; assume A31: h.y <> m.y; then A32: y <> bound_in H by A29; assume x <> y; then f.y = g.y & m.y = f.y & h.y = g.y by A25,A27,A29,A32; hence contradiction by A31; end; hence contradiction by A28,A30,ZF_MODEL:16; end; hence thesis by A21; end; hence thesis by A4,A7,A10,A16,ZF_LANG:25; end; theorem Th10: not x in Free H & E,f |= H implies E,f |= All(x,H) proof A1: for n holds Lm2[n] from Comp_Ind(Lm2); len H = len H; hence thesis by A1; end; Lm3: the_scope_of All(x,H) = H & bound_in All(x,H) = x proof All(x,H) is universal by ZF_LANG:16; then All(x,H) = All(bound_in All(x,H),the_scope_of All(x,H)) by ZF_LANG:62 ; hence thesis by ZF_LANG:12; end; theorem Th11: { x,y } misses Free H & E,f |= H implies E,f |= All(x,y,H) proof assume A1: { x,y } misses Free H & E,f |= H; y in { x,y } & x in { x,y } by TARSKI:def 2; then A2: not y in Free H & not x in Free H by A1,XBOOLE_0:3; then A3: E,f |= All(y,H) by A1,Th10; All(y,H) is universal & the_scope_of All(y,H) = H & bound_in All(y,H) = y by Lm3,ZF_LANG:16; then Free All(y,H) = Free H \ { y } by ZF_MODEL:1; then not x in Free All(y,H) by A2,XBOOLE_0:def 4; then E,f |= All(x,All(y,H)) & All(x,y,H) = All(x,All(y,H)) by A3,Th10,ZF_LANG:23; hence thesis; end; theorem { x,y,z } misses Free H & E,f |= H implies E,f |= All(x,y,z,H) proof assume A1: { x,y,z } misses Free H & E,f |= H; now let a; assume a in { y,z }; then a = y or a = z by TARSKI:def 2; then a in { x,y,z } by ENUMSET1:14; hence not a in Free H by A1,XBOOLE_0:3; end; then { y,z } misses Free H by XBOOLE_0:3; then A2: E,f |= All(y,z,H) by A1,Th11; A3: All(y,z,H) = All(y,All(z,H)) & All(y,All(z,H)) is universal & the_scope_of All(y,All(z,H)) = All(z,H) & bound_in All(y,All(z,H)) = y & All(z,H) is universal & the_scope_of All(z,H) = H & bound_in All(z,H)= z by Lm3,ZF_LANG:16,23; then A4: Free All(y,z,H) = Free All(z,H) \ { y } by ZF_MODEL:1 .= (Free H \ { z }) \ { y } by A3,ZF_MODEL:1; x in { x,y,z } by ENUMSET1:14; then not x in Free H by A1,XBOOLE_0:3; then not x in Free H \ { z } by XBOOLE_0:def 4; then not x in (Free H \ { z }) \ { y } by XBOOLE_0:def 4; then E,f |= All(x,All(y,z,H)) & All(x,y,z,H) = All(x,All(y,z,H)) by A2,A4,Th10,ZF_LANG:24; hence thesis; end; definition let H,E; let val be Function of VAR,E; assume A1:not x.0 in Free H & E,val |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))); func def_func'(H,val) -> Function of E,E means :Def1: for g st for y st g.y <> val.y holds x.0 = y or x.3 = y or x.4 = y holds E,g |= H iff it.(g.x.3) = g.x.4; existence proof defpred Like[Function of VAR,E] means for y st $1.y <> val.y holds x0 = y or x3 = y or x4 = y; defpred P[set] means for g st Like[g] & g.x3 = $1`1 & g.x4 = $1`2 holds E,g |= H; consider X such that A2: a in X iff a in [:E,E:] & P[a] from Separation; X is Relation-like Function-like proof thus a in X implies ex b,c st [b,c] = a proof assume a in X; then a in [:E,E:] by A2; hence thesis by ZFMISC_1:102; end; let a,b,c; assume A3: [a,b] in X & [a,c] in X; then [a,b] in [:E,E:] & [a,c] in [:E,E:] & (for f st Like[f] & f.x3 = [a,b]`1 & f.x4 = [a,b]`2 holds E,f |= H) & for f st Like[f] & f.x3 = [a,c]`1 & f.x4 = [a,c]`2 holds E,f |= H by A2; then reconsider a' = a , b' = b , c' = c as Element of E by ZFMISC_1:106 ; A4: [a,b]`1 = a' & [a,b]`2 = b' & [a,c]`1 = a' & [a,c]`2 = c' by MCART_1:7; consider f such that A5: f.x3 = a' & for x st x <> x3 holds f.x = val.x by ZF_MODEL:21; for x st f.x <> val.x holds x = x3 by A5; then E,f |= Ex(x0,All(x4,H <=> x4 '=' x0)) by A1,ZF_MODEL:16; then consider g such that A6: (for x st g.x <> f.x holds x0 = x) & E,g |= All(x4,H <=> x4 '=' x0) by ZF_MODEL:20; consider g1 being Function of VAR,E such that A7: g1.x4 = b' & for x st x <> x4 holds g1.x = g.x by ZF_MODEL:21; consider g2 being Function of VAR,E such that A8: g2.x4 = c' & for x st x <> x4 holds g2.x = g.x by ZF_MODEL:21; (for x st g1.x <> g.x holds x4 = x) & (for x st g2.x <> g.x holds x4 = x) by A7,A8; then A9: E,g1 |= H <=> x4 '=' x0 & E,g2 |= H <=> x4 '=' x0 & g1.x3 = g.x3 & g2.x3 = g.x3 & g.x3 = f.x3 by A6,Lm1,ZF_MODEL:16; A10: Like[g1] proof let y; assume A11: g1.y <> val.y; assume x0 <> y & x3 <> y & x4 <> y; then f.y = val.y & g.y = f.y & g1.y = g.y by A5,A6,A7; hence contradiction by A11; end; Like[g2] proof let y; assume A12: g2.y <> val.y; assume x0 <> y & x3 <> y & x4 <> y; then f.y = val.y & g.y = f.y & g2.y = g.y by A5,A6,A8; hence contradiction by A12; end; then E,g1 |= H & E,g2 |= H by A2,A3,A4,A5,A7,A8,A9,A10; then E,g1 |= x4 '=' x0 & E,g2 |= x4 '=' x0 by A9,ZF_MODEL:19; then g1.x4 = g1.x0 & g2.x4 = g2.x0 & g1.x0 = g.x0 & g2.x0 = g.x0 by A7,A8,Lm1,ZF_MODEL:12; hence b = c by A7,A8; end; then reconsider F = X as Function; A13: E = dom F proof thus E c= dom F proof let a; assume a in E; then reconsider a' = a as Element of E; consider g such that A14: g.x3 = a' & for x st x <> x3 holds g.x = val.x by ZF_MODEL:21; for x st g.x <> val.x holds x = x3 by A14; then E,g |= Ex(x0,All(x4,H <=> x4 '=' x0)) by A1,ZF_MODEL:16; then consider h such that A15: (for x st h.x <> g.x holds x = x0) & E,h |= All(x4,H <=> x4 '=' x0) by ZF_MODEL:20; set u = h.x0; A16: [a',u] in [:E,E:] by ZFMISC_1:106; now let f such that A17: Like[f] & f.x3 = [a',u]`1 & f.x4 = [a',u]`2; consider m being Function of VAR,E such that A18: m.x4 = u & for x st x <> x4 holds m.x = h.x by ZF_MODEL:21; for x st m.x <> h.x holds x4 = x by A18; then A19: E,m |= H <=> x4 '=' x0 by A15,ZF_MODEL:16; m.x0 = h.x0 by A18; then E,m |= x4 '=' x0 by A18,ZF_MODEL:12; then E,m |= H by A19,ZF_MODEL:19; then A20: E,m |= All(x0,H) by A1,Th10; now let x such that A21: f.x <> m.x; assume A22: x0 <> x; g.x3 = h.x3 & h.x3 = m.x3 by A15,A18,Lm1; then x <> x4 & x <> x3 by A14,A17,A18,A21,MCART_1:7; then f.x = val.x & g.x = val.x & h.x = g.x & m.x = h.x by A14,A15,A17,A18,A22; hence contradiction by A21; end; hence E,f |= H by A20,ZF_MODEL:16; end; then [a',u] in X by A2,A16; hence a in dom F by FUNCT_1:8; end; thus dom F c= E proof let a; assume a in dom F; then consider b such that A23: [a,b] in F by RELAT_1:def 4; [a,b] in [:E,E:] by A2,A23; hence a in E by ZFMISC_1:106; end; end; rng F c= E proof let b; assume b in rng F; then consider a such that A24: a in dom F & b = F.a by FUNCT_1:def 5; [a,b] in F by A24,FUNCT_1:8; then [a,b] in [:E,E:] by A2; hence b in E by ZFMISC_1:106; end; then reconsider F as Function of E,E by A13,FUNCT_2:def 1,RELSET_1:11; take F; let f such that A25: for y st f.y <> val.y holds x.0 = y or x.3 = y or x.4 = y; A26: [f.x3,f.x4]`1 = f.x3 & [f.x3,f.x4]`2 = f.x4 by MCART_1:7; thus E,f |= H implies F.(f.x.3) = f.x.4 proof assume E,f |= H; then A27: E,f |= All(x0,H) by A1,Th10; A28: [f.x3,f.x4] in [:E,E:] by ZFMISC_1:106; now let g such that A29: Like[g] & g.x3 = [f.x3,f.x4]`1 & g.x4 = [f.x3,f.x4]`2; now let x; assume that A30: g.x <> f.x and A31: x0 <> x; x <> x3 & x <> x4 by A29,A30,MCART_1:7; then f.x = val.x & g.x = val.x by A25,A29,A31; hence contradiction by A30; end; hence E,g |= H by A27,ZF_MODEL:16; end; then [f.x3,f.x4] in X by A2,A28; hence F.(f.x.3) = f.x.4 by FUNCT_1:8; end; A32: f.x3 in E & dom F = E by FUNCT_2:def 1; assume F.(f.x.3) = f.x.4; then [f.x3,f.x4] in F by A32,FUNCT_1:8; hence E,f |= H by A2,A25,A26; end; uniqueness proof let F1,F2 be Function of E,E; assume that A33: for g st for y st g.y <> val.y holds x.0 = y or x.3 = y or x.4 = y holds E,g |= H iff F1.(g.x.3) = g.x.4 and A34: for g st for y st g.y <> val.y holds x.0 = y or x.3 = y or x.4 = y holds E,g |= H iff F2.(g.x.3) = g.x.4; now let a; assume a in E; then reconsider a' = a as Element of E; consider f such that A35: f.x3 = a' & for x st x <> x3 holds f.x = val.x by ZF_MODEL:21; for x st f.x <> val.x holds x3 = x by A35; then E,f |= Ex(x0,All(x4,H <=> x4 '=' x0)) by A1,ZF_MODEL:16; then consider g such that A36: (for x st g.x <> f.x holds x0 = x) & E,g |= All(x4,H <=> x4 '=' x0) by ZF_MODEL:20; consider h such that A37: h.x4 = g.x0 & for x st x <> x4 holds h.x = g.x by ZF_MODEL:21; for x st h.x <> g.x holds x4 = x by A37; then A38: E,h |= H <=> x4 '=' x0 by A36,ZF_MODEL:16; h.x0 = g.x0 by A37; then E,h |= x4 '=' x0 by A37,ZF_MODEL:12; then A39: E,h |= H by A38,ZF_MODEL:19; now let x; assume that A40: h.x <> val.x and A41: x.0 <> x & x.3 <> x & x.4 <> x; f.x = val.x & g.x = f.x & h.x = g.x by A35,A36,A37,A41; hence contradiction by A40; end; then A42: F1.(h.x.3) = h.x.4 & F2.(h.x.3) = h.x.4 by A33,A34,A39; h.x3 = g.x3 & g.x3 = f.x3 by A36,A37,Lm1; hence F1.a = F2.a by A35,A42; end; hence F1 = F2 by FUNCT_2:18; end; end; canceled; theorem Th14: for H,f,g st (for x st f.x <> g.x holds not x in Free H) & E,f |= H holds E,g |= H proof defpred Th[ZF-formula] means for f,g st (for x st f.x <> g.x holds not x in Free $1) & E,f |= $1 holds E,g |= $1; A1: for H st H is atomic holds Th[H] proof let H such that A2: H is_equality or H is_membership; let f,g such that A3: for x st f.x <> g.x holds not x in Free H and A4: E,f |= H; A5: now assume H is_equality; then A6: H = (Var1 H) '=' Var2 H & Free H = { Var1 H,Var2 H } by ZF_LANG:53,ZF_MODEL:1; then A7: f.(Var1 H) = f.(Var2 H) by A4,ZF_MODEL:12; Var1 H in Free H & Var2 H in Free H by A6,TARSKI:def 2; then f.(Var1 H) = g.(Var1 H) & f.(Var2 H) = g.(Var2 H) by A3; hence E,g |= H by A6,A7,ZF_MODEL:12; end; now assume H is_membership; then A8: H = (Var1 H) 'in' Var2 H & Free H = { Var1 H,Var2 H } by ZF_LANG:54,ZF_MODEL:1; then A9: f.(Var1 H) in f.(Var2 H) by A4,ZF_MODEL:13; Var1 H in Free H & Var2 H in Free H by A8,TARSKI:def 2; then f.(Var1 H) = g.(Var1 H) & f.(Var2 H) = g.(Var2 H) by A3; hence E,g |= H by A8,A9,ZF_MODEL:13; end; hence thesis by A2,A5; end; A10: for H st H is negative & Th[the_argument_of H] holds Th[H] proof let H; assume H is negative; then A11: H = 'not' the_argument_of H & Free H = Free the_argument_of H by ZF_LANG:def 30,ZF_MODEL:1; assume A12: for f,g st (for x st f.x <> g.x holds not x in Free the_argument_of H)& E,f |= the_argument_of H holds E,g |= the_argument_of H; let f,g such that A13: for x st f.x <> g.x holds not x in Free H and A14: E,f |= H and A15: not E,g |= H; E,g |= the_argument_of H by A11,A15,ZF_MODEL:14; then E,f |= the_argument_of H & not E,f |= the_argument_of H by A11,A12,A13,A14,ZF_MODEL:14; hence thesis; end; A16: for H st H is conjunctive & Th[the_left_argument_of H] & Th[the_right_argument_of H] holds Th[H] proof let H; assume H is conjunctive; then A17: H = (the_left_argument_of H) '&' the_right_argument_of H & Free H = Free the_left_argument_of H \/ Free the_right_argument_of H by ZF_LANG:58,ZF_MODEL:1; assume that A18: for f,g st (for x st f.x <> g.x holds not x in Free the_left_argument_of H)& E,f |= the_left_argument_of H holds E,g |= the_left_argument_of H and A19: for f,g st (for x st f.x <> g.x holds not x in Free the_right_argument_of H)& E,f |= the_right_argument_of H holds E,g |= the_right_argument_of H; let f,g such that A20: for x st f.x <> g.x holds not x in Free H and A21: E,f |= H; A22: E,f |= the_left_argument_of H & E,f |= the_right_argument_of H by A17,A21,ZF_MODEL:15; now let x; assume f.x <> g.x; then not x in Free H by A20; hence not x in Free the_left_argument_of H by A17,XBOOLE_0:def 2; end; then A23: E,g |= the_left_argument_of H by A18,A22; now let x; assume f.x <> g.x; then not x in Free H by A20; hence not x in Free the_right_argument_of H by A17,XBOOLE_0:def 2; end; then E,g |= the_right_argument_of H by A19,A22; hence thesis by A17,A23,ZF_MODEL:15; end; A24: for H st H is universal & Th[the_scope_of H] holds Th[H] proof let H; assume H is universal; then A25: H = All(bound_in H,the_scope_of H) & Free H = Free the_scope_of H \ { bound_in H } by ZF_LANG:62,ZF_MODEL:1; assume A26: for f,g st (for x st f.x <> g.x holds not x in Free the_scope_of H)& E,f |= the_scope_of H holds E,g |= the_scope_of H; let f,g such that A27: for x st f.x <> g.x holds not x in Free H and A28: E,f |= H; now let j such that A29: for x st j.x <> g.x holds bound_in H = x; consider h such that A30: h.(bound_in H) = j.(bound_in H) & for x st x <> bound_in H holds h.x = f.x by ZF_MODEL:21; for x st h.x <> f.x holds bound_in H = x by A30; then A31: E,h |= the_scope_of H by A25,A28,ZF_MODEL:16; now let x; assume A32: h.x <> j.x; then x <> bound_in H by A30; then A33: h.x = f.x & j.x = g.x & not x in { bound_in H } by A29,A30,TARSKI:def 1; then not x in Free H by A27,A32; hence not x in Free the_scope_of H by A25,A33,XBOOLE_0:def 4; end; hence E,j |= the_scope_of H by A26,A31; end; hence E,g |= H by A25,ZF_MODEL:16; end; thus for H holds Th[H] from ZF_Ind(A1,A10,A16,A24); end; definition let H,E; assume A1:Free H c= { x.3,x.4 } & E |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))); func def_func(H,E) -> Function of E,E means :Def2: for g holds E,g |= H iff it.(g.x.3) = g.x.4; existence proof consider f; take F = def_func'(H,f); A2: not x0 in Free H by A1,Lm1,TARSKI:def 2; A3: E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) by A1,ZF_MODEL:def 5; let g; thus E,g |= H implies F.(g.x.3) = g.x.4 proof assume A4: E,g |= H; consider g3 being Function of VAR,E such that A5: g3.x3 = g.x3 & for x st x <> x3 holds g3.x = f.x by ZF_MODEL:21; consider g4 being Function of VAR,E such that A6: g4.x4 = g.x4 & for x st x <> x4 holds g4.x = g3.x by ZF_MODEL:21; now let x; assume A7: g.x <> g4.x; then A8: x4 <> x by A6; then x3 <> x by A5,A6,A7; hence not x in Free H by A1,A8,TARSKI:def 2 ; end; then A9: E,g4 |= H by A4,Th14; now let x such that A10: g4.x <> f.x and A11: x.0 <> x & x.3 <> x & x.4 <> x; g4.x = g3.x by A6,A11 .= f.x by A5,A11; hence contradiction by A10; end; then F.(g4.x.3) = g4.x.4 by A2,A3,A9,Def1; hence F.(g.x.3) = g.x.4 by A5,A6,Lm1; end; assume that A12: F.(g.x.3) = g.x.4 and A13: not E,g |= H; consider j such that A14: j.x3 = g.x3 & for x st x <> x3 holds j.x = f.x by ZF_MODEL:21; consider h such that A15: h.x4 = g.x4 & for x st x <> x4 holds h.x = j.x by ZF_MODEL:21; now let x; assume A16: h.x <> g.x; then A17: x4 <> x by A15; then x3 <> x by A14,A15,A16; hence not x in Free H by A1,A17,TARSKI:def 2; end; then A18: not E,h |= H by A13,Th14; now let x such that A19: h.x <> f.x and A20: x.0 <> x & x.3 <> x & x.4 <> x; h.x = j.x by A15,A20 .= f.x by A14,A20; hence contradiction by A19; end; then F.(h.x.3) <> h.x.4 by A2,A3,A18,Def1; hence contradiction by A12,A14,A15,Lm1; end; uniqueness proof let F1,F2 be Function of E,E such that A21: for g holds E,g |= H iff F1.(g.x.3) = g.x.4 and A22: for g holds E,g |= H iff F2.(g.x.3) = g.x.4; now let a; assume a in E; then reconsider e = a as Element of E; consider f; consider g such that A23: g.x3 = e & for x st x <> x3 holds g.x = f.x by ZF_MODEL:21; E |= Ex(x0,All(x4,H <=> x4 '=' x0)) by A1,ZF_MODEL:25; then E,g |= Ex(x0,All(x4,H <=> x4 '=' x0)) by ZF_MODEL:def 5; then consider h such that A24: (for x st h.x <> g.x holds x0 = x) & E,h |= All(x4,H <=> x4 '=' x0) by ZF_MODEL:20; consider j such that A25: j.x4 = h.x0 & for x st x <> x4 holds j.x = h.x by ZF_MODEL:21; for x st j.x <> h.x holds x4 = x by A25; then A26: E,j |= H <=> x4 '=' x0 by A24,ZF_MODEL:16; j.x0 = h.x0 by A25; then E,j |= x4 '=' x0 by A25,ZF_MODEL:12; then E,j |= H by A26,ZF_MODEL:19; then A27: F1.(j.x3) = j.x4 & F2.(j.x3) = j.x4 by A21,A22; j.x3 = h.x3 & h.x3 = g.x3 by A24,A25,Lm1; hence F1.a = F2.a by A23,A27; end; hence thesis by FUNCT_2:18; end; end; definition let F be Function; let E; pred F is_definable_in E means ex H st Free H c= { x.3,x.4 } & E |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) & F = def_func(H,E); pred F is_parametrically_definable_in E means :Def4: ex H,f st { x.0,x.1,x.2 } misses Free H & E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) & F = def_func'(H,f); end; canceled 3; theorem for F being Function st F is_definable_in E holds F is_parametrically_definable_in E proof let F be Function; given H such that A1: Free H c= { x.3,x.4 } and A2: E |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) & F = def_func(H,E); consider f; reconsider F1 = F as Function of E,E by A2; take H,f; A3: now let a; assume a in { x.0,x.1,x.2 }; then a <> x3 & a <> x4 by Lm1,ENUMSET1:13; hence not a in Free H by A1,TARSKI:def 2; end; hence { x.0,x.1,x.2 } misses Free H by XBOOLE_0:3; A4: now assume x.0 in Free H; then not x.0 in { x.0,x.1,x.2 } & x.0 in { x.0,x.1,x.2 } by A3,ENUMSET1:14; hence contradiction; end; thus A5: E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) by A2,ZF_MODEL:def 5; for g st for y st g.y <> f.y holds x.0 = y or x.3 = y or x.4 = y holds E,g |= H iff F1.(g.x.3) = g.x.4 by A1,A2,Def2; hence F = def_func'(H,f) by A4,A5,Def1; end; theorem Th19: E is epsilon-transitive implies ((for H st { x.0,x.1,x.2 } misses Free H holds E |= the_axiom_of_substitution_for H) iff for H,f st { x.0,x.1,x.2 } misses Free H & E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) for u holds def_func'(H,f).:u in E ) proof assume A1: X in E implies X c= E; A2:now assume A3: for H st { x.0,x.1,x.2 } misses Free H holds E |= the_axiom_of_substitution_for H; let H,f; assume that A4: { x.0,x.1,x.2 } misses Free H and A5: E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))); x0 in { x0,x1,x2 } by ENUMSET1:14; then A6: not x0 in Free H by A4,XBOOLE_0:3; now let a; assume a in { x1,x2 }; then a = x1 or a = x2 by TARSKI:def 2; then a in { x0,x1,x2 } by ENUMSET1:14; hence not a in Free H by A4,XBOOLE_0:3; end; then A7: { x1,x2 } misses Free H by XBOOLE_0:3; let u; E |= the_axiom_of_substitution_for H by A3,A4; then E,f |= the_axiom_of_substitution_for H & the_axiom_of_substitution_for H = All(x3,Ex(x0,All(x4,H <=> x4 '=' x0))) => All(x1,Ex(x2,All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H)))) by ZF_MODEL:def 5,def 11; then A8: E,f |= All(x1,Ex(x2, All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H)) )) by A5,ZF_MODEL:18; consider g such that A9: g.x1 = u & for x st x <> x1 holds g.x = f.x by ZF_MODEL:21; for x st g.x <> f.x holds x1 = x by A9; then E,g |= Ex(x2,All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H))) by A8,ZF_MODEL:16; then consider h such that A10: (for x st h.x <> g.x holds x2 = x) & E,h |= All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H)) by ZF_MODEL:20; set v = h.x2; A11: def_func'(H,f).:u c= v proof let a; assume A12: a in def_func'(H,f).:u; then consider b such that A13: b in dom def_func'(H,f) & b in u & def_func'(H,f).b = a by FUNCT_1: def 12; reconsider e = a as Element of E by A12; reconsider b as Element of E by A13; consider i such that A14: i.x4 = e & for x st x <> x4 holds i.x = h.x by ZF_MODEL:21; for x st i.x <> h.x holds x4 = x by A14; then A15: E,i |= x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H) by A10,ZF_MODEL:16 ; consider j such that A16: j.x3 = b & for x st x <> x3 holds j.x = i.x by ZF_MODEL:21; j.x1 = i.x1 & i.x1 = h.x1 & h.x1 = g.x1 by A10,A14,A16,Lm1; then A17: E,j |= x3 'in' x1 by A9,A13,A16,ZF_MODEL:13; consider m1 being Function of VAR,E such that A18: m1.x3 = b & for x st x <> x3 holds m1.x = f.x by ZF_MODEL:21; consider m being Function of VAR,E such that A19: m.x4 = e & for x st x <> x4 holds m.x = m1.x by ZF_MODEL:21; now let y; assume A20: m.y <> f.y; assume x.0 <> y & x.3 <> y & x.4 <> y; then m.y = m1.y & m1.y = f.y by A18,A19; hence contradiction by A20; end; then A21: E,m |= H iff def_func'(H,f).(m.x.3) = m.x.4 by A5,A6,Def1; A22: m.x3 = m1.x3 by A19,Lm1; A23: E,m |= All(x1,x2,H) by A7,A13,A18,A19,A21,Lm1,Th11; consider k being Function of VAR,E such that A24: k.x1 = j.x1 & for x st x <> x1 holds k.x = m.x by ZF_MODEL:21; All(x1,x2,H) = All(x1,All(x2,H)) & for x st k.x <> m.x holds x1 = x by A24,ZF_LANG:23; then A25: E,k |= All(x2,H) by A23,ZF_MODEL:16; now let x; assume that A26: j.x <> k.x and A27: x2 <> x; A28: x <> x1 by A24,A26; A29: x <> x3 by A16,A18,A22,A24,A26,Lm1; k.x4 = m.x4 & j.x4 = i.x4 by A16,A24,Lm1; then A30: x <> x4 by A14,A19,A26; k.x = m.x by A24,A28 .= m1.x by A19,A30 .= f.x by A18,A29 .= g.x by A9,A28 .= h.x by A10,A27 .= i.x by A14,A30 .= j.x by A16,A29; hence contradiction by A26; end; then E,j |= H by A25,ZF_MODEL:16; then A31: E,j |= x3 'in' x1 '&' H by A17,ZF_MODEL:15; for x st i.x <> j.x holds x3 = x by A16; then E,i |= Ex(x3,x3 'in' x1 '&' H) by A31,ZF_MODEL:20; then E,i |= x4 'in' x2 by A15,ZF_MODEL:19; then i.x4 in i.x2 & i.x2 = h.x2 by A14,Lm1,ZF_MODEL:13; hence a in v by A14; end; v c= def_func'(H,f).:u proof let a such that A32: a in v; v c= E by A1; then reconsider e = a as Element of E by A32; consider i such that A33: i.x4 = e & for x st x <> x4 holds i.x = h.x by ZF_MODEL:21; for x st i.x <> h.x holds x4 = x by A33; then A34: E,i |= x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H) by A10,ZF_MODEL:16 ; i.x2 = h.x2 by A33,Lm1; then E,i |= x4 'in' x2 by A32,A33,ZF_MODEL:13; then E,i |= Ex(x3,x3 'in' x1 '&' H) by A34,ZF_MODEL:19; then consider j such that A35: (for x st j.x <> i.x holds x3 = x) & E,j |= x3 'in' x1 '&' H by ZF_MODEL:20; A36: E,j |= x3 'in' x1 & E,j |= H by A35,ZF_MODEL:15; then A37: j.x3 in j.x1 & j.x1 = i.x1 & i.x1 = h.x1 & h.x1 = g.x1 by A10,A33,A35,Lm1,ZF_MODEL:13; consider m1 being Function of VAR,E such that A38: m1.x3 = j.x3 & for x st x <> x3 holds m1.x = f.x by ZF_MODEL:21; consider m being Function of VAR,E such that A39: m.x4 = e & for x st x <> x4 holds m.x = m1.x by ZF_MODEL:21; now let y; assume A40: m.y <> f.y; assume x.0 <> y & x.3 <> y & x.4 <> y; then m.y = m1.y & m1.y = f.y by A38,A39; hence contradiction by A40; end; then A41: E,m |= H iff def_func'(H,f).(m.x.3) = m.x.4 by A5,A6,Def1; A42: E,j |= All(x1,x2,H) by A7,A36,Th11; consider k being Function of VAR,E such that A43: k.x1 = m.x1 & for x st x <> x1 holds k.x = j.x by ZF_MODEL:21; All(x1,x2,H) = All(x1,All(x2,H)) & for x st k.x <> j.x holds x1 = x by A43,ZF_LANG:23; then A44: E,k |= All(x2,H) by A42,ZF_MODEL:16; now let x; assume that A45: m.x <> k.x and A46: x2 <> x; A47: x1 <> x by A43,A45; k.x3 = j.x3 & m1.x3 = m.x3 by A39,A43,Lm1; then A48: x3 <> x by A38,A45; k.x4 = j.x4 & j.x4 = i.x4 by A35,A43,Lm1; then A49: x4 <> x by A33,A39,A45; k.x = j.x by A43,A47 .= i.x by A35,A48 .= h.x by A33,A49 .= g.x by A10,A46 .= f.x by A9,A47 .= m1.x by A38,A48 .= m.x by A39,A49; hence contradiction by A45; end; then A50: def_func'(H,f).(j.x3) = a by A38,A39,A41,A44,Lm1,ZF_MODEL:16; j.x3 in E & dom def_func'(H,f) = E by FUNCT_2:def 1; hence a in def_func'(H,f).:u by A9,A37,A50,FUNCT_1:def 12; end; then def_func'(H,f).:u = v by A11,XBOOLE_0:def 10; hence def_func'(H,f).:u in E; end; now assume A51: for H,f st { x.0,x.1,x.2 } misses Free H & E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) for u holds def_func'(H,f).:u in E; let H; assume A52: { x.0,x.1,x.2 } misses Free H; A53: the_axiom_of_substitution_for H = All(x3,Ex(x0,All(x4,H <=> x4 '=' x0))) => All(x1,Ex(x2,All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H)))) by ZF_MODEL:def 11; x0 in { x0,x1,x2 } by ENUMSET1:14; then A54: not x0 in Free H by A52,XBOOLE_0:3; now let a; assume a in { x1,x2 }; then a = x1 or a = x2 by TARSKI:def 2; then a in { x0,x1,x2 } by ENUMSET1:14; hence not a in Free H by A52,XBOOLE_0:3; end; then A55: { x1,x2 } misses Free H by XBOOLE_0:3; thus E |= the_axiom_of_substitution_for H proof let f; now assume A56: E,f |= All(x3,Ex(x0,All(x4,H <=> x4 '=' x0))); now let g such that A57: for x st g.x <> f.x holds x1 = x; reconsider v = def_func'(H,f).: (g.x1) as Element of E by A51,A52,A56; consider h such that A58: h.x2 = v & for x st x <> x2 holds h.x = g.x by ZF_MODEL:21; now let i such that A59: for x st i.x <> h.x holds x4 = x; A60: now assume E,i |= x4 'in' x2; then i.x4 in i.x2 & i.x2 = h.x2 by A59,Lm1,ZF_MODEL:13; then consider a such that A61: a in dom def_func'(H,f) & a in g.x1 & i.x4 = def_func'(H,f).a by A58,FUNCT_1:def 12; reconsider a as Element of E by A61; consider j such that A62: j.x3 = a & for x st x <> x3 holds j.x = i.x by ZF_MODEL:21; j.x1 = i.x1 & i.x1 = h.x1 & h.x1 = g.x1 by A58,A59,A62,Lm1 ; then A63: E,j |= x3 'in' x1 by A61,A62,ZF_MODEL:13; consider m1 being Function of VAR,E such that A64: m1.x3 = j.x3 & for x st x <> x3 holds m1.x = f.x by ZF_MODEL:21; consider m being Function of VAR,E such that A65: m.x4 = i.x4 & for x st x <> x4 holds m.x = m1.x by ZF_MODEL:21; now let x such that A66: m.x <> f.x and A67: x.0 <> x & x.3 <> x & x.4 <> x; m.x = m1.x & m1.x = f.x by A64,A65,A67; hence contradiction by A66; end; then (E,m |= H iff def_func'(H,f).(m.x.3) = m.x.4) & m.x3 = m1 .x3 by A54,A56,A65,Def1,Lm1; then A68: E,m |= All(x1,x2,H) by A55,A61,A62,A64,A65,Th11; consider k being Function of VAR,E such that A69: k.x1 = j.x1 & for x st x <> x1 holds k.x = m.x by ZF_MODEL: 21; All(x1,x2,H) = All(x1,All(x2,H)) & for x st k.x <> m.x holds x1 = x by A69,ZF_LANG:23; then A70: E,k |= All(x2,H) by A68,ZF_MODEL:16; now let x such that A71: j.x <> k.x and A72: x2 <> x; A73: x1 <> x by A69,A71; k.x3 = m.x3 & m.x3 = m1.x3 by A65,A69,Lm1; then A74: x3 <> x by A64,A71; j.x4 = i.x4 & k.x4 = m.x4 by A62,A69,Lm1; then A75: x4 <> x by A65,A71; j.x = i.x by A62,A74 .= h.x by A59,A75 .= g.x by A58,A72 .= f.x by A57,A73 .= m1.x by A64,A74 .= m.x by A65,A75 .= k.x by A69,A73; hence contradiction by A71; end; then E,j |= H by A70,ZF_MODEL:16; then E,j |= x3 'in' x1 '&' H & for x st j.x <> i.x holds x3 = x by A62,A63,ZF_MODEL:15; hence E,i |= Ex(x3,x3 'in' x1 '&' H) by ZF_MODEL:20; end; now assume E,i |= Ex(x3,x3 'in' x1 '&' H); then consider j such that A76: (for x st j.x <> i.x holds x3 = x) & E,j |= x3 'in' x1 '&' H by ZF_MODEL:20; A77: E,j |= x3 'in' x1 & E,j |= H by A76,ZF_MODEL:15; then A78: E,j |= All(x1,x2,H) by A55,Th11; consider m1 being Function of VAR,E such that A79: m1.x3 = j.x3 & for x st x <> x3 holds m1.x = f.x by ZF_MODEL:21; consider m being Function of VAR,E such that A80: m.x4 = i.x4 & for x st x <> x4 holds m.x = m1.x by ZF_MODEL:21; consider k being Function of VAR,E such that A81: k.x1 = m.x1 & for x st x <> x1 holds k.x = j.x by ZF_MODEL:21; All(x1,x2,H) = All(x1,All(x2,H)) & for x st k.x <> j.x holds x1 = x by A81,ZF_LANG:23; then A82: E,k |= All(x2,H) by A78,ZF_MODEL:16; now let x such that A83: m.x <> k.x and A84: x2 <> x; A85: x1 <> x by A81,A83; m.x3 = m1.x3 & k.x3 = j.x3 by A80,A81,Lm1; then A86: x3 <> x by A79,A83; k.x4 = j.x4 & j.x4 = i.x4 by A76,A81,Lm1; then A87: x4 <> x by A80,A83; then m.x = m1.x by A80 .= f.x by A79,A86 .= g.x by A57,A85 .= h.x by A58,A84 .= i.x by A59,A87 .= j.x by A76,A86 .= k.x by A81,A85; hence contradiction by A83; end; then A88: E,m |= H by A82,ZF_MODEL:16; now let x such that A89: m.x <> f.x and A90: x.0 <> x & x.3 <> x & x.4 <> x; f.x = m1.x by A79,A90 .= m.x by A80,A90; hence contradiction by A89; end; then A91: def_func'(H,f).(m.x.3) = m.x.4 & m.x3 = m1.x3 by A54,A56,A80,A88,Def1,Lm1; A92: j.x3 in j.x1 & j.x1 = i.x1 & i.x1 = h.x1 & h.x1 = g.x1 by A58,A59,A76,A77,Lm1,ZF_MODEL:13; j.x3 in E & dom def_func'(H,f) = E by FUNCT_2:def 1; then A93: i.x4 in def_func'(H,f).:(g.x1) by A79,A80,A91,A92, FUNCT_1:def 12; i.x2 = h.x2 by A59,Lm1; hence E,i |= x4 'in' x2 by A58,A93,ZF_MODEL:13; end; hence E,i |= x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H) by A60,ZF_MODEL:19; end; then E,h |= All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H)) & for x st h.x <> g.x holds x2 = x by A58,ZF_MODEL:16; hence E,g |= Ex(x2,All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H))) by ZF_MODEL:20; end; hence E,f |= All(x1,Ex(x2,All(x4,x4 'in' x2 <=> Ex(x3,x3 'in' x1 '&' H)))) by ZF_MODEL:16; end; hence E,f |= the_axiom_of_substitution_for H by A53,ZF_MODEL:18; end; end; hence thesis by A2; end; theorem E is epsilon-transitive implies ((for H st { x.0,x.1,x.2 } misses Free H holds E |= the_axiom_of_substitution_for H) iff for F being Function st F is_parametrically_definable_in E for X st X in E holds F.:X in E ) proof assume A1: E is epsilon-transitive; thus (for H st { x.0,x.1,x.2 } misses Free H holds E |= the_axiom_of_substitution_for H) implies for F being Function st F is_parametrically_definable_in E for X st X in E holds F.:X in E proof assume A2: for H st { x.0,x.1,x.2 } misses Free H holds E |= the_axiom_of_substitution_for H; let F be Function; given H,f such that A3: { x.0,x.1,x.2 } misses Free H and A4: E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) and A5: F = def_func'(H,f); let X; assume X in E; then reconsider u = X as Element of E; def_func'(H,f).:u in E by A1,A2,A3,A4,Th19; hence thesis by A5; end; assume A6: for F being Function st F is_parametrically_definable_in E for X st X in E holds F.:X in E; for H,f st { x.0,x.1,x.2 } misses Free H & E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) for u holds def_func'(H,f).:u in E proof let H,f; assume that A7: { x.0,x.1,x.2 } misses Free H and A8: E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))); A9: def_func'(H,f) is_parametrically_definable_in E by A7,A8,Def4; let u; thus thesis by A6,A9; end; hence thesis by A1,Th19; end; Lm4:E is epsilon-transitive implies for u,v st for w holds w in u iff w in v holds u = v proof assume A1: X in E implies X c= E; let u,v such that A2: for w holds w in u iff w in v; A3: u c= E & v c= E by A1; thus u c= v proof let a; assume A4: a in u; then reconsider e = a as Element of E by A3; e in v by A2,A4; hence a in v; end; let a; assume A5: a in v; then reconsider e = a as Element of E by A3; e in u by A2,A5; hence a in u; end; theorem E is_a_model_of_ZF implies E is epsilon-transitive & (for u,v st for w holds w in u iff w in v holds u = v) & (for u,v holds { u,v } in E) & (for u holds union u in E) & (ex u st u <> {} & for v st v in u ex w st v c< w & w in u) & (for u holds E /\ bool u in E) & (for H,f st { x.0,x.1,x.2 } misses Free H & E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) for u holds def_func'(H,f).:u in E ) proof assume E is epsilon-transitive & E |= the_axiom_of_pairs & E |= the_axiom_of_unions & E |= the_axiom_of_infinity & E |= the_axiom_of_power_sets & for H st { x.0,x.1,x.2 } misses Free H holds E |= the_axiom_of_substitution_for H; hence thesis by Lm4,Th2,Th4,Th6,Th8,Th19; end; theorem E is epsilon-transitive & (for u,v holds { u,v } in E) & (for u holds union u in E) & (ex u st u <> {} & for v st v in u ex w st v c< w & w in u) & (for u holds E /\ bool u in E) & (for H,f st { x.0,x.1,x.2 } misses Free H & E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) for u holds def_func'(H,f).:u in E ) implies E is_a_model_of_ZF proof assume E is epsilon-transitive & (for u,v holds { u,v } in E) & (for u holds union u in E) & (ex u st u <> {} & for v st v in u ex w st v c< w & w in u) & (for u holds E /\ bool u in E) & (for H,f st { x.0,x.1,x.2 } misses Free H & E,f |= All(x.3,Ex(x.0,All(x.4,H <=> x.4 '=' x.0))) for u holds def_func'(H,f).:u in E ); hence E is epsilon-transitive & E |= the_axiom_of_pairs & E |= the_axiom_of_unions & E |= the_axiom_of_infinity & E |= the_axiom_of_power_sets & for H st { x.0,x.1,x.2 } misses Free H holds E |= the_axiom_of_substitution_for H by Th2,Th4,Th6,Th8,Th19; end;