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

Theorem r1om 8058
Description: The set of hereditarily finite sets is countable. See ackbij2 8057 for an explicit bijection that works without Infinity. See also r1omALT 8585. (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 7532 . . . 4  |-  om  e.  _V
2 limom 4801 . . . 4  |-  Lim  om
3 r1lim 7632 . . . 4  |-  ( ( om  e.  _V  /\  Lim  om )  ->  ( R1 `  om )  = 
U_ a  e.  om  ( R1 `  a ) )
41, 2, 3mp2an 654 . . 3  |-  ( R1
`  om )  =  U_ a  e.  om  ( R1 `  a )
5 r1fnon 7627 . . . 4  |-  R1  Fn  On
6 fnfun 5483 . . . 4  |-  ( R1  Fn  On  ->  Fun  R1 )
7 funiunfv 5935 . . . 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 2408 . 2  |-  ( R1
`  om )  =  U. ( R1 " om )
10 iuneq1 4049 . . . . . . 7  |-  ( e  =  a  ->  U_ f  e.  e  ( {
f }  X.  ~P f )  =  U_ f  e.  a  ( { f }  X.  ~P f ) )
11 sneq 3769 . . . . . . . . 9  |-  ( f  =  b  ->  { f }  =  { b } )
12 pweq 3746 . . . . . . . . 9  |-  ( f  =  b  ->  ~P f  =  ~P b
)
1311, 12xpeq12d 4844 . . . . . . . 8  |-  ( f  =  b  ->  ( { f }  X.  ~P f )  =  ( { b }  X.  ~P b ) )
1413cbviunv 4072 . . . . . . 7  |-  U_ f  e.  a  ( {
f }  X.  ~P f )  =  U_ b  e.  a  ( { b }  X.  ~P b )
1510, 14syl6eq 2436 . . . . . 6  |-  ( e  =  a  ->  U_ f  e.  e  ( {
f }  X.  ~P f )  =  U_ b  e.  a  ( { b }  X.  ~P b ) )
1615fveq2d 5673 . . . . 5  |-  ( e  =  a  ->  ( card `  U_ f  e.  e  ( { f }  X.  ~P f
) )  =  (
card `  U_ b  e.  a  ( { b }  X.  ~P b
) ) )
1716cbvmptv 4242 . . . 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 5011 . . . . . . . 8  |-  ( c  =  a  ->  dom  c  =  dom  a )
1918pweqd 3748 . . . . . . 7  |-  ( c  =  a  ->  ~P dom  c  =  ~P dom  a )
20 imaeq1 5139 . . . . . . . 8  |-  ( c  =  a  ->  (
c " d )  =  ( a "
d ) )
2120fveq2d 5673 . . . . . . 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 4229 . . . . . 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 5140 . . . . . . . 8  |-  ( d  =  b  ->  (
a " d )  =  ( a "
b ) )
2423fveq2d 5673 . . . . . . 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 4242 . . . . . 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 2436 . . . . 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 4242 . . . 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 2388 . . . 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 8057 . . 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 5683 . . . . 5  |-  ( R1
`  om )  e.  _V
319, 30eqeltrri 2459 . . . 4  |-  U. ( R1 " om )  e. 
_V
3231f1oen 7065 . . 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 8 . 2  |-  U. ( R1 " om )  ~~  om
349, 33eqbrtri 4173 1  |-  ( R1
`  om )  ~~  om
Colors of variables: wff set class
Syntax hints:    = wceq 1649    e. wcel 1717   _Vcvv 2900    i^i cin 3263   (/)c0 3572   ~Pcpw 3743   {csn 3758   U.cuni 3958   U_ciun 4036   class class class wbr 4154    e. cmpt 4208   Oncon0 4523   Lim wlim 4524   omcom 4786    X. cxp 4817   dom cdm 4819   "cima 4822   Fun wfun 5389    Fn wfn 5390   -1-1-onto->wf1o 5394   ` cfv 5395   reccrdg 6604    ~~ cen 7043   Fincfn 7046   R1cr1 7622   cardccrd 7756
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-13 1719  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2369  ax-rep 4262  ax-sep 4272  ax-nul 4280  ax-pow 4319  ax-pr 4345  ax-un 4642  ax-inf2 7530
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2243  df-mo 2244  df-clab 2375  df-cleq 2381  df-clel 2384  df-nfc 2513  df-ne 2553  df-ral 2655  df-rex 2656  df-reu 2657  df-rmo 2658  df-rab 2659  df-v 2902  df-sbc 3106  df-csb 3196  df-dif 3267  df-un 3269  df-in 3271  df-ss 3278  df-pss 3280  df-nul 3573  df-if 3684  df-pw 3745  df-sn 3764  df-pr 3765  df-tp 3766  df-op 3767  df-uni 3959  df-int 3994  df-iun 4038  df-br 4155  df-opab 4209  df-mpt 4210  df-tr 4245  df-eprel 4436  df-id 4440  df-po 4445  df-so 4446  df-fr 4483  df-we 4485  df-ord 4526  df-on 4527  df-lim 4528  df-suc 4529  df-om 4787  df-xp 4825  df-rel 4826  df-cnv 4827  df-co 4828  df-dm 4829  df-rn 4830  df-res 4831  df-ima 4832  df-iota 5359  df-fun 5397  df-fn 5398  df-f 5399  df-f1 5400  df-fo 5401  df-f1o 5402  df-fv 5403  df-ov 6024  df-oprab 6025  df-mpt2 6026  df-1st 6289  df-2nd 6290  df-recs 6570  df-rdg 6605  df-1o 6661  df-2o 6662  df-oadd 6665  df-er 6842  df-map 6957  df-en 7047  df-dom 7048  df-sdom 7049  df-fin 7050  df-r1 7624  df-rank 7625  df-card 7760  df-cda 7982
  Copyright terms: Public domain W3C validator