Theorem qerclwwlknfi

Description: The quotient set of the set of closed walks (defined as words) with a fixed length according to the equivalence relation .~ is finite. (Contributed by Alexander van der Vekens, 10-Apr-2018) (Revised by AV, 30-Apr-2021)

	Ref	Expression
Hypotheses	erclwwlkn.w	$$⊢W=N\mathrm{ClWWalksN}G$$
	erclwwlkn.r	$$⊢\underset{\dot{}}{\sim }=\left\{⟨t,u⟩|\left(t\in W\wedge u\in W\wedge \exists n\in \left(0\dots N\right)t=u\mathrm{cyclShift}n\right)\right\}$$
Assertion	qerclwwlknfi	$$⊢\mathrm{Vtx}\left(G\right)\in \mathrm{Fin}\to W/\underset{\dot{}}{\sim }\in \mathrm{Fin}$$

Proof

Step	Hyp	Ref	Expression
1		erclwwlkn.w	$$⊢W=N\mathrm{ClWWalksN}G$$
2		erclwwlkn.r	$$⊢\underset{\dot{}}{\sim }=\left\{⟨t,u⟩|\left(t\in W\wedge u\in W\wedge \exists n\in \left(0\dots N\right)t=u\mathrm{cyclShift}n\right)\right\}$$
3		clwwlknfi	$$⊢\mathrm{Vtx}\left(G\right)\in \mathrm{Fin}\to N\mathrm{ClWWalksN}G\in \mathrm{Fin}$$
4	1 3	eqeltrid	$$⊢\mathrm{Vtx}\left(G\right)\in \mathrm{Fin}\to W\in \mathrm{Fin}$$
5		pwfi	$$⊢W\in \mathrm{Fin}\leftrightarrow 𝒫W\in \mathrm{Fin}$$
6	4 5	sylib	$$⊢\mathrm{Vtx}\left(G\right)\in \mathrm{Fin}\to 𝒫W\in \mathrm{Fin}$$
7	1 2	erclwwlkn	$$⊢\underset{\dot{}}{\sim }\mathrm{Er}W$$
8	7	a1i	$$⊢\mathrm{Vtx}\left(G\right)\in \mathrm{Fin}\to \underset{\dot{}}{\sim }\mathrm{Er}W$$
9	8	qsss	$$⊢\mathrm{Vtx}\left(G\right)\in \mathrm{Fin}\to W/\underset{\dot{}}{\sim }\subseteq 𝒫W$$
10	6 9	ssfid	$$⊢\mathrm{Vtx}\left(G\right)\in \mathrm{Fin}\to W/\underset{\dot{}}{\sim }\in \mathrm{Fin}$$