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 34471
Description: Lemma for subfacp1 34475. In subfacp1lem6 34474 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 . . . . . . 7 𝐴 = {𝑓 ∣ (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦)}
2 fzfi 13941 . . . . . . . 8 (1...(𝑁 + 1)) ∈ Fin
3 deranglem 34455 . . . . . . . 8 ((1...(𝑁 + 1)) ∈ Fin → {𝑓 ∣ (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦)} ∈ Fin)
42, 3ax-mp 5 . . . . . . 7 {𝑓 ∣ (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦)} ∈ Fin
51, 4eqeltri 2827 . . . . . 6 𝐴 ∈ Fin
6 subfacp1lem3.b . . . . . . 7 𝐵 = {𝑔𝐴 ∣ ((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1)}
76ssrab3 4079 . . . . . 6 𝐵𝐴
8 ssfi 9175 . . . . . 6 ((𝐴 ∈ Fin ∧ 𝐵𝐴) → 𝐵 ∈ Fin)
95, 7, 8mp2an 688 . . . . 5 𝐵 ∈ Fin
109elexi 3492 . . . 4 𝐵 ∈ V
1110a1i 11 . . 3 (𝜑𝐵 ∈ V)
12 eqid 2730 . . . 4 (𝑏𝐵 ↦ (𝑏𝐾)) = (𝑏𝐵 ↦ (𝑏𝐾))
13 simpr 483 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → 𝑏𝐵)
14 fveq1 6889 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → (𝑔‘1) = (𝑏‘1))
1514eqeq1d 2732 . . . . . . . . . . . . . 14 (𝑔 = 𝑏 → ((𝑔‘1) = 𝑀 ↔ (𝑏‘1) = 𝑀))
16 fveq1 6889 . . . . . . . . . . . . . . 15 (𝑔 = 𝑏 → (𝑔𝑀) = (𝑏𝑀))
1716eqeq1d 2732 . . . . . . . . . . . . . 14 (𝑔 = 𝑏 → ((𝑔𝑀) = 1 ↔ (𝑏𝑀) = 1))
1815, 17anbi12d 629 . . . . . . . . . . . . 13 (𝑔 = 𝑏 → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
1918, 6elrab2 3685 . . . . . . . . . . . 12 (𝑏𝐵 ↔ (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
2013, 19sylib 217 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → (𝑏𝐴 ∧ ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1)))
2120simpld 493 . . . . . . . . . 10 ((𝜑𝑏𝐵) → 𝑏𝐴)
22 vex 3476 . . . . . . . . . . 11 𝑏 ∈ V
23 f1oeq1 6820 . . . . . . . . . . . 12 (𝑓 = 𝑏 → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
24 fveq1 6889 . . . . . . . . . . . . . 14 (𝑓 = 𝑏 → (𝑓𝑦) = (𝑏𝑦))
2524neeq1d 2998 . . . . . . . . . . . . 13 (𝑓 = 𝑏 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
2625ralbidv 3175 . . . . . . . . . . . 12 (𝑓 = 𝑏 → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
2723, 26anbi12d 629 . . . . . . . . . . 11 (𝑓 = 𝑏 → ((𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦) ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)))
2822, 27, 1elab2 3671 . . . . . . . . . 10 (𝑏𝐴 ↔ (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
2921, 28sylib 217 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦))
3029simpld 493 . . . . . . . 8 ((𝜑𝑏𝐵) → 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
31 f1of1 6831 . . . . . . . 8 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)))
32 df-f1 6547 . . . . . . . . 9 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) ↔ (𝑏:(1...(𝑁 + 1))⟶(1...(𝑁 + 1)) ∧ Fun 𝑏))
3332simprbi 495 . . . . . . . 8 (𝑏:(1...(𝑁 + 1))–1-1→(1...(𝑁 + 1)) → Fun 𝑏)
3430, 31, 333syl 18 . . . . . . 7 ((𝜑𝑏𝐵) → Fun 𝑏)
35 f1ofn 6833 . . . . . . . . . . 11 (𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → 𝑏 Fn (1...(𝑁 + 1)))
3630, 35syl 17 . . . . . . . . . 10 ((𝜑𝑏𝐵) → 𝑏 Fn (1...(𝑁 + 1)))
37 fnresdm 6668 . . . . . . . . . 10 (𝑏 Fn (1...(𝑁 + 1)) → (𝑏 ↾ (1...(𝑁 + 1))) = 𝑏)
38 f1oeq1 6820 . . . . . . . . . 10 ((𝑏 ↾ (1...(𝑁 + 1))) = 𝑏 → ((𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
3936, 37, 383syl 18 . . . . . . . . 9 ((𝜑𝑏𝐵) → ((𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ 𝑏:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
4030, 39mpbird 256 . . . . . . . 8 ((𝜑𝑏𝐵) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
41 f1ofo 6839 . . . . . . . 8 ((𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–onto→(1...(𝑁 + 1)))
4240, 41syl 17 . . . . . . 7 ((𝜑𝑏𝐵) → (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–onto→(1...(𝑁 + 1)))
43 ssun2 4172 . . . . . . . . . . . 12 {1, 𝑀} ⊆ (𝐾 ∪ {1, 𝑀})
44 derang.d . . . . . . . . . . . . . 14 𝐷 = (𝑥 ∈ Fin ↦ (♯‘{𝑓 ∣ (𝑓:𝑥1-1-onto𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) ≠ 𝑦)}))
45 subfac.n . . . . . . . . . . . . . 14 𝑆 = (𝑛 ∈ ℕ0 ↦ (𝐷‘(1...𝑛)))
46 subfacp1lem1.n . . . . . . . . . . . . . 14 (𝜑𝑁 ∈ ℕ)
47 subfacp1lem1.m . . . . . . . . . . . . . 14 (𝜑𝑀 ∈ (2...(𝑁 + 1)))
48 subfacp1lem1.x . . . . . . . . . . . . . 14 𝑀 ∈ V
49 subfacp1lem1.k . . . . . . . . . . . . . 14 𝐾 = ((2...(𝑁 + 1)) ∖ {𝑀})
5044, 45, 1, 46, 47, 48, 49subfacp1lem1 34468 . . . . . . . . . . . . 13 (𝜑 → ((𝐾 ∩ {1, 𝑀}) = ∅ ∧ (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)) ∧ (♯‘𝐾) = (𝑁 − 1)))
5150simp2d 1141 . . . . . . . . . . . 12 (𝜑 → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
5243, 51sseqtrid 4033 . . . . . . . . . . 11 (𝜑 → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
5352adantr 479 . . . . . . . . . 10 ((𝜑𝑏𝐵) → {1, 𝑀} ⊆ (1...(𝑁 + 1)))
5436, 53fnssresd 6673 . . . . . . . . 9 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀})
5520simprd 494 . . . . . . . . . . . . 13 ((𝜑𝑏𝐵) → ((𝑏‘1) = 𝑀 ∧ (𝑏𝑀) = 1))
5655simpld 493 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏‘1) = 𝑀)
5748prid2 4766 . . . . . . . . . . . 12 𝑀 ∈ {1, 𝑀}
5856, 57eqeltrdi 2839 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → (𝑏‘1) ∈ {1, 𝑀})
5955simprd 494 . . . . . . . . . . . 12 ((𝜑𝑏𝐵) → (𝑏𝑀) = 1)
60 1ex 11214 . . . . . . . . . . . . 13 1 ∈ V
6160prid1 4765 . . . . . . . . . . . 12 1 ∈ {1, 𝑀}
6259, 61eqeltrdi 2839 . . . . . . . . . . 11 ((𝜑𝑏𝐵) → (𝑏𝑀) ∈ {1, 𝑀})
63 fveq2 6890 . . . . . . . . . . . . 13 (𝑥 = 1 → (𝑏𝑥) = (𝑏‘1))
6463eleq1d 2816 . . . . . . . . . . . 12 (𝑥 = 1 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏‘1) ∈ {1, 𝑀}))
65 fveq2 6890 . . . . . . . . . . . . 13 (𝑥 = 𝑀 → (𝑏𝑥) = (𝑏𝑀))
6665eleq1d 2816 . . . . . . . . . . . 12 (𝑥 = 𝑀 → ((𝑏𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑀) ∈ {1, 𝑀}))
6760, 48, 64, 66ralpr 4703 . . . . . . . . . . 11 (∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀} ↔ ((𝑏‘1) ∈ {1, 𝑀} ∧ (𝑏𝑀) ∈ {1, 𝑀}))
6858, 62, 67sylanbrc 581 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
69 fvres 6909 . . . . . . . . . . . 12 (𝑥 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑥) = (𝑏𝑥))
7069eleq1d 2816 . . . . . . . . . . 11 (𝑥 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ (𝑏𝑥) ∈ {1, 𝑀}))
7170ralbiia 3089 . . . . . . . . . 10 (∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀} ↔ ∀𝑥 ∈ {1, 𝑀} (𝑏𝑥) ∈ {1, 𝑀})
7268, 71sylibr 233 . . . . . . . . 9 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀})
73 ffnfv 7119 . . . . . . . . 9 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}) Fn {1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀} ((𝑏 ↾ {1, 𝑀})‘𝑥) ∈ {1, 𝑀}))
7454, 72, 73sylanbrc 581 . . . . . . . 8 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀})
75 fveqeq2 6899 . . . . . . . . . . . 12 (𝑦 = 𝑀 → ((𝑏𝑦) = 1 ↔ (𝑏𝑀) = 1))
7675rspcev 3611 . . . . . . . . . . 11 ((𝑀 ∈ {1, 𝑀} ∧ (𝑏𝑀) = 1) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
7757, 59, 76sylancr 585 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1)
78 fveqeq2 6899 . . . . . . . . . . . 12 (𝑦 = 1 → ((𝑏𝑦) = 𝑀 ↔ (𝑏‘1) = 𝑀))
7978rspcev 3611 . . . . . . . . . . 11 ((1 ∈ {1, 𝑀} ∧ (𝑏‘1) = 𝑀) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
8061, 56, 79sylancr 585 . . . . . . . . . 10 ((𝜑𝑏𝐵) → ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀)
81 eqeq2 2742 . . . . . . . . . . . 12 (𝑥 = 1 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 1))
8281rexbidv 3176 . . . . . . . . . . 11 (𝑥 = 1 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1))
83 eqeq2 2742 . . . . . . . . . . . 12 (𝑥 = 𝑀 → ((𝑏𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑀))
8483rexbidv 3176 . . . . . . . . . . 11 (𝑥 = 𝑀 → (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
8560, 48, 82, 84ralpr 4703 . . . . . . . . . 10 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥 ↔ (∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 1 ∧ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑀))
8677, 80, 85sylanbrc 581 . . . . . . . . 9 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
87 eqcom 2737 . . . . . . . . . . . 12 (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥)
88 fvres 6909 . . . . . . . . . . . . 13 (𝑦 ∈ {1, 𝑀} → ((𝑏 ↾ {1, 𝑀})‘𝑦) = (𝑏𝑦))
8988eqeq1d 2732 . . . . . . . . . . . 12 (𝑦 ∈ {1, 𝑀} → (((𝑏 ↾ {1, 𝑀})‘𝑦) = 𝑥 ↔ (𝑏𝑦) = 𝑥))
9087, 89bitrid 282 . . . . . . . . . . 11 (𝑦 ∈ {1, 𝑀} → (𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ (𝑏𝑦) = 𝑥))
9190rexbiia 3090 . . . . . . . . . 10 (∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
9291ralbii 3091 . . . . . . . . 9 (∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦) ↔ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀} (𝑏𝑦) = 𝑥)
9386, 92sylibr 233 . . . . . . . 8 ((𝜑𝑏𝐵) → ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦))
94 dffo3 7102 . . . . . . . 8 ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀} ↔ ((𝑏 ↾ {1, 𝑀}):{1, 𝑀}⟶{1, 𝑀} ∧ ∀𝑥 ∈ {1, 𝑀}∃𝑦 ∈ {1, 𝑀}𝑥 = ((𝑏 ↾ {1, 𝑀})‘𝑦)))
9574, 93, 94sylanbrc 581 . . . . . . 7 ((𝜑𝑏𝐵) → (𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀})
96 resdif 6853 . . . . . . 7 ((Fun 𝑏 ∧ (𝑏 ↾ (1...(𝑁 + 1))):(1...(𝑁 + 1))–onto→(1...(𝑁 + 1)) ∧ (𝑏 ↾ {1, 𝑀}):{1, 𝑀}–onto→{1, 𝑀}) → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}))
9734, 42, 95, 96syl3anc 1369 . . . . . 6 ((𝜑𝑏𝐵) → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}))
98 uncom 4152 . . . . . . . . . 10 ({1, 𝑀} ∪ 𝐾) = (𝐾 ∪ {1, 𝑀})
9998, 51eqtrid 2782 . . . . . . . . 9 (𝜑 → ({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)))
100 incom 4200 . . . . . . . . . . 11 ({1, 𝑀} ∩ 𝐾) = (𝐾 ∩ {1, 𝑀})
10150simp1d 1140 . . . . . . . . . . 11 (𝜑 → (𝐾 ∩ {1, 𝑀}) = ∅)
102100, 101eqtrid 2782 . . . . . . . . . 10 (𝜑 → ({1, 𝑀} ∩ 𝐾) = ∅)
103 uneqdifeq 4491 . . . . . . . . . 10 (({1, 𝑀} ⊆ (1...(𝑁 + 1)) ∧ ({1, 𝑀} ∩ 𝐾) = ∅) → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
10452, 102, 103syl2anc 582 . . . . . . . . 9 (𝜑 → (({1, 𝑀} ∪ 𝐾) = (1...(𝑁 + 1)) ↔ ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾))
10599, 104mpbid 231 . . . . . . . 8 (𝜑 → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
106105adantr 479 . . . . . . 7 ((𝜑𝑏𝐵) → ((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾)
107 reseq2 5975 . . . . . . . . 9 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → (𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})) = (𝑏𝐾))
108107f1oeq1d 6827 . . . . . . . 8 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
109 f1oeq2 6821 . . . . . . . 8 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀})))
110 f1oeq3 6822 . . . . . . . 8 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏𝐾):𝐾1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
111108, 109, 1103bitrd 304 . . . . . . 7 (((1...(𝑁 + 1)) ∖ {1, 𝑀}) = 𝐾 → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
112106, 111syl 17 . . . . . 6 ((𝜑𝑏𝐵) → ((𝑏 ↾ ((1...(𝑁 + 1)) ∖ {1, 𝑀})):((1...(𝑁 + 1)) ∖ {1, 𝑀})–1-1-onto→((1...(𝑁 + 1)) ∖ {1, 𝑀}) ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
11397, 112mpbid 231 . . . . 5 ((𝜑𝑏𝐵) → (𝑏𝐾):𝐾1-1-onto𝐾)
114 ssun1 4171 . . . . . . . 8 𝐾 ⊆ (𝐾 ∪ {1, 𝑀})
115114, 51sseqtrid 4033 . . . . . . 7 (𝜑𝐾 ⊆ (1...(𝑁 + 1)))
116115adantr 479 . . . . . 6 ((𝜑𝑏𝐵) → 𝐾 ⊆ (1...(𝑁 + 1)))
11729simprd 494 . . . . . 6 ((𝜑𝑏𝐵) → ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦)
118 ssralv 4049 . . . . . 6 (𝐾 ⊆ (1...(𝑁 + 1)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) ≠ 𝑦 → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
119116, 117, 118sylc 65 . . . . 5 ((𝜑𝑏𝐵) → ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)
12022resex 6028 . . . . . 6 (𝑏𝐾) ∈ V
121 f1oeq1 6820 . . . . . . 7 (𝑓 = (𝑏𝐾) → (𝑓:𝐾1-1-onto𝐾 ↔ (𝑏𝐾):𝐾1-1-onto𝐾))
122 fveq1 6889 . . . . . . . . . 10 (𝑓 = (𝑏𝐾) → (𝑓𝑦) = ((𝑏𝐾)‘𝑦))
123 fvres 6909 . . . . . . . . . 10 (𝑦𝐾 → ((𝑏𝐾)‘𝑦) = (𝑏𝑦))
124122, 123sylan9eq 2790 . . . . . . . . 9 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → (𝑓𝑦) = (𝑏𝑦))
125124neeq1d 2998 . . . . . . . 8 ((𝑓 = (𝑏𝐾) ∧ 𝑦𝐾) → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑏𝑦) ≠ 𝑦))
126125ralbidva 3173 . . . . . . 7 (𝑓 = (𝑏𝐾) → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
127121, 126anbi12d 629 . . . . . 6 (𝑓 = (𝑏𝐾) → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦)))
128 subfacp1lem3.c . . . . . 6 𝐶 = {𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}
129120, 127, 128elab2 3671 . . . . 5 ((𝑏𝐾) ∈ 𝐶 ↔ ((𝑏𝐾):𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑏𝑦) ≠ 𝑦))
130113, 119, 129sylanbrc 581 . . . 4 ((𝜑𝑏𝐵) → (𝑏𝐾) ∈ 𝐶)
13146adantr 479 . . . . . . . 8 ((𝜑𝑐𝐶) → 𝑁 ∈ ℕ)
13247adantr 479 . . . . . . . 8 ((𝜑𝑐𝐶) → 𝑀 ∈ (2...(𝑁 + 1)))
133 eqid 2730 . . . . . . . 8 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})
134 simpr 483 . . . . . . . . . 10 ((𝜑𝑐𝐶) → 𝑐𝐶)
135 vex 3476 . . . . . . . . . . 11 𝑐 ∈ V
136 f1oeq1 6820 . . . . . . . . . . . 12 (𝑓 = 𝑐 → (𝑓:𝐾1-1-onto𝐾𝑐:𝐾1-1-onto𝐾))
137 fveq1 6889 . . . . . . . . . . . . . 14 (𝑓 = 𝑐 → (𝑓𝑦) = (𝑐𝑦))
138137neeq1d 2998 . . . . . . . . . . . . 13 (𝑓 = 𝑐 → ((𝑓𝑦) ≠ 𝑦 ↔ (𝑐𝑦) ≠ 𝑦))
139138ralbidv 3175 . . . . . . . . . . . 12 (𝑓 = 𝑐 → (∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
140136, 139anbi12d 629 . . . . . . . . . . 11 (𝑓 = 𝑐 → ((𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦) ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)))
141135, 140, 128elab2 3671 . . . . . . . . . 10 (𝑐𝐶 ↔ (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
142134, 141sylib 217 . . . . . . . . 9 ((𝜑𝑐𝐶) → (𝑐:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦))
143142simpld 493 . . . . . . . 8 ((𝜑𝑐𝐶) → 𝑐:𝐾1-1-onto𝐾)
14444, 45, 1, 131, 132, 48, 49, 133, 143subfacp1lem2a 34469 . . . . . . 7 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
145144simp1d 1140 . . . . . 6 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
14644, 45, 1, 131, 132, 48, 49, 133, 143subfacp1lem2b 34470 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = (𝑐𝑦))
147142simprd 494 . . . . . . . . . . 11 ((𝜑𝑐𝐶) → ∀𝑦𝐾 (𝑐𝑦) ≠ 𝑦)
148147r19.21bi 3246 . . . . . . . . . 10 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → (𝑐𝑦) ≠ 𝑦)
149146, 148eqnetrd 3006 . . . . . . . . 9 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
150149ralrimiva 3144 . . . . . . . 8 ((𝜑𝑐𝐶) → ∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
151144simp2d 1141 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
152 elfzuz 13501 . . . . . . . . . . . 12 (𝑀 ∈ (2...(𝑁 + 1)) → 𝑀 ∈ (ℤ‘2))
153 eluz2b3 12910 . . . . . . . . . . . . 13 (𝑀 ∈ (ℤ‘2) ↔ (𝑀 ∈ ℕ ∧ 𝑀 ≠ 1))
154153simprbi 495 . . . . . . . . . . . 12 (𝑀 ∈ (ℤ‘2) → 𝑀 ≠ 1)
15547, 152, 1543syl 18 . . . . . . . . . . 11 (𝜑𝑀 ≠ 1)
156155adantr 479 . . . . . . . . . 10 ((𝜑𝑐𝐶) → 𝑀 ≠ 1)
157151, 156eqnetrd 3006 . . . . . . . . 9 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1)
158144simp3d 1142 . . . . . . . . . 10 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
159156necomd 2994 . . . . . . . . . 10 ((𝜑𝑐𝐶) → 1 ≠ 𝑀)
160158, 159eqnetrd 3006 . . . . . . . . 9 ((𝜑𝑐𝐶) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀)
161 fveq2 6890 . . . . . . . . . . 11 (𝑦 = 1 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
162 id 22 . . . . . . . . . . 11 (𝑦 = 1 → 𝑦 = 1)
163161, 162neeq12d 3000 . . . . . . . . . 10 (𝑦 = 1 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1))
164 fveq2 6890 . . . . . . . . . . 11 (𝑦 = 𝑀 → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
165 id 22 . . . . . . . . . . 11 (𝑦 = 𝑀𝑦 = 𝑀)
166164, 165neeq12d 3000 . . . . . . . . . 10 (𝑦 = 𝑀 → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
16760, 48, 163, 166ralpr 4703 . . . . . . . . 9 (∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ≠ 1 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) ≠ 𝑀))
168157, 160, 167sylanbrc 581 . . . . . . . 8 ((𝜑𝑐𝐶) → ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
169 ralunb 4190 . . . . . . . 8 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ (∀𝑦𝐾 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ∧ ∀𝑦 ∈ {1, 𝑀} ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
170150, 168, 169sylanbrc 581 . . . . . . 7 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
17151adantr 479 . . . . . . . 8 ((𝜑𝑐𝐶) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
172171raleqdv 3323 . . . . . . 7 ((𝜑𝑐𝐶) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
173170, 172mpbid 231 . . . . . 6 ((𝜑𝑐𝐶) → ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)
174 prex 5431 . . . . . . . 8 {⟨1, 𝑀⟩, ⟨𝑀, 1⟩} ∈ V
175135, 174unex 7735 . . . . . . 7 (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ V
176 f1oeq1 6820 . . . . . . . 8 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ↔ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1))))
177 fveq1 6889 . . . . . . . . . 10 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑓𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
178177neeq1d 2998 . . . . . . . . 9 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑓𝑦) ≠ 𝑦 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
179178ralbidv 3175 . . . . . . . 8 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦 ↔ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
180176, 179anbi12d 629 . . . . . . 7 (𝑓 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑓:(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑓𝑦) ≠ 𝑦) ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦)))
181175, 180, 1elab2 3671 . . . . . 6 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) ∧ ∀𝑦 ∈ (1...(𝑁 + 1))((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ≠ 𝑦))
182145, 173, 181sylanbrc 581 . . . . 5 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴)
183151, 158jca 510 . . . . 5 ((𝜑𝑐𝐶) → (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
184 fveq1 6889 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
185184eqeq1d 2732 . . . . . . 7 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔‘1) = 𝑀 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀))
186 fveq1 6889 . . . . . . . 8 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (𝑔𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
187186eqeq1d 2732 . . . . . . 7 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → ((𝑔𝑀) = 1 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1))
188185, 187anbi12d 629 . . . . . 6 (𝑔 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) → (((𝑔‘1) = 𝑀 ∧ (𝑔𝑀) = 1) ↔ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
189188, 6elrab2 3685 . . . . 5 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵 ↔ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐴 ∧ (((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀 ∧ ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)))
190182, 183, 189sylanbrc 581 . . . 4 ((𝜑𝑐𝐶) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ∈ 𝐵)
19156adantrr 713 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = 𝑀)
192151adantrl 712 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) = 𝑀)
193191, 192eqtr4d 2773 . . . . . . . . . 10 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1))
19459adantrr 713 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = 1)
195158adantrl 712 . . . . . . . . . . 11 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀) = 1)
196194, 195eqtr4d 2773 . . . . . . . . . 10 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀))
197 fveq2 6890 . . . . . . . . . . . 12 (𝑦 = 1 → (𝑏𝑦) = (𝑏‘1))
198197, 161eqeq12d 2746 . . . . . . . . . . 11 (𝑦 = 1 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1)))
199 fveq2 6890 . . . . . . . . . . . 12 (𝑦 = 𝑀 → (𝑏𝑦) = (𝑏𝑀))
200199, 164eqeq12d 2746 . . . . . . . . . . 11 (𝑦 = 𝑀 → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
20160, 48, 198, 200ralpr 4703 . . . . . . . . . 10 (∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ((𝑏‘1) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘1) ∧ (𝑏𝑀) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑀)))
202193, 196, 201sylanbrc 581 . . . . . . . . 9 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))
203202biantrud 530 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦))))
204 ralunb 4190 . . . . . . . 8 (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ∧ ∀𝑦 ∈ {1, 𝑀} (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
205203, 204bitr4di 288 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
206146eqeq2d 2741 . . . . . . . . 9 (((𝜑𝑐𝐶) ∧ 𝑦𝐾) → ((𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
207206ralbidva 3173 . . . . . . . 8 ((𝜑𝑐𝐶) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
208207adantrl 712 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦𝐾 (𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
20951adantr 479 . . . . . . . 8 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝐾 ∪ {1, 𝑀}) = (1...(𝑁 + 1)))
210209raleqdv 3323 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (𝐾 ∪ {1, 𝑀})(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
211205, 208, 2103bitr3rd 309 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦)))
212123eqeq2d 2741 . . . . . . . 8 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑐𝑦) = (𝑏𝑦)))
213 eqcom 2737 . . . . . . . 8 ((𝑐𝑦) = (𝑏𝑦) ↔ (𝑏𝑦) = (𝑐𝑦))
214212, 213bitrdi 286 . . . . . . 7 (𝑦𝐾 → ((𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ (𝑏𝑦) = (𝑐𝑦)))
215214ralbiia 3089 . . . . . 6 (∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦) ↔ ∀𝑦𝐾 (𝑏𝑦) = (𝑐𝑦))
216211, 215bitr4di 288 . . . . 5 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
21736adantrr 713 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑏 Fn (1...(𝑁 + 1)))
218145adantrl 712 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)))
219 f1ofn 6833 . . . . . . 7 ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}):(1...(𝑁 + 1))–1-1-onto→(1...(𝑁 + 1)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1)))
220218, 219syl 17 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1)))
221 eqfnfv 7031 . . . . . 6 ((𝑏 Fn (1...(𝑁 + 1)) ∧ (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) Fn (1...(𝑁 + 1))) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
222217, 220, 221syl2anc 582 . . . . 5 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ ∀𝑦 ∈ (1...(𝑁 + 1))(𝑏𝑦) = ((𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩})‘𝑦)))
223143adantrl 712 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐:𝐾1-1-onto𝐾)
224 f1ofn 6833 . . . . . . 7 (𝑐:𝐾1-1-onto𝐾𝑐 Fn 𝐾)
225223, 224syl 17 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝑐 Fn 𝐾)
226115adantr 479 . . . . . . 7 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → 𝐾 ⊆ (1...(𝑁 + 1)))
227217, 226fnssresd 6673 . . . . . 6 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏𝐾) Fn 𝐾)
228 eqfnfv 7031 . . . . . 6 ((𝑐 Fn 𝐾 ∧ (𝑏𝐾) Fn 𝐾) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
229225, 227, 228syl2anc 582 . . . . 5 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑐 = (𝑏𝐾) ↔ ∀𝑦𝐾 (𝑐𝑦) = ((𝑏𝐾)‘𝑦)))
230216, 222, 2293bitr4d 310 . . . 4 ((𝜑 ∧ (𝑏𝐵𝑐𝐶)) → (𝑏 = (𝑐 ∪ {⟨1, 𝑀⟩, ⟨𝑀, 1⟩}) ↔ 𝑐 = (𝑏𝐾)))
23112, 130, 190, 230f1o2d 7662 . . 3 (𝜑 → (𝑏𝐵 ↦ (𝑏𝐾)):𝐵1-1-onto𝐶)
23211, 231hasheqf1od 14317 . 2 (𝜑 → (♯‘𝐵) = (♯‘𝐶))
233128fveq2i 6893 . . . 4 (♯‘𝐶) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
234 fzfi 13941 . . . . . . 7 (2...(𝑁 + 1)) ∈ Fin
235 diffi 9181 . . . . . . 7 ((2...(𝑁 + 1)) ∈ Fin → ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin)
236234, 235ax-mp 5 . . . . . 6 ((2...(𝑁 + 1)) ∖ {𝑀}) ∈ Fin
23749, 236eqeltri 2827 . . . . 5 𝐾 ∈ Fin
23844derangval 34456 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)}))
239237, 238ax-mp 5 . . . 4 (𝐷𝐾) = (♯‘{𝑓 ∣ (𝑓:𝐾1-1-onto𝐾 ∧ ∀𝑦𝐾 (𝑓𝑦) ≠ 𝑦)})
24044, 45derangen2 34463 . . . . 5 (𝐾 ∈ Fin → (𝐷𝐾) = (𝑆‘(♯‘𝐾)))
241237, 240ax-mp 5 . . . 4 (𝐷𝐾) = (𝑆‘(♯‘𝐾))
242233, 239, 2413eqtr2ri 2765 . . 3 (𝑆‘(♯‘𝐾)) = (♯‘𝐶)
24350simp3d 1142 . . . 4 (𝜑 → (♯‘𝐾) = (𝑁 − 1))
244243fveq2d 6894 . . 3 (𝜑 → (𝑆‘(♯‘𝐾)) = (𝑆‘(𝑁 − 1)))
245242, 244eqtr3id 2784 . 2 (𝜑 → (♯‘𝐶) = (𝑆‘(𝑁 − 1)))
246232, 245eqtrd 2770 1 (𝜑 → (♯‘𝐵) = (𝑆‘(𝑁 − 1)))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 394   = wceq 1539  wcel 2104  {cab 2707  wne 2938  wral 3059  wrex 3068  {crab 3430  Vcvv 3472  cdif 3944  cun 3945  cin 3946  wss 3947  c0 4321  {csn 4627  {cpr 4629  cop 4633  cmpt 5230  ccnv 5674  cres 5677  Fun wfun 6536   Fn wfn 6537  wf 6538  1-1wf1 6539  ontowfo 6540  1-1-ontowf1o 6541  cfv 6542  (class class class)co 7411  Fincfn 8941  1c1 11113   + caddc 11115  cmin 11448  cn 12216  2c2 12271  0cn0 12476  cuz 12826  ...cfz 13488  chash 14294
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1795  ax-4 1809  ax-5 1911  ax-6 1969  ax-7 2009  ax-8 2106  ax-9 2114  ax-10 2135  ax-11 2152  ax-12 2169  ax-ext 2701  ax-rep 5284  ax-sep 5298  ax-nul 5305  ax-pow 5362  ax-pr 5426  ax-un 7727  ax-cnex 11168  ax-resscn 11169  ax-1cn 11170  ax-icn 11171  ax-addcl 11172  ax-addrcl 11173  ax-mulcl 11174  ax-mulrcl 11175  ax-mulcom 11176  ax-addass 11177  ax-mulass 11178  ax-distr 11179  ax-i2m1 11180  ax-1ne0 11181  ax-1rid 11182  ax-rnegex 11183  ax-rrecex 11184  ax-cnre 11185  ax-pre-lttri 11186  ax-pre-lttrn 11187  ax-pre-ltadd 11188  ax-pre-mulgt0 11189
This theorem depends on definitions:  df-bi 206  df-an 395  df-or 844  df-3or 1086  df-3an 1087  df-tru 1542  df-fal 1552  df-ex 1780  df-nf 1784  df-sb 2066  df-mo 2532  df-eu 2561  df-clab 2708  df-cleq 2722  df-clel 2808  df-nfc 2883  df-ne 2939  df-nel 3045  df-ral 3060  df-rex 3069  df-reu 3375  df-rab 3431  df-v 3474  df-sbc 3777  df-csb 3893  df-dif 3950  df-un 3952  df-in 3954  df-ss 3964  df-pss 3966  df-nul 4322  df-if 4528  df-pw 4603  df-sn 4628  df-pr 4630  df-op 4634  df-uni 4908  df-int 4950  df-iun 4998  df-br 5148  df-opab 5210  df-mpt 5231  df-tr 5265  df-id 5573  df-eprel 5579  df-po 5587  df-so 5588  df-fr 5630  df-we 5632  df-xp 5681  df-rel 5682  df-cnv 5683  df-co 5684  df-dm 5685  df-rn 5686  df-res 5687  df-ima 5688  df-pred 6299  df-ord 6366  df-on 6367  df-lim 6368  df-suc 6369  df-iota 6494  df-fun 6544  df-fn 6545  df-f 6546  df-f1 6547  df-fo 6548  df-f1o 6549  df-fv 6550  df-riota 7367  df-ov 7414  df-oprab 7415  df-mpo 7416  df-om 7858  df-1st 7977  df-2nd 7978  df-frecs 8268  df-wrecs 8299  df-recs 8373  df-rdg 8412  df-1o 8468  df-oadd 8472  df-er 8705  df-map 8824  df-pm 8825  df-en 8942  df-dom 8943  df-sdom 8944  df-fin 8945  df-dju 9898  df-card 9936  df-pnf 11254  df-mnf 11255  df-xr 11256  df-ltxr 11257  df-le 11258  df-sub 11450  df-neg 11451  df-nn 12217  df-2 12279  df-n0 12477  df-xnn0 12549  df-z 12563  df-uz 12827  df-fz 13489  df-hash 14295
This theorem is referenced by:  subfacp1lem6  34474
  Copyright terms: Public domain W3C validator