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

Theorem pwfseqlem5 8375
 Description: Lemma for pwfseq 8376. Although in some ways pwfseqlem4 8374 is the "main" part of the proof, one last aspect which makes up a remark in the original text is by far the hardest part to formalize. The main proof relies on the existence of an injection from the set of finite sequences on an infinite set to . Now this alone would not be difficult to prove; this is mostly the claim of fseqen 7744. However, what is needed for the proof is a canonical injection on these sets, so we have to start from scratch pulling together explicit bijections from the lemmas. If one attempts such a program, it will mostly go through, but there is one key step which is inherently nonconstructive, namely the proof of infxpen 7732. The resolution is not obvious, but it turns out that reversing an infinite ordinal's Cantor normal form absorbs all the non-leading terms (cnfcom3c 7499), which can be used to construct a pairing function explicitly using properties of the ordinal exponential (infxpenc 7735). (Contributed by Mario Carneiro, 31-May-2015.)
Hypotheses
Ref Expression
pwfseqlem5.g
pwfseqlem5.x
pwfseqlem5.h
pwfseqlem5.ps
pwfseqlem5.n har
pwfseqlem5.o OrdIso
pwfseqlem5.t
pwfseqlem5.p
pwfseqlem5.s seq𝜔
pwfseqlem5.q
pwfseqlem5.i
pwfseqlem5.k
Assertion
Ref Expression
pwfseqlem5
Distinct variable groups:   ,,   ,,,   ,,,   ,,,,,,,,,   ,,,,,,,   ,,   ,   ,,,,   ,,   ,,,,   ,,,,,
Allowed substitution hints:   (,,)   (,,,,,)   (,,,,,)   (,,,,,,)   (,,,,,,,,,)   (,,,,,,,)   (,,,,,,,,,)   (,,,,,,,)   (,,,,,,)   (,,,,,,,,,)   (,,,,,,,)   (,,,,,,,,)   (,,,,)   (,,,,,,,,,)

