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

Theorem 1arith 13346
Description: Fundamental theorem of arithmetic, where a prime factorization is represented as a sequence of prime exponents, for which only finitely many primes have nonzero exponent. The function maps the set of positive integers one-to-one onto the set of prime factorizations . (Contributed by Paul Chapman, 17-Nov-2012.) (Proof shortened by Mario Carneiro, 30-May-2014.)
Hypotheses
Ref Expression
1arith.1
1arith.2
Assertion
Ref Expression
1arith
Distinct variable groups:   , ,   ,M   ,
Allowed substitution hints:   ( , )   M( , )

Proof of Theorem 1arith
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 zex 10342 . . . . . . 7
2 prmz 13134 . . . . . . . 8
32ssriv 3341 . . . . . . 7
41, 3ssexi 4387 . . . . . 6
54mptex 6014 . . . . 5
6 1arith.1 . . . . 5
75, 6fnmpti 5620 . . . 4
861arithlem3 13344 . . . . . . 7
9 nn0ex 10278 . . . . . . . 8
109, 4elmap 7091 . . . . . . 7
118, 10sylibr 205 . . . . . 6
12 fzfi 11362 . . . . . . 7
13 ffn 5638 . . . . . . . . . 10
14 elpreima 5898 . . . . . . . . . 10
158, 13, 143syl 19 . . . . . . . . 9
1661arithlem2 13343 . . . . . . . . . . . 12
1716eleq1d 2509 . . . . . . . . . . 11
18 id 21 . . . . . . . . . . . . 13
19 dvdsle 12946 . . . . . . . . . . . . 13
202, 18, 19syl2anr 466 . . . . . . . . . . . 12
21 pcelnn 13294 . . . . . . . . . . . . 13
2221ancoms 441 . . . . . . . . . . . 12
23 prmnn 13133 . . . . . . . . . . . . . 14
24 nnuz 10572 . . . . . . . . . . . . . 14
2523, 24syl6eleq 2533 . . . . . . . . . . . . 13
26 nnz 10354 . . . . . . . . . . . . 13
27 elfz5 11102 . . . . . . . . . . . . 13
2825, 26, 27syl2anr 466 . . . . . . . . . . . 12
2920, 22, 283imtr4d 261 . . . . . . . . . . 11
3017, 29sylbid 208 . . . . . . . . . 10
3130expimpd 588 . . . . . . . . 9
3215, 31sylbid 208 . . . . . . . 8
3332ssrdv 3343 . . . . . . 7
34 ssfi 7378 . . . . . . 7
3512, 33, 34sylancr 646 . . . . . 6
36 cnveq 5088 . . . . . . . . 9
3736imaeq1d 5246 . . . . . . . 8
3837eleq1d 2509 . . . . . . 7
39 1arith.2 . . . . . . 7
4038, 39elrab2 3103 . . . . . 6
4111, 35, 40sylanbrc 647 . . . . 5
4241rgen 2778 . . . 4
43 ffnfv 5942 . . . 4
447, 42, 43mpbir2an 888 . . 3
4516adantlr 697 . . . . . . . 8
4661arithlem2 13343 . . . . . . . . 9
4746adantll 696 . . . . . . . 8
4845, 47eqeq12d 2457 . . . . . . 7
4948ralbidva 2728 . . . . . 6
5061arithlem3 13344 . . . . . . 7
51 ffn 5638 . . . . . . . 8
52 eqfnfv 5875 . . . . . . . 8
5313, 51, 52syl2an 465 . . . . . . 7
548, 50, 53syl2an 465 . . . . . 6
55 nnnn0 10279 . . . . . . 7
56 nnnn0 10279 . . . . . . 7
57 pc11 13304 . . . . . . 7
5855, 56, 57syl2an 465 . . . . . 6
5949, 54, 583bitr4d 278 . . . . 5
6059biimpd 200 . . . 4
6160rgen2a 2779 . . 3
62 dff13 6052 . . 3
6344, 61, 62mpbir2an 888 . 2
64 cnvimass 5268 . . . . . . 7
65 cnveq 5088 . . . . . . . . . . . . . 14
6665imaeq1d 5246 . . . . . . . . . . . . 13
6766eleq1d 2509 . . . . . . . . . . . 12
6867, 39elrab2 3103 . . . . . . . . . . 11
6968simplbi 448 . . . . . . . . . 10
709, 4elmap 7091 . . . . . . . . . 10
7169, 70sylib 190 . . . . . . . . 9
72 fdm 5642 . . . . . . . . 9
7371, 72syl 16 . . . . . . . 8
74 zssre 10340 . . . . . . . . 9
753, 74sstri 3346 . . . . . . . 8
7673, 75syl6eqss 3387 . . . . . . 7
7764, 76syl5ss 3348 . . . . . 6
7868simprbi 452 . . . . . 6
79 fimaxre2 10007 . . . . . 6
8077, 78, 79syl2anc 644 . . . . 5
81 eqid 2443 . . . . . . . 8
8271ad2antrr 708 . . . . . . . 8
83 simplr 733 . . . . . . . . . . 11
84 0re 9142 . . . . . . . . . . 11
85 ifcl 3800 . . . . . . . . . . 11
8683, 84, 85sylancl 645 . . . . . . . . . 10
87 max1 10824 . . . . . . . . . . 11
8884, 83, 87sylancr 646 . . . . . . . . . 10
89 flge0nn0 11276 . . . . . . . . . 10
9086, 88, 89syl2anc 644 . . . . . . . . 9
91 nn0p1nn 10310 . . . . . . . . 9
9290, 91syl 16 . . . . . . . 8
9383adantr 453 . . . . . . . . . . . 12
9492adantr 453 . . . . . . . . . . . . 13
9594nnred 10066 . . . . . . . . . . . 12
96 simprl 734 . . . . . . . . . . . . 13
9775, 96sseldi 3335 . . . . . . . . . . . 12
9886adantr 453 . . . . . . . . . . . . 13
99 max2 10826 . . . . . . . . . . . . . 14
10084, 93, 99sylancr 646 . . . . . . . . . . . . 13
101 flltp1 11260 . . . . . . . . . . . . . 14
10298, 101syl 16 . . . . . . . . . . . . 13
10393, 98, 95, 100, 102lelttrd 9279 . . . . . . . . . . . 12
104 simprr 735 . . . . . . . . . . . 12
10593, 95, 97, 103, 104ltletrd 9281 . . . . . . . . . . 11
10693, 97ltnled 9271 . . . . . . . . . . 11
107105, 106mpbid 203 . . . . . . . . . 10
10896biantrurd 496 . . . . . . . . . . . 12
10982adantr 453 . . . . . . . . . . . . 13
110 ffn 5638 . . . . . . . . . . . . 13
111 elpreima 5898 . . . . . . . . . . . . 13
112109, 110, 1113syl 19 . . . . . . . . . . . 12
113108, 112bitr4d 249 . . . . . . . . . . 11
114 simplr 733 . . . . . . . . . . . 12
115 breq1 4246 . . . . . . . . . . . . 13
116115rspccv 3058 . . . . . . . . . . . 12
117114, 116syl 16 . . . . . . . . . . 11
118113, 117sylbid 208 . . . . . . . . . 10
119107, 118mtod 171 . . . . . . . . 9
120109, 96ffvelrnd 5919 . . . . . . . . . . 11
121 elnn0 10274 . . . . . . . . . . 11
122120, 121sylib 190 . . . . . . . . . 10
123122ord 368 . . . . . . . . 9
124119, 123mpd 15 . . . . . . . 8
1256, 81, 82, 92, 1241arithlem4 13345 . . . . . . 7
126125ex 425 . . . . . 6
127126rexlimdva 2837 . . . . 5
12880, 127mpd 15 . . . 4
129128rgen 2778 . . 3
130 dffo3 5932 . . 3
13144, 129, 130mpbir2an 888 . 2
132 df-f1o 5508 . 2
13363, 131, 132mpbir2an 888 1
Colors of variables: wff set class
Syntax hints:  -.wn 3  ->wi 4  <->wb 178  \/wo 359  /\wa 360  =wceq 1654  e.wcel 1728  A.wral 2712  E.wrex 2713  {crab 2716  C_wss 3309  ifcif 3765   class class class wbr 4243  e.cmpt 4301  `'ccnv 4918  domcdm 4919  "cima 4922  Fnwfn 5496  -->wf 5497  -1-1->wf1 5498  -onto->wfo 5499  -1-1-onto->wf1o 5500  `cfv 5501  (class class class)co 6129   cmap 7067   cfn 7158   cr 9040  0cc0 9041  1c1 9042   caddc 9044   clt 9171   cle 9172   cn 10051   cn0 10272   cz 10333   cuz 10539   cfz 11094   cfl 11252   cexp 11433   cdivides 12903   cprime 13130   cpc 13261
This theorem is referenced by:  1arith2  13347  sqff1o  21016
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1556  ax-5 1567  ax-17 1628  ax-9 1669  ax-8 1690  ax-13 1730  ax-14 1732  ax-6 1747  ax-7 1752  ax-11 1764  ax-12 1954  ax-ext 2424  ax-rep 4354  ax-sep 4364  ax-nul 4372  ax-pow 4416  ax-pr 4442  ax-un 4742  ax-cnex 9097  ax-resscn 9098  ax-1cn 9099  ax-icn 9100  ax-addcl 9101  ax-addrcl 9102  ax-mulcl 9103  ax-mulrcl 9104  ax-mulcom 9105  ax-addass 9106  ax-mulass 9107  ax-distr 9108  ax-i2m1 9109  ax-1ne0 9110  ax-1rid 9111  ax-rnegex 9112  ax-rrecex 9113  ax-cnre 9114  ax-pre-lttri 9115  ax-pre-lttrn 9116  ax-pre-ltadd 9117  ax-pre-mulgt0 9118  ax-pre-sup 9119
This theorem depends on definitions:  df-bi 179  df-or 361  df-an 362  df-3or 938  df-3an 939  df-tru 1329  df-fal 1330  df-ex 1552  df-nf 1555  df-sb 1661  df-eu 2292  df-mo 2293  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2568  df-ne 2608  df-nel 2609  df-ral 2717  df-rex 2718  df-reu 2719  df-rmo 2720  df-rab 2721  df-v 2967  df-sbc 3171  df-csb 3271  df-dif 3312  df-un 3314  df-in 3316  df-ss 3323  df-pss 3325  df-nul 3617  df-if 3766  df-pw 3828  df-sn 3847  df-pr 3848  df-tp 3849  df-op 3850  df-uni 4044  df-int 4080  df-iun 4124  df-br 4244  df-opab 4302  df-mpt 4303  df-tr 4337  df-eprel 4535  df-id 4539  df-po 4544  df-so 4545  df-fr 4582  df-we 4584  df-ord 4625  df-on 4626  df-lim 4627  df-suc 4628  df-om 4887  df-xp 4925  df-rel 4926  df-cnv 4927  df-co 4928  df-dm 4929  df-rn 4930  df-res 4931  df-ima 4932  df-iota 5464  df-fun 5503  df-fn 5504  df-f 5505  df-f1 5506  df-fo 5507  df-f1o 5508  df-fv 5509  df-ov 6132  df-oprab 6133  df-mpt2 6134  df-1st 6399  df-2nd 6400  df-riota 6599  df-recs 6682  df-rdg 6717  df-1o 6773  df-2o 6774  df-oadd 6777  df-er 6954  df-map 7069  df-en 7159  df-dom 7160  df-sdom 7161  df-fin 7162  df-sup 7495  df-pnf 9173  df-mnf 9174  df-xr 9175  df-ltxr 9176  df-le 9177  df-sub 9344  df-neg 9345  df-div 9729  df-nn 10052  df-2 10109  df-3 10110  df-n0 10273  df-z 10334  df-uz 10540  df-q 10626  df-rp 10664  df-fz 11095  df-fl 11253  df-mod 11302  df-seq 11375  df-exp 11434  df-cj 11955  df-re 11956  df-im 11957  df-sqr 12091  df-abs 12092  df-dvds 12904  df-gcd 13058  df-prm 13131  df-pc 13262
  Copyright terms: Public domain W3C validator