Metamath Proof Explorer


Theorem erclwwlkneq

Description: Two classes are equivalent regarding .~ if both are words of the same fixed length and one is the other cyclically shifted. (Contributed by Alexander van der Vekens, 25-Mar-2018) (Revised by AV, 30-Apr-2021)

Ref Expression
Hypotheses erclwwlkn.w 𝑊 = ( 𝑁 ClWWalksN 𝐺 )
erclwwlkn.r = { ⟨ 𝑡 , 𝑢 ⟩ ∣ ( 𝑡𝑊𝑢𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑡 = ( 𝑢 cyclShift 𝑛 ) ) }
Assertion erclwwlkneq ( ( 𝑇𝑋𝑈𝑌 ) → ( 𝑇 𝑈 ↔ ( 𝑇𝑊𝑈𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑇 = ( 𝑈 cyclShift 𝑛 ) ) ) )

Proof

Step Hyp Ref Expression
1 erclwwlkn.w 𝑊 = ( 𝑁 ClWWalksN 𝐺 )
2 erclwwlkn.r = { ⟨ 𝑡 , 𝑢 ⟩ ∣ ( 𝑡𝑊𝑢𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑡 = ( 𝑢 cyclShift 𝑛 ) ) }
3 eleq1 ( 𝑡 = 𝑇 → ( 𝑡𝑊𝑇𝑊 ) )
4 3 adantr ( ( 𝑡 = 𝑇𝑢 = 𝑈 ) → ( 𝑡𝑊𝑇𝑊 ) )
5 eleq1 ( 𝑢 = 𝑈 → ( 𝑢𝑊𝑈𝑊 ) )
6 5 adantl ( ( 𝑡 = 𝑇𝑢 = 𝑈 ) → ( 𝑢𝑊𝑈𝑊 ) )
7 simpl ( ( 𝑡 = 𝑇𝑢 = 𝑈 ) → 𝑡 = 𝑇 )
8 oveq1 ( 𝑢 = 𝑈 → ( 𝑢 cyclShift 𝑛 ) = ( 𝑈 cyclShift 𝑛 ) )
9 8 adantl ( ( 𝑡 = 𝑇𝑢 = 𝑈 ) → ( 𝑢 cyclShift 𝑛 ) = ( 𝑈 cyclShift 𝑛 ) )
10 7 9 eqeq12d ( ( 𝑡 = 𝑇𝑢 = 𝑈 ) → ( 𝑡 = ( 𝑢 cyclShift 𝑛 ) ↔ 𝑇 = ( 𝑈 cyclShift 𝑛 ) ) )
11 10 rexbidv ( ( 𝑡 = 𝑇𝑢 = 𝑈 ) → ( ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑡 = ( 𝑢 cyclShift 𝑛 ) ↔ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑇 = ( 𝑈 cyclShift 𝑛 ) ) )
12 4 6 11 3anbi123d ( ( 𝑡 = 𝑇𝑢 = 𝑈 ) → ( ( 𝑡𝑊𝑢𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑡 = ( 𝑢 cyclShift 𝑛 ) ) ↔ ( 𝑇𝑊𝑈𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑇 = ( 𝑈 cyclShift 𝑛 ) ) ) )
13 12 2 brabga ( ( 𝑇𝑋𝑈𝑌 ) → ( 𝑇 𝑈 ↔ ( 𝑇𝑊𝑈𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑇 = ( 𝑈 cyclShift 𝑛 ) ) ) )