Theorem isinf 7811

Description: Any set that is not finite is literally infinite, in the sense that it contains subsets of arbitrarily large finite cardinality. (It cannot be proven that the set has countably infinite subsets unless AC is invoked.) The proof does not require the Axiom of Infinity. (Contributed by Mario Carneiro, 15-Jan-2013.)

Assertion

Ref	Expression
isinf	|- ( -. A e. Fin -> A. n e. om E. x ( x C_ A /\ x ~~ n ) )

Distinct variable group:   x, A, n

Proof of Theorem isinf

Dummy variables f m y z g are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		breq2 4420	. . . . . 6 |- ( n = (/) -> ( x ~~ n <-> x ~~ (/) ) )
2	1	anbi2d 715	. . . . 5 |- ( n = (/) -> ( ( x C_ A /\ x ~~ n ) <-> ( x C_ A /\ x ~~ (/) ) ) )
3	2	exbidv 1779	. . . 4 |- ( n = (/) -> ( E. x ( x C_ A /\ x ~~ n ) <-> E. x ( x C_ A /\ x ~~ (/) ) ) )
4		breq2 4420	. . . . . 6 |- ( n = m -> ( x ~~ n <-> x ~~ m ) )
5	4	anbi2d 715	. . . . 5 |- ( n = m -> ( ( x C_ A /\ x ~~ n ) <-> ( x C_ A /\ x ~~ m ) ) )
6	5	exbidv 1779	. . . 4 |- ( n = m -> ( E. x ( x C_ A /\ x ~~ n ) <-> E. x ( x C_ A /\ x ~~ m ) ) )
7		sseq1 3465	. . . . . . 7 |- ( x = y -> ( x C_ A <-> y C_ A ) )
8	7	adantl 472	. . . . . 6 |- ( ( n = suc m /\ x = y ) -> ( x C_ A <-> y C_ A ) )
9		breq1 4419	. . . . . . 7 |- ( x = y -> ( x ~~ n <-> y ~~ n ) )
10		breq2 4420	. . . . . . 7 |- ( n = suc m -> ( y ~~ n <-> y ~~ suc m ) )
11	9, 10	sylan9bbr 712	. . . . . 6 |- ( ( n = suc m /\ x = y ) -> ( x ~~ n <-> y ~~ suc m ) )
12	8, 11	anbi12d 722	. . . . 5 |- ( ( n = suc m /\ x = y ) -> ( ( x C_ A /\ x ~~ n ) <-> ( y C_ A /\ y ~~ suc m ) ) )
13	12	cbvexdva 2136	. . . 4 |- ( n = suc m -> ( E. x ( x C_ A /\ x ~~ n ) <-> E. y ( y C_ A /\ y ~~ suc m ) ) )
14		0ss 3775	. . . . . 6 |- (/) C_ A
15		0ex 4549	. . . . . . 7 |- (/) e. _V
16	15	enref 7628	. . . . . 6 |- (/) ~~ (/)
17		sseq1 3465	. . . . . . . 8 |- ( x = (/) -> ( x C_ A <-> (/) C_ A ) )
18		breq1 4419	. . . . . . . 8 |- ( x = (/) -> ( x ~~ (/) <-> (/) ~~ (/) ) )
19	17, 18	anbi12d 722	. . . . . . 7 |- ( x = (/) -> ( ( x C_ A /\ x ~~ (/) ) <-> ( (/) C_ A /\ (/) ~~ (/) ) ) )
20	15, 19	spcev 3153	. . . . . 6 |- ( ( (/) C_ A /\ (/) ~~ (/) ) -> E. x ( x C_ A /\ x ~~ (/) ) )
21	14, 16, 20	mp2an 683	. . . . 5 |- E. x ( x C_ A /\ x ~~ (/) )
22	21	a1i 11	. . . 4 |- ( -. A e. Fin -> E. x ( x C_ A /\ x ~~ (/) ) )
23		ssdif0 3835	. . . . . . . . . . . . 13 |- ( A C_ x <-> ( A \ x ) = (/) )
24		eqss 3459	. . . . . . . . . . . . . . 15 |- ( x = A <-> ( x C_ A /\ A C_ x ) )
25		breq1 4419	. . . . . . . . . . . . . . . . . . 19 |- ( x = A -> ( x ~~ m <-> A ~~ m ) )
26	25	biimpa 491	. . . . . . . . . . . . . . . . . 18 |- ( ( x = A /\ x ~~ m ) -> A ~~ m )
27		rspe 2857	. . . . . . . . . . . . . . . . . 18 |- ( ( m e. om /\ A ~~ m ) -> E. m e. om A ~~ m )
28	26, 27	sylan2 481	. . . . . . . . . . . . . . . . 17 |- ( ( m e. om /\ ( x = A /\ x ~~ m ) ) -> E. m e. om A ~~ m )
29		isfi 7619	. . . . . . . . . . . . . . . . 17 |- ( A e. Fin <-> E. m e. om A ~~ m )
30	28, 29	sylibr 217	. . . . . . . . . . . . . . . 16 |- ( ( m e. om /\ ( x = A /\ x ~~ m ) ) -> A e. Fin )
31	30	expcom 441	. . . . . . . . . . . . . . 15 |- ( ( x = A /\ x ~~ m ) -> ( m e. om -> A e. Fin ) )
32	24, 31	sylanbr 480	. . . . . . . . . . . . . 14 |- ( ( ( x C_ A /\ A C_ x ) /\ x ~~ m ) -> ( m e. om -> A e. Fin ) )
33	32	ex 440	. . . . . . . . . . . . 13 |- ( ( x C_ A /\ A C_ x ) -> ( x ~~ m -> ( m e. om -> A e. Fin ) ) )
34	23, 33	sylan2br 483	. . . . . . . . . . . 12 |- ( ( x C_ A /\ ( A \ x ) = (/) ) -> ( x ~~ m -> ( m e. om -> A e. Fin ) ) )
35	34	expcom 441	. . . . . . . . . . 11 |- ( ( A \ x ) = (/) -> ( x C_ A -> ( x ~~ m -> ( m e. om -> A e. Fin ) ) ) )
36	35	3impd 1231	. . . . . . . . . 10 |- ( ( A \ x ) = (/) -> ( ( x C_ A /\ x ~~ m /\ m e. om ) -> A e. Fin ) )
37	36	com12 32	. . . . . . . . 9 |- ( ( x C_ A /\ x ~~ m /\ m e. om ) -> ( ( A \ x ) = (/) -> A e. Fin ) )
38	37	con3d 140	. . . . . . . 8 |- ( ( x C_ A /\ x ~~ m /\ m e. om ) -> ( -. A e. Fin -> -. ( A \ x ) = (/) ) )
39		bren 7604	. . . . . . . . . . 11 |- ( x ~~ m <-> E. f f : x -1-1-onto-> m )
40		neq0 3754	. . . . . . . . . . . . . . 15 |- ( -. ( A \ x ) = (/) <-> E. z z e. ( A \ x ) )
41		eldifi 3567	. . . . . . . . . . . . . . . . . . . . . 22 |- ( z e. ( A \ x ) -> z e. A )
42	41	snssd 4130	. . . . . . . . . . . . . . . . . . . . 21 |- ( z e. ( A \ x ) -> { z } C_ A )
43		unss 3620	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( x C_ A /\ { z } C_ A ) <-> ( x u. { z } ) C_ A )
44	43	biimpi 199	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( x C_ A /\ { z } C_ A ) -> ( x u. { z } ) C_ A )
45	42, 44	sylan2 481	. . . . . . . . . . . . . . . . . . . 20 |- ( ( x C_ A /\ z e. ( A \ x ) ) -> ( x u. { z } ) C_ A )
46	45	ad2ant2r 758	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( x C_ A /\ f : x -1-1-onto-> m ) /\ ( z e. ( A \ x ) /\ m e. om ) ) -> ( x u. { z } ) C_ A )
47		vex 3060	. . . . . . . . . . . . . . . . . . . . . . . 24 |- z e. _V
48		vex 3060	. . . . . . . . . . . . . . . . . . . . . . . 24 |- m e. _V
49	47, 48	f1osn 5875	. . . . . . . . . . . . . . . . . . . . . . 23 |- { <. z , m >. } : { z } -1-1-onto-> { m }
50	49	jctr 549	. . . . . . . . . . . . . . . . . . . . . 22 |- ( f : x -1-1-onto-> m -> ( f : x -1-1-onto-> m /\ { <. z , m >. } : { z } -1-1-onto-> { m } ) )
51		eldifn 3568	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( z e. ( A \ x ) -> -. z e. x )
52		disjsn 4044	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( ( x i^i { z } ) = (/) <-> -. z e. x )
53	51, 52	sylibr 217	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( z e. ( A \ x ) -> ( x i^i { z } ) = (/) )
54		nnord 6727	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( m e. om -> Ord m )
55		orddisj 5480	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( Ord m -> ( m i^i { m } ) = (/) )
56	54, 55	syl 17	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( m e. om -> ( m i^i { m } ) = (/) )
57	53, 56	anim12i 574	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( z e. ( A \ x ) /\ m e. om ) -> ( ( x i^i { z } ) = (/) /\ ( m i^i { m } ) = (/) ) )
58		f1oun 5856	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( ( f : x -1-1-onto-> m /\ { <. z , m >. } : { z } -1-1-onto-> { m } ) /\ ( ( x i^i { z } ) = (/) /\ ( m i^i { m } ) = (/) ) ) -> ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> ( m u. { m } ) )
59	50, 57, 58	syl2an 484	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( f : x -1-1-onto-> m /\ ( z e. ( A \ x ) /\ m e. om ) ) -> ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> ( m u. { m } ) )
60		df-suc 5448	. . . . . . . . . . . . . . . . . . . . . . 23 |- suc m = ( m u. { m } )
61		f1oeq3 5830	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( suc m = ( m u. { m } ) -> ( ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> suc m <-> ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> ( m u. { m } ) ) )
62	60, 61	ax-mp 5	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> suc m <-> ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> ( m u. { m } ) )
63		vex 3060	. . . . . . . . . . . . . . . . . . . . . . . . 25 |- f e. _V
64		snex 4655	. . . . . . . . . . . . . . . . . . . . . . . . 25 |- { <. z , m >. } e. _V
65	63, 64	unex 6616	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( f u. { <. z , m >. } ) e. _V
66		f1oeq1 5828	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( g = ( f u. { <. z , m >. } ) -> ( g : ( x u. { z } ) -1-1-onto-> suc m <-> ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> suc m ) )
67	65, 66	spcev 3153	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> suc m -> E. g g : ( x u. { z } ) -1-1-onto-> suc m )
68		bren 7604	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( x u. { z } ) ~~ suc m <-> E. g g : ( x u. { z } ) -1-1-onto-> suc m )
69	67, 68	sylibr 217	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> suc m -> ( x u. { z } ) ~~ suc m )
70	62, 69	sylbir 218	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( f u. { <. z , m >. } ) : ( x u. { z } ) -1-1-onto-> ( m u. { m } ) -> ( x u. { z } ) ~~ suc m )
71	59, 70	syl 17	. . . . . . . . . . . . . . . . . . . 20 |- ( ( f : x -1-1-onto-> m /\ ( z e. ( A \ x ) /\ m e. om ) ) -> ( x u. { z } ) ~~ suc m )
72	71	adantll 725	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( x C_ A /\ f : x -1-1-onto-> m ) /\ ( z e. ( A \ x ) /\ m e. om ) ) -> ( x u. { z } ) ~~ suc m )
73		vex 3060	. . . . . . . . . . . . . . . . . . . . 21 |- x e. _V
74		snex 4655	. . . . . . . . . . . . . . . . . . . . 21 |- { z } e. _V
75	73, 74	unex 6616	. . . . . . . . . . . . . . . . . . . 20 |- ( x u. { z } ) e. _V
76		sseq1 3465	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( x u. { z } ) -> ( y C_ A <-> ( x u. { z } ) C_ A ) )
77		breq1 4419	. . . . . . . . . . . . . . . . . . . . 21 |- ( y = ( x u. { z } ) -> ( y ~~ suc m <-> ( x u. { z } ) ~~ suc m ) )
78	76, 77	anbi12d 722	. . . . . . . . . . . . . . . . . . . 20 |- ( y = ( x u. { z } ) -> ( ( y C_ A /\ y ~~ suc m ) <-> ( ( x u. { z } ) C_ A /\ ( x u. { z } ) ~~ suc m ) ) )
79	75, 78	spcev 3153	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( x u. { z } ) C_ A /\ ( x u. { z } ) ~~ suc m ) -> E. y ( y C_ A /\ y ~~ suc m ) )
80	46, 72, 79	syl2anc 671	. . . . . . . . . . . . . . . . . 18 |- ( ( ( x C_ A /\ f : x -1-1-onto-> m ) /\ ( z e. ( A \ x ) /\ m e. om ) ) -> E. y ( y C_ A /\ y ~~ suc m ) )
81	80	expcom 441	. . . . . . . . . . . . . . . . 17 |- ( ( z e. ( A \ x ) /\ m e. om ) -> ( ( x C_ A /\ f : x -1-1-onto-> m ) -> E. y ( y C_ A /\ y ~~ suc m ) ) )
82	81	ex 440	. . . . . . . . . . . . . . . 16 |- ( z e. ( A \ x ) -> ( m e. om -> ( ( x C_ A /\ f : x -1-1-onto-> m ) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) )
83	82	exlimiv 1787	. . . . . . . . . . . . . . 15 |- ( E. z z e. ( A \ x ) -> ( m e. om -> ( ( x C_ A /\ f : x -1-1-onto-> m ) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) )
84	40, 83	sylbi 200	. . . . . . . . . . . . . 14 |- ( -. ( A \ x ) = (/) -> ( m e. om -> ( ( x C_ A /\ f : x -1-1-onto-> m ) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) )
85	84	com13 83	. . . . . . . . . . . . 13 |- ( ( x C_ A /\ f : x -1-1-onto-> m ) -> ( m e. om -> ( -. ( A \ x ) = (/) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) )
86	85	expcom 441	. . . . . . . . . . . 12 |- ( f : x -1-1-onto-> m -> ( x C_ A -> ( m e. om -> ( -. ( A \ x ) = (/) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) ) )
87	86	exlimiv 1787	. . . . . . . . . . 11 |- ( E. f f : x -1-1-onto-> m -> ( x C_ A -> ( m e. om -> ( -. ( A \ x ) = (/) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) ) )
88	39, 87	sylbi 200	. . . . . . . . . 10 |- ( x ~~ m -> ( x C_ A -> ( m e. om -> ( -. ( A \ x ) = (/) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) ) )
89	88	com12 32	. . . . . . . . 9 |- ( x C_ A -> ( x ~~ m -> ( m e. om -> ( -. ( A \ x ) = (/) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) ) )
90	89	3imp 1208	. . . . . . . 8 |- ( ( x C_ A /\ x ~~ m /\ m e. om ) -> ( -. ( A \ x ) = (/) -> E. y ( y C_ A /\ y ~~ suc m ) ) )
91	38, 90	syld 45	. . . . . . 7 |- ( ( x C_ A /\ x ~~ m /\ m e. om ) -> ( -. A e. Fin -> E. y ( y C_ A /\ y ~~ suc m ) ) )
92	91	3expia 1217	. . . . . 6 |- ( ( x C_ A /\ x ~~ m ) -> ( m e. om -> ( -. A e. Fin -> E. y ( y C_ A /\ y ~~ suc m ) ) ) )
93	92	exlimiv 1787	. . . . 5 |- ( E. x ( x C_ A /\ x ~~ m ) -> ( m e. om -> ( -. A e. Fin -> E. y ( y C_ A /\ y ~~ suc m ) ) ) )
94	93	com3l 84	. . . 4 |- ( m e. om -> ( -. A e. Fin -> ( E. x ( x C_ A /\ x ~~ m ) -> E. y ( y C_ A /\ y ~~ suc m ) ) ) )
95	3, 6, 13, 22, 94	finds2 6748	. . 3 |- ( n e. om -> ( -. A e. Fin -> E. x ( x C_ A /\ x ~~ n ) ) )
96	95	com12 32	. 2 |- ( -. A e. Fin -> ( n e. om -> E. x ( x C_ A /\ x ~~ n ) ) )
97	96	ralrimiv 2812	1 |- ( -. A e. Fin -> A. n e. om E. x ( x C_ A /\ x ~~ n ) )

Syntax hints:   -. wn 3   -> wi 4   <-> wb 189   /\ wa 375   /\ w3a 991   = wceq 1455   E.wex 1674   e. wcel 1898   A.wral 2749   E.wrex 2750   \ cdif 3413   u. cun 3414   i^i cin 3415   C_ wss 3416   (/)c0 3743   {csn 3980   <.cop 3986   class class class wbr 4416   Ord word 5441   suc csuc 5444   -1-1-onto->wf1o 5600   omcom 6719   ~~ cen 7592   Fincfn 7595

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1680  ax-4 1693  ax-5 1769  ax-6 1816  ax-7 1862  ax-8 1900  ax-9 1907  ax-10 1926  ax-11 1931  ax-12 1944  ax-13 2102  ax-ext 2442  ax-sep 4539  ax-nul 4548  ax-pow 4595  ax-pr 4653  ax-un 6610

This theorem depends on definitions:  df-bi 190  df-or 376  df-an 377  df-3or 992  df-3an 993  df-tru 1458  df-ex 1675  df-nf 1679  df-sb 1809  df-eu 2314  df-mo 2315  df-clab 2449  df-cleq 2455  df-clel 2458  df-nfc 2592  df-ne 2635  df-ral 2754  df-rex 2755  df-rab 2758  df-v 3059  df-sbc 3280  df-dif 3419  df-un 3421  df-in 3423  df-ss 3430  df-pss 3432  df-nul 3744  df-if 3894  df-pw 3965  df-sn 3981  df-pr 3983  df-tp 3985  df-op 3987  df-uni 4213  df-br 4417  df-opab 4476  df-tr 4512  df-eprel 4764  df-id 4768  df-po 4774  df-so 4775  df-fr 4812  df-we 4814  df-xp 4859  df-rel 4860  df-cnv 4861  df-co 4862  df-dm 4863  df-rn 4864  df-res 4865  df-ima 4866  df-ord 5445  df-on 5446  df-lim 5447  df-suc 5448  df-fun 5603  df-fn 5604  df-f 5605  df-f1 5606  df-fo 5607  df-f1o 5608  df-om 6720  df-en 7596  df-fin 7599

This theorem is referenced by:  fineqvlem  7812  isinffi  8452  domtriomlem  8898  ishashinf  12659