This is an inofficial mirror of http://metamath.tirix.org for personal testing of a visualizer extension only.

Metamath Proof Explorer

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 ⊢ ∃ 𝑥 ∀ 𝑦 ∀ 𝑧 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) → ∃ 𝑤 ∀ 𝑦 ( ∃ 𝑤 ( ( 𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑤 ) ∧ ( 𝑦 ∈ 𝑤 ∧ 𝑤 ∈ 𝑥 ) ) ↔ 𝑦 = 𝑤 ) )