Users' Mathboxes Mathbox for Mario Carneiro < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  subfacp1lem3 Structured version   Visualization version   GIF version

Theorem subfacp1lem3 32327
Description: Lemma for subfacp1 32331. In subfacp1lem6 32330 we cut up the set of all derangements on 1...(𝑁 + 1) first according to the value at 1, and then by whether or not (𝑓‘(𝑓‘1)) = 1. In this lemma, we show that the subset of all 𝑁 + 1 derangements that satisfy this for fixed 𝑀 = (𝑓‘1) is in bijection with 𝑁 − 1 derangements, by simply dropping the 𝑥 = 1 and 𝑥 = 𝑀 points from the function to get a derangement on 𝐾 = (1...(𝑁 − 1)) ∖ {1, 𝑀}. (Contributed by Mario Carneiro, 23-Jan-2015.)
Hypotheses
Ref Expression
derang.d 𝐷 = (𝑥 ∈ Fin ↦ (♯‘{𝑓 ∣ (𝑓:𝑥1-1-onto𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) ≠ 𝑦)}))
subfac.n 𝑆 = (𝑛 ∈ ℕ0 ↦ (𝐷‘(1...𝑛)))
subfacp1lem.a 𝐴 = {𝑓 ∣ (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦)}
subfacp1lem1.n (𝜑𝑁 ∈ ℕ)
subfacp1lem1.m (𝜑𝑀 ∈ (2...(𝑁 + 1)))
subfacp1lem1.x 𝑀 ∈ V
subfacp1lem1.k 𝐾 = ((2...(𝑁 + 1)) ∖ {𝑀})
subfacp1lem3.b 𝐵 = {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)}
subfacp1lem3.c 𝐶 = {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}
Assertion
Ref Expression
subfacp1lem3 (𝜑 → (♯‘𝐵) = (𝑆‘(𝑁 − 1)))
Distinct variable groups:   𝑓,𝑔,𝑛,𝑥,𝑦,𝐴   𝑓,𝑁,𝑔,𝑛,𝑥,𝑦   𝐵,𝑓,𝑔,𝑥,𝑦   𝑥,𝐶,𝑦   𝜑,𝑥,𝑦   𝐷,𝑛   𝑓,𝐾,𝑛,𝑥,𝑦   𝑓,𝑀,𝑔,𝑥,𝑦   𝑆,𝑛,𝑥,𝑦
Allowed substitution hints:   𝜑(𝑓,𝑔,𝑛)   𝐵(𝑛)   𝐶(𝑓,𝑔,𝑛)   𝐷(𝑥,𝑦,𝑓,𝑔)   𝑆(𝑓,𝑔)   𝐾(𝑔)   𝑀(𝑛)

