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 32326
Description: Lemma for subfacp1 32330. In subfacp1lem6 32329 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 13328 . . . . . . . . 9 (1...(𝑁 + 1)) ∈ Fin
3 deranglem 32310 . . . . . . . . 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 2906 . . . . . . 7 𝐴 ∈ Fin
6 subfacp1lem3.b . . . . . . . 8 𝐵 = {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)}
7 ssrab2 4053 . . . . . . . 8 {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)} ⊆ 𝐴
86, 7eqsstri 3998 . . . . . . 7 𝐵𝐴
9 ssfi 8726 . . . . . . 7 ((𝐴 ∈ Fin ∧ 𝐵𝐴) → 𝐵 ∈ Fin)
105, 8, 9mp2an 688 . . . . . 6 𝐵 ∈ Fin
1110elexi 3511 . . . . 5 𝐵 ∈ V
1211a1i 11 . . . 4 (𝜑𝐵 ∈ V)
13 subfacp1lem3.c . . . . . . 7 𝐶 = {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}
14 subfacp1lem1.k . . . . . . . . 9 𝐾 = ((2...(𝑁 + 1)) ∖ {𝑀})
15 fzfi 13328 . . . . . . . . . 10 (2...(𝑁 + 1)) ∈ Fin
16 diffi 8738 . . . . . . . . . 10 ((2...(𝑁 + 1)) ∈ Fin → ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin)
1715, 16ax-mp 5 . . . . . . . . 9 ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin
1814, 17eqeltri 2906 . . . . . . . 8 𝐾 ∈ Fin
19 deranglem 32310 . . . . . . . 8 (𝐾 ∈ Fin → {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin)
2018, 19ax-mp 5 . . . . . . 7 {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin
2113, 20eqeltri 2906 . . . . . 6 𝐶 ∈ Fin
2221elexi 3511 . . . . 5 𝐶 ∈ V
2322a1i 11 . . . 4 (𝜑𝐶 ∈ V)
24 simpr 485 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → 𝑏𝐵)
25 fveq1 6662 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔‘1) = (𝑏‘1))
2625eqeq1d 2820 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔‘1) = 𝑀 ↔ (𝑏‘1) = 𝑀))
27 fveq1 6662 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔𝑀) = (𝑏𝑀))
2827eqeq1d 2820 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔𝑀) = 1 ↔ (𝑏𝑀) = 1))
2926, 28anbi12d 630 . . . . . . . . . . . . . 14 (𝑔 = 𝑏 → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3029, 6elrab2 3680 . . . . . . . . . . . . 13 (𝑏𝐵 ↔ (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3124, 30sylib 219 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3231simpld 495 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏𝐴)
33 vex 3495 . . . . . . . . . . . 12 𝑏 ∈ V
34 f1oeq1 6597 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
35 fveq1 6662 . . . . . . . . . . . . . . 15 (𝑓 = 𝑏 → (𝑓𝑦) = (𝑏𝑦))
3635neeq1d 3072 . . . . . . . . . . . . . 14 (𝑓 = 𝑏 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
3736ralbidv 3194 . . . . . . . . . . . . 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 3667 . . . . . . . . . . 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 6607 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)))
43 df-f1 6353 . . . . . . . . . 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 6609 . . . . . . . . . . . 12 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏 Fn (1...(𝑁 + 1)))
4741, 46syl 17 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏 Fn (1...(𝑁 + 1)))
48 fnresdm 6459 . . . . . . . . . . 11 (𝑏 Fn (1...(𝑁 + 1)) → (𝑏 ↾ (1...(𝑁 + 1))) = 𝑏)
49 f1oeq1 6597 . . . . . . . . . . 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 6615 . . . . . . . . 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 4146 . . . . . . . . . . . . 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 32323 . . . . . . . . . . . . . 14 (𝜑 → ((𝐾 ∩ {1, 𝑀}) = ∅ ∧ (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)) ∧ (♯‘𝐾) = (𝑁 − 1)))
6160simp2d 1135 . . . . . . . . . . . . 13 (𝜑 → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
6254, 61sseqtrid 4016 . . . . . . . . . . . 12 (𝜑 → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
6362adantr 481 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
64 fnssres 6463 . . . . . . . . . . 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 4691 . . . . . . . . . . . . 13 𝑀 ∈ {1, 𝑀}
6967, 68syl6eqel 2918 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏‘1) ∈ {1, 𝑀})
7066simprd 496 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → (𝑏𝑀) = 1)
71 1ex 10625 . . . . . . . . . . . . . 14 1 ∈ V
7271prid1 4690 . . . . . . . . . . . . 13 1 ∈ {1, 𝑀}
7370, 72syl6eqel 2918 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝑀) ∈ {1, 𝑀})
74 fveq2 6663 . . . . . . . . . . . . . 14 (𝑥 = 1 → (𝑏𝑥) = (𝑏‘1))
7574eleq1d 2894 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏‘1) ∈ {1, 𝑀}))
76 fveq2 6663 . . . . . . . . . . . . . 14 (𝑥 = 𝑀 → (𝑏𝑥) = (𝑏𝑀))
7776eleq1d 2894 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑀) ∈ {1, 𝑀}))
7871, 59, 75, 77ralpr 4628 . . . . . . . . . . . 12 (∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀} ↔ ((𝑏‘1) ∈ {1, 𝑀} ∧ (𝑏𝑀) ∈ {1, 𝑀}))
7969, 73, 78sylanbrc 583 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
80 fvres 6682 . . . . . . . . . . . . 13 (𝑥 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑥) = (𝑏𝑥))
8180eleq1d 2894 . . . . . . . . . . . 12 (𝑥 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑥) ∈ {1, 𝑀}))
8281ralbiia 3161 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
8379, 82sylibr 235 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀})
84 ffnfv 6874 . . . . . . . . . 10 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀}))
8565, 83, 84sylanbrc 583 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀})
86 fveqeq2 6672 . . . . . . . . . . . . 13 (𝑦 = 𝑀 → ((𝑏𝑦) = 1 ↔ (𝑏𝑀) = 1))
8786rspcev 3620 . . . . . . . . . . . 12 ((𝑀 ∈ {1, 𝑀} ∧ (𝑏𝑀) = 1) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
8868, 70, 87sylancr 587 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
89 fveqeq2 6672 . . . . . . . . . . . . 13 (𝑦 = 1 → ((𝑏𝑦) = 𝑀 ↔ (𝑏‘1) = 𝑀))
9089rspcev 3620 . . . . . . . . . . . 12 ((1 ∈ {1, 𝑀} ∧ (𝑏‘1) = 𝑀) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
9172, 67, 90sylancr 587 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
92 eqeq2 2830 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 1))
9392rexbidv 3294 . . . . . . . . . . . 12 (𝑥 = 1 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1))
94 eqeq2 2830 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑀))
9594rexbidv 3294 . . . . . . . . . . . 12 (𝑥 = 𝑀 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9671, 59, 93, 95ralpr 4628 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1 ∧ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9788, 91, 96sylanbrc 583 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
98 eqcom 2825 . . . . . . . . . . . . 13 (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥)
99 fvres 6682 . . . . . . . . . . . . . 14 (𝑦 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑦) = (𝑏𝑦))
10099eqeq1d 2820 . . . . . . . . . . . . 13 (𝑦 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑥))
10198, 100syl5bb 284 . . . . . . . . . . . 12 (𝑦 ∈ {1, 𝑀} → (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ (𝑏𝑦) = 𝑥))
102101rexbiia 3243 . . . . . . . . . . 11 (∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
103102ralbii 3162 . . . . . . . . . 10 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
10497, 103sylibr 235 . . . . . . . . 9 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦))
105 dffo3 6860 . . . . . . . . 9 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦)))
10685, 104, 105sylanbrc 583 . . . . . . . 8 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀})
107 resdif 6628 . . . . . . . 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 4126 . . . . . . . . . . 11 ({1, 𝑀} ∪ 𝐾) = (𝐾 ∪ {1, 𝑀})
110109, 61syl5eq 2865 . . . . . . . . . 10 (𝜑 → ({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)))
111 incom 4175 . . . . . . . . . . . 12 ({1, 𝑀} ∩ 𝐾) = (𝐾 ∩ {1, 𝑀})
11260simp1d 1134 . . . . . . . . . . . 12 (𝜑 → (𝐾 ∩ {1, 𝑀}) = ∅)
113111, 112syl5eq 2865 . . . . . . . . . . 11 (𝜑 → ({1, 𝑀} ∩ 𝐾) = ∅)
114 uneqdifeq 4434 . . . . . . . . . . 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 5841 . . . . . . . . . 10 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})) = (𝑏𝐾))
119 f1oeq1 6597 . . . . . . . . . 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 6598 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
122 f1oeq3 6599 . . . . . . . . 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 4145 . . . . . . . . 9 𝐾 ⊆ (𝐾 ∪ {1, 𝑀})
127126, 61sseqtrid 4016 . . . . . . . 8 (𝜑𝐾 ⊆ (1...(𝑁 + 1)))
128127adantr 481 . . . . . . 7 ((𝜑𝑏𝐵) → 𝐾 ⊆ (1...(𝑁 + 1)))
12940simprd 496 . . . . . . 7 ((𝜑𝑏𝐵) → ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)
130 ssralv 4030 . . . . . . 7 (𝐾 ⊆ (1...(𝑁 + 1)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦 → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
131128, 129, 130sylc 65 . . . . . 6 ((𝜑𝑏𝐵) → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)
13233resex 5892 . . . . . . 7 (𝑏𝐾) ∈ V
133 f1oeq1 6597 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (𝑓:𝐾1-1-onto𝐾 ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
134 fveq1 6662 . . . . . . . . . . 11 (𝑓 = (𝑏𝐾) → (𝑓𝑦) = ((𝑏𝐾)‘𝑦))
135 fvres 6682 . . . . . . . . . . 11 (𝑦𝐾 → ((𝑏𝐾)‘𝑦) = (𝑏𝑦))
136134, 135sylan9eq 2873 . . . . . . . . . 10 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → (𝑓𝑦) = (𝑏𝑦))
137136neeq1d 3072 . . . . . . . . 9 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
138137ralbidva 3193 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
139133, 138anbi12d 630 . . . . . . 7 (𝑓 = (𝑏𝐾) → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)))
140132, 139, 13elab2 3667 . . . . . 6 ((𝑏𝐾) ∈ 𝐶 ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
141125, 131, 140sylanbrc 583 . . . . 5 ((𝜑𝑏𝐵) → (𝑏𝐾) ∈ 𝐶)
142141ex 413 . . . 4 (𝜑 → (𝑏𝐵 → (𝑏𝐾) ∈ 𝐶))
14357adantr 481 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑁 ∈ ℕ)
14458adantr 481 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑀 ∈ (2...(𝑁 + 1)))
145 eqid 2818 . . . . . . . . 9 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})
146 simpr 485 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑐𝐶)
147 vex 3495 . . . . . . . . . . . 12 𝑐 ∈ V
148 f1oeq1 6597 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (𝑓:𝐾1-1-onto𝐾𝑐:𝐾1-1-onto𝐾))
149 fveq1 6662 . . . . . . . . . . . . . . 15 (𝑓 = 𝑐 → (𝑓𝑦) = (𝑐𝑦))
150149neeq1d 3072 . . . . . . . . . . . . . 14 (𝑓 = 𝑐 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑐𝑦) ≠ 𝑦))
151150ralbidv 3194 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
152148, 151anbi12d 630 . . . . . . . . . . . 12 (𝑓 = 𝑐 → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)))
153147, 152, 13elab2 3667 . . . . . . . . . . 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 32324 . . . . . . . 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 32325 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = (𝑐𝑦))
159154simprd 496 . . . . . . . . . . . 12 ((𝜑𝑐𝐶) → ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)
160159r19.21bi 3205 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → (𝑐𝑦) ≠ 𝑦)
161158, 160eqnetrd 3080 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
162161ralrimiva 3179 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
163156simp2d 1135 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
164 elfzuz 12892 . . . . . . . . . . . . 13 (𝑀 ∈ (2...(𝑁 + 1)) → 𝑀 ∈ (ℤ‘2))
165 eluz2b3 12310 . . . . . . . . . . . . . 14 (𝑀 ∈ (ℤ‘2) ↔ (𝑀 ∈ ℕ ∧ 𝑀 ≠ 1))
166165simprbi 497 . . . . . . . . . . . . 13 (𝑀 ∈ (ℤ‘2) → 𝑀 ≠ 1)
16758, 164, 1663syl 18 . . . . . . . . . . . 12 (𝜑𝑀 ≠ 1)
168167adantr 481 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑀 ≠ 1)
169163, 168eqnetrd 3080 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1)
170156simp3d 1136 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
171168necomd 3068 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 1 ≠ 𝑀)
172170, 171eqnetrd 3080 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀)
173 fveq2 6663 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
174 id 22 . . . . . . . . . . . 12 (𝑦 = 1 → 𝑦 = 1)
175173, 174neeq12d 3074 . . . . . . . . . . 11 (𝑦 = 1 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1))
176 fveq2 6663 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
177 id 22 . . . . . . . . . . . 12 (𝑦 = 𝑀𝑦 = 𝑀)
178176, 177neeq12d 3074 . . . . . . . . . . 11 (𝑦 = 𝑀 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
17971, 59, 175, 178ralpr 4628 . . . . . . . . . 10 (∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
180169, 172, 179sylanbrc 583 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
181 ralunb 4164 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ∧ ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
182162, 180, 181sylanbrc 583 . . . . . . . 8 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
18361adantr 481 . . . . . . . . 9 ((𝜑𝑐𝐶) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
184183raleqdv 3413 . . . . . . . 8 ((𝜑𝑐𝐶) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
185182, 184mpbid 233 . . . . . . 7 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
186 prex 5323 . . . . . . . . 9 {⟨1, 𝑀⟩, ⟨𝑀, 1⟩} ∈ V
187147, 186unex 7458 . . . . . . . 8 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ V
188 f1oeq1 6597 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
189 fveq1 6662 . . . . . . . . . . 11 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
190189neeq1d 3072 . . . . . . . . . 10 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑓𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
191190ralbidv 3194 . . . . . . . . 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 3667 . . . . . . 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 6662 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
197196eqeq1d 2820 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔‘1) = 𝑀 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀))
198 fveq1 6662 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
199198eqeq1d 2820 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔𝑀) = 1 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
200197, 199anbi12d 630 . . . . . . 7 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
201200, 6elrab2 3680 . . . . . 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 2856 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
20770adantrr 713 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = 1)
208170adantrl 712 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
209207, 208eqtr4d 2856 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
210 fveq2 6663 . . . . . . . . . . . . 13 (𝑦 = 1 → (𝑏𝑦) = (𝑏‘1))
211210, 173eqeq12d 2834 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1)))
212 fveq2 6663 . . . . . . . . . . . . 13 (𝑦 = 𝑀 → (𝑏𝑦) = (𝑏𝑀))
213212, 176eqeq12d 2834 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
21471, 59, 211, 213ralpr 4628 . . . . . . . . . . 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 4164 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
218216, 217syl6bbr 290 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
219158eqeq2d 2829 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
220219ralbidva 3193 . . . . . . . . 9 ((𝜑𝑐𝐶) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
221220adantrl 712 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
22261adantr 481 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
223222raleqdv 3413 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
224218, 221, 2233bitr3rd 311 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
225135eqeq2d 2829 . . . . . . . . 9 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑐𝑦) = (𝑏𝑦)))
226 eqcom 2825 . . . . . . . . 9 ((𝑐𝑦) = (𝑏𝑦) ↔ (𝑏𝑦) = (𝑐𝑦))
227225, 226syl6bb 288 . . . . . . . 8 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
228227ralbiia 3161 . . . . . . 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 6609 . . . . . . . 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 6794 . . . . . . 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 6609 . . . . . . . 8 (𝑐:𝐾1-1-onto𝐾𝑐 Fn 𝐾)
238236, 237syl 17 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐 Fn 𝐾)
239127adantr 481 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝐾 ⊆ (1...(𝑁 + 1)))
240 fnssres 6463 . . . . . . . 8 ((𝑏 Fn (1...(𝑁 + 1)) ∧ 𝐾 ⊆ (1...(𝑁 + 1))) → (𝑏𝐾) Fn 𝐾)
241230, 239, 240syl2anc 584 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝐾) Fn 𝐾)
242 eqfnfv 6794 . . . . . . 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 8534 . . 3 (𝜑𝐵𝐶)
247 hashen 13695 . . . 4 ((𝐵 ∈ Fin ∧ 𝐶 ∈ Fin) → ((♯‘𝐵) = (♯‘𝐶) ↔ 𝐵𝐶))
24810, 21, 247mp2an 688 . . 3 ((♯‘𝐵) = (♯‘𝐶) ↔ 𝐵𝐶)
249246, 248sylibr 235 . 2 (𝜑 → (♯‘𝐵) = (♯‘𝐶))
25013fveq2i 6666 . . . 4 (♯‘𝐶) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25155derangval 32311 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}))
25218, 251ax-mp 5 . . . 4 (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25355, 56derangen2 32318 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (𝑆‘(♯‘𝐾)))
25418, 253ax-mp 5 . . . 4 (𝐷𝐾) = (𝑆‘(♯‘𝐾))
255250, 252, 2543eqtr2ri 2848 . . 3 (𝑆‘(♯‘𝐾)) = (♯‘𝐶)
25660simp3d 1136 . . . 4 (𝜑 → (♯‘𝐾) = (𝑁 − 1))
257256fveq2d 6667 . . 3 (𝜑 → (𝑆‘(♯‘𝐾)) = (𝑆‘(𝑁 − 1)))
258255, 257syl5eqr 2867 . 2 (𝜑 → (♯‘𝐶) = (𝑆‘(𝑁 − 1)))
259249, 258eqtrd 2853 1 (𝜑 → (♯‘𝐵) = (𝑆‘(𝑁 − 1)))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 207  wa 396   = wceq 1528  wcel 2105  {cab 2796  wne 3013  wral 3135  wrex 3136  {crab 3139  Vcvv 3492  cdif 3930  cun 3931  cin 3932  wss 3933  c0 4288  {csn 4557  {cpr 4559  cop 4563   class class class wbr 5057  cmpt 5137  ccnv 5547  cres 5550  Fun wfun 6342   Fn wfn 6343  wf 6344  1-1wf1 6345  ontowfo 6346  1-1-ontowf1o 6347  cfv 6348  (class class class)co 7145  cen 8494  Fincfn 8497  1c1 10526   + caddc 10528  cmin 10858  cn 11626  2c2 11680  0cn0 11885  cuz 12231  ...cfz 12880  chash 13678
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 2790  ax-rep 5181  ax-sep 5194  ax-nul 5201  ax-pow 5257  ax-pr 5320  ax-un 7450  ax-cnex 10581  ax-resscn 10582  ax-1cn 10583  ax-icn 10584  ax-addcl 10585  ax-addrcl 10586  ax-mulcl 10587  ax-mulrcl 10588  ax-mulcom 10589  ax-addass 10590  ax-mulass 10591  ax-distr 10592  ax-i2m1 10593  ax-1ne0 10594  ax-1rid 10595  ax-rnegex 10596  ax-rrecex 10597  ax-cnre 10598  ax-pre-lttri 10599  ax-pre-lttrn 10600  ax-pre-ltadd 10601  ax-pre-mulgt0 10602
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 2615  df-eu 2647  df-clab 2797  df-cleq 2811  df-clel 2890  df-nfc 2960  df-ne 3014  df-nel 3121  df-ral 3140  df-rex 3141  df-reu 3142  df-rmo 3143  df-rab 3144  df-v 3494  df-sbc 3770  df-csb 3881  df-dif 3936  df-un 3938  df-in 3940  df-ss 3949  df-pss 3951  df-nul 4289  df-if 4464  df-pw 4537  df-sn 4558  df-pr 4560  df-tp 4562  df-op 4564  df-uni 4831  df-int 4868  df-iun 4912  df-br 5058  df-opab 5120  df-mpt 5138  df-tr 5164  df-id 5453  df-eprel 5458  df-po 5467  df-so 5468  df-fr 5507  df-we 5509  df-xp 5554  df-rel 5555  df-cnv 5556  df-co 5557  df-dm 5558  df-rn 5559  df-res 5560  df-ima 5561  df-pred 6141  df-ord 6187  df-on 6188  df-lim 6189  df-suc 6190  df-iota 6307  df-fun 6350  df-fn 6351  df-f 6352  df-f1 6353  df-fo 6354  df-f1o 6355  df-fv 6356  df-riota 7103  df-ov 7148  df-oprab 7149  df-mpo 7150  df-om 7570  df-1st 7678  df-2nd 7679  df-wrecs 7936  df-recs 7997  df-rdg 8035  df-1o 8091  df-2o 8092  df-oadd 8095  df-er 8278  df-map 8397  df-pm 8398  df-en 8498  df-dom 8499  df-sdom 8500  df-fin 8501  df-dju 9318  df-card 9356  df-pnf 10665  df-mnf 10666  df-xr 10667  df-ltxr 10668  df-le 10669  df-sub 10860  df-neg 10861  df-nn 11627  df-2 11688  df-n0 11886  df-xnn0 11956  df-z 11970  df-uz 12232  df-fz 12881  df-hash 13679
This theorem is referenced by:  subfacp1lem6  32329
  Copyright terms: Public domain W3C validator