MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  isinf Structured version   Visualization version   Unicode version

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.
StepHypRef Expression
1 breq2 4420 . . . . . 6  |-  ( n  =  (/)  ->  ( x 
~~  n  <->  x  ~~  (/) ) )
21anbi2d 715 . . . . 5  |-  ( n  =  (/)  ->  ( ( x  C_  A  /\  x  ~~  n )  <->  ( x  C_  A  /\  x  ~~  (/) ) ) )
32exbidv 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 ) )
54anbi2d 715 . . . . 5  |-  ( n  =  m  ->  (
( x  C_  A  /\  x  ~~  n )  <-> 
( x  C_  A  /\  x  ~~  m ) ) )
65exbidv 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 ) )
87adantl 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 )
)
119, 10sylan9bbr 712 . . . . . 6  |-  ( ( n  =  suc  m  /\  x  =  y
)  ->  ( x  ~~  n  <->  y  ~~  suc  m ) )
128, 11anbi12d 722 . . . . 5  |-  ( ( n  =  suc  m  /\  x  =  y
)  ->  ( (
x  C_  A  /\  x  ~~  n )  <->  ( y  C_  A  /\  y  ~~  suc  m ) ) )
1312cbvexdva 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
1615enref 7628 . . . . . 6  |-  (/)  ~~  (/)
17 sseq1 3465 . . . . . . . 8  |-  ( x  =  (/)  ->  ( x 
C_  A  <->  (/)  C_  A
) )
18 breq1 4419 . . . . . . . 8  |-  ( x  =  (/)  ->  ( x 
~~  (/)  <->  (/)  ~~  (/) ) )
1917, 18anbi12d 722 . . . . . . 7  |-  ( x  =  (/)  ->  ( ( x  C_  A  /\  x  ~~  (/) )  <->  ( (/)  C_  A  /\  (/)  ~~  (/) ) ) )
2015, 19spcev 3153 . . . . . 6  |-  ( (
(/)  C_  A  /\  (/)  ~~  (/) )  ->  E. x ( x  C_  A  /\  x  ~~  (/) ) )
2114, 16, 20mp2an 683 . . . . 5  |-  E. x
( x  C_  A  /\  x  ~~  (/) )
2221a1i 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 ) )
2625biimpa 491 . . . . . . . . . . . . . . . . . 18  |-  ( ( x  =  A  /\  x  ~~  m )  ->  A  ~~  m )
27 rspe 2857 . . . . . . . . . . . . . . . . . 18  |-  ( ( m  e.  om  /\  A  ~~  m )  ->  E. m  e.  om  A  ~~  m )
2826, 27sylan2 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
)
3028, 29sylibr 217 . . . . . . . . . . . . . . . 16  |-  ( ( m  e.  om  /\  ( x  =  A  /\  x  ~~  m ) )  ->  A  e.  Fin )
3130expcom 441 . . . . . . . . . . . . . . 15  |-  ( ( x  =  A  /\  x  ~~  m )  -> 
( m  e.  om  ->  A  e.  Fin )
)
3224, 31sylanbr 480 . . . . . . . . . . . . . 14  |-  ( ( ( x  C_  A  /\  A  C_  x )  /\  x  ~~  m
)  ->  ( m  e.  om  ->  A  e.  Fin ) )
3332ex 440 . . . . . . . . . . . . 13  |-  ( ( x  C_  A  /\  A  C_  x )  -> 
( x  ~~  m  ->  ( m  e.  om  ->  A  e.  Fin )
) )
3423, 33sylan2br 483 . . . . . . . . . . . 12  |-  ( ( x  C_  A  /\  ( A  \  x
)  =  (/) )  -> 
( x  ~~  m  ->  ( m  e.  om  ->  A  e.  Fin )
) )
3534expcom 441 . . . . . . . . . . 11  |-  ( ( A  \  x )  =  (/)  ->  ( x 
C_  A  ->  (
x  ~~  m  ->  ( m  e.  om  ->  A  e.  Fin ) ) ) )
36353impd 1231 . . . . . . . . . 10  |-  ( ( A  \  x )  =  (/)  ->  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  A  e.  Fin ) )
3736com12 32 . . . . . . . . 9  |-  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  (
( A  \  x
)  =  (/)  ->  A  e.  Fin ) )
3837con3d 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 )
4241snssd 4130 . . . . . . . . . . . . . . . . . . . . 21  |-  ( z  e.  ( A  \  x )  ->  { z }  C_  A )
43 unss 3620 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( x  C_  A  /\  { z }  C_  A
)  <->  ( x  u. 
{ z } ) 
C_  A )
4443biimpi 199 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( x  C_  A  /\  { z }  C_  A
)  ->  ( x  u.  { z } ) 
C_  A )
4542, 44sylan2 481 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( x  C_  A  /\  z  e.  ( A  \  x ) )  -> 
( x  u.  {
z } )  C_  A )
4645ad2ant2r 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
4947, 48f1osn 5875 . . . . . . . . . . . . . . . . . . . . . . 23  |-  { <. z ,  m >. } : { z } -1-1-onto-> { m }
5049jctr 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 )
5351, 52sylibr 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 } )  =  (/) )
5654, 55syl 17 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( m  e.  om  ->  (
m  i^i  { m } )  =  (/) )
5753, 56anim12i 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 } ) )
5950, 57, 58syl2an 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 } ) ) )
6260, 61ax-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
6563, 64unex 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 ) )
6765, 66spcev 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
)
6967, 68sylibr 217 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( f  u.  { <. z ,  m >. } ) : ( x  u. 
{ z } ) -1-1-onto-> suc  m  ->  ( x  u.  { z } ) 
~~  suc  m )
7062, 69sylbir 218 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( f  u.  { <. z ,  m >. } ) : ( x  u. 
{ z } ) -1-1-onto-> ( m  u.  { m } )  ->  (
x  u.  { z } )  ~~  suc  m )
7159, 70syl 17 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( f : x -1-1-onto-> m  /\  ( z  e.  ( A  \  x )  /\  m  e.  om ) )  ->  (
x  u.  { z } )  ~~  suc  m )
7271adantll 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
7573, 74unex 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 )
)
7876, 77anbi12d 722 . . . . . . . . . . . . . . . . . . . 20  |-  ( y  =  ( x  u. 
{ z } )  ->  ( ( y 
C_  A  /\  y  ~~  suc  m )  <->  ( (
x  u.  { z } )  C_  A  /\  ( x  u.  {
z } )  ~~  suc  m ) ) )
7975, 78spcev 3153 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( x  u.  {
z } )  C_  A  /\  ( x  u. 
{ z } ) 
~~  suc  m )  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) )
8046, 72, 79syl2anc 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
) )
8180expcom 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
) ) )
8281ex 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 ) ) ) )
8382exlimiv 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
) ) ) )
8440, 83sylbi 200 . . . . . . . . . . . . . 14  |-  ( -.  ( A  \  x
)  =  (/)  ->  (
m  e.  om  ->  ( ( x  C_  A  /\  f : x -1-1-onto-> m )  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) )
8584com13 83 . . . . . . . . . . . . 13  |-  ( ( x  C_  A  /\  f : x -1-1-onto-> m )  ->  (
m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) )
8685expcom 441 . . . . . . . . . . . 12  |-  ( f : x -1-1-onto-> m  ->  ( x 
C_  A  ->  (
m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) ) )
8786exlimiv 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 ) ) ) ) )
8839, 87sylbi 200 . . . . . . . . . 10  |-  ( x 
~~  m  ->  (
x  C_  A  ->  ( m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) ) )
8988com12 32 . . . . . . . . 9  |-  ( x 
C_  A  ->  (
x  ~~  m  ->  ( m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) ) )
90893imp 1208 . . . . . . . 8  |-  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  ( -.  ( A  \  x
)  =  (/)  ->  E. y
( y  C_  A  /\  y  ~~  suc  m
) ) )
9138, 90syld 45 . . . . . . 7  |-  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  ( -.  A  e.  Fin  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) )
92913expia 1217 . . . . . 6  |-  ( ( x  C_  A  /\  x  ~~  m )  -> 
( m  e.  om  ->  ( -.  A  e. 
Fin  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) )
9392exlimiv 1787 . . . . 5  |-  ( E. x ( x  C_  A  /\  x  ~~  m
)  ->  ( m  e.  om  ->  ( -.  A  e.  Fin  ->  E. y
( y  C_  A  /\  y  ~~  suc  m
) ) ) )
9493com3l 84 . . . 4  |-  ( m  e.  om  ->  ( -.  A  e.  Fin  ->  ( E. x ( x  C_  A  /\  x  ~~  m )  ->  E. y ( y  C_  A  /\  y  ~~  suc  m ) ) ) )
953, 6, 13, 22, 94finds2 6748 . . 3  |-  ( n  e.  om  ->  ( -.  A  e.  Fin  ->  E. x ( x 
C_  A  /\  x  ~~  n ) ) )
9695com12 32 . 2  |-  ( -.  A  e.  Fin  ->  ( n  e.  om  ->  E. x ( x  C_  A  /\  x  ~~  n
) ) )
9796ralrimiv 2812 1  |-  ( -.  A  e.  Fin  ->  A. n  e.  om  E. x ( x  C_  A  /\  x  ~~  n
) )
Colors of variables: wff setvar class
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
  Copyright terms: Public domain W3C validator