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

Theorem rpnnen2 14355
 Description: The other half of rpnnen 14356, where we show an injection from sets of positive integers to real numbers. The obvious choice for this is binary expansion, but it has the unfortunate property that it does not produce an injection on numbers which end with all 0's or all 1's (the more well-known decimal version of this is 0.999... 14014). Instead, we opt for a ternary expansion, which produces (a scaled version of) the Cantor set. Since the Cantor set is riddled with gaps, we can show that any two sequences that are not equal must differ somewhere, and when they do, they are placed a finite distance apart, thus ensuring that the map is injective. Our map assigns to each subset of the positive integers the number , where (rpnnen2lem1 14344). This is an infinite sum of real numbers (rpnnen2lem2 14345), and since implies (rpnnen2lem4 14347) and converges to (rpnnen2lem3 14346) by geoisum1 14012, the sum is convergent to some real (rpnnen2lem5 14348 and rpnnen2lem6 14349) by the comparison test for convergence cvgcmp 13953. The comparison test also tells us that implies (rpnnen2lem7 14350). Putting it all together, if we have two sets , there must differ somewhere, and so there must be an such that but or vice versa. In this case, we split off the first terms (rpnnen2lem8 14351) and cancel them (rpnnen2lem10 14353), since these are the same for both sets. For the remaining terms, we use the subset property to establish that and (where these sums are only over ), and since (rpnnen2lem9 14352) and , we establish that (rpnnen2lem11 14354) so that they must be different. By contraposition, we find that this map is an injection. (Contributed by Mario Carneiro, 13-May-2013.) (Proof shortened by Mario Carneiro, 30-Apr-2014.)
Hypothesis
Ref Expression
rpnnen2.1
Assertion
Ref Expression
rpnnen2
Distinct variable group:   ,
Allowed substitution hints:   (,)