Proof of Theorem pwfseqlem5
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 pwfseqlem5.g . 2
2 pwfseqlem5.x . 2
3 pwfseqlem5.h . 2
4 pwfseqlem5.ps . 2
5 vex 2867 . . . . . . . . . . 11
6 simprl3 1002 . . . . . . . . . . . 12
74, 6sylan2b 461 . . . . . . . . . . 11
8 pwfseqlem5.o . . . . . . . . . . . 12 OrdIso
98oiiso 7342 . . . . . . . . . . 11
105, 7, 9sylancr 644 . . . . . . . . . 10
11 isof1o 5909 . . . . . . . . . 10
1210, 11syl 15 . . . . . . . . 9
138oion 7341 . . . . . . . . . . . . 13
145, 13ax-mp 8 . . . . . . . . . . . 12
1514a1i 10 . . . . . . . . . . 11
168oien 7343 . . . . . . . . . . . . 13
175, 7, 16sylancr 644 . . . . . . . . . . . 12
181adantr 451 . . . . . . . . . . . . . . . 16
19 omex 7434 . . . . . . . . . . . . . . . . 17
20 ovex 5970 . . . . . . . . . . . . . . . . 17
2119, 20iunex 5857 . . . . . . . . . . . . . . . 16
22 f1dmex 5837 . . . . . . . . . . . . . . . 16
2318, 21, 22sylancl 643 . . . . . . . . . . . . . . 15
24 pwexb 4646 . . . . . . . . . . . . . . 15
2523, 24sylibr 203 . . . . . . . . . . . . . 14
26 simprl1 1000 . . . . . . . . . . . . . . 15
274, 26sylan2b 461 . . . . . . . . . . . . . 14
28 ssdomg 6995 . . . . . . . . . . . . . 14
2925, 27, 28sylc 56 . . . . . . . . . . . . 13
30 canth2g 7103 . . . . . . . . . . . . . 14
31 sdomdom 6977 . . . . . . . . . . . . . 14
3225, 30, 313syl 18 . . . . . . . . . . . . 13
33 domtr 7002 . . . . . . . . . . . . 13
3429, 32, 33syl2anc 642 . . . . . . . . . . . 12
35 endomtr 7007 . . . . . . . . . . . 12
3617, 34, 35syl2anc 642 . . . . . . . . . . 11
37 elharval 7367 . . . . . . . . . . 11 har
3815, 36, 37sylanbrc 645 . . . . . . . . . 10 har
39 pwfseqlem5.n . . . . . . . . . . 11 har
4039adantr 451 . . . . . . . . . 10 har
41 cardom 7709 . . . . . . . . . . . 12
42 simprr 733 . . . . . . . . . . . . . . 15
434, 42sylan2b 461 . . . . . . . . . . . . . 14
44 ensym 6998 . . . . . . . . . . . . . . 15
4517, 44syl 15 . . . . . . . . . . . . . 14
46 domentr 7008 . . . . . . . . . . . . . 14
4743, 45, 46syl2anc 642 . . . . . . . . . . . . 13
48 omelon 7437 . . . . . . . . . . . . . . 15
49 onenon 7672 . . . . . . . . . . . . . . 15
5048, 49ax-mp 8 . . . . . . . . . . . . . 14
51 onenon 7672 . . . . . . . . . . . . . . 15
5214, 51mp1i 11 . . . . . . . . . . . . . 14
53 carddom2 7700 . . . . . . . . . . . . . 14
5450, 52, 53sylancr 644 . . . . . . . . . . . . 13
5547, 54mpbird 223 . . . . . . . . . . . 12
5641, 55syl5eqssr 3299 . . . . . . . . . . 11
57 cardonle 7680 . . . . . . . . . . . 12
5815, 57syl 15 . . . . . . . . . . 11
5956, 58sstrd 3265 . . . . . . . . . 10
60 sseq2 3276 . . . . . . . . . . . 12
61 fveq2 5608 . . . . . . . . . . . . . 14
62 f1oeq1 5546 . . . . . . . . . . . . . 14
6361, 62syl 15 . . . . . . . . . . . . 13
64 xpeq12 4790 . . . . . . . . . . . . . . 15
6564anidms 626 . . . . . . . . . . . . . 14
66 f1oeq2 5547 . . . . . . . . . . . . . 14
6765, 66syl 15 . . . . . . . . . . . . 13
68 f1oeq3 5548 . . . . . . . . . . . . 13
6963, 67, 683bitrd 270 . . . . . . . . . . . 12
7060, 69imbi12d 311 . . . . . . . . . . 11
7170rspcv 2956 . . . . . . . . . 10 har har
7238, 40, 59, 71syl3c 57 . . . . . . . . 9
73 f1oco 5579 . . . . . . . . 9
7412, 72, 73syl2anc 642 . . . . . . . 8
75 f1of 5555 . . . . . . . . . . . . . . 15
7612, 75syl 15 . . . . . . . . . . . . . 14
7776feqmptd 5658 . . . . . . . . . . . . 13
78 f1oeq1 5546 . . . . . . . . . . . . 13
7977, 78syl 15 . . . . . . . . . . . 12
8012, 79mpbid 201 . . . . . . . . . . 11
8176feqmptd 5658 . . . . . . . . . . . . 13
82 f1oeq1 5546 . . . . . . . . . . . . 13
8381, 82syl 15 . . . . . . . . . . . 12
8412, 83mpbid 201 . . . . . . . . . . 11
8580, 84xpf1o 7111 . . . . . . . . . 10
86 pwfseqlem5.t . . . . . . . . . . 11
87 f1oeq1 5546 . . . . . . . . . . 11
8886, 87ax-mp 8 . . . . . . . . . 10
8985, 88sylibr 203 . . . . . . . . 9
90 f1ocnv 5568 . . . . . . . . 9
9189, 90syl 15 . . . . . . . 8
92 f1oco 5579 . . . . . . . 8
9374, 91, 92syl2anc 642 . . . . . . 7
94 pwfseqlem5.p . . . . . . . 8
95 f1oeq1 5546 . . . . . . . 8
9694, 95ax-mp 8 . . . . . . 7
9793, 96sylibr 203 . . . . . 6
98 f1of1 5554 . . . . . 6
9997, 98syl 15 . . . . 5
100 f1of1 5554 . . . . . . . . . . . . 13
10112, 100syl 15 . . . . . . . . . . . 12
102 f1ssres 5527 . . . . . . . . . . . 12
103101, 59, 102syl2anc 642 . . . . . . . . . . 11
104 f1f1orn 5566 . . . . . . . . . . 11
105103, 104syl 15 . . . . . . . . . 10
10676, 59feqresmpt 5659 . . . . . . . . . . 11
107 f1oeq1 5546 . . . . . . . . . . 11
108106, 107syl 15 . . . . . . . . . 10
109105, 108mpbid 201 . . . . . . . . 9
110 mptresid 5086 . . . . . . . . . 10
111 f1oi 5594 . . . . . . . . . . 11
112 f1oeq1 5546 . . . . . . . . . . 11
113111, 112mpbiri 224 . . . . . . . . . 10
114110, 113mp1i 11 . . . . . . . . 9
115109, 114xpf1o 7111 . . . . . . . 8
116 pwfseqlem5.i . . . . . . . . 9
117 f1oeq1 5546 . . . . . . . . 9
118116, 117ax-mp 8 . . . . . . . 8
119115, 118sylibr 203 . . . . . . 7
120 f1of1 5554 . . . . . . 7
121119, 120syl 15 . . . . . 6
122 f1f 5520 . . . . . . . 8
123 frn 5478 . . . . . . . 8
124103, 122, 1233syl 18 . . . . . . 7
125 xpss1 4877 . . . . . . 7
126124, 125syl 15 . . . . . 6
127 f1ss 5525 . . . . . 6
128121, 126, 127syl2anc 642 . . . . 5
129 f1co 5529 . . . . 5
13099, 128, 129syl2anc 642 . . . 4
1315a1i 10 . . . . 5
132 peano1 4757 . . . . . . . 8
133132a1i 10 . . . . . . 7
13459, 133sseldd 3257 . . . . . 6
135 ffvelrn 5746 . . . . . 6
13676, 134, 135syl2anc 642 . . . . 5
137 pwfseqlem5.s . . . . 5 seq𝜔
138 pwfseqlem5.q . . . . 5
139131, 136, 97, 137, 138fseqenlem2 7742 . . . 4
140 f1co 5529 . . . 4
141130, 139, 140syl2anc 642 . . 3
142 pwfseqlem5.k . . . 4
143 f1eq1 5515 . . . 4
144142, 143ax-mp 8 . . 3
145141, 144sylibr 203 . 2
146 eqid 2358 . 2
147 eqid 2358 . 2
148 eqid 2358 . . 3
149148fpwwe2cbv 8342 . 2
150 eqid 2358 . 2
1511, 2, 3, 4, 145, 146, 147, 149, 150pwfseqlem4 8374 1
 Colors of variables: wff set class Syntax hints:   wn 3   wi 4   wb 176   wa 358   w3a 934   wceq 1642   wcel 1710  wral 2619  crab 2623  cvv 2864  wsbc 3067   cin 3227   wss 3228  c0 3531  cif 3641  cpw 3701  csn 3716  cop 3719  cuni 3908  cint 3943  ciun 3986   class class class wbr 4104  copab 4157   cmpt 4158   cep 4385   cid 4386   wwe 4433  con0 4474   csuc 4476  com 4738   cxp 4769  ccnv 4770   cdm 4771   crn 4772   cres 4773  cima 4774   ccom 4775  wf 5333  wf1 5334  wf1o 5336  cfv 5337   wiso 5338  (class class class)co 5945   cmpt2 5947  seq𝜔cseqom 6546   cmap 6860   cen 6948   cdom 6949   csdm 6950  cfn 6951  OrdIsocoi 7314  harchar 7360  ccrd 7658 This theorem is referenced by:  pwfseq  8376 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1546  ax-5 1557  ax-17 1616  ax-9 1654  ax-8 1675  ax-13 1712  ax-14 1714  ax-6 1729  ax-7 1734  ax-11 1746  ax-12 1930  ax-ext 2339  ax-rep 4212  ax-sep 4222  ax-nul 4230  ax-pow 4269  ax-pr 4295  ax-un 4594  ax-inf2 7432 This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1319  df-ex 1542  df-nf 1545  df-sb 1649  df-eu 2213  df-mo 2214  df-clab 2345  df-cleq 2351  df-clel 2354  df-nfc 2483  df-ne 2523  df-ral 2624  df-rex 2625  df-reu 2626  df-rmo 2627  df-rab 2628  df-v 2866  df-sbc 3068  df-csb 3158  df-dif 3231  df-un 3233  df-in 3235  df-ss 3242  df-pss 3244  df-nul 3532  df-if 3642  df-pw 3703  df-sn 3722  df-pr 3723  df-tp 3724  df-op 3725  df-uni 3909  df-int 3944  df-iun 3988  df-br 4105  df-opab 4159  df-mpt 4160  df-tr 4195  df-eprel 4387  df-id 4391  df-po 4396  df-so 4397  df-fr 4434  df-se 4435  df-we 4436  df-ord 4477  df-on 4478  df-lim 4479  df-suc 4480  df-om 4739  df-xp 4777  df-rel 4778  df-cnv 4779  df-co 4780  df-dm 4781  df-rn 4782  df-res 4783  df-ima 4784  df-iota 5301  df-fun 5339  df-fn 5340  df-f 5341  df-f1 5342  df-fo 5343  df-f1o 5344  df-fv 5345  df-isom 5346  df-ov 5948  df-oprab 5949  df-mpt2 5950  df-1st 6209  df-2nd 6210  df-riota 6391  df-recs 6475  df-rdg 6510  df-seqom 6547  df-1o 6566  df-er 6747  df-map 6862  df-en 6952  df-dom 6953  df-sdom 6954  df-fin 6955  df-oi 7315  df-har 7362  df-card 7662
 Copyright terms: Public domain W3C validator