Theorem hta

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 https://us.metamath.org/downloads/choice.txt (copy of obsolete link http://ghilbert.org/choice.txt) and https://us.metamath.org/downloads/megillaward2005he.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 the least rank for which ph ( x ) is true. Class B , which emulates Hilbert's 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 setvar 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 exlimiv and weth , using scottexs to establish the existence of A .

For a version of this theorem scheme using class (meta)variables instead of wff (meta)variables, see htalem . (Contributed by NM, 11-Mar-2004) (Revised by Mario Carneiro, 25-Jun-2015)

	Ref	Expression
Hypotheses	hta.1	$$⊢A=\left\{x|\left(\phi \wedge \forall y\left(\underset{\dot{}}{[}y/x\underset{\dot{}}{]}\phi \to \mathrm{rank}\left(x\right)\subseteq \mathrm{rank}\left(y\right)\right)\right)\right\}$$
	hta.2	$$⊢B=\left(\iota z\in A|\forall w\in A\neg wRz\right)$$
Assertion	hta	$$⊢R\mathrm{We}A\to \left(\phi \to \underset{\dot{}}{[}B/x\underset{\dot{}}{]}\phi \right)$$

Proof

Step	Hyp	Ref	Expression
1		hta.1	$$⊢A=\left\{x|\left(\phi \wedge \forall y\left(\underset{\dot{}}{[}y/x\underset{\dot{}}{]}\phi \to \mathrm{rank}\left(x\right)\subseteq \mathrm{rank}\left(y\right)\right)\right)\right\}$$
2		hta.2	$$⊢B=\left(\iota z\in A|\forall w\in A\neg wRz\right)$$
3		19.8a	$$⊢\phi \to \exists x\phi$$
4		scott0s	$$⊢\exists x\phi \leftrightarrow \left\{x|\left(\phi \wedge \forall y\left(\underset{\dot{}}{[}y/x\underset{\dot{}}{]}\phi \to \mathrm{rank}\left(x\right)\subseteq \mathrm{rank}\left(y\right)\right)\right)\right\}\ne \varnothing$$
5	1	neeq1i	$$⊢A\ne \varnothing \leftrightarrow \left\{x|\left(\phi \wedge \forall y\left(\underset{\dot{}}{[}y/x\underset{\dot{}}{]}\phi \to \mathrm{rank}\left(x\right)\subseteq \mathrm{rank}\left(y\right)\right)\right)\right\}\ne \varnothing$$
6	4 5	bitr4i	$$⊢\exists x\phi \leftrightarrow A\ne \varnothing$$
7	3 6	sylib	$$⊢\phi \to A\ne \varnothing$$
8		scottexs	$$⊢\left\{x|\left(\phi \wedge \forall y\left(\underset{\dot{}}{[}y/x\underset{\dot{}}{]}\phi \to \mathrm{rank}\left(x\right)\subseteq \mathrm{rank}\left(y\right)\right)\right)\right\}\in \mathrm{V}$$
9	1 8	eqeltri	$$⊢A\in \mathrm{V}$$
10	9 2	htalem	$$⊢\left(R\mathrm{We}A\wedge A\ne \varnothing \right)\to B\in A$$
11	10	ex	$$⊢R\mathrm{We}A\to \left(A\ne \varnothing \to B\in A\right)$$
12		simpl	$$⊢\left(\phi \wedge \forall y\left(\underset{\dot{}}{[}y/x\underset{\dot{}}{]}\phi \to \mathrm{rank}\left(x\right)\subseteq \mathrm{rank}\left(y\right)\right)\right)\to \phi$$
13	12	ss2abi	$$⊢\left\{x|\left(\phi \wedge \forall y\left(\underset{\dot{}}{[}y/x\underset{\dot{}}{]}\phi \to \mathrm{rank}\left(x\right)\subseteq \mathrm{rank}\left(y\right)\right)\right)\right\}\subseteq \left\{x|\phi \right\}$$
14	1 13	eqsstri	$$⊢A\subseteq \left\{x|\phi \right\}$$
15	14	sseli	$$⊢B\in A\to B\in \left\{x|\phi \right\}$$
16		df-sbc	$$⊢\underset{\dot{}}{[}B/x\underset{\dot{}}{]}\phi \leftrightarrow B\in \left\{x|\phi \right\}$$
17	15 16	sylibr	$$⊢B\in A\to \underset{\dot{}}{[}B/x\underset{\dot{}}{]}\phi$$
18	7 11 17	syl56	$$⊢R\mathrm{We}A\to \left(\phi \to \underset{\dot{}}{[}B/x\underset{\dot{}}{]}\phi \right)$$