Proof of Theorem subfacp1lem3
Dummy variables 𝑏 𝑐 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 subfacp1lem.a . . . . . . . 8 𝐴 = {𝑓 ∣ (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦)}
2 fzfi 13330 . . . . . . . . 9 (1...(𝑁 + 1)) ∈ Fin
3 deranglem 32311 . . . . . . . . 9 ((1...(𝑁 + 1)) ∈ Fin → {𝑓 ∣ (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦)} ∈ Fin)
42, 3ax-mp 5 . . . . . . . 8 {𝑓 ∣ (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦)} ∈ Fin
51, 4eqeltri 2909 . . . . . . 7 𝐴 ∈ Fin
6 subfacp1lem3.b . . . . . . . 8 𝐵 = {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)}
7 ssrab2 4055 . . . . . . . 8 {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)} ⊆ 𝐴
86, 7eqsstri 4000 . . . . . . 7 𝐵𝐴
9 ssfi 8727 . . . . . . 7 ((𝐴 ∈ Fin ∧ 𝐵𝐴) → 𝐵 ∈ Fin)
105, 8, 9mp2an 688 . . . . . 6 𝐵 ∈ Fin
1110elexi 3514 . . . . 5 𝐵 ∈ V
1211a1i 11 . . . 4 (𝜑𝐵 ∈ V)
13 subfacp1lem3.c . . . . . . 7 𝐶 = {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}
14 subfacp1lem1.k . . . . . . . . 9 𝐾 = ((2...(𝑁 + 1)) ∖ {𝑀})
15 fzfi 13330 . . . . . . . . . 10 (2...(𝑁 + 1)) ∈ Fin
16 diffi 8739 . . . . . . . . . 10 ((2...(𝑁 + 1)) ∈ Fin → ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin)
1715, 16ax-mp 5 . . . . . . . . 9 ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin
1814, 17eqeltri 2909 . . . . . . . 8 𝐾 ∈ Fin
19 deranglem 32311 . . . . . . . 8 (𝐾 ∈ Fin → {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin)
2018, 19ax-mp 5 . . . . . . 7 {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin
2113, 20eqeltri 2909 . . . . . 6 𝐶 ∈ Fin
2221elexi 3514 . . . . 5 𝐶 ∈ V
2322a1i 11 . . . 4 (𝜑𝐶 ∈ V)
24 simpr 485 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → 𝑏𝐵)
25 fveq1 6663 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔‘1) = (𝑏‘1))
2625eqeq1d 2823 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔‘1) = 𝑀 ↔ (𝑏‘1) = 𝑀))
27 fveq1 6663 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔𝑀) = (𝑏𝑀))
2827eqeq1d 2823 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔𝑀) = 1 ↔ (𝑏𝑀) = 1))
2926, 28anbi12d 630 . . . . . . . . . . . . . 14 (𝑔 = 𝑏 → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3029, 6elrab2 3682 . . . . . . . . . . . . 13 (𝑏𝐵 ↔ (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3124, 30sylib 219 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3231simpld 495 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏𝐴)
33 vex 3498 . . . . . . . . . . . 12 𝑏 ∈ V
34 f1oeq1 6598 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
35 fveq1 6663 . . . . . . . . . . . . . . 15 (𝑓 = 𝑏 → (𝑓𝑦) = (𝑏𝑦))
3635neeq1d 3075 . . . . . . . . . . . . . 14 (𝑓 = 𝑏 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
3736ralbidv 3197 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
3834, 37anbi12d 630 . . . . . . . . . . . 12 (𝑓 = 𝑏 → ((𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦) ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)))
3933, 38, 1elab2 3669 . . . . . . . . . . 11 (𝑏𝐴 ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
4032, 39sylib 219 . . . . . . . . . 10 ((𝜑𝑏𝐵) → (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
4140simpld 495 . . . . . . . . 9 ((𝜑𝑏𝐵) → 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
42 f1of1 6608 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)))
43 df-f1 6354 . . . . . . . . . 10 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) ↔ (𝑏:(1...(𝑁 + 1))⟶(1...(𝑁 + 1)) ∧ Fun 𝑏))
4443simprbi 497 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) → Fun 𝑏)
4541, 42, 443syl 18 . . . . . . . 8 ((𝜑𝑏𝐵) → Fun 𝑏)
46 f1ofn 6610 . . . . . . . . . . . 12 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏 Fn (1...(𝑁 + 1)))
4741, 46syl 17 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏 Fn (1...(𝑁 + 1)))
48 fnresdm 6460 . . . . . . . . . . 11 (𝑏 Fn (1...(𝑁 + 1)) → (𝑏 ↾ (1...(𝑁 + 1))) = 𝑏)
49 f1oeq1 6598 . . . . . . . . . . 11 ((𝑏 ↾ (1...(𝑁 + 1))) = 𝑏 → ((𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
5047, 48, 493syl 18 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ((𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
5141, 50mpbird 258 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
52 f1ofo 6616 . . . . . . . . 9 ((𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–onto→(1...(𝑁 + 1)))
5351, 52syl 17 . . . . . . . 8 ((𝜑𝑏𝐵) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–onto→(1...(𝑁 + 1)))
54 ssun2 4148 . . . . . . . . . . . . 13 {1, 𝑀} ⊆ (𝐾 ∪ {1, 𝑀})
55 derang.d . . . . . . . . . . . . . . 15 𝐷 = (𝑥 ∈ Fin ↦ (♯‘{𝑓 ∣ (𝑓:𝑥1-1-onto𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) ≠ 𝑦)}))
56 subfac.n . . . . . . . . . . . . . . 15 𝑆 = (𝑛 ∈ ℕ0 ↦ (𝐷‘(1...𝑛)))
57 subfacp1lem1.n . . . . . . . . . . . . . . 15 (𝜑𝑁 ∈ ℕ)
58 subfacp1lem1.m . . . . . . . . . . . . . . 15 (𝜑𝑀 ∈ (2...(𝑁 + 1)))
59 subfacp1lem1.x . . . . . . . . . . . . . . 15 𝑀 ∈ V
6055, 56, 1, 57, 58, 59, 14subfacp1lem1 32324 . . . . . . . . . . . . . 14 (𝜑 → ((𝐾 ∩ {1, 𝑀}) = ∅ ∧ (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)) ∧ (♯‘𝐾) = (𝑁 − 1)))
6160simp2d 1135 . . . . . . . . . . . . 13 (𝜑 → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
6254, 61sseqtrid 4018 . . . . . . . . . . . 12 (𝜑 → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
6362adantr 481 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
64 fnssres 6464 . . . . . . . . . . 11 ((𝑏 Fn (1...(𝑁 + 1)) ∧ {1, 𝑀} ⊆ (1...(𝑁 + 1))) → (𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀})
6547, 63, 64syl2anc 584 . . . . . . . . . 10 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀})
6631simprd 496 . . . . . . . . . . . . . 14 ((𝜑𝑏𝐵) → ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1))
6766simpld 495 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → (𝑏‘1) = 𝑀)
6859prid2 4693 . . . . . . . . . . . . 13 𝑀 ∈ {1, 𝑀}
6967, 68syl6eqel 2921 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏‘1) ∈ {1, 𝑀})
7066simprd 496 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → (𝑏𝑀) = 1)
71 1ex 10626 . . . . . . . . . . . . . 14 1 ∈ V
7271prid1 4692 . . . . . . . . . . . . 13 1 ∈ {1, 𝑀}
7370, 72syl6eqel 2921 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝑀) ∈ {1, 𝑀})
74 fveq2 6664 . . . . . . . . . . . . . 14 (𝑥 = 1 → (𝑏𝑥) = (𝑏‘1))
7574eleq1d 2897 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏‘1) ∈ {1, 𝑀}))
76 fveq2 6664 . . . . . . . . . . . . . 14 (𝑥 = 𝑀 → (𝑏𝑥) = (𝑏𝑀))
7776eleq1d 2897 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑀) ∈ {1, 𝑀}))
7871, 59, 75, 77ralpr 4630 . . . . . . . . . . . 12 (∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀} ↔ ((𝑏‘1) ∈ {1, 𝑀} ∧ (𝑏𝑀) ∈ {1, 𝑀}))
7969, 73, 78sylanbrc 583 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
80 fvres 6683 . . . . . . . . . . . . 13 (𝑥 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑥) = (𝑏𝑥))
8180eleq1d 2897 . . . . . . . . . . . 12 (𝑥 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑥) ∈ {1, 𝑀}))
8281ralbiia 3164 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
8379, 82sylibr 235 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀})
84 ffnfv 6875 . . . . . . . . . 10 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀}))
8565, 83, 84sylanbrc 583 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀})
86 fveqeq2 6673 . . . . . . . . . . . . 13 (𝑦 = 𝑀 → ((𝑏𝑦) = 1 ↔ (𝑏𝑀) = 1))
8786rspcev 3622 . . . . . . . . . . . 12 ((𝑀 ∈ {1, 𝑀} ∧ (𝑏𝑀) = 1) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
8868, 70, 87sylancr 587 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
89 fveqeq2 6673 . . . . . . . . . . . . 13 (𝑦 = 1 → ((𝑏𝑦) = 𝑀 ↔ (𝑏‘1) = 𝑀))
9089rspcev 3622 . . . . . . . . . . . 12 ((1 ∈ {1, 𝑀} ∧ (𝑏‘1) = 𝑀) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
9172, 67, 90sylancr 587 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
92 eqeq2 2833 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 1))
9392rexbidv 3297 . . . . . . . . . . . 12 (𝑥 = 1 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1))
94 eqeq2 2833 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑀))
9594rexbidv 3297 . . . . . . . . . . . 12 (𝑥 = 𝑀 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9671, 59, 93, 95ralpr 4630 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1 ∧ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9788, 91, 96sylanbrc 583 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
98 eqcom 2828 . . . . . . . . . . . . 13 (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥)
99 fvres 6683 . . . . . . . . . . . . . 14 (𝑦 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑦) = (𝑏𝑦))
10099eqeq1d 2823 . . . . . . . . . . . . 13 (𝑦 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑥))
10198, 100syl5bb 284 . . . . . . . . . . . 12 (𝑦 ∈ {1, 𝑀} → (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ (𝑏𝑦) = 𝑥))
102101rexbiia 3246 . . . . . . . . . . 11 (∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
103102ralbii 3165 . . . . . . . . . 10 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
10497, 103sylibr 235 . . . . . . . . 9 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦))
105 dffo3 6861 . . . . . . . . 9 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦)))
10685, 104, 105sylanbrc 583 . . . . . . . 8 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀})
107 resdif 6629 . . . . . . . 8 ((Fun 𝑏 ∧ (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–onto→(1...(𝑁 + 1)) ∧ (𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀}) → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}))
10845, 53, 106, 107syl3anc 1363 . . . . . . 7 ((𝜑𝑏𝐵) → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}))
109 uncom 4128 . . . . . . . . . . 11 ({1, 𝑀} ∪ 𝐾) = (𝐾 ∪ {1, 𝑀})
110109, 61syl5eq 2868 . . . . . . . . . 10 (𝜑 → ({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)))
111 incom 4177 . . . . . . . . . . . 12 ({1, 𝑀} ∩ 𝐾) = (𝐾 ∩ {1, 𝑀})
11260simp1d 1134 . . . . . . . . . . . 12 (𝜑 → (𝐾 ∩ {1, 𝑀}) = ∅)
113111, 112syl5eq 2868 . . . . . . . . . . 11 (𝜑 → ({1, 𝑀} ∩ 𝐾) = ∅)
114 uneqdifeq 4436 . . . . . . . . . . 11 (({1, 𝑀} ⊆ (1...(𝑁 + 1)) ∧ ({1, 𝑀} ∩ 𝐾) = ∅) → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
11562, 113, 114syl2anc 584 . . . . . . . . . 10 (𝜑 → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
116110, 115mpbid 233 . . . . . . . . 9 (𝜑 → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
117116adantr 481 . . . . . . . 8 ((𝜑𝑏𝐵) → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
118 reseq2 5842 . . . . . . . . . 10 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})) = (𝑏𝐾))
119 f1oeq1 6598 . . . . . . . . . 10 ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})) = (𝑏𝐾) → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
120118, 119syl 17 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
121 f1oeq2 6599 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
122 f1oeq3 6600 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
123120, 121, 1223bitrd 306 . . . . . . . 8 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
124117, 123syl 17 . . . . . . 7 ((𝜑𝑏𝐵) → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
125108, 124mpbid 233 . . . . . 6 ((𝜑𝑏𝐵) → (𝑏𝐾):𝐾1-1-onto𝐾)
126 ssun1 4147 . . . . . . . . 9 𝐾 ⊆ (𝐾 ∪ {1, 𝑀})
127126, 61sseqtrid 4018 . . . . . . . 8 (𝜑𝐾 ⊆ (1...(𝑁 + 1)))
128127adantr 481 . . . . . . 7 ((𝜑𝑏𝐵) → 𝐾 ⊆ (1...(𝑁 + 1)))
12940simprd 496 . . . . . . 7 ((𝜑𝑏𝐵) → ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)
130 ssralv 4032 . . . . . . 7 (𝐾 ⊆ (1...(𝑁 + 1)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦 → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
131128, 129, 130sylc 65 . . . . . 6 ((𝜑𝑏𝐵) → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)
13233resex 5893 . . . . . . 7 (𝑏𝐾) ∈ V
133 f1oeq1 6598 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (𝑓:𝐾1-1-onto𝐾 ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
134 fveq1 6663 . . . . . . . . . . 11 (𝑓 = (𝑏𝐾) → (𝑓𝑦) = ((𝑏𝐾)‘𝑦))
135 fvres 6683 . . . . . . . . . . 11 (𝑦𝐾 → ((𝑏𝐾)‘𝑦) = (𝑏𝑦))
136134, 135sylan9eq 2876 . . . . . . . . . 10 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → (𝑓𝑦) = (𝑏𝑦))
137136neeq1d 3075 . . . . . . . . 9 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
138137ralbidva 3196 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
139133, 138anbi12d 630 . . . . . . 7 (𝑓 = (𝑏𝐾) → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)))
140132, 139, 13elab2 3669 . . . . . 6 ((𝑏𝐾) ∈ 𝐶 ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
141125, 131, 140sylanbrc 583 . . . . 5 ((𝜑𝑏𝐵) → (𝑏𝐾) ∈ 𝐶)
142141ex 413 . . . 4 (𝜑 → (𝑏𝐵 → (𝑏𝐾) ∈ 𝐶))
14357adantr 481 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑁 ∈ ℕ)
14458adantr 481 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑀 ∈ (2...(𝑁 + 1)))
145 eqid 2821 . . . . . . . . 9 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})
146 simpr 485 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑐𝐶)
147 vex 3498 . . . . . . . . . . . 12 𝑐 ∈ V
148 f1oeq1 6598 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (𝑓:𝐾1-1-onto𝐾𝑐:𝐾1-1-onto𝐾))
149 fveq1 6663 . . . . . . . . . . . . . . 15 (𝑓 = 𝑐 → (𝑓𝑦) = (𝑐𝑦))
150149neeq1d 3075 . . . . . . . . . . . . . 14 (𝑓 = 𝑐 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑐𝑦) ≠ 𝑦))
151150ralbidv 3197 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
152148, 151anbi12d 630 . . . . . . . . . . . 12 (𝑓 = 𝑐 → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)))
153147, 152, 13elab2 3669 . . . . . . . . . . 11 (𝑐𝐶 ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
154146, 153sylib 219 . . . . . . . . . 10 ((𝜑𝑐𝐶) → (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
155154simpld 495 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑐:𝐾1-1-onto𝐾)
15655, 56, 1, 143, 144, 59, 14, 145, 155subfacp1lem2a 32325 . . . . . . . 8 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
157156simp1d 1134 . . . . . . 7 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
15855, 56, 1, 143, 144, 59, 14, 145, 155subfacp1lem2b 32326 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = (𝑐𝑦))
159154simprd 496 . . . . . . . . . . . 12 ((𝜑𝑐𝐶) → ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)
160159r19.21bi 3208 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → (𝑐𝑦) ≠ 𝑦)
161158, 160eqnetrd 3083 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
162161ralrimiva 3182 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
163156simp2d 1135 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
164 elfzuz 12894 . . . . . . . . . . . . 13 (𝑀 ∈ (2...(𝑁 + 1)) → 𝑀 ∈ (ℤ‘2))
165 eluz2b3 12311 . . . . . . . . . . . . . 14 (𝑀 ∈ (ℤ‘2) ↔ (𝑀 ∈ ℕ ∧ 𝑀 ≠ 1))
166165simprbi 497 . . . . . . . . . . . . 13 (𝑀 ∈ (ℤ‘2) → 𝑀 ≠ 1)
16758, 164, 1663syl 18 . . . . . . . . . . . 12 (𝜑𝑀 ≠ 1)
168167adantr 481 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑀 ≠ 1)
169163, 168eqnetrd 3083 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1)
170156simp3d 1136 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
171168necomd 3071 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 1 ≠ 𝑀)
172170, 171eqnetrd 3083 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀)
173 fveq2 6664 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
174 id 22 . . . . . . . . . . . 12 (𝑦 = 1 → 𝑦 = 1)
175173, 174neeq12d 3077 . . . . . . . . . . 11 (𝑦 = 1 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1))
176 fveq2 6664 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
177 id 22 . . . . . . . . . . . 12 (𝑦 = 𝑀𝑦 = 𝑀)
178176, 177neeq12d 3077 . . . . . . . . . . 11 (𝑦 = 𝑀 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
17971, 59, 175, 178ralpr 4630 . . . . . . . . . 10 (∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
180169, 172, 179sylanbrc 583 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
181 ralunb 4166 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ∧ ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
182162, 180, 181sylanbrc 583 . . . . . . . 8 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
18361adantr 481 . . . . . . . . 9 ((𝜑𝑐𝐶) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
184183raleqdv 3416 . . . . . . . 8 ((𝜑𝑐𝐶) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
185182, 184mpbid 233 . . . . . . 7 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
186 prex 5324 . . . . . . . . 9 {⟨1, 𝑀⟩, ⟨𝑀, 1⟩} ∈ V
187147, 186unex 7457 . . . . . . . 8 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ V
188 f1oeq1 6598 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
189 fveq1 6663 . . . . . . . . . . 11 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
190189neeq1d 3075 . . . . . . . . . 10 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑓𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
191190ralbidv 3197 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
192188, 191anbi12d 630 . . . . . . . 8 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦) ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)))
193187, 192, 1elab2 3669 . . . . . . 7 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
194157, 185, 193sylanbrc 583 . . . . . 6 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴)
195163, 170jca 512 . . . . . 6 ((𝜑𝑐𝐶) → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
196 fveq1 6663 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
197196eqeq1d 2823 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔‘1) = 𝑀 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀))
198 fveq1 6663 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
199198eqeq1d 2823 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔𝑀) = 1 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
200197, 199anbi12d 630 . . . . . . 7 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
201200, 6elrab2 3682 . . . . . 6 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ∧ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
202194, 195, 201sylanbrc 583 . . . . 5 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵)
203202ex 413 . . . 4 (𝜑 → (𝑐𝐶 → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵))
20467adantrr 713 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = 𝑀)
205163adantrl 712 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
206204, 205eqtr4d 2859 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
20770adantrr 713 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = 1)
208170adantrl 712 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
209207, 208eqtr4d 2859 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
210 fveq2 6664 . . . . . . . . . . . . 13 (𝑦 = 1 → (𝑏𝑦) = (𝑏‘1))
211210, 173eqeq12d 2837 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1)))
212 fveq2 6664 . . . . . . . . . . . . 13 (𝑦 = 𝑀 → (𝑏𝑦) = (𝑏𝑀))
213212, 176eqeq12d 2837 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
21471, 59, 211, 213ralpr 4630 . . . . . . . . . . 11 (∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ((𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ∧ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
215206, 209, 214sylanbrc 583 . . . . . . . . . 10 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
216215biantrud 532 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))))
217 ralunb 4166 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
218216, 217syl6bbr 290 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
219158eqeq2d 2832 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
220219ralbidva 3196 . . . . . . . . 9 ((𝜑𝑐𝐶) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
221220adantrl 712 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
22261adantr 481 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
223222raleqdv 3416 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
224218, 221, 2233bitr3rd 311 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
225135eqeq2d 2832 . . . . . . . . 9 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑐𝑦) = (𝑏𝑦)))
226 eqcom 2828 . . . . . . . . 9 ((𝑐𝑦) = (𝑏𝑦) ↔ (𝑏𝑦) = (𝑐𝑦))
227225, 226syl6bb 288 . . . . . . . 8 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
228227ralbiia 3164 . . . . . . 7 (∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦))
229224, 228syl6bbr 290 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
23047adantrr 713 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑏 Fn (1...(𝑁 + 1)))
231157adantrl 712 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
232 f1ofn 6610 . . . . . . . 8 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1)))
233231, 232syl 17 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1)))
234 eqfnfv 6795 . . . . . . 7 ((𝑏 Fn (1...(𝑁 + 1)) ∧ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1))) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
235230, 233, 234syl2anc 584 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
236155adantrl 712 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐:𝐾1-1-onto𝐾)
237 f1ofn 6610 . . . . . . . 8 (𝑐:𝐾1-1-onto𝐾𝑐 Fn 𝐾)
238236, 237syl 17 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐 Fn 𝐾)
239127adantr 481 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝐾 ⊆ (1...(𝑁 + 1)))
240 fnssres 6464 . . . . . . . 8 ((𝑏 Fn (1...(𝑁 + 1)) ∧ 𝐾 ⊆ (1...(𝑁 + 1))) → (𝑏𝐾) Fn 𝐾)
241230, 239, 240syl2anc 584 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝐾) Fn 𝐾)
242 eqfnfv 6795 . . . . . . 7 ((𝑐 Fn 𝐾 ∧ (𝑏𝐾) Fn 𝐾) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
243238, 241, 242syl2anc 584 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
244229, 235, 2433bitr4d 312 . . . . 5 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ 𝑐 = (𝑏𝐾)))
245244ex 413 . . . 4 (𝜑 → ((𝑏𝐵𝑐𝐶) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ 𝑐 = (𝑏𝐾))))
24612, 23, 142, 203, 245en3d 8535 . . 3 (𝜑𝐵𝐶)
247 hashen 13697 . . . 4 ((𝐵 ∈ Fin ∧ 𝐶 ∈ Fin) → ((♯‘𝐵) = (♯‘𝐶) ↔ 𝐵𝐶))
24810, 21, 247mp2an 688 . . 3 ((♯‘𝐵) = (♯‘𝐶) ↔ 𝐵𝐶)
249246, 248sylibr 235 . 2 (𝜑 → (♯‘𝐵) = (♯‘𝐶))
25013fveq2i 6667 . . . 4 (♯‘𝐶) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25155derangval 32312 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}))
25218, 251ax-mp 5 . . . 4 (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25355, 56derangen2 32319 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (𝑆‘(♯‘𝐾)))
25418, 253ax-mp 5 . . . 4 (𝐷𝐾) = (𝑆‘(♯‘𝐾))
255250, 252, 2543eqtr2ri 2851 . . 3 (𝑆‘(♯‘𝐾)) = (♯‘𝐶)
25660simp3d 1136 . . . 4 (𝜑 → (♯‘𝐾) = (𝑁 − 1))
257256fveq2d 6668 . . 3 (𝜑 → (𝑆‘(♯‘𝐾)) = (𝑆‘(𝑁 − 1)))
258255, 257syl5eqr 2870 . 2 (𝜑 → (♯‘𝐶) = (𝑆‘(𝑁 − 1)))
259249, 258eqtrd 2856 1 (𝜑 → (♯‘𝐵) = (𝑆‘(𝑁 − 1)))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 207  wa 396   = wceq 1528  wcel 2105  {cab 2799  wne 3016  wral 3138  wrex 3139  {crab 3142  Vcvv 3495  cdif 3932  cun 3933  cin 3934  wss 3935  c0 4290  {csn 4559  {cpr 4561  cop 4565   class class class wbr 5058  cmpt 5138  ccnv 5548  cres 5551  Fun wfun 6343   Fn wfn 6344  wf 6345  1-1wf1 6346  ontowfo 6347  1-1-ontowf1o 6348  cfv 6349  (class class class)co 7145  cen 8495  Fincfn 8498  1c1 10527   + caddc 10529  cmin 10859  cn 11627  2c2 11681  0cn0 11886  cuz 12232  ...cfz 12882  chash 13680
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1787  ax-4 1801  ax-5 1902  ax-6 1961  ax-7 2006  ax-8 2107  ax-9 2115  ax-10 2136  ax-11 2151  ax-12 2167  ax-ext 2793  ax-rep 5182  ax-sep 5195  ax-nul 5202  ax-pow 5258  ax-pr 5321  ax-un 7450  ax-cnex 10582  ax-resscn 10583  ax-1cn 10584  ax-icn 10585  ax-addcl 10586  ax-addrcl 10587  ax-mulcl 10588  ax-mulrcl 10589  ax-mulcom 10590  ax-addass 10591  ax-mulass 10592  ax-distr 10593  ax-i2m1 10594  ax-1ne0 10595  ax-1rid 10596  ax-rnegex 10597  ax-rrecex 10598  ax-cnre 10599  ax-pre-lttri 10600  ax-pre-lttrn 10601  ax-pre-ltadd 10602  ax-pre-mulgt0 10603
This theorem depends on definitions:  df-bi 208  df-an 397  df-or 842  df-3or 1080  df-3an 1081  df-tru 1531  df-ex 1772  df-nf 1776  df-sb 2061  df-mo 2618  df-eu 2650  df-clab 2800  df-cleq 2814  df-clel 2893  df-nfc 2963  df-ne 3017  df-nel 3124  df-ral 3143  df-rex 3144  df-reu 3145  df-rmo 3146  df-rab 3147  df-v 3497  df-sbc 3772  df-csb 3883  df-dif 3938  df-un 3940  df-in 3942  df-ss 3951  df-pss 3953  df-nul 4291  df-if 4466  df-pw 4539  df-sn 4560  df-pr 4562  df-tp 4564  df-op 4566  df-uni 4833  df-int 4870  df-iun 4914  df-br 5059  df-opab 5121  df-mpt 5139  df-tr 5165  df-id 5454  df-eprel 5459  df-po 5468  df-so 5469  df-fr 5508  df-we 5510  df-xp 5555  df-rel 5556  df-cnv 5557  df-co 5558  df-dm 5559  df-rn 5560  df-res 5561  df-ima 5562  df-pred 6142  df-ord 6188  df-on 6189  df-lim 6190  df-suc 6191  df-iota 6308  df-fun 6351  df-fn 6352  df-f 6353  df-f1 6354  df-fo 6355  df-f1o 6356  df-fv 6357  df-riota 7103  df-ov 7148  df-oprab 7149  df-mpo 7150  df-om 7569  df-1st 7680  df-2nd 7681  df-wrecs 7938  df-recs 7999  df-rdg 8037  df-1o 8093  df-2o 8094  df-oadd 8097  df-er 8279  df-map 8398  df-pm 8399  df-en 8499  df-dom 8500  df-sdom 8501  df-fin 8502  df-dju 9319  df-card 9357  df-pnf 10666  df-mnf 10667  df-xr 10668  df-ltxr 10669  df-le 10670  df-sub 10861  df-neg 10862  df-nn 11628  df-2 11689  df-n0 11887  df-xnn0 11957  df-z 11971  df-uz 12233  df-fz 12883  df-hash 13681
This theorem is referenced by:  subfacp1lem6  32330
  Copyright terms: Public domain W3C validator