MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  hashecclwwlkn1 Structured version   Visualization version   GIF version

Theorem hashecclwwlkn1 29765
Description: The size of every equivalence class of the equivalence relation over the set of closed walks (defined as words) with a fixed length which is a prime number is 1 or equals this length. (Contributed by Alexander van der Vekens, 17-Jun-2018.) (Revised by AV, 1-May-2021.)
Hypotheses
Ref Expression
erclwwlkn.w 𝑊 = (𝑁 ClWWalksN 𝐺)
erclwwlkn.r = {⟨𝑡, 𝑢⟩ ∣ (𝑡𝑊𝑢𝑊 ∧ ∃𝑛 ∈ (0...𝑁)𝑡 = (𝑢 cyclShift 𝑛))}
Assertion
Ref Expression
hashecclwwlkn1 ((𝑁 ∈ ℙ ∧ 𝑈 ∈ (𝑊 / )) → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))
Distinct variable groups:   𝑡,𝑊,𝑢   𝑛,𝑁,𝑢,𝑡   𝑛,𝑊   𝑛,𝐺,𝑢   𝑈,𝑛,𝑢
Allowed substitution hints:   (𝑢,𝑡,𝑛)   𝑈(𝑡)   𝐺(𝑡)

Proof of Theorem hashecclwwlkn1
Dummy variables 𝑥 𝑦 𝑚 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 erclwwlkn.w . . . . 5 𝑊 = (𝑁 ClWWalksN 𝐺)
2 erclwwlkn.r . . . . 5 = {⟨𝑡, 𝑢⟩ ∣ (𝑡𝑊𝑢𝑊 ∧ ∃𝑛 ∈ (0...𝑁)𝑡 = (𝑢 cyclShift 𝑛))}
31, 2eclclwwlkn1 29763 . . . 4 (𝑈 ∈ (𝑊 / ) → (𝑈 ∈ (𝑊 / ) ↔ ∃𝑥𝑊 𝑈 = {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)}))
4 rabeq 3438 . . . . . . . . . 10 (𝑊 = (𝑁 ClWWalksN 𝐺) → {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ (𝑁 ClWWalksN 𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)})
51, 4mp1i 13 . . . . . . . . 9 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ (𝑁 ClWWalksN 𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)})
6 prmnn 16607 . . . . . . . . . . 11 (𝑁 ∈ ℙ → 𝑁 ∈ ℕ)
76nnnn0d 12528 . . . . . . . . . 10 (𝑁 ∈ ℙ → 𝑁 ∈ ℕ0)
81eleq2i 2817 . . . . . . . . . . 11 (𝑥𝑊𝑥 ∈ (𝑁 ClWWalksN 𝐺))
98biimpi 215 . . . . . . . . . 10 (𝑥𝑊𝑥 ∈ (𝑁 ClWWalksN 𝐺))
10 clwwlknscsh 29750 . . . . . . . . . 10 ((𝑁 ∈ ℕ0𝑥 ∈ (𝑁 ClWWalksN 𝐺)) → {𝑦 ∈ (𝑁 ClWWalksN 𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)})
117, 9, 10syl2an 595 . . . . . . . . 9 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → {𝑦 ∈ (𝑁 ClWWalksN 𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)})
125, 11eqtrd 2764 . . . . . . . 8 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)})
1312eqeq2d 2735 . . . . . . 7 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → (𝑈 = {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} ↔ 𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)}))
14 simpll 764 . . . . . . . . . . . . . . . 16 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) ∧ 𝑁 ∈ ℕ) → 𝑥 ∈ Word (Vtx‘𝐺))
15 elnnne0 12482 . . . . . . . . . . . . . . . . . 18 (𝑁 ∈ ℕ ↔ (𝑁 ∈ ℕ0𝑁 ≠ 0))
16 eqeq1 2728 . . . . . . . . . . . . . . . . . . . . . 22 (𝑁 = (♯‘𝑥) → (𝑁 = 0 ↔ (♯‘𝑥) = 0))
1716eqcoms 2732 . . . . . . . . . . . . . . . . . . . . 21 ((♯‘𝑥) = 𝑁 → (𝑁 = 0 ↔ (♯‘𝑥) = 0))
18 hasheq0 14319 . . . . . . . . . . . . . . . . . . . . 21 (𝑥 ∈ Word (Vtx‘𝐺) → ((♯‘𝑥) = 0 ↔ 𝑥 = ∅))
1917, 18sylan9bbr 510 . . . . . . . . . . . . . . . . . . . 20 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → (𝑁 = 0 ↔ 𝑥 = ∅))
2019necon3bid 2977 . . . . . . . . . . . . . . . . . . 19 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → (𝑁 ≠ 0 ↔ 𝑥 ≠ ∅))
2120biimpcd 248 . . . . . . . . . . . . . . . . . 18 (𝑁 ≠ 0 → ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → 𝑥 ≠ ∅))
2215, 21simplbiim 504 . . . . . . . . . . . . . . . . 17 (𝑁 ∈ ℕ → ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → 𝑥 ≠ ∅))
2322impcom 407 . . . . . . . . . . . . . . . 16 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) ∧ 𝑁 ∈ ℕ) → 𝑥 ≠ ∅)
24 simplr 766 . . . . . . . . . . . . . . . . 17 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) ∧ 𝑁 ∈ ℕ) → (♯‘𝑥) = 𝑁)
2524eqcomd 2730 . . . . . . . . . . . . . . . 16 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) ∧ 𝑁 ∈ ℕ) → 𝑁 = (♯‘𝑥))
2614, 23, 253jca 1125 . . . . . . . . . . . . . . 15 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) ∧ 𝑁 ∈ ℕ) → (𝑥 ∈ Word (Vtx‘𝐺) ∧ 𝑥 ≠ ∅ ∧ 𝑁 = (♯‘𝑥)))
2726ex 412 . . . . . . . . . . . . . 14 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → (𝑁 ∈ ℕ → (𝑥 ∈ Word (Vtx‘𝐺) ∧ 𝑥 ≠ ∅ ∧ 𝑁 = (♯‘𝑥))))
28 eqid 2724 . . . . . . . . . . . . . . 15 (Vtx‘𝐺) = (Vtx‘𝐺)
2928clwwlknbp 29723 . . . . . . . . . . . . . 14 (𝑥 ∈ (𝑁 ClWWalksN 𝐺) → (𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁))
3027, 29syl11 33 . . . . . . . . . . . . 13 (𝑁 ∈ ℕ → (𝑥 ∈ (𝑁 ClWWalksN 𝐺) → (𝑥 ∈ Word (Vtx‘𝐺) ∧ 𝑥 ≠ ∅ ∧ 𝑁 = (♯‘𝑥))))
318, 30biimtrid 241 . . . . . . . . . . . 12 (𝑁 ∈ ℕ → (𝑥𝑊 → (𝑥 ∈ Word (Vtx‘𝐺) ∧ 𝑥 ≠ ∅ ∧ 𝑁 = (♯‘𝑥))))
326, 31syl 17 . . . . . . . . . . 11 (𝑁 ∈ ℙ → (𝑥𝑊 → (𝑥 ∈ Word (Vtx‘𝐺) ∧ 𝑥 ≠ ∅ ∧ 𝑁 = (♯‘𝑥))))
3332imp 406 . . . . . . . . . 10 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → (𝑥 ∈ Word (Vtx‘𝐺) ∧ 𝑥 ≠ ∅ ∧ 𝑁 = (♯‘𝑥)))
34 scshwfzeqfzo 14773 . . . . . . . . . 10 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ 𝑥 ≠ ∅ ∧ 𝑁 = (♯‘𝑥)) → {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)})
3533, 34syl 17 . . . . . . . . 9 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)})
3635eqeq2d 2735 . . . . . . . 8 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} ↔ 𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)}))
37 oveq2 7409 . . . . . . . . . . . . . . . . . . . . . . 23 (𝑛 = 𝑚 → (𝑥 cyclShift 𝑛) = (𝑥 cyclShift 𝑚))
3837eqeq2d 2735 . . . . . . . . . . . . . . . . . . . . . 22 (𝑛 = 𝑚 → (𝑦 = (𝑥 cyclShift 𝑛) ↔ 𝑦 = (𝑥 cyclShift 𝑚)))
3938cbvrexvw 3227 . . . . . . . . . . . . . . . . . . . . 21 (∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛) ↔ ∃𝑚 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑚))
40 eqeq1 2728 . . . . . . . . . . . . . . . . . . . . . . 23 (𝑦 = 𝑢 → (𝑦 = (𝑥 cyclShift 𝑚) ↔ 𝑢 = (𝑥 cyclShift 𝑚)))
41 eqcom 2731 . . . . . . . . . . . . . . . . . . . . . . 23 (𝑢 = (𝑥 cyclShift 𝑚) ↔ (𝑥 cyclShift 𝑚) = 𝑢)
4240, 41bitrdi 287 . . . . . . . . . . . . . . . . . . . . . 22 (𝑦 = 𝑢 → (𝑦 = (𝑥 cyclShift 𝑚) ↔ (𝑥 cyclShift 𝑚) = 𝑢))
4342rexbidv 3170 . . . . . . . . . . . . . . . . . . . . 21 (𝑦 = 𝑢 → (∃𝑚 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑚) ↔ ∃𝑚 ∈ (0..^(♯‘𝑥))(𝑥 cyclShift 𝑚) = 𝑢))
4439, 43bitrid 283 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝑢 → (∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛) ↔ ∃𝑚 ∈ (0..^(♯‘𝑥))(𝑥 cyclShift 𝑚) = 𝑢))
4544cbvrabv 3434 . . . . . . . . . . . . . . . . . . 19 {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} = {𝑢 ∈ Word (Vtx‘𝐺) ∣ ∃𝑚 ∈ (0..^(♯‘𝑥))(𝑥 cyclShift 𝑚) = 𝑢}
4645cshwshash 17036 . . . . . . . . . . . . . . . . . 18 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) ∈ ℙ) → ((♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = (♯‘𝑥) ∨ (♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = 1))
4746adantr 480 . . . . . . . . . . . . . . . . 17 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) ∈ ℙ) ∧ 𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) → ((♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = (♯‘𝑥) ∨ (♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = 1))
4847orcomd 868 . . . . . . . . . . . . . . . 16 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) ∈ ℙ) ∧ 𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) → ((♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = 1 ∨ (♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = (♯‘𝑥)))
49 fveqeq2 6890 . . . . . . . . . . . . . . . . . 18 (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ↔ (♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = 1))
50 fveqeq2 6890 . . . . . . . . . . . . . . . . . 18 (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = (♯‘𝑥) ↔ (♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = (♯‘𝑥)))
5149, 50orbi12d 915 . . . . . . . . . . . . . . . . 17 (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → (((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥)) ↔ ((♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = 1 ∨ (♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = (♯‘𝑥))))
5251adantl 481 . . . . . . . . . . . . . . . 16 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) ∈ ℙ) ∧ 𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) → (((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥)) ↔ ((♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = 1 ∨ (♯‘{𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) = (♯‘𝑥))))
5348, 52mpbird 257 . . . . . . . . . . . . . . 15 (((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) ∈ ℙ) ∧ 𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}) → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥)))
5453ex 412 . . . . . . . . . . . . . 14 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) ∈ ℙ) → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥))))
5554ex 412 . . . . . . . . . . . . 13 (𝑥 ∈ Word (Vtx‘𝐺) → ((♯‘𝑥) ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥)))))
5655adantr 480 . . . . . . . . . . . 12 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → ((♯‘𝑥) ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥)))))
57 eleq1 2813 . . . . . . . . . . . . . . 15 (𝑁 = (♯‘𝑥) → (𝑁 ∈ ℙ ↔ (♯‘𝑥) ∈ ℙ))
58 oveq2 7409 . . . . . . . . . . . . . . . . . . 19 (𝑁 = (♯‘𝑥) → (0..^𝑁) = (0..^(♯‘𝑥)))
5958rexeqdv 3318 . . . . . . . . . . . . . . . . . 18 (𝑁 = (♯‘𝑥) → (∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛) ↔ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)))
6059rabbidv 3432 . . . . . . . . . . . . . . . . 17 (𝑁 = (♯‘𝑥) → {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)})
6160eqeq2d 2735 . . . . . . . . . . . . . . . 16 (𝑁 = (♯‘𝑥) → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} ↔ 𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)}))
62 eqeq2 2736 . . . . . . . . . . . . . . . . 17 (𝑁 = (♯‘𝑥) → ((♯‘𝑈) = 𝑁 ↔ (♯‘𝑈) = (♯‘𝑥)))
6362orbi2d 912 . . . . . . . . . . . . . . . 16 (𝑁 = (♯‘𝑥) → (((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁) ↔ ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥))))
6461, 63imbi12d 344 . . . . . . . . . . . . . . 15 (𝑁 = (♯‘𝑥) → ((𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁)) ↔ (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥)))))
6557, 64imbi12d 344 . . . . . . . . . . . . . 14 (𝑁 = (♯‘𝑥) → ((𝑁 ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))) ↔ ((♯‘𝑥) ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥))))))
6665eqcoms 2732 . . . . . . . . . . . . 13 ((♯‘𝑥) = 𝑁 → ((𝑁 ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))) ↔ ((♯‘𝑥) ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥))))))
6766adantl 481 . . . . . . . . . . . 12 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → ((𝑁 ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))) ↔ ((♯‘𝑥) ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^(♯‘𝑥))𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = (♯‘𝑥))))))
6856, 67mpbird 257 . . . . . . . . . . 11 ((𝑥 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑥) = 𝑁) → (𝑁 ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))))
6929, 68syl 17 . . . . . . . . . 10 (𝑥 ∈ (𝑁 ClWWalksN 𝐺) → (𝑁 ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))))
7069, 1eleq2s 2843 . . . . . . . . 9 (𝑥𝑊 → (𝑁 ∈ ℙ → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))))
7170impcom 407 . . . . . . . 8 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0..^𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁)))
7236, 71sylbid 239 . . . . . . 7 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → (𝑈 = {𝑦 ∈ Word (Vtx‘𝐺) ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁)))
7313, 72sylbid 239 . . . . . 6 ((𝑁 ∈ ℙ ∧ 𝑥𝑊) → (𝑈 = {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁)))
7473rexlimdva 3147 . . . . 5 (𝑁 ∈ ℙ → (∃𝑥𝑊 𝑈 = {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁)))
7574com12 32 . . . 4 (∃𝑥𝑊 𝑈 = {𝑦𝑊 ∣ ∃𝑛 ∈ (0...𝑁)𝑦 = (𝑥 cyclShift 𝑛)} → (𝑁 ∈ ℙ → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁)))
763, 75syl6bi 253 . . 3 (𝑈 ∈ (𝑊 / ) → (𝑈 ∈ (𝑊 / ) → (𝑁 ∈ ℙ → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))))
7776pm2.43i 52 . 2 (𝑈 ∈ (𝑊 / ) → (𝑁 ∈ ℙ → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁)))
7877impcom 407 1 ((𝑁 ∈ ℙ ∧ 𝑈 ∈ (𝑊 / )) → ((♯‘𝑈) = 1 ∨ (♯‘𝑈) = 𝑁))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 395  wo 844  w3a 1084   = wceq 1533  wcel 2098  wne 2932  wrex 3062  {crab 3424  c0 4314  {copab 5200  cfv 6533  (class class class)co 7401   / cqs 8697  0cc0 11105  1c1 11106  cn 12208  0cn0 12468  ...cfz 13480  ..^cfzo 13623  chash 14286  Word cword 14460   cyclShift ccsh 14734  cprime 16604  Vtxcvtx 28691   ClWWalksN cclwwlkn 29712
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1789  ax-4 1803  ax-5 1905  ax-6 1963  ax-7 2003  ax-8 2100  ax-9 2108  ax-10 2129  ax-11 2146  ax-12 2163  ax-ext 2695  ax-rep 5275  ax-sep 5289  ax-nul 5296  ax-pow 5353  ax-pr 5417  ax-un 7718  ax-inf2 9631  ax-cnex 11161  ax-resscn 11162  ax-1cn 11163  ax-icn 11164  ax-addcl 11165  ax-addrcl 11166  ax-mulcl 11167  ax-mulrcl 11168  ax-mulcom 11169  ax-addass 11170  ax-mulass 11171  ax-distr 11172  ax-i2m1 11173  ax-1ne0 11174  ax-1rid 11175  ax-rnegex 11176  ax-rrecex 11177  ax-cnre 11178  ax-pre-lttri 11179  ax-pre-lttrn 11180  ax-pre-ltadd 11181  ax-pre-mulgt0 11182  ax-pre-sup 11183
This theorem depends on definitions:  df-bi 206  df-an 396  df-or 845  df-3or 1085  df-3an 1086  df-tru 1536  df-fal 1546  df-ex 1774  df-nf 1778  df-sb 2060  df-mo 2526  df-eu 2555  df-clab 2702  df-cleq 2716  df-clel 2802  df-nfc 2877  df-ne 2933  df-nel 3039  df-ral 3054  df-rex 3063  df-rmo 3368  df-reu 3369  df-rab 3425  df-v 3468  df-sbc 3770  df-csb 3886  df-dif 3943  df-un 3945  df-in 3947  df-ss 3957  df-pss 3959  df-nul 4315  df-if 4521  df-pw 4596  df-sn 4621  df-pr 4623  df-op 4627  df-uni 4900  df-int 4941  df-iun 4989  df-disj 5104  df-br 5139  df-opab 5201  df-mpt 5222  df-tr 5256  df-id 5564  df-eprel 5570  df-po 5578  df-so 5579  df-fr 5621  df-se 5622  df-we 5623  df-xp 5672  df-rel 5673  df-cnv 5674  df-co 5675  df-dm 5676  df-rn 5677  df-res 5678  df-ima 5679  df-pred 6290  df-ord 6357  df-on 6358  df-lim 6359  df-suc 6360  df-iota 6485  df-fun 6535  df-fn 6536  df-f 6537  df-f1 6538  df-fo 6539  df-f1o 6540  df-fv 6541  df-isom 6542  df-riota 7357  df-ov 7404  df-oprab 7405  df-mpo 7406  df-om 7849  df-1st 7968  df-2nd 7969  df-frecs 8261  df-wrecs 8292  df-recs 8366  df-rdg 8405  df-1o 8461  df-2o 8462  df-oadd 8465  df-er 8698  df-ec 8700  df-qs 8704  df-map 8817  df-en 8935  df-dom 8936  df-sdom 8937  df-fin 8938  df-sup 9432  df-inf 9433  df-oi 9500  df-dju 9891  df-card 9929  df-pnf 11246  df-mnf 11247  df-xr 11248  df-ltxr 11249  df-le 11250  df-sub 11442  df-neg 11443  df-div 11868  df-nn 12209  df-2 12271  df-3 12272  df-n0 12469  df-xnn0 12541  df-z 12555  df-uz 12819  df-rp 12971  df-ico 13326  df-fz 13481  df-fzo 13624  df-fl 13753  df-mod 13831  df-seq 13963  df-exp 14024  df-hash 14287  df-word 14461  df-lsw 14509  df-concat 14517  df-substr 14587  df-pfx 14617  df-reps 14715  df-csh 14735  df-cj 15042  df-re 15043  df-im 15044  df-sqrt 15178  df-abs 15179  df-clim 15428  df-sum 15629  df-dvds 16194  df-gcd 16432  df-prm 16605  df-phi 16697  df-clwwlk 29670  df-clwwlkn 29713
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator