Theorem ac3 10218

Description: Axiom of Choice using abbreviations. The logical equivalence to ax-ac 10215 can be established by chaining aceq0 9874 and aceq2 9875. A standard textbook version of AC is derived from this one in dfac2a 9885, and this version of AC is derived from the textbook version in dfac2b 9886, showing their logical equivalence (see dfac2 9887).

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 9376. The key theorem for this (used in the proof of dfac2b 9886) is preleq 9374. 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 10217	. 2 ⊢ ∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢)
2		aceq2 9875	. 2 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 ∀𝑤 ∈ 𝑧 ∃!𝑣 ∈ 𝑧 ∃𝑢 ∈ 𝑦 (𝑧 ∈ 𝑢 ∧ 𝑣 ∈ 𝑢) ↔ ∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
3	1, 2	mpbi 229	1 ⊢ ∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))

Syntax hints:   → wi 4   ∧ wa 396  ∃wex 1782   ≠ wne 2943  ∀wral 3064  ∃wrex 3065  ∃!wreu 3066  ∅c0 4256

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  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 2709  ax-ac 10215

This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-tru 1542  df-fal 1552  df-ex 1783  df-nf 1787  df-sb 2068  df-mo 2540  df-eu 2569  df-clab 2716  df-cleq 2730  df-clel 2816  df-ne 2944  df-ral 3069  df-rex 3070  df-reu 3072  df-dif 3890  df-nul 4257

This theorem is referenced by:  axac2  10222