Theorem zorn 6444

Description: Zorn's Lemma. If the union of every chain (with respect to inclusion) in a set belongs to the set, then the set contains a maximal element. This theorem is equivalent to the Axiom of Choice. Theorem 6M of [Enderton] p. 151. See zorn2 6443 for a version with general partial orderings.

Hypothesis

Ref	Expression
zorn2.1	|- A e. _V

Assertion

Ref	Expression
zorn	|- (A.z((z C_ A /\ A.x e. z A.y e. z (x C_ y \/ y C_ x)) -> U.z e. A) -> E.x e. A A.y e. A -. x C. y)

Distinct variable group:   x,y,z,A

Proof of Theorem zorn

Step	Hyp	Ref	Expression
1		pssirr 2964	. . . . . . . 8 |- -. u C. u
2		zornlem 6442	. . . . . . . 8 |- (u{<.w, v>. | w C. v}u <-> u C. u)
3	1, 2	mtbir 367	. . . . . . 7 |- -. u{<.w, v>. | w C. v}u
4		zornlem 6442	. . . . . . . 8 |- (u{<.w, v>. | w C. v}y <-> u C. y)
5		zornlem 6442	. . . . . . . 8 |- (y{<.w, v>. | w C. v}x <-> y C. x)
6		psstr 2968	. . . . . . . . 9 |- ((u C. y /\ y C. x) -> u C. x)
7		zornlem 6442	. . . . . . . . 9 |- (u{<.w, v>. | w C. v}x <-> u C. x)
8	6, 7	sylibr 264	. . . . . . . 8 |- ((u C. y /\ y C. x) -> u{<.w, v>. | w C. v}x)
9	4, 5, 8	syl2anb 700	. . . . . . 7 |- ((u{<.w, v>. | w C. v}y /\ y{<.w, v>. | w C. v}x) -> u{<.w, v>. | w C. v}x)
10	3, 9	pm3.2i 514	. . . . . 6 |- (-. u{<.w, v>. | w C. v}u /\ ((u{<.w, v>. | w C. v}y /\ y{<.w, v>. | w C. v}x) -> u{<.w, v>. | w C. v}x))
11	10	a1i 8	. . . . 5 |- ((u e. A /\ y e. A /\ x e. A) -> (-. u{<.w, v>. | w C. v}u /\ ((u{<.w, v>. | w C. v}y /\ y{<.w, v>. | w C. v}x) -> u{<.w, v>. | w C. v}x)))
12	11	rgen3 2468	. . . 4 |- A.u e. A A.y e. A A.x e. A (-. u{<.w, v>. | w C. v}u /\ ((u{<.w, v>. | w C. v}y /\ y{<.w, v>. | w C. v}x) -> u{<.w, v>. | w C. v}x))
13		df-po 3784	. . . 4 |- ({<.w, v>. | w C. v} Po A <-> A.u e. A A.y e. A A.x e. A (-. u{<.w, v>. | w C. v}u /\ ((u{<.w, v>. | w C. v}y /\ y{<.w, v>. | w C. v}x) -> u{<.w, v>. | w C. v}x)))
14	12, 13	mpbir 255	. . 3 |- {<.w, v>. | w C. v} Po A
15		df-so 3796	. . . . . . . 8 |- ({<.w, v>. | w C. v} Or z <-> ({<.w, v>. | w C. v} Po z /\ A.x e. z A.y e. z (x{<.w, v>. | w C. v}y \/ x = y \/ y{<.w, v>. | w C. v}x)))
16	15	simprbi 542	. . . . . . 7 |- ({<.w, v>. | w C. v} Or z -> A.x e. z A.y e. z (x{<.w, v>. | w C. v}y \/ x = y \/ y{<.w, v>. | w C. v}x))
17		zornlem 6442	. . . . . . . . . 10 |- (x{<.w, v>. | w C. v}y <-> x C. y)
18		biid 289	. . . . . . . . . 10 |- (x = y <-> x = y)
19	17, 18, 5	3orbi123i 1335	. . . . . . . . 9 |- ((x{<.w, v>. | w C. v}y \/ x = y \/ y{<.w, v>. | w C. v}x) <-> (x C. y \/ x = y \/ y C. x))
20		sspsstri 2966	. . . . . . . . 9 |- ((x C_ y \/ y C_ x) <-> (x C. y \/ x = y \/ y C. x))
21	19, 20	bitr4i 310	. . . . . . . 8 |- ((x{<.w, v>. | w C. v}y \/ x = y \/ y{<.w, v>. | w C. v}x) <-> (x C_ y \/ y C_ x))
22	21	2ralbii 2409	. . . . . . 7 |- (A.x e. z A.y e. z (x{<.w, v>. | w C. v}y \/ x = y \/ y{<.w, v>. | w C. v}x) <-> A.x e. z A.y e. z (x C_ y \/ y C_ x))
23	16, 22	sylib 263	. . . . . 6 |- ({<.w, v>. | w C. v} Or z -> A.x e. z A.y e. z (x C_ y \/ y C_ x))
24	23	anim2i 635	. . . . 5 |- ((z C_ A /\ {<.w, v>. | w C. v} Or z) -> (z C_ A /\ A.x e. z A.y e. z (x C_ y \/ y C_ x)))
25		risset 2425	. . . . . 6 |- (U.z e. A <-> E.x e. A x = U.z)
26		eqimss2 2927	. . . . . . . . 9 |- (x = U.z -> U.z C_ x)
27		unissb 3426	. . . . . . . . 9 |- (U.z C_ x <-> A.u e. z u C_ x)
28	26, 27	sylib 263	. . . . . . . 8 |- (x = U.z -> A.u e. z u C_ x)
29	7	orbi1i 574	. . . . . . . . . 10 |- ((u{<.w, v>. | w C. v}x \/ u = x) <-> (u C. x \/ u = x))
30		sspss 2963	. . . . . . . . . 10 |- (u C_ x <-> (u C. x \/ u = x))
31	29, 30	bitr4i 310	. . . . . . . . 9 |- ((u{<.w, v>. | w C. v}x \/ u = x) <-> u C_ x)
32	31	ralbii 2407	. . . . . . . 8 |- (A.u e. z (u{<.w, v>. | w C. v}x \/ u = x) <-> A.u e. z u C_ x)
33	28, 32	sylibr 264	. . . . . . 7 |- (x = U.z -> A.u e. z (u{<.w, v>. | w C. v}x \/ u = x))
34	33	reximi 2478	. . . . . 6 |- (E.x e. A x = U.z -> E.x e. A A.u e. z (u{<.w, v>. | w C. v}x \/ u = x))
35	25, 34	sylbi 237	. . . . 5 |- (U.z e. A -> E.x e. A A.u e. z (u{<.w, v>. | w C. v}x \/ u = x))
36	24, 35	imim12i 35	. . . 4 |- (((z C_ A /\ A.x e. z A.y e. z (x C_ y \/ y C_ x)) -> U.z e. A) -> ((z C_ A /\ {<.w, v>. | w C. v} Or z) -> E.x e. A A.u e. z (u{<.w, v>. | w C. v}x \/ u = x)))
37	36	alimi 1656	. . 3 |- (A.z((z C_ A /\ A.x e. z A.y e. z (x C_ y \/ y C_ x)) -> U.z e. A) -> A.z((z C_ A /\ {<.w, v>. | w C. v} Or z) -> E.x e. A A.u e. z (u{<.w, v>. | w C. v}x \/ u = x)))
38		zorn2.1	. . . 4 |- A e. _V
39	38	zorn2 6443	. . 3 |- (({<.w, v>. | w C. v} Po A /\ A.z((z C_ A /\ {<.w, v>. | w C. v} Or z) -> E.x e. A A.u e. z (u{<.w, v>. | w C. v}x \/ u = x))) -> E.x e. A A.y e. A -. x{<.w, v>. | w C. v}y)
40	14, 37, 39	sylancr 758	. 2 |- (A.z((z C_ A /\ A.x e. z A.y e. z (x C_ y \/ y C_ x)) -> U.z e. A) -> E.x e. A A.y e. A -. x{<.w, v>. | w C. v}y)
41	17	notbii 362	. . . 4 |- (-. x{<.w, v>. | w C. v}y <-> -. x C. y)
42	41	ralbii 2407	. . 3 |- (A.y e. A -. x{<.w, v>. | w C. v}y <-> A.y e. A -. x C. y)
43	42	rexbii 2408	. 2 |- (E.x e. A A.y e. A -. x{<.w, v>. | w C. v}y <-> E.x e. A A.y e. A -. x C. y)
44	40, 43	sylib 263	1 |- (A.z((z C_ A /\ A.x e. z A.y e. z (x C_ y \/ y C_ x)) -> U.z e. A) -> E.x e. A A.y e. A -. x C. y)

