Theorem hta 4874

Description: A ZFC emulation of Hilbert's transfinite axiom. The set B has the properties of Hilbert's epsilon, except that it also depends on a well-ordering R. This theorem arose from discussions with Raph Levien on 5-Mar-2004 about translating the HOL proof language, which uses Hilbert's epsilon. See http://ghilbert.org/choice.txt and http://us.metamath.org/downloads/megillaward2004.pdf.

Hilbert's epsilon is described at http://plato.stanford.edu/entries/epsilon-calculus/. This theorem differs from Hilbert's transfinite axiom described on that page in that it requires R We A as an antecedent. Class A collects the sets of least rank for which ph(x) is true. Class B, which emulates the epsilon, is the minimum element in a well-ordering R on A.

If a well-ordering R on A can be expressed in a closed form, as might be the case if we are working with say natural numbers, we can eliminate the antecedent with modus ponens, giving us the exact equivalent of Hilbert's transfinite axiom. Otherwise, we replace R with a dummy set variable, say w, and attach w We A as an antecedent in each step of the ZFC version of the HOL proof until the epsilon is eliminated. At that point, B (which will have w as a free variable) will no longer be present, and we can eliminate w We A by applying 19.23aiv 1333 and weth 4933, using scottexs 4864 to establish the existence of A.

For a version of this theorem scheme using class (meta)variables instead of wff (meta)variables, see htalem 4873.

Hypotheses

Ref	Expression
hta.1	|- A = {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))}
hta.2	|- B = U.{x e. A | A.y e. A -. yRx}

Assertion

Ref	Expression
hta	|- (R We A -> (ph -> [B / x]ph))

Distinct variable groups:   x,y,R   ph,y

Proof of Theorem hta

