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 31633
Description: Lemma for subfacp1 31637. In subfacp1lem6 31636 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 12984 . . . . . . . . 9 (1...(𝑁 + 1)) ∈ Fin
3 deranglem 31617 . . . . . . . . 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 2840 . . . . . . 7 𝐴 ∈ Fin
6 subfacp1lem3.b . . . . . . . 8 𝐵 = {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)}
7 ssrab2 3849 . . . . . . . 8 {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)} ⊆ 𝐴
86, 7eqsstri 3797 . . . . . . 7 𝐵𝐴
9 ssfi 8391 . . . . . . 7 ((𝐴 ∈ Fin ∧ 𝐵𝐴) → 𝐵 ∈ Fin)
105, 8, 9mp2an 683 . . . . . 6 𝐵 ∈ Fin
1110elexi 3366 . . . . 5 𝐵 ∈ V
1211a1i 11 . . . 4 (𝜑𝐵 ∈ V)
13 subfacp1lem3.c . . . . . . 7 𝐶 = {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}
14 subfacp1lem1.k . . . . . . . . 9 𝐾 = ((2...(𝑁 + 1)) ∖ {𝑀})
15 fzfi 12984 . . . . . . . . . 10 (2...(𝑁 + 1)) ∈ Fin
16 diffi 8403 . . . . . . . . . 10 ((2...(𝑁 + 1)) ∈ Fin → ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin)
1715, 16ax-mp 5 . . . . . . . . 9 ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin
1814, 17eqeltri 2840 . . . . . . . 8 𝐾 ∈ Fin
19 deranglem 31617 . . . . . . . 8 (𝐾 ∈ Fin → {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin)
2018, 19ax-mp 5 . . . . . . 7 {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin
2113, 20eqeltri 2840 . . . . . 6 𝐶 ∈ Fin
2221elexi 3366 . . . . 5 𝐶 ∈ V
2322a1i 11 . . . 4 (𝜑𝐶 ∈ V)
24 simpr 477 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → 𝑏𝐵)
25 fveq1 6378 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔‘1) = (𝑏‘1))
2625eqeq1d 2767 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔‘1) = 𝑀 ↔ (𝑏‘1) = 𝑀))
27 fveq1 6378 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔𝑀) = (𝑏𝑀))
2827eqeq1d 2767 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔𝑀) = 1 ↔ (𝑏𝑀) = 1))
2926, 28anbi12d 624 . . . . . . . . . . . . . 14 (𝑔 = 𝑏 → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3029, 6elrab2 3525 . . . . . . . . . . . . 13 (𝑏𝐵 ↔ (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3124, 30sylib 209 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3231simpld 488 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏𝐴)
33 vex 3353 . . . . . . . . . . . 12 𝑏 ∈ V
34 f1oeq1 6314 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
35 fveq1 6378 . . . . . . . . . . . . . . 15 (𝑓 = 𝑏 → (𝑓𝑦) = (𝑏𝑦))
3635neeq1d 2996 . . . . . . . . . . . . . 14 (𝑓 = 𝑏 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
3736ralbidv 3133 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
3834, 37anbi12d 624 . . . . . . . . . . . 12 (𝑓 = 𝑏 → ((𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦) ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)))
3933, 38, 1elab2 3511 . . . . . . . . . . 11 (𝑏𝐴 ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
4032, 39sylib 209 . . . . . . . . . 10 ((𝜑𝑏𝐵) → (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
4140simpld 488 . . . . . . . . 9 ((𝜑𝑏𝐵) → 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
42 f1of1 6323 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)))
43 df-f1 6075 . . . . . . . . . 10 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) ↔ (𝑏:(1...(𝑁 + 1))⟶(1...(𝑁 + 1)) ∧ Fun 𝑏))
4443simprbi 490 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) → Fun 𝑏)
4541, 42, 443syl 18 . . . . . . . 8 ((𝜑𝑏𝐵) → Fun 𝑏)
46 f1ofn 6325 . . . . . . . . . . . 12 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏 Fn (1...(𝑁 + 1)))
4741, 46syl 17 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏 Fn (1...(𝑁 + 1)))
48 fnresdm 6180 . . . . . . . . . . 11 (𝑏 Fn (1...(𝑁 + 1)) → (𝑏 ↾ (1...(𝑁 + 1))) = 𝑏)
49 f1oeq1 6314 . . . . . . . . . . 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 248 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
52 f1ofo 6331 . . . . . . . . 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 3941 . . . . . . . . . . . . 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 31630 . . . . . . . . . . . . . 14 (𝜑 → ((𝐾 ∩ {1, 𝑀}) = ∅ ∧ (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)) ∧ (♯‘𝐾) = (𝑁 − 1)))
6160simp2d 1173 . . . . . . . . . . . . 13 (𝜑 → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
6254, 61syl5sseq 3815 . . . . . . . . . . . 12 (𝜑 → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
6362adantr 472 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
64 fnssres 6184 . . . . . . . . . . 11 ((𝑏 Fn (1...(𝑁 + 1)) ∧ {1, 𝑀} ⊆ (1...(𝑁 + 1))) → (𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀})
6547, 63, 64syl2anc 579 . . . . . . . . . 10 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀})
6631simprd 489 . . . . . . . . . . . . . 14 ((𝜑𝑏𝐵) → ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1))
6766simpld 488 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → (𝑏‘1) = 𝑀)
6859prid2 4455 . . . . . . . . . . . . 13 𝑀 ∈ {1, 𝑀}
6967, 68syl6eqel 2852 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏‘1) ∈ {1, 𝑀})
7066simprd 489 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → (𝑏𝑀) = 1)
71 1ex 10293 . . . . . . . . . . . . . 14 1 ∈ V
7271prid1 4454 . . . . . . . . . . . . 13 1 ∈ {1, 𝑀}
7370, 72syl6eqel 2852 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝑀) ∈ {1, 𝑀})
74 fveq2 6379 . . . . . . . . . . . . . 14 (𝑥 = 1 → (𝑏𝑥) = (𝑏‘1))
7574eleq1d 2829 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏‘1) ∈ {1, 𝑀}))
76 fveq2 6379 . . . . . . . . . . . . . 14 (𝑥 = 𝑀 → (𝑏𝑥) = (𝑏𝑀))
7776eleq1d 2829 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑀) ∈ {1, 𝑀}))
7871, 59, 75, 77ralpr 4396 . . . . . . . . . . . 12 (∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀} ↔ ((𝑏‘1) ∈ {1, 𝑀} ∧ (𝑏𝑀) ∈ {1, 𝑀}))
7969, 73, 78sylanbrc 578 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
80 fvres 6398 . . . . . . . . . . . . 13 (𝑥 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑥) = (𝑏𝑥))
8180eleq1d 2829 . . . . . . . . . . . 12 (𝑥 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑥) ∈ {1, 𝑀}))
8281ralbiia 3126 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
8379, 82sylibr 225 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀})
84 ffnfv 6582 . . . . . . . . . 10 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀}))
8565, 83, 84sylanbrc 578 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀})
86 fveqeq2 6388 . . . . . . . . . . . . 13 (𝑦 = 𝑀 → ((𝑏𝑦) = 1 ↔ (𝑏𝑀) = 1))
8786rspcev 3462 . . . . . . . . . . . 12 ((𝑀 ∈ {1, 𝑀} ∧ (𝑏𝑀) = 1) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
8868, 70, 87sylancr 581 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
89 fveqeq2 6388 . . . . . . . . . . . . 13 (𝑦 = 1 → ((𝑏𝑦) = 𝑀 ↔ (𝑏‘1) = 𝑀))
9089rspcev 3462 . . . . . . . . . . . 12 ((1 ∈ {1, 𝑀} ∧ (𝑏‘1) = 𝑀) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
9172, 67, 90sylancr 581 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
92 eqeq2 2776 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 1))
9392rexbidv 3199 . . . . . . . . . . . 12 (𝑥 = 1 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1))
94 eqeq2 2776 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑀))
9594rexbidv 3199 . . . . . . . . . . . 12 (𝑥 = 𝑀 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9671, 59, 93, 95ralpr 4396 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1 ∧ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9788, 91, 96sylanbrc 578 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
98 eqcom 2772 . . . . . . . . . . . . 13 (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥)
99 fvres 6398 . . . . . . . . . . . . . 14 (𝑦 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑦) = (𝑏𝑦))
10099eqeq1d 2767 . . . . . . . . . . . . 13 (𝑦 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑥))
10198, 100syl5bb 274 . . . . . . . . . . . 12 (𝑦 ∈ {1, 𝑀} → (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ (𝑏𝑦) = 𝑥))
102101rexbiia 3187 . . . . . . . . . . 11 (∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
103102ralbii 3127 . . . . . . . . . 10 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
10497, 103sylibr 225 . . . . . . . . 9 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦))
105 dffo3 6568 . . . . . . . . 9 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦)))
10685, 104, 105sylanbrc 578 . . . . . . . 8 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀})
107 resdif 6344 . . . . . . . 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 1490 . . . . . . 7 ((𝜑𝑏𝐵) → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}))
109 uncom 3921 . . . . . . . . . . 11 ({1, 𝑀} ∪ 𝐾) = (𝐾 ∪ {1, 𝑀})
110109, 61syl5eq 2811 . . . . . . . . . 10 (𝜑 → ({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)))
111 incom 3969 . . . . . . . . . . . 12 ({1, 𝑀} ∩ 𝐾) = (𝐾 ∩ {1, 𝑀})
11260simp1d 1172 . . . . . . . . . . . 12 (𝜑 → (𝐾 ∩ {1, 𝑀}) = ∅)
113111, 112syl5eq 2811 . . . . . . . . . . 11 (𝜑 → ({1, 𝑀} ∩ 𝐾) = ∅)
114 uneqdifeq 4219 . . . . . . . . . . 11 (({1, 𝑀} ⊆ (1...(𝑁 + 1)) ∧ ({1, 𝑀} ∩ 𝐾) = ∅) → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
11562, 113, 114syl2anc 579 . . . . . . . . . 10 (𝜑 → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
116110, 115mpbid 223 . . . . . . . . 9 (𝜑 → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
117116adantr 472 . . . . . . . 8 ((𝜑𝑏𝐵) → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
118 reseq2 5562 . . . . . . . . . 10 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})) = (𝑏𝐾))
119 f1oeq1 6314 . . . . . . . . . 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 6315 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
122 f1oeq3 6316 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
123120, 121, 1223bitrd 296 . . . . . . . 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 223 . . . . . 6 ((𝜑𝑏𝐵) → (𝑏𝐾):𝐾1-1-onto𝐾)
126 ssun1 3940 . . . . . . . . 9 𝐾 ⊆ (𝐾 ∪ {1, 𝑀})
127126, 61syl5sseq 3815 . . . . . . . 8 (𝜑𝐾 ⊆ (1...(𝑁 + 1)))
128127adantr 472 . . . . . . 7 ((𝜑𝑏𝐵) → 𝐾 ⊆ (1...(𝑁 + 1)))
12940simprd 489 . . . . . . 7 ((𝜑𝑏𝐵) → ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)
130 ssralv 3828 . . . . . . 7 (𝐾 ⊆ (1...(𝑁 + 1)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦 → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
131128, 129, 130sylc 65 . . . . . 6 ((𝜑𝑏𝐵) → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)
13233resex 5622 . . . . . . 7 (𝑏𝐾) ∈ V
133 f1oeq1 6314 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (𝑓:𝐾1-1-onto𝐾 ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
134 fveq1 6378 . . . . . . . . . . 11 (𝑓 = (𝑏𝐾) → (𝑓𝑦) = ((𝑏𝐾)‘𝑦))
135 fvres 6398 . . . . . . . . . . 11 (𝑦𝐾 → ((𝑏𝐾)‘𝑦) = (𝑏𝑦))
136134, 135sylan9eq 2819 . . . . . . . . . 10 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → (𝑓𝑦) = (𝑏𝑦))
137136neeq1d 2996 . . . . . . . . 9 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
138137ralbidva 3132 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
139133, 138anbi12d 624 . . . . . . 7 (𝑓 = (𝑏𝐾) → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)))
140132, 139, 13elab2 3511 . . . . . 6 ((𝑏𝐾) ∈ 𝐶 ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
141125, 131, 140sylanbrc 578 . . . . 5 ((𝜑𝑏𝐵) → (𝑏𝐾) ∈ 𝐶)
142141ex 401 . . . 4 (𝜑 → (𝑏𝐵 → (𝑏𝐾) ∈ 𝐶))
14357adantr 472 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑁 ∈ ℕ)
14458adantr 472 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑀 ∈ (2...(𝑁 + 1)))
145 eqid 2765 . . . . . . . . 9 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})
146 simpr 477 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑐𝐶)
147 vex 3353 . . . . . . . . . . . 12 𝑐 ∈ V
148 f1oeq1 6314 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (𝑓:𝐾1-1-onto𝐾𝑐:𝐾1-1-onto𝐾))
149 fveq1 6378 . . . . . . . . . . . . . . 15 (𝑓 = 𝑐 → (𝑓𝑦) = (𝑐𝑦))
150149neeq1d 2996 . . . . . . . . . . . . . 14 (𝑓 = 𝑐 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑐𝑦) ≠ 𝑦))
151150ralbidv 3133 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
152148, 151anbi12d 624 . . . . . . . . . . . 12 (𝑓 = 𝑐 → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)))
153147, 152, 13elab2 3511 . . . . . . . . . . 11 (𝑐𝐶 ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
154146, 153sylib 209 . . . . . . . . . 10 ((𝜑𝑐𝐶) → (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
155154simpld 488 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑐:𝐾1-1-onto𝐾)
15655, 56, 1, 143, 144, 59, 14, 145, 155subfacp1lem2a 31631 . . . . . . . 8 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
157156simp1d 1172 . . . . . . 7 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
15855, 56, 1, 143, 144, 59, 14, 145, 155subfacp1lem2b 31632 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = (𝑐𝑦))
159154simprd 489 . . . . . . . . . . . 12 ((𝜑𝑐𝐶) → ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)
160159r19.21bi 3079 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → (𝑐𝑦) ≠ 𝑦)
161158, 160eqnetrd 3004 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
162161ralrimiva 3113 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
163156simp2d 1173 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
164 elfzuz 12550 . . . . . . . . . . . . 13 (𝑀 ∈ (2...(𝑁 + 1)) → 𝑀 ∈ (ℤ‘2))
165 eluz2b3 11968 . . . . . . . . . . . . . 14 (𝑀 ∈ (ℤ‘2) ↔ (𝑀 ∈ ℕ ∧ 𝑀 ≠ 1))
166165simprbi 490 . . . . . . . . . . . . 13 (𝑀 ∈ (ℤ‘2) → 𝑀 ≠ 1)
16758, 164, 1663syl 18 . . . . . . . . . . . 12 (𝜑𝑀 ≠ 1)
168167adantr 472 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑀 ≠ 1)
169163, 168eqnetrd 3004 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1)
170156simp3d 1174 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
171168necomd 2992 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 1 ≠ 𝑀)
172170, 171eqnetrd 3004 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀)
173 fveq2 6379 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
174 id 22 . . . . . . . . . . . 12 (𝑦 = 1 → 𝑦 = 1)
175173, 174neeq12d 2998 . . . . . . . . . . 11 (𝑦 = 1 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1))
176 fveq2 6379 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
177 id 22 . . . . . . . . . . . 12 (𝑦 = 𝑀𝑦 = 𝑀)
178176, 177neeq12d 2998 . . . . . . . . . . 11 (𝑦 = 𝑀 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
17971, 59, 175, 178ralpr 4396 . . . . . . . . . 10 (∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
180169, 172, 179sylanbrc 578 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
181 ralunb 3958 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ∧ ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
182162, 180, 181sylanbrc 578 . . . . . . . 8 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
18361adantr 472 . . . . . . . . 9 ((𝜑𝑐𝐶) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
184183raleqdv 3292 . . . . . . . 8 ((𝜑𝑐𝐶) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
185182, 184mpbid 223 . . . . . . 7 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
186 prex 5067 . . . . . . . . 9 {⟨1, 𝑀⟩, ⟨𝑀, 1⟩} ∈ V
187147, 186unex 7158 . . . . . . . 8 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ V
188 f1oeq1 6314 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
189 fveq1 6378 . . . . . . . . . . 11 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
190189neeq1d 2996 . . . . . . . . . 10 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑓𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
191190ralbidv 3133 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
192188, 191anbi12d 624 . . . . . . . 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 3511 . . . . . . 7 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
194157, 185, 193sylanbrc 578 . . . . . 6 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴)
195163, 170jca 507 . . . . . 6 ((𝜑𝑐𝐶) → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
196 fveq1 6378 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
197196eqeq1d 2767 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔‘1) = 𝑀 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀))
198 fveq1 6378 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
199198eqeq1d 2767 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔𝑀) = 1 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
200197, 199anbi12d 624 . . . . . . 7 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
201200, 6elrab2 3525 . . . . . 6 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ∧ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
202194, 195, 201sylanbrc 578 . . . . 5 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵)
203202ex 401 . . . 4 (𝜑 → (𝑐𝐶 → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵))
20467adantrr 708 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = 𝑀)
205163adantrl 707 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
206204, 205eqtr4d 2802 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
20770adantrr 708 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = 1)
208170adantrl 707 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
209207, 208eqtr4d 2802 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
210 fveq2 6379 . . . . . . . . . . . . 13 (𝑦 = 1 → (𝑏𝑦) = (𝑏‘1))
211210, 173eqeq12d 2780 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1)))
212 fveq2 6379 . . . . . . . . . . . . 13 (𝑦 = 𝑀 → (𝑏𝑦) = (𝑏𝑀))
213212, 176eqeq12d 2780 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
21471, 59, 211, 213ralpr 4396 . . . . . . . . . . 11 (∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ((𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ∧ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
215206, 209, 214sylanbrc 578 . . . . . . . . . 10 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
216215biantrud 527 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))))
217 ralunb 3958 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
218216, 217syl6bbr 280 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
219158eqeq2d 2775 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
220219ralbidva 3132 . . . . . . . . 9 ((𝜑𝑐𝐶) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
221220adantrl 707 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
22261adantr 472 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
223222raleqdv 3292 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
224218, 221, 2233bitr3rd 301 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
225135eqeq2d 2775 . . . . . . . . 9 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑐𝑦) = (𝑏𝑦)))
226 eqcom 2772 . . . . . . . . 9 ((𝑐𝑦) = (𝑏𝑦) ↔ (𝑏𝑦) = (𝑐𝑦))
227225, 226syl6bb 278 . . . . . . . 8 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
228227ralbiia 3126 . . . . . . 7 (∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦))
229224, 228syl6bbr 280 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
23047adantrr 708 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑏 Fn (1...(𝑁 + 1)))
231157adantrl 707 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
232 f1ofn 6325 . . . . . . . 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 6505 . . . . . . 7 ((𝑏 Fn (1...(𝑁 + 1)) ∧ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1))) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
235230, 233, 234syl2anc 579 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
236155adantrl 707 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐:𝐾1-1-onto𝐾)
237 f1ofn 6325 . . . . . . . 8 (𝑐:𝐾1-1-onto𝐾𝑐 Fn 𝐾)
238236, 237syl 17 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐 Fn 𝐾)
239127adantr 472 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝐾 ⊆ (1...(𝑁 + 1)))
240 fnssres 6184 . . . . . . . 8 ((𝑏 Fn (1...(𝑁 + 1)) ∧ 𝐾 ⊆ (1...(𝑁 + 1))) → (𝑏𝐾) Fn 𝐾)
241230, 239, 240syl2anc 579 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝐾) Fn 𝐾)
242 eqfnfv 6505 . . . . . . 7 ((𝑐 Fn 𝐾 ∧ (𝑏𝐾) Fn 𝐾) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
243238, 241, 242syl2anc 579 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
244229, 235, 2433bitr4d 302 . . . . 5 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ 𝑐 = (𝑏𝐾)))
245244ex 401 . . . 4 (𝜑 → ((𝑏𝐵𝑐𝐶) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ 𝑐 = (𝑏𝐾))))
24612, 23, 142, 203, 245en3d 8201 . . 3 (𝜑𝐵𝐶)
247 hashen 13344 . . . 4 ((𝐵 ∈ Fin ∧ 𝐶 ∈ Fin) → ((♯‘𝐵) = (♯‘𝐶) ↔ 𝐵𝐶))
24810, 21, 247mp2an 683 . . 3 ((♯‘𝐵) = (♯‘𝐶) ↔ 𝐵𝐶)
249246, 248sylibr 225 . 2 (𝜑 → (♯‘𝐵) = (♯‘𝐶))
25013fveq2i 6382 . . . 4 (♯‘𝐶) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25155derangval 31618 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}))
25218, 251ax-mp 5 . . . 4 (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25355, 56derangen2 31625 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (𝑆‘(♯‘𝐾)))
25418, 253ax-mp 5 . . . 4 (𝐷𝐾) = (𝑆‘(♯‘𝐾))
255250, 252, 2543eqtr2ri 2794 . . 3 (𝑆‘(♯‘𝐾)) = (♯‘𝐶)
25660simp3d 1174 . . . 4 (𝜑 → (♯‘𝐾) = (𝑁 − 1))
257256fveq2d 6383 . . 3 (𝜑 → (𝑆‘(♯‘𝐾)) = (𝑆‘(𝑁 − 1)))
258255, 257syl5eqr 2813 . 2 (𝜑 → (♯‘𝐶) = (𝑆‘(𝑁 − 1)))
259249, 258eqtrd 2799 1 (𝜑 → (♯‘𝐵) = (𝑆‘(𝑁 − 1)))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 197  wa 384   = wceq 1652  wcel 2155  {cab 2751  wne 2937  wral 3055  wrex 3056  {crab 3059  Vcvv 3350  cdif 3731  cun 3732  cin 3733  wss 3734  c0 4081  {csn 4336  {cpr 4338  cop 4342   class class class wbr 4811  cmpt 4890  ccnv 5278  cres 5281  Fun wfun 6064   Fn wfn 6065  wf 6066  1-1wf1 6067  ontowfo 6068  1-1-ontowf1o 6069  cfv 6070  (class class class)co 6846  cen 8161  Fincfn 8164  1c1 10194   + caddc 10196  cmin 10524  cn 11278  2c2 11331  0cn0 11542  cuz 11891  ...cfz 12538  chash 13326
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1890  ax-4 1904  ax-5 2005  ax-6 2070  ax-7 2105  ax-8 2157  ax-9 2164  ax-10 2183  ax-11 2198  ax-12 2211  ax-13 2352  ax-ext 2743  ax-rep 4932  ax-sep 4943  ax-nul 4951  ax-pow 5003  ax-pr 5064  ax-un 7151  ax-cnex 10249  ax-resscn 10250  ax-1cn 10251  ax-icn 10252  ax-addcl 10253  ax-addrcl 10254  ax-mulcl 10255  ax-mulrcl 10256  ax-mulcom 10257  ax-addass 10258  ax-mulass 10259  ax-distr 10260  ax-i2m1 10261  ax-1ne0 10262  ax-1rid 10263  ax-rnegex 10264  ax-rrecex 10265  ax-cnre 10266  ax-pre-lttri 10267  ax-pre-lttrn 10268  ax-pre-ltadd 10269  ax-pre-mulgt0 10270
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 874  df-3or 1108  df-3an 1109  df-tru 1656  df-ex 1875  df-nf 1879  df-sb 2063  df-mo 2565  df-eu 2582  df-clab 2752  df-cleq 2758  df-clel 2761  df-nfc 2896  df-ne 2938  df-nel 3041  df-ral 3060  df-rex 3061  df-reu 3062  df-rmo 3063  df-rab 3064  df-v 3352  df-sbc 3599  df-csb 3694  df-dif 3737  df-un 3739  df-in 3741  df-ss 3748  df-pss 3750  df-nul 4082  df-if 4246  df-pw 4319  df-sn 4337  df-pr 4339  df-tp 4341  df-op 4343  df-uni 4597  df-int 4636  df-iun 4680  df-br 4812  df-opab 4874  df-mpt 4891  df-tr 4914  df-id 5187  df-eprel 5192  df-po 5200  df-so 5201  df-fr 5238  df-we 5240  df-xp 5285  df-rel 5286  df-cnv 5287  df-co 5288  df-dm 5289  df-rn 5290  df-res 5291  df-ima 5292  df-pred 5867  df-ord 5913  df-on 5914  df-lim 5915  df-suc 5916  df-iota 6033  df-fun 6072  df-fn 6073  df-f 6074  df-f1 6075  df-fo 6076  df-f1o 6077  df-fv 6078  df-riota 6807  df-ov 6849  df-oprab 6850  df-mpt2 6851  df-om 7268  df-1st 7370  df-2nd 7371  df-wrecs 7614  df-recs 7676  df-rdg 7714  df-1o 7768  df-2o 7769  df-oadd 7772  df-er 7951  df-map 8066  df-pm 8067  df-en 8165  df-dom 8166  df-sdom 8167  df-fin 8168  df-card 9020  df-cda 9247  df-pnf 10334  df-mnf 10335  df-xr 10336  df-ltxr 10337  df-le 10338  df-sub 10526  df-neg 10527  df-nn 11279  df-2 11339  df-n0 11543  df-xnn0 11615  df-z 11629  df-uz 11892  df-fz 12539  df-hash 13327
This theorem is referenced by:  subfacp1lem6  31636
  Copyright terms: Public domain W3C validator