Syntax hints:  -. wn 2   -> wi 3   \/ wo 432   /\ wa 433   \/ w3o 1129   /\ w3a 1130  A.wal 1613   = wceq 1615   e. wcel 1617  A.wral 2385  E.wrex 2386  _Vcvv 2569   C_ wss 2859   C. wpss 2860  U.cuni 3398   class class class wbr 3539  {copab 3597   Po wpo 3782   Or wor 3783

This theorem is referenced by:  infxpidmlem9OLD 9359  alexsublem2 16523  filssufil 16656  zornn0 16849

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 1621  ax-gen 1622  ax-8 1623  ax-9 1624  ax-10 1625  ax-11 1626  ax-12 1627  ax-13 1628  ax-14 1629  ax-17 1634  ax-4 1637  ax-5o 1639  ax-6o 1642  ax-9o 1792  ax-10o 1810  ax-16 1883  ax-11o 1893  ax-ext 2152  ax-rep 3628  ax-sep 3638  ax-nul 3645  ax-pow 3681  ax-pr 3719  ax-un 3961  ax-ac 6385

This theorem depends on definitions:  df-bi 232  df-or 434  df-an 435  df-3or 1131  df-3an 1132  df-ex 1645  df-sb 1845  df-eu 2070  df-mo 2071  df-clab 2158  df-cleq 2163  df-clel 2166  df-ne 2297  df-ral 2389  df-rex 2390  df-reu 2391  df-rab 2392  df-v 2571  df-sbc 2731  df-csb 2806  df-dif 2862  df-un 2864  df-in 2866  df-ss 2868  df-pss 2870  df-nul 3115  df-pw 3261  df-sn 3274  df-pr 3275  df-tp 3277  df-op 3278  df-uni 3399  df-int 3433  df-iun 3470  df-br 3540  df-opab 3598  df-tr 3612  df-eprel 3776  df-id 3779  df-po 3784  df-so 3796  df-fr 3814  df-we 3830  df-ord 3846  df-on 3847  df-suc 3849  df-xp 4165  df-rel 4166  df-cnv 4167  df-co 4168  df-dm 4169  df-rn 4170  df-res 4171  df-ima 4172  df-fun 4173  df-fn 4174  df-f 4175  df-f1 4176  df-fo 4177  df-f1o 4178  df-fv 4179  df-iso 4180  df-en 5631

Copyright terms: Public domain