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

Theorem isinf 7219
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 4129 . . . . . 6  |-  ( n  =  (/)  ->  ( x 
~~  n  <->  x  ~~  (/) ) )
21anbi2d 684 . . . . 5  |-  ( n  =  (/)  ->  ( ( x  C_  A  /\  x  ~~  n )  <->  ( x  C_  A  /\  x  ~~  (/) ) ) )
32exbidv 1631 . . . 4  |-  ( n  =  (/)  ->  ( E. x ( x  C_  A  /\  x  ~~  n
)  <->  E. x ( x 
C_  A  /\  x  ~~  (/) ) ) )
4 breq2 4129 . . . . . 6  |-  ( n  =  m  ->  (
x  ~~  n  <->  x  ~~  m ) )
54anbi2d 684 . . . . 5  |-  ( n  =  m  ->  (
( x  C_  A  /\  x  ~~  n )  <-> 
( x  C_  A  /\  x  ~~  m ) ) )
65exbidv 1631 . . . 4  |-  ( n  =  m  ->  ( E. x ( x  C_  A  /\  x  ~~  n
)  <->  E. x ( x 
C_  A  /\  x  ~~  m ) ) )
7 nfv 1624 . . . . 5  |-  F/ y  n  =  suc  m
8 nfvd 1625 . . . . 5  |-  ( n  =  suc  m  ->  F/ y ( x  C_  A  /\  x  ~~  n
) )
9 sseq1 3285 . . . . . . . 8  |-  ( x  =  y  ->  (
x  C_  A  <->  y  C_  A ) )
109adantl 452 . . . . . . 7  |-  ( ( n  =  suc  m  /\  x  =  y
)  ->  ( x  C_  A  <->  y  C_  A
) )
11 breq1 4128 . . . . . . . 8  |-  ( x  =  y  ->  (
x  ~~  n  <->  y  ~~  n ) )
12 breq2 4129 . . . . . . . 8  |-  ( n  =  suc  m  -> 
( y  ~~  n  <->  y 
~~  suc  m )
)
1311, 12sylan9bbr 681 . . . . . . 7  |-  ( ( n  =  suc  m  /\  x  =  y
)  ->  ( x  ~~  n  <->  y  ~~  suc  m ) )
1410, 13anbi12d 691 . . . . . 6  |-  ( ( n  =  suc  m  /\  x  =  y
)  ->  ( (
x  C_  A  /\  x  ~~  n )  <->  ( y  C_  A  /\  y  ~~  suc  m ) ) )
1514ex 423 . . . . 5  |-  ( n  =  suc  m  -> 
( x  =  y  ->  ( ( x 
C_  A  /\  x  ~~  n )  <->  ( y  C_  A  /\  y  ~~  suc  m ) ) ) )
167, 8, 15cbvexd 2022 . . . 4  |-  ( n  =  suc  m  -> 
( E. x ( x  C_  A  /\  x  ~~  n )  <->  E. y
( y  C_  A  /\  y  ~~  suc  m
) ) )
17 0ss 3571 . . . . . 6  |-  (/)  C_  A
18 0ex 4252 . . . . . . 7  |-  (/)  e.  _V
1918enref 7037 . . . . . 6  |-  (/)  ~~  (/)
20 sseq1 3285 . . . . . . . 8  |-  ( x  =  (/)  ->  ( x 
C_  A  <->  (/)  C_  A
) )
21 breq1 4128 . . . . . . . 8  |-  ( x  =  (/)  ->  ( x 
~~  (/)  <->  (/)  ~~  (/) ) )
2220, 21anbi12d 691 . . . . . . 7  |-  ( x  =  (/)  ->  ( ( x  C_  A  /\  x  ~~  (/) )  <->  ( (/)  C_  A  /\  (/)  ~~  (/) ) ) )
2318, 22spcev 2960 . . . . . 6  |-  ( (
(/)  C_  A  /\  (/)  ~~  (/) )  ->  E. x ( x  C_  A  /\  x  ~~  (/) ) )
2417, 19, 23mp2an 653 . . . . 5  |-  E. x
( x  C_  A  /\  x  ~~  (/) )
2524a1i 10 . . . 4  |-  ( -.  A  e.  Fin  ->  E. x ( x  C_  A  /\  x  ~~  (/) ) )
26 ssdif0 3601 . . . . . . . . . . . . 13  |-  ( A 
C_  x  <->  ( A  \  x )  =  (/) )
27 eqss 3280 . . . . . . . . . . . . . . 15  |-  ( x  =  A  <->  ( x  C_  A  /\  A  C_  x ) )
28 breq1 4128 . . . . . . . . . . . . . . . . . . 19  |-  ( x  =  A  ->  (
x  ~~  m  <->  A  ~~  m ) )
2928biimpa 470 . . . . . . . . . . . . . . . . . 18  |-  ( ( x  =  A  /\  x  ~~  m )  ->  A  ~~  m )
30 rspe 2689 . . . . . . . . . . . . . . . . . 18  |-  ( ( m  e.  om  /\  A  ~~  m )  ->  E. m  e.  om  A  ~~  m )
3129, 30sylan2 460 . . . . . . . . . . . . . . . . 17  |-  ( ( m  e.  om  /\  ( x  =  A  /\  x  ~~  m ) )  ->  E. m  e.  om  A  ~~  m
)
32 isfi 7028 . . . . . . . . . . . . . . . . 17  |-  ( A  e.  Fin  <->  E. m  e.  om  A  ~~  m
)
3331, 32sylibr 203 . . . . . . . . . . . . . . . 16  |-  ( ( m  e.  om  /\  ( x  =  A  /\  x  ~~  m ) )  ->  A  e.  Fin )
3433expcom 424 . . . . . . . . . . . . . . 15  |-  ( ( x  =  A  /\  x  ~~  m )  -> 
( m  e.  om  ->  A  e.  Fin )
)
3527, 34sylanbr 459 . . . . . . . . . . . . . 14  |-  ( ( ( x  C_  A  /\  A  C_  x )  /\  x  ~~  m
)  ->  ( m  e.  om  ->  A  e.  Fin ) )
3635ex 423 . . . . . . . . . . . . 13  |-  ( ( x  C_  A  /\  A  C_  x )  -> 
( x  ~~  m  ->  ( m  e.  om  ->  A  e.  Fin )
) )
3726, 36sylan2br 462 . . . . . . . . . . . 12  |-  ( ( x  C_  A  /\  ( A  \  x
)  =  (/) )  -> 
( x  ~~  m  ->  ( m  e.  om  ->  A  e.  Fin )
) )
3837expcom 424 . . . . . . . . . . 11  |-  ( ( A  \  x )  =  (/)  ->  ( x 
C_  A  ->  (
x  ~~  m  ->  ( m  e.  om  ->  A  e.  Fin ) ) ) )
39383impd 1166 . . . . . . . . . 10  |-  ( ( A  \  x )  =  (/)  ->  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  A  e.  Fin ) )
4039com12 27 . . . . . . . . 9  |-  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  (
( A  \  x
)  =  (/)  ->  A  e.  Fin ) )
4140con3d 125 . . . . . . . 8  |-  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  ( -.  A  e.  Fin  ->  -.  ( A  \  x )  =  (/) ) )
42 bren 7014 . . . . . . . . . . 11  |-  ( x 
~~  m  <->  E. f 
f : x -1-1-onto-> m )
43 neq0 3553 . . . . . . . . . . . . . . 15  |-  ( -.  ( A  \  x
)  =  (/)  <->  E. z 
z  e.  ( A 
\  x ) )
44 eldifi 3385 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( z  e.  ( A  \  x )  ->  z  e.  A )
4544snssd 3858 . . . . . . . . . . . . . . . . . . . . 21  |-  ( z  e.  ( A  \  x )  ->  { z }  C_  A )
46 unss 3437 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( x  C_  A  /\  { z }  C_  A
)  <->  ( x  u. 
{ z } ) 
C_  A )
4746biimpi 186 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( x  C_  A  /\  { z }  C_  A
)  ->  ( x  u.  { z } ) 
C_  A )
4845, 47sylan2 460 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( x  C_  A  /\  z  e.  ( A  \  x ) )  -> 
( x  u.  {
z } )  C_  A )
4948ad2ant2r 727 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( x  C_  A  /\  f : x -1-1-onto-> m )  /\  ( z  e.  ( A  \  x
)  /\  m  e.  om ) )  ->  (
x  u.  { z } )  C_  A
)
50 vex 2876 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  z  e. 
_V
51 vex 2876 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  m  e. 
_V
5250, 51f1osn 5619 . . . . . . . . . . . . . . . . . . . . . . 23  |-  { <. z ,  m >. } : { z } -1-1-onto-> { m }
5352jctr 526 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( f : x -1-1-onto-> m  ->  ( f : x -1-1-onto-> m  /\  { <. z ,  m >. } : { z } -1-1-onto-> { m } ) )
54 eldifn 3386 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( z  e.  ( A  \  x )  ->  -.  z  e.  x )
55 disjsn 3783 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( ( x  i^i  { z } )  =  (/)  <->  -.  z  e.  x )
5654, 55sylibr 203 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( z  e.  ( A  \  x )  ->  (
x  i^i  { z } )  =  (/) )
57 nnord 4767 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( m  e.  om  ->  Ord  m )
58 orddisj 4533 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( Ord  m  ->  ( m  i^i  { m } )  =  (/) )
5957, 58syl 15 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( m  e.  om  ->  (
m  i^i  { m } )  =  (/) )
6056, 59anim12i 549 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( z  e.  ( A 
\  x )  /\  m  e.  om )  ->  ( ( x  i^i 
{ z } )  =  (/)  /\  (
m  i^i  { m } )  =  (/) ) )
61 f1oun 5598 . . . . . . . . . . . . . . . . . . . . . 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 } ) )
6253, 60, 61syl2an 463 . . . . . . . . . . . . . . . . . . . . 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 } ) )
63 df-suc 4501 . . . . . . . . . . . . . . . . . . . . . . 23  |-  suc  m  =  ( m  u. 
{ m } )
64 f1oeq3 5571 . . . . . . . . . . . . . . . . . . . . . . 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 } ) ) )
6563, 64ax-mp 8 . . . . . . . . . . . . . . . . . . . . . 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 } ) )
66 vex 2876 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  f  e. 
_V
67 snex 4318 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  { <. z ,  m >. }  e.  _V
6866, 67unex 4621 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( f  u.  { <. z ,  m >. } )  e. 
_V
69 f1oeq1 5569 . . . . . . . . . . . . . . . . . . . . . . . 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 ) )
7068, 69spcev 2960 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( f  u.  { <. z ,  m >. } ) : ( x  u. 
{ z } ) -1-1-onto-> suc  m  ->  E. g 
g : ( x  u.  { z } ) -1-1-onto-> suc  m )
71 bren 7014 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( x  u.  { z } )  ~~  suc  m 
<->  E. g  g : ( x  u.  {
z } ) -1-1-onto-> suc  m
)
7270, 71sylibr 203 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( f  u.  { <. z ,  m >. } ) : ( x  u. 
{ z } ) -1-1-onto-> suc  m  ->  ( x  u.  { z } ) 
~~  suc  m )
7365, 72sylbir 204 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( f  u.  { <. z ,  m >. } ) : ( x  u. 
{ z } ) -1-1-onto-> ( m  u.  { m } )  ->  (
x  u.  { z } )  ~~  suc  m )
7462, 73syl 15 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( f : x -1-1-onto-> m  /\  ( z  e.  ( A  \  x )  /\  m  e.  om ) )  ->  (
x  u.  { z } )  ~~  suc  m )
7574adantll 694 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( x  C_  A  /\  f : x -1-1-onto-> m )  /\  ( z  e.  ( A  \  x
)  /\  m  e.  om ) )  ->  (
x  u.  { z } )  ~~  suc  m )
76 vex 2876 . . . . . . . . . . . . . . . . . . . . 21  |-  x  e. 
_V
77 snex 4318 . . . . . . . . . . . . . . . . . . . . 21  |-  { z }  e.  _V
7876, 77unex 4621 . . . . . . . . . . . . . . . . . . . 20  |-  ( x  u.  { z } )  e.  _V
79 sseq1 3285 . . . . . . . . . . . . . . . . . . . . 21  |-  ( y  =  ( x  u. 
{ z } )  ->  ( y  C_  A 
<->  ( x  u.  {
z } )  C_  A ) )
80 breq1 4128 . . . . . . . . . . . . . . . . . . . . 21  |-  ( y  =  ( x  u. 
{ z } )  ->  ( y  ~~  suc  m  <->  ( x  u. 
{ z } ) 
~~  suc  m )
)
8179, 80anbi12d 691 . . . . . . . . . . . . . . . . . . . 20  |-  ( y  =  ( x  u. 
{ z } )  ->  ( ( y 
C_  A  /\  y  ~~  suc  m )  <->  ( (
x  u.  { z } )  C_  A  /\  ( x  u.  {
z } )  ~~  suc  m ) ) )
8278, 81spcev 2960 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( x  u.  {
z } )  C_  A  /\  ( x  u. 
{ z } ) 
~~  suc  m )  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) )
8349, 75, 82syl2anc 642 . . . . . . . . . . . . . . . . . 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
) )
8483expcom 424 . . . . . . . . . . . . . . . . 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
) ) )
8584ex 423 . . . . . . . . . . . . . . . 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 ) ) ) )
8685exlimiv 1639 . . . . . . . . . . . . . . 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
) ) ) )
8743, 86sylbi 187 . . . . . . . . . . . . . 14  |-  ( -.  ( A  \  x
)  =  (/)  ->  (
m  e.  om  ->  ( ( x  C_  A  /\  f : x -1-1-onto-> m )  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) )
8887com13 74 . . . . . . . . . . . . 13  |-  ( ( x  C_  A  /\  f : x -1-1-onto-> m )  ->  (
m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) )
8988expcom 424 . . . . . . . . . . . 12  |-  ( f : x -1-1-onto-> m  ->  ( x 
C_  A  ->  (
m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) ) )
9089exlimiv 1639 . . . . . . . . . . 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 ) ) ) ) )
9142, 90sylbi 187 . . . . . . . . . 10  |-  ( x 
~~  m  ->  (
x  C_  A  ->  ( m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) ) )
9291com12 27 . . . . . . . . 9  |-  ( x 
C_  A  ->  (
x  ~~  m  ->  ( m  e.  om  ->  ( -.  ( A  \  x )  =  (/)  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) ) )
93923imp 1146 . . . . . . . 8  |-  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  ( -.  ( A  \  x
)  =  (/)  ->  E. y
( y  C_  A  /\  y  ~~  suc  m
) ) )
9441, 93syld 40 . . . . . . 7  |-  ( ( x  C_  A  /\  x  ~~  m  /\  m  e.  om )  ->  ( -.  A  e.  Fin  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) )
95943expia 1154 . . . . . 6  |-  ( ( x  C_  A  /\  x  ~~  m )  -> 
( m  e.  om  ->  ( -.  A  e. 
Fin  ->  E. y ( y 
C_  A  /\  y  ~~  suc  m ) ) ) )
9695exlimiv 1639 . . . . 5  |-  ( E. x ( x  C_  A  /\  x  ~~  m
)  ->  ( m  e.  om  ->  ( -.  A  e.  Fin  ->  E. y
( y  C_  A  /\  y  ~~  suc  m
) ) ) )
9796com3l 75 . . . 4  |-  ( m  e.  om  ->  ( -.  A  e.  Fin  ->  ( E. x ( x  C_  A  /\  x  ~~  m )  ->  E. y ( y  C_  A  /\  y  ~~  suc  m ) ) ) )
983, 6, 16, 25, 97finds2 4787 . . 3  |-  ( n  e.  om  ->  ( -.  A  e.  Fin  ->  E. x ( x 
C_  A  /\  x  ~~  n ) ) )
9998com12 27 . 2  |-  ( -.  A  e.  Fin  ->  ( n  e.  om  ->  E. x ( x  C_  A  /\  x  ~~  n
) ) )
10099ralrimiv 2710 1  |-  ( -.  A  e.  Fin  ->  A. n  e.  om  E. x ( x  C_  A  /\  x  ~~  n
) )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 176    /\ wa 358    /\ w3a 935   E.wex 1546    = wceq 1647    e. wcel 1715   A.wral 2628   E.wrex 2629    \ cdif 3235    u. cun 3236    i^i cin 3237    C_ wss 3238   (/)c0 3543   {csn 3729   <.cop 3732   class class class wbr 4125   Ord word 4494   suc csuc 4497   omcom 4759   -1-1-onto->wf1o 5357    ~~ cen 7003   Fincfn 7006
This theorem is referenced by:  fineqvlem  7220  isinffi  7772  domtriomlem  8215  ishashinf  23562
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1551  ax-5 1562  ax-17 1621  ax-9 1659  ax-8 1680  ax-13 1717  ax-14 1719  ax-6 1734  ax-7 1739  ax-11 1751  ax-12 1937  ax-ext 2347  ax-sep 4243  ax-nul 4251  ax-pow 4290  ax-pr 4316  ax-un 4615
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 936  df-3an 937  df-tru 1324  df-ex 1547  df-nf 1550  df-sb 1654  df-eu 2221  df-mo 2222  df-clab 2353  df-cleq 2359  df-clel 2362  df-nfc 2491  df-ne 2531  df-ral 2633  df-rex 2634  df-rab 2637  df-v 2875  df-sbc 3078  df-dif 3241  df-un 3243  df-in 3245  df-ss 3252  df-pss 3254  df-nul 3544  df-if 3655  df-pw 3716  df-sn 3735  df-pr 3736  df-tp 3737  df-op 3738  df-uni 3930  df-br 4126  df-opab 4180  df-tr 4216  df-eprel 4408  df-id 4412  df-po 4417  df-so 4418  df-fr 4455  df-we 4457  df-ord 4498  df-on 4499  df-lim 4500  df-suc 4501  df-om 4760  df-xp 4798  df-rel 4799  df-cnv 4800  df-co 4801  df-dm 4802  df-rn 4803  df-res 4804  df-ima 4805  df-fun 5360  df-fn 5361  df-f 5362  df-f1 5363  df-fo 5364  df-f1o 5365  df-en 7007  df-fin 7010
  Copyright terms: Public domain W3C validator