Theorem ackm 5740

Description: A remarkable equivalent to the Axiom of Choice that has only 5 quantifiers (when expanded to e., = 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 5739. 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 (e.,=)-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	|- A.xE.yA.zE.vA.u((y e. x /\ (z e. y -> ((v e. x /\ -. y = v) /\ z e. v))) \/ (-. y e. x /\ (z e. x -> ((v e. z /\ v e. y) /\ ((u e. z /\ u e. y) -> u = v)))))

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

Proof of Theorem ackm

Step	Hyp	Ref	Expression
1		aceqkm 5739	. 2 |- (A.xE.f(f C_ x /\ f Fn dom x) <-> A.xE.yA.zE.vA.u((y e. x /\ (z e. y -> ((v e. x /\ -. y = v) /\ z e. v))) \/ (-. y e. x /\ (z e. x -> ((v e. z /\ v e. y) /\ ((u e. z /\ u e. y) -> u = v))))))
2		ac7 5706	. 2 |- E.f(f C_ x /\ f Fn dom x)
3	1, 2	mpgbi 1171	1 |- A.xE.yA.zE.vA.u((y e. x /\ (z e. y -> ((v e. x /\ -. y = v) /\ z e. v))) \/ (-. y e. x /\ (z e. x -> ((v e. z /\ v e. y) /\ ((u e. z /\ u e. y) -> u = v)))))

Syntax hints:  -. wn 2   -> wi 3   \/ wo 238   /\ wa 239  A.wal 1134   = wceq 1136   e. wcel 1138  E.wex 1164   C_ wss 2426  dom cdm 3797   Fn wfn 3804

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 1142  ax-gen 1143  ax-8 1144  ax-9 1145  ax-10 1146  ax-11 1147  ax-12 1148  ax-13 1149  ax-14 1150  ax-17 1155  ax-4 1157  ax-5o 1159  ax-6o 1162  ax-9o 1319  ax-10o 1338  ax-16 1418  ax-11o 1426  ax-ext 1702  ax-rep 3243  ax-sep 3253  ax-nul 3260  ax-pow 3296  ax-pr 3339  ax-un 3601  ax-ac 5702

This theorem depends on definitions:  df-bi 163  df-or 240  df-an 241  df-ex 1165  df-sb 1374  df-eu 1613  df-mo 1614  df-clab 1709  df-cleq 1714  df-clel 1717  df-ne 1856  df-ral 1943  df-rex 1944  df-reu 1945  df-rab 1946  df-v 2127  df-sbc 2287  df-csb 2374  df-dif 2430  df-un 2433  df-in 2436  df-ss 2438  df-nul 2702  df-pw 2859  df-sn 2873  df-pr 2874  df-op 2877  df-uni 3000  df-iun 3079  df-br 3159  df-opab 3214  df-id 3401  df-xp 3811  df-rel 3812  df-cnv 3813  df-co 3814  df-dm 3815  df-rn 3816  df-res 3817  df-ima 3818  df-fun 3819  df-fn 3820  df-fv 3825

Copyright terms: Public domain