Step	Hyp	Ref	Expression
1		hta.1	. . . . 5 |- A = {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))}
2		weeq2 2965	. . . . 5 |- (A = {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> (R We A <-> R We {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))}))
3	1, 2	ax-mp 7	. . . 4 |- (R We A <-> R We {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
4		scottexs 4864	. . . . . 6 |- {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} e. V
5		hta.2	. . . . . . 7 |- B = U.{x e. A | A.y e. A -. yRx}
6		ax-17 1007	. . . . . . . . . . . . . . . 16 |- (ph -> A.yph)
7		hba1 1039	. . . . . . . . . . . . . . . 16 |- (A.y([y / x]ph -> (rank` x) (_ (rank` y)) -> A.yA.y([y / x]ph -> (rank` x) (_ (rank` y)))
8	6, 7	hban 1045	. . . . . . . . . . . . . . 15 |- ((ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y))) -> A.y(ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y))))
9	8	hbab 1509	. . . . . . . . . . . . . 14 |- (z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> A.y z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
10	1, 9	hbxfr 1606	. . . . . . . . . . . . 13 |- (z e. A -> A.y z e. A)
11	10, 9	raleq1f 1829	. . . . . . . . . . . 12 |- (A = {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> (A.y e. A -. yRx <-> A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx))
12	1, 11	ax-mp 7	. . . . . . . . . . 11 |- (A.y e. A -. yRx <-> A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx)
13	12	a1i 8	. . . . . . . . . 10 |- (x e. A -> (A.y e. A -. yRx <-> A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx))
14	13	rabbii 1851	. . . . . . . . 9 |- {x e. A | A.y e. A -. yRx} = {x e. A | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx}
15		hbab1 1508	. . . . . . . . . . . 12 |- (z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> A.x z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
16	1, 15	hbxfr 1606	. . . . . . . . . . 11 |- (z e. A -> A.x z e. A)
17	16, 15	rabeqf 1854	. . . . . . . . . 10 |- (A = {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> {x e. A | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx} = {x e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx})
18	1, 17	ax-mp 7	. . . . . . . . 9 |- {x e. A | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx} = {x e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx}
19		hbab1 1508	. . . . . . . . . . 11 |- (v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> A.x v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
20		ax-17 1007	. . . . . . . . . . 11 |- (v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> A.z v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
21		ax-17 1007	. . . . . . . . . . 11 |- (A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx -> A.zA.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx)
22		hbab1 1508	. . . . . . . . . . . 12 |- (y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> A.x y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
23		ax-17 1007	. . . . . . . . . . . 12 |- (-. yRz -> A.x -. yRz)
24	22, 23	hbral 1732	. . . . . . . . . . 11 |- (A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRz -> A.xA.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRz)
25		breq2 2696	. . . . . . . . . . . . 13 |- (x = z -> (yRx <-> yRz))
26	25	notbid 614	. . . . . . . . . . . 12 |- (x = z -> (-. yRx <-> -. yRz))
27	26	ralbidv 1709	. . . . . . . . . . 11 |- (x = z -> (A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx <-> A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRz))
28	19, 20, 21, 24, 27	cbvrab 1956	. . . . . . . . . 10 |- {x e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx} = {z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRz}
29		ax-17 1007	. . . . . . . . . . . . 13 |- (z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> A.v z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
30		ax-17 1007	. . . . . . . . . . . . 13 |- (-. yRz -> A.v -. yRz)
31		ax-17 1007	. . . . . . . . . . . . 13 |- (-. vRz -> A.y -. vRz)
32		breq1 2695	. . . . . . . . . . . . . 14 |- (y = v -> (yRz <-> vRz))
33	32	notbid 614	. . . . . . . . . . . . 13 |- (y = v -> (-. yRz <-> -. vRz))
34	9, 29, 30, 31, 33	cbvralf 1842	. . . . . . . . . . . 12 |- (A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRz <-> A.v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. vRz)
35	34	a1i 8	. . . . . . . . . . 11 |- (z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> (A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRz <-> A.v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. vRz))
36	35	rabbii 1851	. . . . . . . . . 10 |- {z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRz} = {z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. vRz}
37	28, 36	eqtri 1538	. . . . . . . . 9 |- {x e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.y e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. yRx} = {z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. vRz}
38	14, 18, 37	3eqtri 1542	. . . . . . . 8 |- {x e. A | A.y e. A -. yRx} = {z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. vRz}
39	38	unieqi 2577	. . . . . . 7 |- U.{x e. A | A.y e. A -. yRx} = U.{z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. vRz}
40	5, 39	eqtri 1538	. . . . . 6 |- B = U.{z e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} | A.v e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -. vRz}
41	4, 40	htalem 4873	. . . . 5 |- ((R We {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} /\ {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} =/= (/)) -> B e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))})
42	41	ex 371	. . . 4 |- (R We {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> ({x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} =/= (/) -> B e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))}))
43	3, 42	sylbi 197	. . 3 |- (R We A -> ({x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} =/= (/) -> B e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))}))
44		pm3.26 317	. . . . . 6 |- ((ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y))) -> ph)
45	44	ss2abi 2172	. . . . 5 |- {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} (_ {x | ph}
46	45	sseli 2117	. . . 4 |- (B e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> B e. {x | ph})
47	1, 4	eqeltri 1587	. . . . . . . 8 |- A e. V
48		ax-17 1007	. . . . . . . . . . 11 |- (z e. v -> A.x z e. v)
49	48, 16	hbel 1609	. . . . . . . . . 10 |- (v e. A -> A.x v e. A)
50		ax-17 1007	. . . . . . . . . 10 |- (v e. A -> A.z v e. A)
51		ax-17 1007	. . . . . . . . . 10 |- (A.y e. A -. yRx -> A.zA.y e. A -. yRx)
52		ax-17 1007	. . . . . . . . . . . 12 |- (z e. y -> A.x z e. y)
53	52, 16	hbel 1609	. . . . . . . . . . 11 |- (y e. A -> A.x y e. A)
54	53, 23	hbral 1732	. . . . . . . . . 10 |- (A.y e. A -. yRz -> A.xA.y e. A -. yRz)
55	26	ralbidv 1709	. . . . . . . . . 10 |- (x = z -> (A.y e. A -. yRx <-> A.y e. A -. yRz))
56	49, 50, 51, 54, 55	cbvrab 1956	. . . . . . . . 9 |- {x e. A | A.y e. A -. yRx} = {z e. A | A.y e. A -. yRz}
57		ssrab2 2183	. . . . . . . . 9 |- {z e. A | A.y e. A -. yRz} (_ A
58	56, 57	eqsstri 2143	. . . . . . . 8 |- {x e. A | A.y e. A -. yRx} (_ A
59	47, 58	ssexi 2794	. . . . . . 7 |- {x e. A | A.y e. A -. yRx} e. V
60	59	uniex 3093	. . . . . 6 |- U.{x e. A | A.y e. A -. yRx} e. V
61	5, 60	eqeltri 1587	. . . . 5 |- B e. V
62	61	elabs 2014	. . . 4 |- (B e. {x | ph} <-> [B / x]ph)
63	46, 62	sylib 196	. . 3 |- (B e. {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} -> [B / x]ph)
64	43, 63	syl6 22	. 2 |- (R We A -> ({x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} =/= (/) -> [B / x]ph))
65		19.8a 1065	. . 3 |- (ph -> E.xph)
66		scott0s 4865	. . 3 |- (E.xph <-> {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} =/= (/))
67	65, 66	sylib 196	. 2 |- (ph -> {x | (ph /\ A.y([y / x]ph -> (rank` x) (_ (rank` y)))} =/= (/))
68	64, 67	syl5 21	1 |- (R We A -> (ph -> [B / x]ph))

Syntax hints:  -. wn 2   -> wi 3   <-> wb 144   /\ wa 221  A.wal 990   = wceq 992   e. wcel 994  E.wex 1016  [wsbc 1207  {cab 1505   =/= wne 1628  A.wral 1691  {crab 1694  Vcvv 1857   (_ wss 2099  (/)c0 2332  U.cuni 2569   class class class wbr 2692   We wwe 2946  ` cfv 3263  rankcrnk 4788

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 998  ax-gen 999  ax-8 1000  ax-9 1001  ax-10 1002  ax-11 1003  ax-12 1004  ax-13 1005  ax-14 1006  ax-17 1007  ax-4 1009  ax-5o 1011  ax-6o 1014  ax-9o 1159  ax-10o 1177  ax-16 1247  ax-11o 1255  ax-ext 1500  ax-rep 2767  ax-sep 2777  ax-nul 2784  ax-pow 2818  ax-pr 2855  ax-un 3089  ax-reg 4736  ax-inf2 4770

This theorem depends on definitions:  df-bi 145  df-or 222  df-an 223  df-3or 782  df-3an 783  df-ex 1017  df-sb 1209  df-eu 1421  df-mo 1422  df-clab 1506  df-cleq 1511  df-clel 1514  df-ne 1630  df-ral 1695  df-rex 1696  df-reu 1697  df-rab 1698  df-v 1858  df-sbc 1987  df-csb 2052  df-dif 2101  df-un 2102  df-in 2103  df-ss 2105  df-nul 2333  df-if 2416  df-pw 2459  df-sn 2470  df-pr 2471  df-tp 2473  df-op 2474  df-uni 2570  df-int 2601  df-iun 2635  df-iin 2636  df-br 2693  df-opab 2741  df-tr 2755  df-eprel 2910  df-id 2913  df-po 2918  df-so 2929  df-fr 2947  df-we 2962  df-ord 2978  df-on 2979  df-lim 2980  df-suc 2981  df-om 3219  df-xp 3265  df-rel 3266  df-cnv 3267  df-co 3268  df-dm 3269  df-rn 3270  df-res 3271  df-ima 3272  df-fun 3273  df-fn 3274  df-fv 3279  df-rdg 4233  df-r1 4789  df-rank 4790

Copyright terms: Public domain