Изменения

Если <tex>u</tex> и <tex>v</tex>, <tex>v</tex> и <tex>z</tex> эквивалентны, то <tex>u</tex> и <tex>z</tex> эквивалентныВведённое выше отношение является [[Транзитивное отношение#Отношение эквивалентности. Класс эквивалентности|отношением эквивалентности]].

# <tex>u \thicksim u</tex> — очевидно.# <tex>u\thicksim v \Rightarrow v\thicksim u</tex> — очевидно.# <tex>u\thicksim v, v\thicksim z \Rightarrow u\thicksim z</tex>. Пусть <tex>u</tex> и <tex>z</tex> неэквивалентны. Тогда <tex> \mathcal {9} s</tex> такая, что#:# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>,#:# <tex> \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle </tex>, где <tex>t_1 \notin T </tex>.#:Рассмотрим <tex>x</tex> такой, что <tex> \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle </tex>. <br>#:Если <tex>x \in T</tex>, то <tex>v</tex> и <tex>z</tex> различимы строкой <tex>s</tex>. Противоречие. <br>#:Если <tex>x \notin T</tex>, то <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex>. Противоречие. <br>#:Значит, <tex>u</tex> и <tex>z</tex> эквивалентны.