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

Theorem ackbij1 8065
 Description: The Ackermann bijection, part 1: each natural number can be uniquely coded in binary as a finite set of natural numbers and conversely. (Contributed by Stefan O'Rear, 18-Nov-2014.)
Hypothesis
Ref Expression
ackbij.f
Assertion
Ref Expression
ackbij1
Distinct variable group:   ,,

Proof of Theorem ackbij1
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 ackbij.f . . 3
21ackbij1lem17 8063 . 2
3 f1f 5593 . . . 4
4 frn 5551 . . . 4
52, 3, 4mp2b 10 . . 3
6 eleq1 2461 . . . . 5
7 eleq1 2461 . . . . 5
8 eleq1 2461 . . . . 5
9 peano1 4818 . . . . . . . 8
10 ackbij1lem3 8049 . . . . . . . 8
119, 10ax-mp 8 . . . . . . 7
121ackbij1lem13 8059 . . . . . . 7
13 fveq2 5682 . . . . . . . . 9
1413eqeq1d 2409 . . . . . . . 8
1514rspcev 3009 . . . . . . 7
1611, 12, 15mp2an 654 . . . . . 6
17 f1fn 5594 . . . . . . . 8
182, 17ax-mp 8 . . . . . . 7
19 fvelrnb 5727 . . . . . . 7
2018, 19ax-mp 8 . . . . . 6
2116, 20mpbir 201 . . . . 5
221ackbij1lem18 8064 . . . . . . . . 9
2322adantl 453 . . . . . . . 8
24 suceq 4601 . . . . . . . . . 10
2524eqeq2d 2412 . . . . . . . . 9
2625rexbidv 2684 . . . . . . . 8
2723, 26syl5ibcom 212 . . . . . . 7
2827rexlimdva 2787 . . . . . 6
29 fvelrnb 5727 . . . . . . 7
3018, 29ax-mp 8 . . . . . 6
31 fvelrnb 5727 . . . . . . 7
3218, 31ax-mp 8 . . . . . 6
3328, 30, 323imtr4g 262 . . . . 5
346, 7, 8, 7, 21, 33finds 4825 . . . 4
3534ssriv 3309 . . 3
365, 35eqssi 3321 . 2
37 dff1o5 5637 . 2
382, 36, 37mpbir2an 887 1
 Colors of variables: wff set class Syntax hints:   wb 177   wa 359   wceq 1649   wcel 1721  wrex 2664   cin 3276   wss 3277  c0 3585  cpw 3756  csn 3771  ciun 4049   cmpt 4221   csuc 4538  com 4799   cxp 4830   crn 4833   wfn 5403  wf 5404  wf1 5405  wf1o 5407  cfv 5408  cfn 7059  ccrd 7769 This theorem is referenced by:  fictb  8072  ackbijnn  12548 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 1662  ax-8 1683  ax-13 1723  ax-14 1725  ax-6 1740  ax-7 1745  ax-11 1757  ax-12 1946  ax-ext 2382  ax-rep 4275  ax-sep 4285  ax-nul 4293  ax-pow 4332  ax-pr 4358  ax-un 4655 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 2256  df-mo 2257  df-clab 2388  df-cleq 2394  df-clel 2397  df-nfc 2526  df-ne 2566  df-ral 2668  df-rex 2669  df-reu 2670  df-rmo 2671  df-rab 2672  df-v 2915  df-sbc 3119  df-csb 3209  df-dif 3280  df-un 3282  df-in 3284  df-ss 3291  df-pss 3293  df-nul 3586  df-if 3697  df-pw 3758  df-sn 3777  df-pr 3778  df-tp 3779  df-op 3780  df-uni 3972  df-int 4007  df-iun 4051  df-br 4168  df-opab 4222  df-mpt 4223  df-tr 4258  df-eprel 4449  df-id 4453  df-po 4458  df-so 4459  df-fr 4496  df-we 4498  df-ord 4539  df-on 4540  df-lim 4541  df-suc 4542  df-om 4800  df-xp 4838  df-rel 4839  df-cnv 4840  df-co 4841  df-dm 4842  df-rn 4843  df-res 4844  df-ima 4845  df-iota 5372  df-fun 5410  df-fn 5411  df-f 5412  df-f1 5413  df-fo 5414  df-f1o 5415  df-fv 5416  df-ov 6037  df-oprab 6038  df-mpt2 6039  df-1st 6302  df-2nd 6303  df-recs 6583  df-rdg 6618  df-1o 6674  df-2o 6675  df-oadd 6678  df-er 6855  df-map 6970  df-en 7060  df-dom 7061  df-sdom 7062  df-fin 7063  df-card 7773  df-cda 7995
 Copyright terms: Public domain W3C validator