Theorem ackm 4754

Description: A remarkable equivalent to the Axiom of Choice that has only 5 quantifiers (when expanded to ∈, = primitives in prenex form), discovered and proved by Kurt Maes. This establishes a new record, reducing from 6 to 5 the largest number of quantified variables needed by any ZFC axiom. The ZF-equivalence to AC is shown by theorem aceqkm 4753. Maes found this version of AC in April, 2004 (replacing a longer version, also with 5 quantifiers, that he found in November, 2003). See Kurt Maes, "A 5-quantifier (∈,=)-expression ZF-equivalent to the Axiom of Choice" (http://arxiv.org/PS_cache/arxiv/pdf/0705/0705.3162v1.pdf).

The original FOM posts are: http://www.cs.nyu.edu/pipermail/fom/2003-November/007631.html http://www.cs.nyu.edu/pipermail/fom/2003-November/007641.html.

Assertion

Ref	Expression
ackm	⊢ ∀x∃y∀z∃v∀u((y ∈ x ⋀ (z ∈ y → ((v ∈ x ⋀ ¬ y = v) ⋀ z ∈ v))) ⋁ (¬ y ∈ x ⋀ (z ∈ x → ((v ∈ z ⋀ v ∈ y) ⋀ ((u ∈ z ⋀ u ∈ y) → u = v)))))

Distinct variable group:   x,y,z,v,u

Proof of Theorem ackm

Step	Hyp	Ref	Expression
1		aceqkm 4753	. 2 ⊢ (∀x∃f(f ⊆ x ⋀ f Fn dom x) ↔ ∀x∃y∀z∃v∀u((y ∈ x ⋀ (z ∈ y → ((v ∈ x ⋀ ¬ y = v) ⋀ z ∈ v))) ⋁ (¬ y ∈ x ⋀ (z ∈ x → ((v ∈ z ⋀ v ∈ y) ⋀ ((u ∈ z ⋀ u ∈ y) → u = v))))))
2		ac7 4720	. 2 ⊢ ∃f(f ⊆ x ⋀ f Fn dom x)
3	1, 2	mpgbi 984	1 ⊢ ∀x∃y∀z∃v∀u((y ∈ x ⋀ (z ∈ y → ((v ∈ x ⋀ ¬ y = v) ⋀ z ∈ v))) ⋁ (¬ y ∈ x ⋀ (z ∈ x → ((v ∈ z ⋀ v ∈ y) ⋀ ((u ∈ z ⋀ u ∈ y) → u = v)))))

Syntax hints:  ¬ wn 2   → wi 3   ⋁ wo 222   ⋀ wa 223  ∀wal 951   = wceq 953   ∈ wcel 955  ∃wex 977   ⊆ wss 2037  dom cdm 3160   Fn wfn 3167

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 959  ax-gen 960  ax-8 961  ax-9 962  ax-10 963  ax-11 964  ax-12 965  ax-13 966  ax-14 967  ax-17 968  ax-4 970  ax-5o 972  ax-6o 975  ax-9o 1119  ax-10o 1136  ax-16 1206  ax-11o 1213  ax-ext 1452  ax-rep 2683  ax-sep 2693  ax-nul 2700  ax-pow 2732  ax-pr 2769  ax-un 2857  ax-ac 4716

This theorem depends on definitions:  df-bi 147  df-or 224  df-an 225  df-ex 978  df-sb 1168  df-eu 1375  df-mo 1376  df-clab 1457  df-cleq 1462  df-clel 1465  df-ne 1579  df-ral 1641  df-rex 1642  df-reu 1643  df-rab 1644  df-v 1803  df-dif 2039  df-un 2040  df-in 2041  df-ss 2043  df-nul 2271  df-pw 2392  df-sn 2402  df-pr 2403  df-op 2406  df-uni 2494  df-iun 2558  df-br 2610  df-opab 2657  df-id 2824  df-xp 3174  df-rel 3175  df-cnv 3176  df-co 3177  df-dm 3178  df-rn 3179  df-res 3180  df-ima 3181  df-fun 3182  df-fn 3183  df-fv 3188

Copyright terms: Public domain