Theorem ac3 10453

Description: Axiom of Choice using abbreviations. The logical equivalence to ax-ac 10450 can be established by chaining aceq0 10109 and aceq2 10110. A standard textbook version of AC is derived from this one in dfac2a 10120, and this version of AC is derived from the textbook version in dfac2b 10121, showing their logical equivalence (see dfac2 10122).

The following sketch will help you understand this version of the axiom. Given any set 𝑥, the axiom says that there exists a 𝑦 that is a collection of unordered pairs, one pair for each nonempty member of 𝑥. One entry in the pair is the member of 𝑥, and the other entry is some arbitrary member of that member of 𝑥. Using the Axiom of Regularity, we can show that 𝑦 is really a set of ordered pairs, very similar to the ordered pair construction opthreg 9609. The key theorem for this (used in the proof of dfac2b 10121) is preleq 9607. With this modified definition of ordered pair, it can be seen that 𝑦 is actually a choice function on the members of 𝑥.

For example, suppose 𝑥 = {{1, 2}, {1, 3}, {2, 3, 4}}. Let us try 𝑦 = {{{1, 2}, 1}, {{1, 3}, 1}, {{2, 3, 4}, 2}}. For the member (of 𝑥) 𝑧 = {1, 2}, the only assignment to 𝑤 and 𝑣 that satisfies the axiom is 𝑤 = 1 and 𝑣 = {{1, 2}, 1}, so there is exactly one 𝑤 as required. We verify the other two members of 𝑥 similarly. Thus, 𝑦 satisfies the axiom. Using our modified ordered pair definition, we can say that 𝑦 corresponds to the choice function {⟨{1, 2}, 1⟩, ⟨{1, 3}, 1⟩, ⟨{2, 3, 4}, 2⟩}. Of course other choices for 𝑦 will also satisfy the axiom, for example 𝑦 = {{{1, 2}, 2}, {{1, 3}, 1}, {{2, 3, 4}, 4}}. What AC tells us is that there exists at least one such 𝑦, but it doesn't tell us which one.

(New usage is discouraged.) (Contributed by NM, 19-Jul-1996.)

Assertion

Ref	Expression
ac3	⊢ ∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))

Distinct variable group:   𝑥,𝑦,𝑧,𝑤,𝑣

Proof of Theorem ac3

Dummy variable 𝑢 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		ac2 10452	. 2 ⊢ ∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)
2		aceq2 10110	. 2 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢) ↔ ∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
3	1, 2	mpbi 229	1 ⊢ ∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))

Syntax hints:   → wi 4   ∧ wa 396  ∃wex 1781   ≠ wne 2940  ∀wral 3061  ∃wrex 3070  ∃!wreu 3374  ∅c0 4321

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2703  ax-ac 10450

This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2534  df-eu 2563  df-clab 2710  df-cleq 2724  df-clel 2810  df-ne 2941  df-ral 3062  df-rex 3071  df-rmo 3376  df-reu 3377  df-dif 3950  df-nul 4322

This theorem is referenced by:  axac2  10457