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

Theorem r1om 8155
Description: The set of hereditarily finite sets is countable. See ackbij2 8154 for an explicit bijection that works without Infinity. See also r1omALT 8682. (Contributed by Stefan O'Rear, 18-Nov-2014.)
Assertion
Ref Expression
r1om  |-  ( R1
`  om )  ~~  om

Proof of Theorem r1om
Dummy variables  a 
b  c  d  e  f are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 omex 7627 . . . 4  |-  om  e.  _V
2 limom 4889 . . . 4  |-  Lim  om
3 r1lim 7727 . . . 4  |-  ( ( om  e.  _V  /\  Lim  om )  ->  ( R1 `  om )  = 
U_ a  e.  om  ( R1 `  a ) )
41, 2, 3mp2an 655 . . 3  |-  ( R1
`  om )  =  U_ a  e.  om  ( R1 `  a )
5 r1fnon 7722 . . . 4  |-  R1  Fn  On
6 fnfun 5571 . . . 4  |-  ( R1  Fn  On  ->  Fun  R1 )
7 funiunfv 6024 . . . 4  |-  ( Fun 
R1  ->  U_ a  e.  om  ( R1 `  a )  =  U. ( R1
" om ) )
85, 6, 7mp2b 10 . . 3  |-  U_ a  e.  om  ( R1 `  a )  =  U. ( R1 " om )
94, 8eqtri 2462 . 2  |-  ( R1
`  om )  =  U. ( R1 " om )
10 iuneq1 4130 . . . . . . 7  |-  ( e  =  a  ->  U_ f  e.  e  ( {
f }  X.  ~P f )  =  U_ f  e.  a  ( { f }  X.  ~P f ) )
11 sneq 3849 . . . . . . . . 9  |-  ( f  =  b  ->  { f }  =  { b } )
12 pweq 3826 . . . . . . . . 9  |-  ( f  =  b  ->  ~P f  =  ~P b
)
1311, 12xpeq12d 4932 . . . . . . . 8  |-  ( f  =  b  ->  ( { f }  X.  ~P f )  =  ( { b }  X.  ~P b ) )
1413cbviunv 4154 . . . . . . 7  |-  U_ f  e.  a  ( {
f }  X.  ~P f )  =  U_ b  e.  a  ( { b }  X.  ~P b )
1510, 14syl6eq 2490 . . . . . 6  |-  ( e  =  a  ->  U_ f  e.  e  ( {
f }  X.  ~P f )  =  U_ b  e.  a  ( { b }  X.  ~P b ) )
1615fveq2d 5761 . . . . 5  |-  ( e  =  a  ->  ( card `  U_ f  e.  e  ( { f }  X.  ~P f
) )  =  (
card `  U_ b  e.  a  ( { b }  X.  ~P b
) ) )
1716cbvmptv 4325 . . . 4  |-  ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( { f }  X.  ~P f ) ) )  =  ( a  e.  ( ~P
om  i^i  Fin )  |->  ( card `  U_ b  e.  a  ( {
b }  X.  ~P b ) ) )
18 dmeq 5099 . . . . . . . 8  |-  ( c  =  a  ->  dom  c  =  dom  a )
1918pweqd 3828 . . . . . . 7  |-  ( c  =  a  ->  ~P dom  c  =  ~P dom  a )
20 imaeq1 5227 . . . . . . . 8  |-  ( c  =  a  ->  (
c " d )  =  ( a "
d ) )
2120fveq2d 5761 . . . . . . 7  |-  ( c  =  a  ->  (
( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( c "
d ) )  =  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( a "
d ) ) )
2219, 21mpteq12dv 4312 . . . . . 6  |-  ( c  =  a  ->  (
d  e.  ~P dom  c  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( { f }  X.  ~P f ) ) ) `  (
c " d ) ) )  =  ( d  e.  ~P dom  a  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( { f }  X.  ~P f ) ) ) `  (
a " d ) ) ) )
23 imaeq2 5228 . . . . . . . 8  |-  ( d  =  b  ->  (
a " d )  =  ( a "
b ) )
2423fveq2d 5761 . . . . . . 7  |-  ( d  =  b  ->  (
( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( a "
d ) )  =  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( a "
b ) ) )
2524cbvmptv 4325 . . . . . 6  |-  ( d  e.  ~P dom  a  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( a "
d ) ) )  =  ( b  e. 
~P dom  a  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( a "
b ) ) )
2622, 25syl6eq 2490 . . . . 5  |-  ( c  =  a  ->  (
d  e.  ~P dom  c  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( { f }  X.  ~P f ) ) ) `  (
c " d ) ) )  =  ( b  e.  ~P dom  a  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( { f }  X.  ~P f ) ) ) `  (
a " b ) ) ) )
2726cbvmptv 4325 . . . 4  |-  ( c  e.  _V  |->  ( d  e.  ~P dom  c  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( c "
d ) ) ) )  =  ( a  e.  _V  |->  ( b  e.  ~P dom  a  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( a "
b ) ) ) )
28 eqid 2442 . . . 4  |-  U. ( rec ( ( c  e. 
_V  |->  ( d  e. 
~P dom  c  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( c "
d ) ) ) ) ,  (/) ) " om )  =  U. ( rec ( ( c  e.  _V  |->  ( d  e.  ~P dom  c  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( c "
d ) ) ) ) ,  (/) ) " om )
2917, 27, 28ackbij2 8154 . . 3  |-  U. ( rec ( ( c  e. 
_V  |->  ( d  e. 
~P dom  c  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( c "
d ) ) ) ) ,  (/) ) " om ) : U. ( R1 " om ) -1-1-onto-> om
30 fvex 5771 . . . . 5  |-  ( R1
`  om )  e.  _V
319, 30eqeltrri 2513 . . . 4  |-  U. ( R1 " om )  e. 
_V
3231f1oen 7157 . . 3  |-  ( U. ( rec ( ( c  e.  _V  |->  ( d  e.  ~P dom  c  |->  ( ( e  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ f  e.  e  ( {
f }  X.  ~P f ) ) ) `
 ( c "
d ) ) ) ) ,  (/) ) " om ) : U. ( R1 " om ) -1-1-onto-> om  ->  U. ( R1 " om )  ~~  om )
3329, 32ax-mp 5 . 2  |-  U. ( R1 " om )  ~~  om
349, 33eqbrtri 4256 1  |-  ( R1
`  om )  ~~  om
Colors of variables: wff set class
Syntax hints:    = wceq 1653    e. wcel 1727   _Vcvv 2962    i^i cin 3305   (/)c0 3613   ~Pcpw 3823   {csn 3838   U.cuni 4039   U_ciun 4117   class class class wbr 4237    e. cmpt 4291   Oncon0 4610   Lim wlim 4611   omcom 4874    X. cxp 4905   dom cdm 4907   "cima 4910   Fun wfun 5477    Fn wfn 5478   -1-1-onto->wf1o 5482   ` cfv 5483   reccrdg 6696    ~~ cen 7135   Fincfn 7138   R1cr1 7717   cardccrd 7853
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1556  ax-5 1567  ax-17 1627  ax-9 1668  ax-8 1689  ax-13 1729  ax-14 1731  ax-6 1746  ax-7 1751  ax-11 1763  ax-12 1953  ax-ext 2423  ax-rep 4345  ax-sep 4355  ax-nul 4363  ax-pow 4406  ax-pr 4432  ax-un 4730  ax-inf2 7625
This theorem depends on definitions:  df-bi 179  df-or 361  df-an 362  df-3or 938  df-3an 939  df-tru 1329  df-ex 1552  df-nf 1555  df-sb 1660  df-eu 2291  df-mo 2292  df-clab 2429  df-cleq 2435  df-clel 2438  df-nfc 2567  df-ne 2607  df-ral 2716  df-rex 2717  df-reu 2718  df-rmo 2719  df-rab 2720  df-v 2964  df-sbc 3168  df-csb 3268  df-dif 3309  df-un 3311  df-in 3313  df-ss 3320  df-pss 3322  df-nul 3614  df-if 3764  df-pw 3825  df-sn 3844  df-pr 3845  df-tp 3846  df-op 3847  df-uni 4040  df-int 4075  df-iun 4119  df-br 4238  df-opab 4292  df-mpt 4293  df-tr 4328  df-eprel 4523  df-id 4527  df-po 4532  df-so 4533  df-fr 4570  df-we 4572  df-ord 4613  df-on 4614  df-lim 4615  df-suc 4616  df-om 4875  df-xp 4913  df-rel 4914  df-cnv 4915  df-co 4916  df-dm 4917  df-rn 4918  df-res 4919  df-ima 4920  df-iota 5447  df-fun 5485  df-fn 5486  df-f 5487  df-f1 5488  df-fo 5489  df-f1o 5490  df-fv 5491  df-ov 6113  df-oprab 6114  df-mpt2 6115  df-1st 6378  df-2nd 6379  df-recs 6662  df-rdg 6697  df-1o 6753  df-2o 6754  df-oadd 6757  df-er 6934  df-map 7049  df-en 7139  df-dom 7140  df-sdom 7141  df-fin 7142  df-r1 7719  df-rank 7720  df-card 7857  df-cda 8079
  Copyright terms: Public domain W3C validator