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

Theorem ackbij2 8056
Description: The Ackermann bijection, part 2: hereditarily finite sets can be represented by recursive binary notation. (Contributed by Stefan O'Rear, 18-Nov-2014.)
Hypotheses
Ref Expression
ackbij.f  |-  F  =  ( x  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ y  e.  x  ( {
y }  X.  ~P y ) ) )
ackbij.g  |-  G  =  ( x  e.  _V  |->  ( y  e.  ~P dom  x  |->  ( F `  ( x " y
) ) ) )
ackbij.h  |-  H  = 
U. ( rec ( G ,  (/) ) " om )
Assertion
Ref Expression
ackbij2  |-  H : U. ( R1 " om )
-1-1-onto-> om
Distinct variable groups:    x, F, y    x, G, y    x, H, y

Proof of Theorem ackbij2
Dummy variables  a 
b  c are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fveq2 5668 . . . . . 6  |-  ( a  =  b  ->  ( rec ( G ,  (/) ) `  a )  =  ( rec ( G ,  (/) ) `  b ) )
2 fvex 5682 . . . . . 6  |-  ( rec ( G ,  (/) ) `  a )  e.  _V
31, 2fun11iun 5635 . . . . 5  |-  ( A. a  e.  om  (
( rec ( G ,  (/) ) `  a
) : ( R1
`  a ) -1-1-> om  /\ 
A. b  e.  om  ( ( rec ( G ,  (/) ) `  a )  C_  ( rec ( G ,  (/) ) `  b )  \/  ( rec ( G ,  (/) ) `  b
)  C_  ( rec ( G ,  (/) ) `  a ) ) )  ->  U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U_ a  e. 
om  ( R1 `  a ) -1-1-> om )
4 ackbij.f . . . . . . . . 9  |-  F  =  ( x  e.  ( ~P om  i^i  Fin )  |->  ( card `  U_ y  e.  x  ( {
y }  X.  ~P y ) ) )
5 ackbij.g . . . . . . . . 9  |-  G  =  ( x  e.  _V  |->  ( y  e.  ~P dom  x  |->  ( F `  ( x " y
) ) ) )
64, 5ackbij2lem2 8053 . . . . . . . 8  |-  ( a  e.  om  ->  ( rec ( G ,  (/) ) `  a ) : ( R1 `  a ) -1-1-onto-> ( card `  ( R1 `  a ) ) )
7 f1of1 5613 . . . . . . . 8  |-  ( ( rec ( G ,  (/) ) `  a ) : ( R1 `  a ) -1-1-onto-> ( card `  ( R1 `  a ) )  ->  ( rec ( G ,  (/) ) `  a ) : ( R1 `  a )
-1-1-> ( card `  ( R1 `  a ) ) )
86, 7syl 16 . . . . . . 7  |-  ( a  e.  om  ->  ( rec ( G ,  (/) ) `  a ) : ( R1 `  a ) -1-1-> ( card `  ( R1 `  a
) ) )
9 ordom 4794 . . . . . . . 8  |-  Ord  om
10 r1fin 7632 . . . . . . . . 9  |-  ( a  e.  om  ->  ( R1 `  a )  e. 
Fin )
11 ficardom 7781 . . . . . . . . 9  |-  ( ( R1 `  a )  e.  Fin  ->  ( card `  ( R1 `  a ) )  e. 
om )
1210, 11syl 16 . . . . . . . 8  |-  ( a  e.  om  ->  ( card `  ( R1 `  a ) )  e. 
om )
13 ordelss 4538 . . . . . . . 8  |-  ( ( Ord  om  /\  ( card `  ( R1 `  a ) )  e. 
om )  ->  ( card `  ( R1 `  a ) )  C_  om )
149, 12, 13sylancr 645 . . . . . . 7  |-  ( a  e.  om  ->  ( card `  ( R1 `  a ) )  C_  om )
15 f1ss 5584 . . . . . . 7  |-  ( ( ( rec ( G ,  (/) ) `  a
) : ( R1
`  a ) -1-1-> (
card `  ( R1 `  a ) )  /\  ( card `  ( R1 `  a ) )  C_  om )  ->  ( rec ( G ,  (/) ) `  a ) : ( R1 `  a )
-1-1-> om )
168, 14, 15syl2anc 643 . . . . . 6  |-  ( a  e.  om  ->  ( rec ( G ,  (/) ) `  a ) : ( R1 `  a ) -1-1-> om )
17 nnord 4793 . . . . . . . . 9  |-  ( a  e.  om  ->  Ord  a )
18 nnord 4793 . . . . . . . . 9  |-  ( b  e.  om  ->  Ord  b )
19 ordtri2or2 4618 . . . . . . . . 9  |-  ( ( Ord  a  /\  Ord  b )  ->  (
a  C_  b  \/  b  C_  a ) )
2017, 18, 19syl2an 464 . . . . . . . 8  |-  ( ( a  e.  om  /\  b  e.  om )  ->  ( a  C_  b  \/  b  C_  a ) )
214, 5ackbij2lem4 8055 . . . . . . . . . . 11  |-  ( ( ( b  e.  om  /\  a  e.  om )  /\  a  C_  b )  ->  ( rec ( G ,  (/) ) `  a )  C_  ( rec ( G ,  (/) ) `  b )
)
2221ex 424 . . . . . . . . . 10  |-  ( ( b  e.  om  /\  a  e.  om )  ->  ( a  C_  b  ->  ( rec ( G ,  (/) ) `  a
)  C_  ( rec ( G ,  (/) ) `  b ) ) )
2322ancoms 440 . . . . . . . . 9  |-  ( ( a  e.  om  /\  b  e.  om )  ->  ( a  C_  b  ->  ( rec ( G ,  (/) ) `  a
)  C_  ( rec ( G ,  (/) ) `  b ) ) )
244, 5ackbij2lem4 8055 . . . . . . . . . 10  |-  ( ( ( a  e.  om  /\  b  e.  om )  /\  b  C_  a )  ->  ( rec ( G ,  (/) ) `  b )  C_  ( rec ( G ,  (/) ) `  a )
)
2524ex 424 . . . . . . . . 9  |-  ( ( a  e.  om  /\  b  e.  om )  ->  ( b  C_  a  ->  ( rec ( G ,  (/) ) `  b
)  C_  ( rec ( G ,  (/) ) `  a ) ) )
2623, 25orim12d 812 . . . . . . . 8  |-  ( ( a  e.  om  /\  b  e.  om )  ->  ( ( a  C_  b  \/  b  C_  a )  ->  (
( rec ( G ,  (/) ) `  a
)  C_  ( rec ( G ,  (/) ) `  b )  \/  ( rec ( G ,  (/) ) `  b )  C_  ( rec ( G ,  (/) ) `  a
) ) ) )
2720, 26mpd 15 . . . . . . 7  |-  ( ( a  e.  om  /\  b  e.  om )  ->  ( ( rec ( G ,  (/) ) `  a )  C_  ( rec ( G ,  (/) ) `  b )  \/  ( rec ( G ,  (/) ) `  b
)  C_  ( rec ( G ,  (/) ) `  a ) ) )
2827ralrimiva 2732 . . . . . 6  |-  ( a  e.  om  ->  A. b  e.  om  ( ( rec ( G ,  (/) ) `  a )  C_  ( rec ( G ,  (/) ) `  b
)  \/  ( rec ( G ,  (/) ) `  b )  C_  ( rec ( G ,  (/) ) `  a
) ) )
2916, 28jca 519 . . . . 5  |-  ( a  e.  om  ->  (
( rec ( G ,  (/) ) `  a
) : ( R1
`  a ) -1-1-> om  /\ 
A. b  e.  om  ( ( rec ( G ,  (/) ) `  a )  C_  ( rec ( G ,  (/) ) `  b )  \/  ( rec ( G ,  (/) ) `  b
)  C_  ( rec ( G ,  (/) ) `  a ) ) ) )
303, 29mprg 2718 . . . 4  |-  U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U_ a  e.  om  ( R1 `  a ) -1-1-> om
31 rdgfun 6610 . . . . . 6  |-  Fun  rec ( G ,  (/) )
32 funiunfv 5934 . . . . . . 7  |-  ( Fun 
rec ( G ,  (/) )  ->  U_ a  e. 
om  ( rec ( G ,  (/) ) `  a )  =  U. ( rec ( G ,  (/) ) " om )
)
3332eqcomd 2392 . . . . . 6  |-  ( Fun 
rec ( G ,  (/) )  ->  U. ( rec ( G ,  (/) ) " om )  = 
U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) )
34 f1eq1 5574 . . . . . 6  |-  ( U. ( rec ( G ,  (/) ) " om )  =  U_ a  e.  om  ( rec ( G ,  (/) ) `  a )  ->  ( U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-> om  <->  U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U. ( R1
" om ) -1-1-> om ) )
3531, 33, 34mp2b 10 . . . . 5  |-  ( U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-> om  <->  U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U. ( R1
" om ) -1-1-> om )
36 r1funlim 7625 . . . . . . 7  |-  ( Fun 
R1  /\  Lim  dom  R1 )
3736simpli 445 . . . . . 6  |-  Fun  R1
38 funiunfv 5934 . . . . . 6  |-  ( Fun 
R1  ->  U_ a  e.  om  ( R1 `  a )  =  U. ( R1
" om ) )
39 f1eq2 5575 . . . . . 6  |-  ( U_ a  e.  om  ( R1 `  a )  = 
U. ( R1 " om )  ->  ( U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U_ a  e.  om  ( R1 `  a )
-1-1-> om  <->  U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U. ( R1
" om ) -1-1-> om ) )
4037, 38, 39mp2b 10 . . . . 5  |-  ( U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U_ a  e.  om  ( R1 `  a )
-1-1-> om  <->  U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U. ( R1
" om ) -1-1-> om )
4135, 40bitr4i 244 . . . 4  |-  ( U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-> om  <->  U_ a  e.  om  ( rec ( G ,  (/) ) `  a ) : U_ a  e. 
om  ( R1 `  a ) -1-1-> om )
4230, 41mpbir 201 . . 3  |-  U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-> om
43 rnuni 5223 . . . 4  |-  ran  U. ( rec ( G ,  (/) ) " om )  =  U_ a  e.  ( rec ( G ,  (/) ) " om ) ran  a
44 eliun 4039 . . . . . 6  |-  ( b  e.  U_ a  e.  ( rec ( G ,  (/) ) " om ) ran  a  <->  E. a  e.  ( rec ( G ,  (/) ) " om ) b  e.  ran  a )
45 df-rex 2655 . . . . . 6  |-  ( E. a  e.  ( rec ( G ,  (/) ) " om ) b  e.  ran  a  <->  E. a
( a  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  a ) )
46 funfn 5422 . . . . . . . . . . . 12  |-  ( Fun 
rec ( G ,  (/) )  <->  rec ( G ,  (/) )  Fn  dom  rec ( G ,  (/) ) )
4731, 46mpbi 200 . . . . . . . . . . 11  |-  rec ( G ,  (/) )  Fn 
dom  rec ( G ,  (/) )
48 rdgdmlim 6611 . . . . . . . . . . . 12  |-  Lim  dom  rec ( G ,  (/) )
49 limomss 4790 . . . . . . . . . . . 12  |-  ( Lim 
dom  rec ( G ,  (/) )  ->  om  C_  dom  rec ( G ,  (/) ) )
5048, 49ax-mp 8 . . . . . . . . . . 11  |-  om  C_  dom  rec ( G ,  (/) )
51 fvelimab 5721 . . . . . . . . . . 11  |-  ( ( rec ( G ,  (/) )  Fn  dom  rec ( G ,  (/) )  /\  om  C_  dom  rec ( G ,  (/) ) )  -> 
( a  e.  ( rec ( G ,  (/) ) " om )  <->  E. c  e.  om  ( rec ( G ,  (/) ) `  c )  =  a ) )
5247, 50, 51mp2an 654 . . . . . . . . . 10  |-  ( a  e.  ( rec ( G ,  (/) ) " om )  <->  E. c  e.  om  ( rec ( G ,  (/) ) `  c )  =  a )
534, 5ackbij2lem2 8053 . . . . . . . . . . . . . 14  |-  ( c  e.  om  ->  ( rec ( G ,  (/) ) `  c ) : ( R1 `  c ) -1-1-onto-> ( card `  ( R1 `  c ) ) )
54 f1ofo 5621 . . . . . . . . . . . . . 14  |-  ( ( rec ( G ,  (/) ) `  c ) : ( R1 `  c ) -1-1-onto-> ( card `  ( R1 `  c ) )  ->  ( rec ( G ,  (/) ) `  c ) : ( R1 `  c )
-onto-> ( card `  ( R1 `  c ) ) )
55 forn 5596 . . . . . . . . . . . . . 14  |-  ( ( rec ( G ,  (/) ) `  c ) : ( R1 `  c ) -onto-> ( card `  ( R1 `  c
) )  ->  ran  ( rec ( G ,  (/) ) `  c )  =  ( card `  ( R1 `  c ) ) )
5653, 54, 553syl 19 . . . . . . . . . . . . 13  |-  ( c  e.  om  ->  ran  ( rec ( G ,  (/) ) `  c )  =  ( card `  ( R1 `  c ) ) )
57 r1fin 7632 . . . . . . . . . . . . . . 15  |-  ( c  e.  om  ->  ( R1 `  c )  e. 
Fin )
58 ficardom 7781 . . . . . . . . . . . . . . 15  |-  ( ( R1 `  c )  e.  Fin  ->  ( card `  ( R1 `  c ) )  e. 
om )
5957, 58syl 16 . . . . . . . . . . . . . 14  |-  ( c  e.  om  ->  ( card `  ( R1 `  c ) )  e. 
om )
60 ordelss 4538 . . . . . . . . . . . . . 14  |-  ( ( Ord  om  /\  ( card `  ( R1 `  c ) )  e. 
om )  ->  ( card `  ( R1 `  c ) )  C_  om )
619, 59, 60sylancr 645 . . . . . . . . . . . . 13  |-  ( c  e.  om  ->  ( card `  ( R1 `  c ) )  C_  om )
6256, 61eqsstrd 3325 . . . . . . . . . . . 12  |-  ( c  e.  om  ->  ran  ( rec ( G ,  (/) ) `  c ) 
C_  om )
63 rneq 5035 . . . . . . . . . . . . 13  |-  ( ( rec ( G ,  (/) ) `  c )  =  a  ->  ran  ( rec ( G ,  (/) ) `  c )  =  ran  a )
6463sseq1d 3318 . . . . . . . . . . . 12  |-  ( ( rec ( G ,  (/) ) `  c )  =  a  ->  ( ran  ( rec ( G ,  (/) ) `  c
)  C_  om  <->  ran  a  C_  om ) )
6562, 64syl5ibcom 212 . . . . . . . . . . 11  |-  ( c  e.  om  ->  (
( rec ( G ,  (/) ) `  c
)  =  a  ->  ran  a  C_  om )
)
6665rexlimiv 2767 . . . . . . . . . 10  |-  ( E. c  e.  om  ( rec ( G ,  (/) ) `  c )  =  a  ->  ran  a  C_ 
om )
6752, 66sylbi 188 . . . . . . . . 9  |-  ( a  e.  ( rec ( G ,  (/) ) " om )  ->  ran  a  C_ 
om )
6867sselda 3291 . . . . . . . 8  |-  ( ( a  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  a )  ->  b  e.  om )
6968exlimiv 1641 . . . . . . 7  |-  ( E. a ( a  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  a )  ->  b  e.  om )
70 peano2 4805 . . . . . . . . 9  |-  ( b  e.  om  ->  suc  b  e.  om )
71 fnfvima 5915 . . . . . . . . . 10  |-  ( ( rec ( G ,  (/) )  Fn  dom  rec ( G ,  (/) )  /\  om  C_  dom  rec ( G ,  (/) )  /\  suc  b  e.  om )  ->  ( rec ( G ,  (/) ) `  suc  b )  e.  ( rec ( G ,  (/) ) " om )
)
7247, 50, 71mp3an12 1269 . . . . . . . . 9  |-  ( suc  b  e.  om  ->  ( rec ( G ,  (/) ) `  suc  b
)  e.  ( rec ( G ,  (/) ) " om ) )
7370, 72syl 16 . . . . . . . 8  |-  ( b  e.  om  ->  ( rec ( G ,  (/) ) `  suc  b )  e.  ( rec ( G ,  (/) ) " om ) )
74 vex 2902 . . . . . . . . . 10  |-  b  e. 
_V
75 cardnn 7783 . . . . . . . . . . . 12  |-  ( suc  b  e.  om  ->  (
card `  suc  b )  =  suc  b )
76 fvex 5682 . . . . . . . . . . . . . 14  |-  ( R1
`  suc  b )  e.  _V
7736simpri 449 . . . . . . . . . . . . . . . . 17  |-  Lim  dom  R1
78 limomss 4790 . . . . . . . . . . . . . . . . 17  |-  ( Lim 
dom  R1  ->  om  C_  dom  R1 )
7977, 78ax-mp 8 . . . . . . . . . . . . . . . 16  |-  om  C_  dom  R1
8079sseli 3287 . . . . . . . . . . . . . . 15  |-  ( suc  b  e.  om  ->  suc  b  e.  dom  R1 )
81 onssr1 7690 . . . . . . . . . . . . . . 15  |-  ( suc  b  e.  dom  R1  ->  suc  b  C_  ( R1 `  suc  b ) )
8280, 81syl 16 . . . . . . . . . . . . . 14  |-  ( suc  b  e.  om  ->  suc  b  C_  ( R1 ` 
suc  b ) )
83 ssdomg 7089 . . . . . . . . . . . . . 14  |-  ( ( R1 `  suc  b
)  e.  _V  ->  ( suc  b  C_  ( R1 `  suc  b )  ->  suc  b  ~<_  ( R1
`  suc  b )
) )
8476, 82, 83mpsyl 61 . . . . . . . . . . . . 13  |-  ( suc  b  e.  om  ->  suc  b  ~<_  ( R1 `  suc  b ) )
85 nnon 4791 . . . . . . . . . . . . . . 15  |-  ( suc  b  e.  om  ->  suc  b  e.  On )
86 onenon 7769 . . . . . . . . . . . . . . 15  |-  ( suc  b  e.  On  ->  suc  b  e.  dom  card )
8785, 86syl 16 . . . . . . . . . . . . . 14  |-  ( suc  b  e.  om  ->  suc  b  e.  dom  card )
88 r1fin 7632 . . . . . . . . . . . . . . 15  |-  ( suc  b  e.  om  ->  ( R1 `  suc  b
)  e.  Fin )
89 finnum 7768 . . . . . . . . . . . . . . 15  |-  ( ( R1 `  suc  b
)  e.  Fin  ->  ( R1 `  suc  b
)  e.  dom  card )
9088, 89syl 16 . . . . . . . . . . . . . 14  |-  ( suc  b  e.  om  ->  ( R1 `  suc  b
)  e.  dom  card )
91 carddom2 7797 . . . . . . . . . . . . . 14  |-  ( ( suc  b  e.  dom  card  /\  ( R1 `  suc  b )  e.  dom  card )  ->  ( ( card `  suc  b ) 
C_  ( card `  ( R1 `  suc  b ) )  <->  suc  b  ~<_  ( R1
`  suc  b )
) )
9287, 90, 91syl2anc 643 . . . . . . . . . . . . 13  |-  ( suc  b  e.  om  ->  ( ( card `  suc  b )  C_  ( card `  ( R1 `  suc  b ) )  <->  suc  b  ~<_  ( R1 `  suc  b
) ) )
9384, 92mpbird 224 . . . . . . . . . . . 12  |-  ( suc  b  e.  om  ->  (
card `  suc  b ) 
C_  ( card `  ( R1 `  suc  b ) ) )
9475, 93eqsstr3d 3326 . . . . . . . . . . 11  |-  ( suc  b  e.  om  ->  suc  b  C_  ( card `  ( R1 `  suc  b ) ) )
9570, 94syl 16 . . . . . . . . . 10  |-  ( b  e.  om  ->  suc  b  C_  ( card `  ( R1 `  suc  b ) ) )
96 sucssel 4614 . . . . . . . . . 10  |-  ( b  e.  _V  ->  ( suc  b  C_  ( card `  ( R1 `  suc  b ) )  -> 
b  e.  ( card `  ( R1 `  suc  b ) ) ) )
9774, 95, 96mpsyl 61 . . . . . . . . 9  |-  ( b  e.  om  ->  b  e.  ( card `  ( R1 `  suc  b ) ) )
984, 5ackbij2lem2 8053 . . . . . . . . . . 11  |-  ( suc  b  e.  om  ->  ( rec ( G ,  (/) ) `  suc  b
) : ( R1
`  suc  b ) -1-1-onto-> ( card `  ( R1 `  suc  b ) ) )
9970, 98syl 16 . . . . . . . . . 10  |-  ( b  e.  om  ->  ( rec ( G ,  (/) ) `  suc  b ) : ( R1 `  suc  b ) -1-1-onto-> ( card `  ( R1 `  suc  b ) ) )
100 f1ofo 5621 . . . . . . . . . 10  |-  ( ( rec ( G ,  (/) ) `  suc  b
) : ( R1
`  suc  b ) -1-1-onto-> ( card `  ( R1 `  suc  b ) )  -> 
( rec ( G ,  (/) ) `  suc  b ) : ( R1 `  suc  b
) -onto-> ( card `  ( R1 `  suc  b ) ) )
101 forn 5596 . . . . . . . . . 10  |-  ( ( rec ( G ,  (/) ) `  suc  b
) : ( R1
`  suc  b ) -onto->
( card `  ( R1 ` 
suc  b ) )  ->  ran  ( rec ( G ,  (/) ) `  suc  b )  =  (
card `  ( R1 ` 
suc  b ) ) )
10299, 100, 1013syl 19 . . . . . . . . 9  |-  ( b  e.  om  ->  ran  ( rec ( G ,  (/) ) `  suc  b
)  =  ( card `  ( R1 `  suc  b ) ) )
10397, 102eleqtrrd 2464 . . . . . . . 8  |-  ( b  e.  om  ->  b  e.  ran  ( rec ( G ,  (/) ) `  suc  b ) )
104 fvex 5682 . . . . . . . . 9  |-  ( rec ( G ,  (/) ) `  suc  b )  e.  _V
105 eleq1 2447 . . . . . . . . . 10  |-  ( a  =  ( rec ( G ,  (/) ) `  suc  b )  ->  (
a  e.  ( rec ( G ,  (/) ) " om )  <->  ( rec ( G ,  (/) ) `  suc  b )  e.  ( rec ( G ,  (/) ) " om )
) )
106 rneq 5035 . . . . . . . . . . 11  |-  ( a  =  ( rec ( G ,  (/) ) `  suc  b )  ->  ran  a  =  ran  ( rec ( G ,  (/) ) `  suc  b ) )
107106eleq2d 2454 . . . . . . . . . 10  |-  ( a  =  ( rec ( G ,  (/) ) `  suc  b )  ->  (
b  e.  ran  a  <->  b  e.  ran  ( rec ( G ,  (/) ) `  suc  b ) ) )
108105, 107anbi12d 692 . . . . . . . . 9  |-  ( a  =  ( rec ( G ,  (/) ) `  suc  b )  ->  (
( a  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  a )  <->  ( ( rec ( G ,  (/) ) `  suc  b )  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  ( rec ( G ,  (/) ) `  suc  b ) ) ) )
109104, 108spcev 2986 . . . . . . . 8  |-  ( ( ( rec ( G ,  (/) ) `  suc  b )  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  ( rec ( G ,  (/) ) `  suc  b
) )  ->  E. a
( a  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  a ) )
11073, 103, 109syl2anc 643 . . . . . . 7  |-  ( b  e.  om  ->  E. a
( a  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  a ) )
11169, 110impbii 181 . . . . . 6  |-  ( E. a ( a  e.  ( rec ( G ,  (/) ) " om )  /\  b  e.  ran  a )  <->  b  e.  om )
11244, 45, 1113bitri 263 . . . . 5  |-  ( b  e.  U_ a  e.  ( rec ( G ,  (/) ) " om ) ran  a  <->  b  e.  om )
113112eqriv 2384 . . . 4  |-  U_ a  e.  ( rec ( G ,  (/) ) " om ) ran  a  =  om
11443, 113eqtri 2407 . . 3  |-  ran  U. ( rec ( G ,  (/) ) " om )  =  om
115 dff1o5 5623 . . 3  |-  ( U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-onto-> om  <->  ( U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-> om  /\  ran  U. ( rec ( G ,  (/) ) " om )  =  om ) )
11642, 114, 115mpbir2an 887 . 2  |-  U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-onto-> om
117 ackbij.h . . 3  |-  H  = 
U. ( rec ( G ,  (/) ) " om )
118 f1oeq1 5605 . . 3  |-  ( H  =  U. ( rec ( G ,  (/) ) " om )  -> 
( H : U. ( R1 " om ) -1-1-onto-> om  <->  U. ( rec ( G ,  (/) ) " om ) : U. ( R1
" om ) -1-1-onto-> om )
)
119117, 118ax-mp 8 . 2  |-  ( H : U. ( R1
" om ) -1-1-onto-> om  <->  U. ( rec ( G ,  (/) ) " om ) : U. ( R1 " om ) -1-1-onto-> om )
120116, 119mpbir 201 1  |-  H : U. ( R1 " om )
-1-1-onto-> om
Colors of variables: wff set class
Syntax hints:    -> wi 4    <-> wb 177    \/ wo 358    /\ wa 359   E.wex 1547    = wceq 1649    e. wcel 1717   A.wral 2649   E.wrex 2650   _Vcvv 2899    i^i cin 3262    C_ wss 3263   (/)c0 3571   ~Pcpw 3742   {csn 3757   U.cuni 3957   U_ciun 4035   class class class wbr 4153    e. cmpt 4207   Ord word 4521   Oncon0 4522   Lim wlim 4523   suc csuc 4524   omcom 4785    X. cxp 4816   dom cdm 4818   ran crn 4819   "cima 4821   Fun wfun 5388    Fn wfn 5389   -1-1->wf1 5391   -onto->wfo 5392   -1-1-onto->wf1o 5393   ` cfv 5394   reccrdg 6603    ~<_ cdom 7043   Fincfn 7045   R1cr1 7621   cardccrd 7755
This theorem is referenced by:  r1om  8057
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 2368  ax-rep 4261  ax-sep 4271  ax-nul 4279  ax-pow 4318  ax-pr 4344  ax-un 4641
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 2242  df-mo 2243  df-clab 2374  df-cleq 2380  df-clel 2383  df-nfc 2512  df-ne 2552  df-ral 2654  df-rex 2655  df-reu 2656  df-rmo 2657  df-rab 2658  df-v 2901  df-sbc 3105  df-csb 3195  df-dif 3266  df-un 3268  df-in 3270  df-ss 3277  df-pss 3279  df-nul 3572  df-if 3683  df-pw 3744  df-sn 3763  df-pr 3764  df-tp 3765  df-op 3766  df-uni 3958  df-int 3993  df-iun 4037  df-br 4154  df-opab 4208  df-mpt 4209  df-tr 4244  df-eprel 4435  df-id 4439  df-po 4444  df-so 4445  df-fr 4482  df-we 4484  df-ord 4525  df-on 4526  df-lim 4527  df-suc 4528  df-om 4786  df-xp 4824  df-rel 4825  df-cnv 4826  df-co 4827  df-dm 4828  df-rn 4829  df-res 4830  df-ima 4831  df-iota 5358  df-fun 5396  df-fn 5397  df-f 5398  df-f1 5399  df-fo 5400  df-f1o 5401  df-fv 5402  df-ov 6023  df-oprab 6024  df-mpt2 6025  df-1st 6288  df-2nd 6289  df-recs 6569  df-rdg 6604  df-1o 6660  df-2o 6661  df-oadd 6664  df-er 6841  df-map 6956  df-en 7046  df-dom 7047  df-sdom 7048  df-fin 7049  df-r1 7623  df-rank 7624  df-card 7759  df-cda 7981
  Copyright terms: Public domain W3C validator