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 30418
Description: Lemma for subfacp1 30422. In subfacp1lem6 30421 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 12633 . . . . . . . . 9 (1...(𝑁 + 1)) ∈ Fin
3 deranglem 30402 . . . . . . . . 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 2684 . . . . . . 7 𝐴 ∈ Fin
6 subfacp1lem3.b . . . . . . . 8 𝐵 = {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)}
7 ssrab2 3650 . . . . . . . 8 {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)} ⊆ 𝐴
86, 7eqsstri 3598 . . . . . . 7 𝐵𝐴
9 ssfi 8065 . . . . . . 7 ((𝐴 ∈ Fin ∧ 𝐵𝐴) → 𝐵 ∈ Fin)
105, 8, 9mp2an 704 . . . . . 6 𝐵 ∈ Fin
1110elexi 3186 . . . . 5 𝐵 ∈ V
1211a1i 11 . . . 4 (𝜑𝐵 ∈ V)
13 subfacp1lem3.c . . . . . . 7 𝐶 = {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}
14 subfacp1lem1.k . . . . . . . . 9 𝐾 = ((2...(𝑁 + 1)) ∖ {𝑀})
15 fzfi 12633 . . . . . . . . . 10 (2...(𝑁 + 1)) ∈ Fin
16 diffi 8077 . . . . . . . . . 10 ((2...(𝑁 + 1)) ∈ Fin → ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin)
1715, 16ax-mp 5 . . . . . . . . 9 ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin
1814, 17eqeltri 2684 . . . . . . . 8 𝐾 ∈ Fin
19 deranglem 30402 . . . . . . . 8 (𝐾 ∈ Fin → {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin)
2018, 19ax-mp 5 . . . . . . 7 {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)} ∈ Fin
2113, 20eqeltri 2684 . . . . . 6 𝐶 ∈ Fin
2221elexi 3186 . . . . 5 𝐶 ∈ V
2322a1i 11 . . . 4 (𝜑𝐶 ∈ V)
24 simpr 476 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → 𝑏𝐵)
25 fveq1 6102 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔‘1) = (𝑏‘1))
2625eqeq1d 2612 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔‘1) = 𝑀 ↔ (𝑏‘1) = 𝑀))
27 fveq1 6102 . . . . . . . . . . . . . . . 16 (𝑔 = 𝑏 → (𝑔𝑀) = (𝑏𝑀))
2827eqeq1d 2612 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → ((𝑔𝑀) = 1 ↔ (𝑏𝑀) = 1))
2926, 28anbi12d 743 . . . . . . . . . . . . . 14 (𝑔 = 𝑏 → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3029, 6elrab2 3333 . . . . . . . . . . . . 13 (𝑏𝐵 ↔ (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3124, 30sylib 207 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
3231simpld 474 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏𝐴)
33 vex 3176 . . . . . . . . . . . 12 𝑏 ∈ V
34 f1oeq1 6040 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
35 fveq1 6102 . . . . . . . . . . . . . . 15 (𝑓 = 𝑏 → (𝑓𝑦) = (𝑏𝑦))
3635neeq1d 2841 . . . . . . . . . . . . . 14 (𝑓 = 𝑏 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
3736ralbidv 2969 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
3834, 37anbi12d 743 . . . . . . . . . . . 12 (𝑓 = 𝑏 → ((𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦) ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)))
3933, 38, 1elab2 3323 . . . . . . . . . . 11 (𝑏𝐴 ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
4032, 39sylib 207 . . . . . . . . . 10 ((𝜑𝑏𝐵) → (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
4140simpld 474 . . . . . . . . 9 ((𝜑𝑏𝐵) → 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
42 f1of1 6049 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)))
43 df-f1 5809 . . . . . . . . . 10 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) ↔ (𝑏:(1...(𝑁 + 1))⟶(1...(𝑁 + 1)) ∧ Fun 𝑏))
4443simprbi 479 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) → Fun 𝑏)
4541, 42, 443syl 18 . . . . . . . 8 ((𝜑𝑏𝐵) → Fun 𝑏)
46 f1ofn 6051 . . . . . . . . . . . 12 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏 Fn (1...(𝑁 + 1)))
4741, 46syl 17 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → 𝑏 Fn (1...(𝑁 + 1)))
48 fnresdm 5914 . . . . . . . . . . 11 (𝑏 Fn (1...(𝑁 + 1)) → (𝑏 ↾ (1...(𝑁 + 1))) = 𝑏)
49 f1oeq1 6040 . . . . . . . . . . 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 246 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
52 f1ofo 6057 . . . . . . . . 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 3739 . . . . . . . . . . . . 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 30415 . . . . . . . . . . . . . 14 (𝜑 → ((𝐾 ∩ {1, 𝑀}) = ∅ ∧ (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)) ∧ (#‘𝐾) = (𝑁 − 1)))
6160simp2d 1067 . . . . . . . . . . . . 13 (𝜑 → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
6254, 61syl5sseq 3616 . . . . . . . . . . . 12 (𝜑 → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
6362adantr 480 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
64 fnssres 5918 . . . . . . . . . . 11 ((𝑏 Fn (1...(𝑁 + 1)) ∧ {1, 𝑀} ⊆ (1...(𝑁 + 1))) → (𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀})
6547, 63, 64syl2anc 691 . . . . . . . . . 10 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀})
6631simprd 478 . . . . . . . . . . . . . 14 ((𝜑𝑏𝐵) → ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1))
6766simpld 474 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → (𝑏‘1) = 𝑀)
6859prid2 4242 . . . . . . . . . . . . 13 𝑀 ∈ {1, 𝑀}
6967, 68syl6eqel 2696 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏‘1) ∈ {1, 𝑀})
7066simprd 478 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → (𝑏𝑀) = 1)
71 1ex 9914 . . . . . . . . . . . . . 14 1 ∈ V
7271prid1 4241 . . . . . . . . . . . . 13 1 ∈ {1, 𝑀}
7370, 72syl6eqel 2696 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝑀) ∈ {1, 𝑀})
74 fveq2 6103 . . . . . . . . . . . . . 14 (𝑥 = 1 → (𝑏𝑥) = (𝑏‘1))
7574eleq1d 2672 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏‘1) ∈ {1, 𝑀}))
76 fveq2 6103 . . . . . . . . . . . . . 14 (𝑥 = 𝑀 → (𝑏𝑥) = (𝑏𝑀))
7776eleq1d 2672 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑀) ∈ {1, 𝑀}))
7871, 59, 75, 77ralpr 4185 . . . . . . . . . . . 12 (∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀} ↔ ((𝑏‘1) ∈ {1, 𝑀} ∧ (𝑏𝑀) ∈ {1, 𝑀}))
7969, 73, 78sylanbrc 695 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
80 fvres 6117 . . . . . . . . . . . . 13 (𝑥 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑥) = (𝑏𝑥))
8180eleq1d 2672 . . . . . . . . . . . 12 (𝑥 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑥) ∈ {1, 𝑀}))
8281ralbiia 2962 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
8379, 82sylibr 223 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀})
84 ffnfv 6295 . . . . . . . . . 10 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀}))
8565, 83, 84sylanbrc 695 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀})
86 fveq2 6103 . . . . . . . . . . . . . 14 (𝑦 = 𝑀 → (𝑏𝑦) = (𝑏𝑀))
8786eqeq1d 2612 . . . . . . . . . . . . 13 (𝑦 = 𝑀 → ((𝑏𝑦) = 1 ↔ (𝑏𝑀) = 1))
8887rspcev 3282 . . . . . . . . . . . 12 ((𝑀 ∈ {1, 𝑀} ∧ (𝑏𝑀) = 1) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
8968, 70, 88sylancr 694 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
90 fveq2 6103 . . . . . . . . . . . . . 14 (𝑦 = 1 → (𝑏𝑦) = (𝑏‘1))
9190eqeq1d 2612 . . . . . . . . . . . . 13 (𝑦 = 1 → ((𝑏𝑦) = 𝑀 ↔ (𝑏‘1) = 𝑀))
9291rspcev 3282 . . . . . . . . . . . 12 ((1 ∈ {1, 𝑀} ∧ (𝑏‘1) = 𝑀) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
9372, 67, 92sylancr 694 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
94 eqeq2 2621 . . . . . . . . . . . . 13 (𝑥 = 1 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 1))
9594rexbidv 3034 . . . . . . . . . . . 12 (𝑥 = 1 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1))
96 eqeq2 2621 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑀))
9796rexbidv 3034 . . . . . . . . . . . 12 (𝑥 = 𝑀 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9871, 59, 95, 97ralpr 4185 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1 ∧ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
9989, 93, 98sylanbrc 695 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
100 eqcom 2617 . . . . . . . . . . . . 13 (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥)
101 fvres 6117 . . . . . . . . . . . . . 14 (𝑦 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑦) = (𝑏𝑦))
102101eqeq1d 2612 . . . . . . . . . . . . 13 (𝑦 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑥))
103100, 102syl5bb 271 . . . . . . . . . . . 12 (𝑦 ∈ {1, 𝑀} → (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ (𝑏𝑦) = 𝑥))
104103rexbiia 3022 . . . . . . . . . . 11 (∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
105104ralbii 2963 . . . . . . . . . 10 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
10699, 105sylibr 223 . . . . . . . . 9 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦))
107 dffo3 6282 . . . . . . . . 9 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦)))
10885, 106, 107sylanbrc 695 . . . . . . . 8 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀})
109 resdif 6070 . . . . . . . 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, 𝑀}))
11045, 53, 108, 109syl3anc 1318 . . . . . . 7 ((𝜑𝑏𝐵) → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}))
111 uncom 3719 . . . . . . . . . . 11 ({1, 𝑀} ∪ 𝐾) = (𝐾 ∪ {1, 𝑀})
112111, 61syl5eq 2656 . . . . . . . . . 10 (𝜑 → ({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)))
113 incom 3767 . . . . . . . . . . . 12 ({1, 𝑀} ∩ 𝐾) = (𝐾 ∩ {1, 𝑀})
11460simp1d 1066 . . . . . . . . . . . 12 (𝜑 → (𝐾 ∩ {1, 𝑀}) = ∅)
115113, 114syl5eq 2656 . . . . . . . . . . 11 (𝜑 → ({1, 𝑀} ∩ 𝐾) = ∅)
116 uneqdifeq 4009 . . . . . . . . . . 11 (({1, 𝑀} ⊆ (1...(𝑁 + 1)) ∧ ({1, 𝑀} ∩ 𝐾) = ∅) → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
11762, 115, 116syl2anc 691 . . . . . . . . . 10 (𝜑 → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
118112, 117mpbid 221 . . . . . . . . 9 (𝜑 → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
119118adantr 480 . . . . . . . 8 ((𝜑𝑏𝐵) → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
120 reseq2 5312 . . . . . . . . . 10 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})) = (𝑏𝐾))
121 f1oeq1 6040 . . . . . . . . . 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, 𝑀})))
122120, 121syl 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, 𝑀})))
123 f1oeq2 6041 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
124 f1oeq3 6042 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
125122, 123, 1243bitrd 293 . . . . . . . 8 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
126119, 125syl 17 . . . . . . 7 ((𝜑𝑏𝐵) → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
127110, 126mpbid 221 . . . . . 6 ((𝜑𝑏𝐵) → (𝑏𝐾):𝐾1-1-onto𝐾)
128 ssun1 3738 . . . . . . . . 9 𝐾 ⊆ (𝐾 ∪ {1, 𝑀})
129128, 61syl5sseq 3616 . . . . . . . 8 (𝜑𝐾 ⊆ (1...(𝑁 + 1)))
130129adantr 480 . . . . . . 7 ((𝜑𝑏𝐵) → 𝐾 ⊆ (1...(𝑁 + 1)))
13140simprd 478 . . . . . . 7 ((𝜑𝑏𝐵) → ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)
132 ssralv 3629 . . . . . . 7 (𝐾 ⊆ (1...(𝑁 + 1)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦 → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
133130, 131, 132sylc 63 . . . . . 6 ((𝜑𝑏𝐵) → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)
13433resex 5363 . . . . . . 7 (𝑏𝐾) ∈ V
135 f1oeq1 6040 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (𝑓:𝐾1-1-onto𝐾 ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
136 fveq1 6102 . . . . . . . . . . 11 (𝑓 = (𝑏𝐾) → (𝑓𝑦) = ((𝑏𝐾)‘𝑦))
137 fvres 6117 . . . . . . . . . . 11 (𝑦𝐾 → ((𝑏𝐾)‘𝑦) = (𝑏𝑦))
138136, 137sylan9eq 2664 . . . . . . . . . 10 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → (𝑓𝑦) = (𝑏𝑦))
139138neeq1d 2841 . . . . . . . . 9 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
140139ralbidva 2968 . . . . . . . 8 (𝑓 = (𝑏𝐾) → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
141135, 140anbi12d 743 . . . . . . 7 (𝑓 = (𝑏𝐾) → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)))
142134, 141, 13elab2 3323 . . . . . 6 ((𝑏𝐾) ∈ 𝐶 ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
143127, 133, 142sylanbrc 695 . . . . 5 ((𝜑𝑏𝐵) → (𝑏𝐾) ∈ 𝐶)
144143ex 449 . . . 4 (𝜑 → (𝑏𝐵 → (𝑏𝐾) ∈ 𝐶))
14557adantr 480 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑁 ∈ ℕ)
14658adantr 480 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑀 ∈ (2...(𝑁 + 1)))
147 eqid 2610 . . . . . . . . 9 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})
148 simpr 476 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑐𝐶)
149 vex 3176 . . . . . . . . . . . 12 𝑐 ∈ V
150 f1oeq1 6040 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (𝑓:𝐾1-1-onto𝐾𝑐:𝐾1-1-onto𝐾))
151 fveq1 6102 . . . . . . . . . . . . . . 15 (𝑓 = 𝑐 → (𝑓𝑦) = (𝑐𝑦))
152151neeq1d 2841 . . . . . . . . . . . . . 14 (𝑓 = 𝑐 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑐𝑦) ≠ 𝑦))
153152ralbidv 2969 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
154150, 153anbi12d 743 . . . . . . . . . . . 12 (𝑓 = 𝑐 → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)))
155149, 154, 13elab2 3323 . . . . . . . . . . 11 (𝑐𝐶 ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
156148, 155sylib 207 . . . . . . . . . 10 ((𝜑𝑐𝐶) → (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
157156simpld 474 . . . . . . . . 9 ((𝜑𝑐𝐶) → 𝑐:𝐾1-1-onto𝐾)
15855, 56, 1, 145, 146, 59, 14, 147, 157subfacp1lem2a 30416 . . . . . . . 8 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
159158simp1d 1066 . . . . . . 7 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
16055, 56, 1, 145, 146, 59, 14, 147, 157subfacp1lem2b 30417 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = (𝑐𝑦))
161156simprd 478 . . . . . . . . . . . 12 ((𝜑𝑐𝐶) → ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)
162161r19.21bi 2916 . . . . . . . . . . 11 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → (𝑐𝑦) ≠ 𝑦)
163160, 162eqnetrd 2849 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
164163ralrimiva 2949 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
165158simp2d 1067 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
166 elfzuz 12209 . . . . . . . . . . . . 13 (𝑀 ∈ (2...(𝑁 + 1)) → 𝑀 ∈ (ℤ‘2))
167 eluz2b3 11638 . . . . . . . . . . . . . 14 (𝑀 ∈ (ℤ‘2) ↔ (𝑀 ∈ ℕ ∧ 𝑀 ≠ 1))
168167simprbi 479 . . . . . . . . . . . . 13 (𝑀 ∈ (ℤ‘2) → 𝑀 ≠ 1)
16958, 166, 1683syl 18 . . . . . . . . . . . 12 (𝜑𝑀 ≠ 1)
170169adantr 480 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 𝑀 ≠ 1)
171165, 170eqnetrd 2849 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1)
172158simp3d 1068 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
173170necomd 2837 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → 1 ≠ 𝑀)
174172, 173eqnetrd 2849 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀)
175 fveq2 6103 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
176 id 22 . . . . . . . . . . . 12 (𝑦 = 1 → 𝑦 = 1)
177175, 176neeq12d 2843 . . . . . . . . . . 11 (𝑦 = 1 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1))
178 fveq2 6103 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
179 id 22 . . . . . . . . . . . 12 (𝑦 = 𝑀𝑦 = 𝑀)
180178, 179neeq12d 2843 . . . . . . . . . . 11 (𝑦 = 𝑀 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
18171, 59, 177, 180ralpr 4185 . . . . . . . . . 10 (∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
182171, 174, 181sylanbrc 695 . . . . . . . . 9 ((𝜑𝑐𝐶) → ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
183 ralunb 3756 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ∧ ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
184164, 182, 183sylanbrc 695 . . . . . . . 8 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
18561adantr 480 . . . . . . . . 9 ((𝜑𝑐𝐶) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
186185raleqdv 3121 . . . . . . . 8 ((𝜑𝑐𝐶) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
187184, 186mpbid 221 . . . . . . 7 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
188 prex 4836 . . . . . . . . 9 {⟨1, 𝑀⟩, ⟨𝑀, 1⟩} ∈ V
189149, 188unex 6854 . . . . . . . 8 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ V
190 f1oeq1 6040 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
191 fveq1 6102 . . . . . . . . . . 11 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
192191neeq1d 2841 . . . . . . . . . 10 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑓𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
193192ralbidv 2969 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
194190, 193anbi12d 743 . . . . . . . 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⟩})‘𝑦) ≠ 𝑦)))
195189, 194, 1elab2 3323 . . . . . . 7 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
196159, 187, 195sylanbrc 695 . . . . . 6 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴)
197165, 172jca 553 . . . . . 6 ((𝜑𝑐𝐶) → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
198 fveq1 6102 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
199198eqeq1d 2612 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔‘1) = 𝑀 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀))
200 fveq1 6102 . . . . . . . . 9 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
201200eqeq1d 2612 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔𝑀) = 1 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
202199, 201anbi12d 743 . . . . . . 7 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
203202, 6elrab2 3333 . . . . . 6 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ∧ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
204196, 197, 203sylanbrc 695 . . . . 5 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵)
205204ex 449 . . . 4 (𝜑 → (𝑐𝐶 → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵))
20667adantrr 749 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = 𝑀)
207165adantrl 748 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
208206, 207eqtr4d 2647 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
20970adantrr 749 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = 1)
210172adantrl 748 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
211209, 210eqtr4d 2647 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
21290, 175eqeq12d 2625 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1)))
21386, 178eqeq12d 2625 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
21471, 59, 212, 213ralpr 4185 . . . . . . . . . . 11 (∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ((𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ∧ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
215208, 211, 214sylanbrc 695 . . . . . . . . . 10 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
216215biantrud 527 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))))
217 ralunb 3756 . . . . . . . . 9 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
218216, 217syl6bbr 277 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
219160eqeq2d 2620 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
220219ralbidva 2968 . . . . . . . . 9 ((𝜑𝑐𝐶) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
221220adantrl 748 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
22261adantr 480 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
223222raleqdv 3121 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
224218, 221, 2233bitr3rd 298 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
225137eqeq2d 2620 . . . . . . . . 9 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑐𝑦) = (𝑏𝑦)))
226 eqcom 2617 . . . . . . . . 9 ((𝑐𝑦) = (𝑏𝑦) ↔ (𝑏𝑦) = (𝑐𝑦))
227225, 226syl6bb 275 . . . . . . . 8 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
228227ralbiia 2962 . . . . . . 7 (∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦))
229224, 228syl6bbr 277 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
23047adantrr 749 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑏 Fn (1...(𝑁 + 1)))
231159adantrl 748 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
232 f1ofn 6051 . . . . . . . 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 6219 . . . . . . 7 ((𝑏 Fn (1...(𝑁 + 1)) ∧ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1))) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
235230, 233, 234syl2anc 691 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
236157adantrl 748 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐:𝐾1-1-onto𝐾)
237 f1ofn 6051 . . . . . . . 8 (𝑐:𝐾1-1-onto𝐾𝑐 Fn 𝐾)
238236, 237syl 17 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐 Fn 𝐾)
239129adantr 480 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝐾 ⊆ (1...(𝑁 + 1)))
240 fnssres 5918 . . . . . . . 8 ((𝑏 Fn (1...(𝑁 + 1)) ∧ 𝐾 ⊆ (1...(𝑁 + 1))) → (𝑏𝐾) Fn 𝐾)
241230, 239, 240syl2anc 691 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝐾) Fn 𝐾)
242 eqfnfv 6219 . . . . . . 7 ((𝑐 Fn 𝐾 ∧ (𝑏𝐾) Fn 𝐾) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
243238, 241, 242syl2anc 691 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
244229, 235, 2433bitr4d 299 . . . . 5 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ 𝑐 = (𝑏𝐾)))
245244ex 449 . . . 4 (𝜑 → ((𝑏𝐵𝑐𝐶) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ 𝑐 = (𝑏𝐾))))
24612, 23, 144, 205, 245en3d 7878 . . 3 (𝜑𝐵𝐶)
247 hashen 12997 . . . 4 ((𝐵 ∈ Fin ∧ 𝐶 ∈ Fin) → ((#‘𝐵) = (#‘𝐶) ↔ 𝐵𝐶))
24810, 21, 247mp2an 704 . . 3 ((#‘𝐵) = (#‘𝐶) ↔ 𝐵𝐶)
249246, 248sylibr 223 . 2 (𝜑 → (#‘𝐵) = (#‘𝐶))
25013fveq2i 6106 . . . 4 (#‘𝐶) = (#‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25155derangval 30403 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (#‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}))
25218, 251ax-mp 5 . . . 4 (𝐷𝐾) = (#‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
25355, 56derangen2 30410 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (𝑆‘(#‘𝐾)))
25418, 253ax-mp 5 . . . 4 (𝐷𝐾) = (𝑆‘(#‘𝐾))
255250, 252, 2543eqtr2ri 2639 . . 3 (𝑆‘(#‘𝐾)) = (#‘𝐶)
25660simp3d 1068 . . . 4 (𝜑 → (#‘𝐾) = (𝑁 − 1))
257256fveq2d 6107 . . 3 (𝜑 → (𝑆‘(#‘𝐾)) = (𝑆‘(𝑁 − 1)))
258255, 257syl5eqr 2658 . 2 (𝜑 → (#‘𝐶) = (𝑆‘(𝑁 − 1)))
259249, 258eqtrd 2644 1 (𝜑 → (#‘𝐵) = (𝑆‘(𝑁 − 1)))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 195  wa 383   = wceq 1475  wcel 1977  {cab 2596  wne 2780  wral 2896  wrex 2897  {crab 2900  Vcvv 3173  cdif 3537  cun 3538  cin 3539  wss 3540  c0 3874  {csn 4125  {cpr 4127  cop 4131   class class class wbr 4583  cmpt 4643  ccnv 5037  cres 5040  Fun wfun 5798   Fn wfn 5799  wf 5800  1-1wf1 5801  ontowfo 5802  1-1-ontowf1o 5803  cfv 5804  (class class class)co 6549  cen 7838  Fincfn 7841  1c1 9816   + caddc 9818  cmin 10145  cn 10897  2c2 10947  0cn0 11169  cuz 11563  ...cfz 12197  #chash 12979
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1713  ax-4 1728  ax-5 1827  ax-6 1875  ax-7 1922  ax-8 1979  ax-9 1986  ax-10 2006  ax-11 2021  ax-12 2034  ax-13 2234  ax-ext 2590  ax-rep 4699  ax-sep 4709  ax-nul 4717  ax-pow 4769  ax-pr 4833  ax-un 6847  ax-cnex 9871  ax-resscn 9872  ax-1cn 9873  ax-icn 9874  ax-addcl 9875  ax-addrcl 9876  ax-mulcl 9877  ax-mulrcl 9878  ax-mulcom 9879  ax-addass 9880  ax-mulass 9881  ax-distr 9882  ax-i2m1 9883  ax-1ne0 9884  ax-1rid 9885  ax-rnegex 9886  ax-rrecex 9887  ax-cnre 9888  ax-pre-lttri 9889  ax-pre-lttrn 9890  ax-pre-ltadd 9891  ax-pre-mulgt0 9892
This theorem depends on definitions:  df-bi 196  df-or 384  df-an 385  df-3or 1032  df-3an 1033  df-tru 1478  df-ex 1696  df-nf 1701  df-sb 1868  df-eu 2462  df-mo 2463  df-clab 2597  df-cleq 2603  df-clel 2606  df-nfc 2740  df-ne 2782  df-nel 2783  df-ral 2901  df-rex 2902  df-reu 2903  df-rmo 2904  df-rab 2905  df-v 3175  df-sbc 3403  df-csb 3500  df-dif 3543  df-un 3545  df-in 3547  df-ss 3554  df-pss 3556  df-nul 3875  df-if 4037  df-pw 4110  df-sn 4126  df-pr 4128  df-tp 4130  df-op 4132  df-uni 4373  df-int 4411  df-iun 4457  df-br 4584  df-opab 4644  df-mpt 4645  df-tr 4681  df-eprel 4949  df-id 4953  df-po 4959  df-so 4960  df-fr 4997  df-we 4999  df-xp 5044  df-rel 5045  df-cnv 5046  df-co 5047  df-dm 5048  df-rn 5049  df-res 5050  df-ima 5051  df-pred 5597  df-ord 5643  df-on 5644  df-lim 5645  df-suc 5646  df-iota 5768  df-fun 5806  df-fn 5807  df-f 5808  df-f1 5809  df-fo 5810  df-f1o 5811  df-fv 5812  df-riota 6511  df-ov 6552  df-oprab 6553  df-mpt2 6554  df-om 6958  df-1st 7059  df-2nd 7060  df-wrecs 7294  df-recs 7355  df-rdg 7393  df-1o 7447  df-2o 7448  df-oadd 7451  df-er 7629  df-map 7746  df-pm 7747  df-en 7842  df-dom 7843  df-sdom 7844  df-fin 7845  df-card 8648  df-cda 8873  df-pnf 9955  df-mnf 9956  df-xr 9957  df-ltxr 9958  df-le 9959  df-sub 10147  df-neg 10148  df-nn 10898  df-2 10956  df-n0 11170  df-xnn0 11241  df-z 11255  df-uz 11564  df-fz 12198  df-hash 12980
This theorem is referenced by:  subfacp1lem6  30421
  Copyright terms: Public domain W3C validator