Proof of Theorem rpnnen2
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 ovex 6336 . 2
2 elpwi 3951 . . . . 5
3 nnuz 11218 . . . . . . 7
43sumeq1i 13841 . . . . . 6
5 1nn 10642 . . . . . . 7
6 rpnnen2.1 . . . . . . . 8
76rpnnen2lem6 14349 . . . . . . 7
85, 7mpan2 685 . . . . . 6
94, 8syl5eqel 2553 . . . . 5
102, 9syl 17 . . . 4
11 1zzd 10992 . . . . 5
12 eqidd 2472 . . . . 5
136rpnnen2lem2 14345 . . . . . . 7
142, 13syl 17 . . . . . 6
1514ffvelrnda 6037 . . . . 5
166rpnnen2lem5 14348 . . . . . 6
172, 5, 16sylancl 675 . . . . 5
18 ssid 3437 . . . . . . . 8
196rpnnen2lem4 14347 . . . . . . . 8
2018, 19mp3an2 1378 . . . . . . 7
2120simpld 466 . . . . . 6
222, 21sylan 479 . . . . 5
233, 11, 12, 15, 17, 22isumge0 13904 . . . 4
24 halfre 10851 . . . . . 6
2524a1i 11 . . . . 5
26 1re 9660 . . . . . 6
2726a1i 11 . . . . 5
286rpnnen2lem7 14350 . . . . . . . . 9
2918, 5, 28mp3an23 1382 . . . . . . . 8
302, 29syl 17 . . . . . . 7
31 eqid 2471 . . . . . . . 8
32 eqidd 2472 . . . . . . . 8
33 elnnuz 11219 . . . . . . . . . 10
346rpnnen2lem2 14345 . . . . . . . . . . . . 13
3518, 34ax-mp 5 . . . . . . . . . . . 12
3635ffvelrni 6036 . . . . . . . . . . 11
3736recnd 9687 . . . . . . . . . 10
3833, 37sylbir 218 . . . . . . . . 9
3938adantl 473 . . . . . . . 8
406rpnnen2lem3 14346 . . . . . . . . 9
4140a1i 11 . . . . . . . 8
4231, 11, 32, 39, 41isumclim 13895 . . . . . . 7
4330, 42breqtrd 4420 . . . . . 6
444, 43syl5eqbr 4429 . . . . 5
45 halflt1 10854 . . . . . . 7
4624, 26, 45ltleii 9775 . . . . . 6
4746a1i 11 . . . . 5
4810, 25, 27, 44, 47letrd 9809 . . . 4
49 0re 9661 . . . . 5
5049, 26elicc2i 11725 . . . 4
5110, 23, 48, 50syl3anbrc 1214 . . 3
52 elpwi 3951 . . . . . . . . . . 11
53 ssdifss 3553 . . . . . . . . . . . 12
54 ssdifss 3553 . . . . . . . . . . . 12
55 unss 3599 . . . . . . . . . . . . 13
5655biimpi 199 . . . . . . . . . . . 12
5753, 54, 56syl2an 485 . . . . . . . . . . 11
582, 52, 57syl2an 485 . . . . . . . . . 10
59 eqss 3433 . . . . . . . . . . . . 13
60 ssdif0 3741 . . . . . . . . . . . . . 14
61 ssdif0 3741 . . . . . . . . . . . . . 14
6260, 61anbi12i 711 . . . . . . . . . . . . 13
63 un00 3804 . . . . . . . . . . . . 13
6459, 62, 633bitri 279 . . . . . . . . . . . 12
6564necon3bii 2695 . . . . . . . . . . 11
6665biimpi 199 . . . . . . . . . 10
67 nnwo 11247 . . . . . . . . . 10
6858, 66, 67syl2an 485 . . . . . . . . 9
6968ex 441 . . . . . . . 8
7058sselda 3418 . . . . . . . . . 10
71 df-ral 2761 . . . . . . . . . . . 12
72 con34b 299 . . . . . . . . . . . . . 14
73 eldif 3400 . . . . . . . . . . . . . . . . . 18
74 eldif 3400 . . . . . . . . . . . . . . . . . 18
7573, 74orbi12i 530 . . . . . . . . . . . . . . . . 17
76 elun 3565 . . . . . . . . . . . . . . . . 17
77 xor 908 . . . . . . . . . . . . . . . . 17
7875, 76, 773bitr4ri 286 . . . . . . . . . . . . . . . 16
7978con1bii 338 . . . . . . . . . . . . . . 15
8079imbi2i 319 . . . . . . . . . . . . . 14
8172, 80bitri 257 . . . . . . . . . . . . 13
8281albii 1699 . . . . . . . . . . . 12
8371, 82bitri 257 . . . . . . . . . . 11
84 alral 2772 . . . . . . . . . . . 12
85 nnre 10638 . . . . . . . . . . . . . . 15
86 nnre 10638 . . . . . . . . . . . . . . 15
87 ltnle 9731 . . . . . . . . . . . . . . 15
8885, 86, 87syl2anr 486 . . . . . . . . . . . . . 14
8988imbi1d 324 . . . . . . . . . . . . 13
9089ralbidva 2828 . . . . . . . . . . . 12
9184, 90syl5ibr 229 . . . . . . . . . . 11
9283, 91syl5bi 225 . . . . . . . . . 10
9370, 92syl 17 . . . . . . . . 9
9493reximdva 2858 . . . . . . . 8
9569, 94syld 44 . . . . . . 7
96 rexun 3605 . . . . . . 7
9795, 96syl6ib 234 . . . . . 6
98 simpll 768 . . . . . . . . . 10
99 simplr 770 . . . . . . . . . 10
100 simprl 772 . . . . . . . . . 10
101 simprr 774 . . . . . . . . . 10
102 biid 244 . . . . . . . . . 10
1036, 98, 99, 100, 101, 102rpnnen2lem11 14354 . . . . . . . . 9
104103rexlimdvaa 2872 . . . . . . . 8
105 simplr 770 . . . . . . . . . 10
106 simpll 768 . . . . . . . . . 10
107 simprl 772 . . . . . . . . . 10
108 simprr 774 . . . . . . . . . . 11
109 bicom 205 . . . . . . . . . . . . 13
110109imbi2i 319 . . . . . . . . . . . 12
111110ralbii 2823 . . . . . . . . . . 11
112108, 111sylibr 217 . . . . . . . . . 10
113 eqcom 2478 . . . . . . . . . 10
1146, 105, 106, 107, 112, 113rpnnen2lem11 14354 . . . . . . . . 9
115114rexlimdvaa 2872 . . . . . . . 8
116104, 115jaod 387 . . . . . . 7
1172, 52, 116syl2an 485 . . . . . 6
11897, 117syld 44 . . . . 5
119118necon4ad 2662 . . . 4
120 fveq2 5879 . . . . . 6
121120fveq1d 5881 . . . . 5
122121sumeq2sdv 13847 . . . 4
123119, 122impbid1 208 . . 3
12451, 123dom2 7630 . 2
1251, 124ax-mp 5 1
 Colors of variables: wff setvar class Syntax hints:   wn 3   wi 4   wb 189   wo 375   wa 376  wal 1450   wceq 1452   wcel 1904   wne 2641  wral 2756  wrex 2757  cvv 3031   cdif 3387   cun 3388   wss 3390  c0 3722  cif 3872  cpw 3942   class class class wbr 4395   cmpt 4454   cdm 4839  wf 5585  cfv 5589  (class class class)co 6308   cdom 7585  cc 9555  cr 9556  cc0 9557  c1 9558   caddc 9560   clt 9693   cle 9694   cdiv 10291  cn 10631  c2 10681  c3 10682  cuz 11182  cicc 11663   cseq 12251  cexp 12310   cli 13625  csu 13829 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1677  ax-4 1690  ax-5 1766  ax-6 1813  ax-7 1859  ax-8 1906  ax-9 1913  ax-10 1932  ax-11 1937  ax-12 1950  ax-13 2104  ax-ext 2451  ax-rep 4508  ax-sep 4518  ax-nul 4527  ax-pow 4579  ax-pr 4639  ax-un 6602  ax-inf2 8164  ax-cnex 9613  ax-resscn 9614  ax-1cn 9615  ax-icn 9616  ax-addcl 9617  ax-addrcl 9618  ax-mulcl 9619  ax-mulrcl 9620  ax-mulcom 9621  ax-addass 9622  ax-mulass 9623  ax-distr 9624  ax-i2m1 9625  ax-1ne0 9626  ax-1rid 9627  ax-rnegex 9628  ax-rrecex 9629  ax-cnre 9630  ax-pre-lttri 9631  ax-pre-lttrn 9632  ax-pre-ltadd 9633  ax-pre-mulgt0 9634  ax-pre-sup 9635 This theorem depends on definitions:  df-bi 190  df-or 377  df-an 378  df-3or 1008  df-3an 1009  df-tru 1455  df-fal 1458  df-ex 1672  df-nf 1676  df-sb 1806  df-eu 2323  df-mo 2324  df-clab 2458  df-cleq 2464  df-clel 2467  df-nfc 2601  df-ne 2643  df-nel 2644  df-ral 2761  df-rex 2762  df-reu 2763  df-rmo 2764  df-rab 2765  df-v 3033  df-sbc 3256  df-csb 3350  df-dif 3393  df-un 3395  df-in 3397  df-ss 3404  df-pss 3406  df-nul 3723  df-if 3873  df-pw 3944  df-sn 3960  df-pr 3962  df-tp 3964  df-op 3966  df-uni 4191  df-int 4227  df-iun 4271  df-br 4396  df-opab 4455  df-mpt 4456  df-tr 4491  df-eprel 4750  df-id 4754  df-po 4760  df-so 4761  df-fr 4798  df-se 4799  df-we 4800  df-xp 4845  df-rel 4846  df-cnv 4847  df-co 4848  df-dm 4849  df-rn 4850  df-res 4851  df-ima 4852  df-pred 5387  df-ord 5433  df-on 5434  df-lim 5435  df-suc 5436  df-iota 5553  df-fun 5591  df-fn 5592  df-f 5593  df-f1 5594  df-fo 5595  df-f1o 5596  df-fv 5597  df-isom 5598  df-riota 6270  df-ov 6311  df-oprab 6312  df-mpt2 6313  df-om 6712  df-1st 6812  df-2nd 6813  df-wrecs 7046  df-recs 7108  df-rdg 7146  df-1o 7200  df-oadd 7204  df-er 7381  df-pm 7493  df-en 7588  df-dom 7589  df-sdom 7590  df-fin 7591  df-sup 7974  df-inf 7975  df-oi 8043  df-card 8391  df-pnf 9695  df-mnf 9696  df-xr 9697  df-ltxr 9698  df-le 9699  df-sub 9882  df-neg 9883  df-div 10292  df-nn 10632  df-2 10690  df-3 10691  df-n0 10894  df-z 10962  df-uz 11183  df-rp 11326  df-ico 11666  df-icc 11667  df-fz 11811  df-fzo 11943  df-fl 12061  df-seq 12252  df-exp 12311  df-hash 12554  df-cj 13239  df-re 13240  df-im 13241  df-sqrt 13375  df-abs 13376  df-limsup 13603  df-clim 13629  df-rlim 13630  df-sum 13830 This theorem is referenced by:  rpnnen  14356  opnreen  21927
 Copyright terms: Public domain W3C validator