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

Theorem rpnnen2 12506
 Description: The other half of rpnnen 12507, where we show an injection from sets of natural numbers 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... 12339). 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 natural numbers the number , where (rpnnen2lem1 12495). This is an infinite sum of real numbers (rpnnen2lem2 12496), and since implies (rpnnen2lem4 12498) and converges to (rpnnen2lem3 12497) by geoisum1 12337, the sum is convergent to some real (rpnnen2lem5 12499 and rpnnen2lem6 12500) by the comparison test for convergence cvgcmp 12276. The comparison test also tells us that implies (rpnnen2lem7 12501). 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 12502) and cancel them (rpnnen2lem10 12504), 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 12503) and , we establish that (rpnnen2lem11 12505) 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 5885 . 2
2 elpwi 3635 . . . . 5
3 nnuz 10265 . . . . . . 7
43sumeq1i 12173 . . . . . 6
5 1nn 9759 . . . . . . 7
6 rpnnen2.1 . . . . . . . 8
76rpnnen2lem6 12500 . . . . . . 7
85, 7mpan2 652 . . . . . 6
94, 8syl5eqel 2369 . . . . 5
102, 9syl 15 . . . 4
11 1z 10055 . . . . . 6
1211a1i 10 . . . . 5
13 eqidd 2286 . . . . 5
146rpnnen2lem2 12496 . . . . . . 7
152, 14syl 15 . . . . . 6
16 ffvelrn 5665 . . . . . 6
1715, 16sylan 457 . . . . 5
186rpnnen2lem5 12499 . . . . . 6
192, 5, 18sylancl 643 . . . . 5
20 ssid 3199 . . . . . . . 8
216rpnnen2lem4 12498 . . . . . . . 8
2220, 21mp3an2 1265 . . . . . . 7
2322simpld 445 . . . . . 6
242, 23sylan 457 . . . . 5
253, 12, 13, 17, 19, 24isumge0 12231 . . . 4
26 1re 8839 . . . . . . 7
27 rehalfcl 9940 . . . . . . 7
2826, 27ax-mp 8 . . . . . 6
2928a1i 10 . . . . 5
3026a1i 10 . . . . 5
316rpnnen2lem7 12501 . . . . . . . . 9
3220, 5, 31mp3an23 1269 . . . . . . . 8
332, 32syl 15 . . . . . . 7
34 eqid 2285 . . . . . . . 8
35 eqidd 2286 . . . . . . . 8
36 elnnuz 10266 . . . . . . . . . 10
376rpnnen2lem2 12496 . . . . . . . . . . . . 13
3820, 37ax-mp 8 . . . . . . . . . . . 12
3938ffvelrni 5666 . . . . . . . . . . 11
4039recnd 8863 . . . . . . . . . 10
4136, 40sylbir 204 . . . . . . . . 9
4241adantl 452 . . . . . . . 8
436rpnnen2lem3 12497 . . . . . . . . 9
4443a1i 10 . . . . . . . 8
4534, 12, 35, 42, 44isumclim 12222 . . . . . . 7
4633, 45breqtrd 4049 . . . . . 6
474, 46syl5eqbr 4058 . . . . 5
48 halflt1 9935 . . . . . . 7
4928, 26, 48ltleii 8943 . . . . . 6
5049a1i 10 . . . . 5
5110, 29, 30, 47, 50letrd 8975 . . . 4
52 0re 8840 . . . . 5
5352, 26elicc2i 10718 . . . 4
5410, 25, 51, 53syl3anbrc 1136 . . 3
55 elpwi 3635 . . . . . . . . . . 11
56 ssdifss 3309 . . . . . . . . . . . 12
57 ssdifss 3309 . . . . . . . . . . . 12
58 unss 3351 . . . . . . . . . . . . 13
5958biimpi 186 . . . . . . . . . . . 12
6056, 57, 59syl2an 463 . . . . . . . . . . 11
612, 55, 60syl2an 463 . . . . . . . . . 10
62 eqss 3196 . . . . . . . . . . . . 13
63 ssdif0 3515 . . . . . . . . . . . . . 14
64 ssdif0 3515 . . . . . . . . . . . . . 14
6563, 64anbi12i 678 . . . . . . . . . . . . 13
66 un00 3492 . . . . . . . . . . . . 13
6762, 65, 663bitri 262 . . . . . . . . . . . 12
6867necon3bii 2480 . . . . . . . . . . 11
6968biimpi 186 . . . . . . . . . 10
70 nnwo 10286 . . . . . . . . . 10
7161, 69, 70syl2an 463 . . . . . . . . 9
7271ex 423 . . . . . . . 8
7361sselda 3182 . . . . . . . . . 10
74 df-ral 2550 . . . . . . . . . . . 12
75 con34b 283 . . . . . . . . . . . . . 14
76 eldif 3164 . . . . . . . . . . . . . . . . . 18
77 eldif 3164 . . . . . . . . . . . . . . . . . 18
7876, 77orbi12i 507 . . . . . . . . . . . . . . . . 17
79 elun 3318 . . . . . . . . . . . . . . . . 17
80 xor 861 . . . . . . . . . . . . . . . . 17
8178, 79, 803bitr4ri 269 . . . . . . . . . . . . . . . 16
8281con1bii 321 . . . . . . . . . . . . . . 15
8382imbi2i 303 . . . . . . . . . . . . . 14
8475, 83bitri 240 . . . . . . . . . . . . 13
8584albii 1555 . . . . . . . . . . . 12
8674, 85bitri 240 . . . . . . . . . . 11
87 alral 2603 . . . . . . . . . . . 12
88 nnre 9755 . . . . . . . . . . . . . . 15
89 nnre 9755 . . . . . . . . . . . . . . 15
90 ltnle 8904 . . . . . . . . . . . . . . 15
9188, 89, 90syl2anr 464 . . . . . . . . . . . . . 14
9291imbi1d 308 . . . . . . . . . . . . 13
9392ralbidva 2561 . . . . . . . . . . . 12
9487, 93syl5ibr 212 . . . . . . . . . . 11
9586, 94syl5bi 208 . . . . . . . . . 10
9673, 95syl 15 . . . . . . . . 9
9796reximdva 2657 . . . . . . . 8
9872, 97syld 40 . . . . . . 7
99 rexun 3357 . . . . . . 7
10098, 99syl6ib 217 . . . . . 6
101 simpll 730 . . . . . . . . . . 11
102 simplr 731 . . . . . . . . . . 11
103 simprl 732 . . . . . . . . . . 11
104 simprr 733 . . . . . . . . . . 11
105 biid 227 . . . . . . . . . . 11
1066, 101, 102, 103, 104, 105rpnnen2lem11 12505 . . . . . . . . . 10
107106expr 598 . . . . . . . . 9
108107rexlimdva 2669 . . . . . . . 8
109 simplr 731 . . . . . . . . . . 11
110 simpll 730 . . . . . . . . . . 11
111 simprl 732 . . . . . . . . . . 11
112 simprr 733 . . . . . . . . . . . 12
113 bicom 191 . . . . . . . . . . . . . 14
114113imbi2i 303 . . . . . . . . . . . . 13
115114ralbii 2569 . . . . . . . . . . . 12
116112, 115sylibr 203 . . . . . . . . . . 11
117 eqcom 2287 . . . . . . . . . . 11
1186, 109, 110, 111, 116, 117rpnnen2lem11 12505 . . . . . . . . . 10
119118expr 598 . . . . . . . . 9
120119rexlimdva 2669 . . . . . . . 8
121108, 120jaod 369 . . . . . . 7
1222, 55, 121syl2an 463 . . . . . 6
123100, 122syld 40 . . . . 5
124123necon4ad 2509 . . . 4
125 fveq2 5527 . . . . . 6
126125fveq1d 5529 . . . . 5
127126sumeq2sdv 12179 . . . 4
128124, 127impbid1 194 . . 3
12954, 128dom2 6906 . 2
1301, 129ax-mp 8 1
 Colors of variables: wff set class Syntax hints:   wn 3   wi 4   wb 176   wo 357   wa 358  wal 1529   wceq 1625   wcel 1686   wne 2448  wral 2545  wrex 2546  cvv 2790   cdif 3151   cun 3152   wss 3154  c0 3457  cif 3567  cpw 3627   class class class wbr 4025   cmpt 4079   cdm 4691  wf 5253  cfv 5257  (class class class)co 5860   cdom 6863  cc 8737  cr 8738  cc0 8739  c1 8740   caddc 8742   clt 8869   cle 8870   cdiv 9425  cn 9748  c2 9797  c3 9798  cz 10026  cuz 10232  cicc 10661   cseq 11048  cexp 11106   cli 11960  csu 12160 This theorem is referenced by:  rpnnen  12507  opnreen  18338 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1535  ax-5 1546  ax-17 1605  ax-9 1637  ax-8 1645  ax-13 1688  ax-14 1690  ax-6 1705  ax-7 1710  ax-11 1717  ax-12 1868  ax-ext 2266  ax-rep 4133  ax-sep 4143  ax-nul 4151  ax-pow 4190  ax-pr 4216  ax-un 4514  ax-inf2 7344  ax-cnex 8795  ax-resscn 8796  ax-1cn 8797  ax-icn 8798  ax-addcl 8799  ax-addrcl 8800  ax-mulcl 8801  ax-mulrcl 8802  ax-mulcom 8803  ax-addass 8804  ax-mulass 8805  ax-distr 8806  ax-i2m1 8807  ax-1ne0 8808  ax-1rid 8809  ax-rnegex 8810  ax-rrecex 8811  ax-cnre 8812  ax-pre-lttri 8813  ax-pre-lttrn 8814  ax-pre-ltadd 8815  ax-pre-mulgt0 8816  ax-pre-sup 8817 This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1310  df-ex 1531  df-nf 1534  df-sb 1632  df-eu 2149  df-mo 2150  df-clab 2272  df-cleq 2278  df-clel 2281  df-nfc 2410  df-ne 2450  df-nel 2451  df-ral 2550  df-rex 2551  df-reu 2552  df-rmo 2553  df-rab 2554  df-v 2792  df-sbc 2994  df-csb 3084  df-dif 3157  df-un 3159  df-in 3161  df-ss 3168  df-pss 3170  df-nul 3458  df-if 3568  df-pw 3629  df-sn 3648  df-pr 3649  df-tp 3650  df-op 3651  df-uni 3830  df-int 3865  df-iun 3909  df-br 4026  df-opab 4080  df-mpt 4081  df-tr 4116  df-eprel 4307  df-id 4311  df-po 4316  df-so 4317  df-fr 4354  df-se 4355  df-we 4356  df-ord 4397  df-on 4398  df-lim 4399  df-suc 4400  df-om 4659  df-xp 4697  df-rel 4698  df-cnv 4699  df-co 4700  df-dm 4701  df-rn 4702  df-res 4703  df-ima 4704  df-iota 5221  df-fun 5259  df-fn 5260  df-f 5261  df-f1 5262  df-fo 5263  df-f1o 5264  df-fv 5265  df-isom 5266  df-ov 5863  df-oprab 5864  df-mpt2 5865  df-1st 6124  df-2nd 6125  df-riota 6306  df-recs 6390  df-rdg 6425  df-1o 6481  df-oadd 6485  df-er 6662  df-pm 6777  df-en 6866  df-dom 6867  df-sdom 6868  df-fin 6869  df-sup 7196  df-oi 7227  df-card 7574  df-pnf 8871  df-mnf 8872  df-xr 8873  df-ltxr 8874  df-le 8875  df-sub 9041  df-neg 9042  df-div 9426  df-nn 9749  df-2 9806  df-3 9807  df-n0 9968  df-z 10027  df-uz 10233  df-rp 10357  df-ico 10664  df-icc 10665  df-fz 10785  df-fzo 10873  df-fl 10927  df-seq 11049  df-exp 11107  df-hash 11340  df-cj 11586  df-re 11587  df-im 11588  df-sqr 11722  df-abs 11723  df-limsup 11947  df-clim 11964  df-rlim 11965  df-sum 12161
 Copyright terms: Public domain W3C validator