Theorem zfac

Description: Axiom of Choice expressed with the fewest number of different variables. The penultimate step shows the logical equivalence to ax-ac . (New usage is discouraged.) (Contributed by NM, 14-Aug-2003)

	Ref	Expression
Assertion	zfac	⊢ ∃ 𝑥 ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑤 ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) )

Proof

Step	Hyp	Ref	Expression
1		ax-ac	⊢ ∃ 𝑥 ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑣 ∀ 𝑢 ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) )
2		equequ2	⊢ ( 𝑣 = 𝑤 → ( 𝑢 = 𝑣 ↔ 𝑢 = 𝑤 ) )
3	2	bibi2d	⊢ ( 𝑣 = 𝑤 → ( ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ↔ ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑤 ) ) )
4		elequ2	⊢ ( 𝑡 = 𝑤 → ( 𝑧 ∈ 𝑡 ↔ 𝑧 ∈ 𝑤 ) )
5	4	anbi2d	⊢ ( 𝑡 = 𝑤 → ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ↔ ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ) )
6		elequ2	⊢ ( 𝑡 = 𝑤 → ( 𝑢 ∈ 𝑡 ↔ 𝑢 ∈ 𝑤 ) )
7		elequ1	⊢ ( 𝑡 = 𝑤 → ( 𝑡 ∈ 𝑥 ↔ 𝑤 ∈ 𝑥 ) )
8	6 7	anbi12d	⊢ ( 𝑡 = 𝑤 → ( ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ↔ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) )
9	5 8	anbi12d	⊢ ( 𝑡 = 𝑤 → ( ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ) )
10	9	cbvexvw	⊢ ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ ∃ 𝑤 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) )
11	10	bibi1i	⊢ ( ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑤 ) ↔ ( ∃ 𝑤 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑤 ) )
12	3 11	bitrdi	⊢ ( 𝑣 = 𝑤 → ( ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ↔ ( ∃ 𝑤 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑤 ) ) )
13	12	albidv	⊢ ( 𝑣 = 𝑤 → ( ∀ 𝑢 ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ↔ ∀ 𝑢 ( ∃ 𝑤 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑤 ) ) )
14		elequ1	⊢ ( 𝑢 = 𝑦 → ( 𝑢 ∈ 𝑧 ↔ 𝑦 ∈ 𝑧 ) )
15	14	anbi1d	⊢ ( 𝑢 = 𝑦 → ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ↔ ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ) )
16		elequ1	⊢ ( 𝑢 = 𝑦 → ( 𝑢 ∈ 𝑤 ↔ 𝑦 ∈ 𝑤 ) )
17	16	anbi1d	⊢ ( 𝑢 = 𝑦 → ( ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ↔ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) )
18	15 17	anbi12d	⊢ ( 𝑢 = 𝑦 → ( ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ) )
19	18	exbidv	⊢ ( 𝑢 = 𝑦 → ( ∃ 𝑤 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ) )
20		equequ1	⊢ ( 𝑢 = 𝑦 → ( 𝑢 = 𝑤 ↔ 𝑦 = 𝑤 ) )
21	19 20	bibi12d	⊢ ( 𝑢 = 𝑦 → ( ( ∃ 𝑤 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑤 ) ↔ ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) ) )
22	21	cbvalvw	⊢ ( ∀ 𝑢 ( ∃ 𝑤 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑢 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑤 ) ↔ ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) )
23	13 22	bitrdi	⊢ ( 𝑣 = 𝑤 → ( ∀ 𝑢 ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ↔ ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) ) )
24	23	cbvexvw	⊢ ( ∃ 𝑣 ∀ 𝑢 ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ↔ ∃ 𝑤 ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) )
25	24	imbi2i	⊢ ( ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑣 ∀ 𝑢 ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ) ↔ ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑤 ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) ) )
26	25	2albii	⊢ ( ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑣 ∀ 𝑢 ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ) ↔ ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑤 ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) ) )
27	26	exbii	⊢ ( ∃ 𝑥 ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑣 ∀ 𝑢 ( ∃ 𝑡 ( ( 𝑢 ∈ 𝑧 ∧ 𝑧 ∈ 𝑡 ) ∧ ( 𝑢 ∈ 𝑡 ∧ 𝑡 ∈ 𝑥 ) ) ↔ 𝑢 = 𝑣 ) ) ↔ ∃ 𝑥 ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑤 ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) ) )
28	1 27	mpbi	⊢ ∃ 𝑥 ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑤 ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) )