Theorem ac3 10362

Description: Axiom of Choice using abbreviations. The logical equivalence to ax-ac 10359 can be established by chaining aceq0 10018 and aceq2 10019. A standard textbook version of AC is derived from this one in dfac2a 10030, and this version of AC is derived from the textbook version in dfac2b 10031, showing their logical equivalence (see dfac2 10032).

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 9517. The key theorem for this (used in the proof of dfac2b 10031) is preleq 9515. 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 10361	. 2 ⊢ ∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)
2		aceq2 10019	. 2 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢) ↔ ∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
3	1, 2	mpbi 230	1 ⊢ ∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))

Syntax hints:   → wi 4   ∧ wa 395  ∃wex 1780   ≠ wne 2929  ∀wral 3048  ∃wrex 3057  ∃!wreu 3345  ∅c0 4282

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1968  ax-7 2009  ax-8 2115  ax-9 2123  ax-10 2146  ax-11 2162  ax-12 2182  ax-ext 2705  ax-ac 10359

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2068  df-mo 2537  df-eu 2566  df-clab 2712  df-cleq 2725  df-clel 2808  df-ne 2930  df-ral 3049  df-rex 3058  df-rmo 3347  df-reu 3348  df-dif 3901  df-nul 4283

This theorem is referenced by:  axac2  10366