Доказательство. Необходимость. (Þ) Покажем, что если Ut1 = Ut2, то образцы t1 и t2 совпадают с точностью до переименования переменных.

Необходимость. (Þ) Покажем, что если Ut₁ = Ut₂, то образцы t₁ и t₂ совпадают с точностью до переименования переменных.

Пусть Ut₁ = Ut₂. Без ограничения общности можно считать, что множества символов переменных в образцах t₁ и t₂ не пересекаются.

Длины слов t₁ и t₂ совпадают. Действительно, всякое применение произвольного образца, получаемое заменой символов переменных на слова, состоящие из одного символа, имеет длину, равную длине самого образца. Поэтому если бы длины образцов t₁ и t₂ были разными, то множество применений более короткого образца содержало бы слова, не входящие во множество применений другого образца.

Пусть t₁ = s₁, ... , s_k и t₂ = d₁, ... , d_k.

Произведем последовательное посимвольное сравнение t₁ и t₂слева направо.

При этом возможны следующие случаи:

1) s_i Î (А B);

2) s_i Î V.

Рассмотрим первый из этих случаев и покажем, что справедливы соотношения d_i Î (А B)и s_i = d_i.

Для этого рассмотрим множества всех таких применений t₁ и t₂, которые получаются из t₁ и t₂ заменой символов переменных на слова длины 1.

Тогда, если d_i s_i, то рассматриваемые множества кратчайших по длине слов в Ut₁ и Ut₂ являются разными, так как i-й символ всех слов первого множества равен s_i. Однако значения i-го символа слов второго множества могут быть отличными от s_i.

Из проведенных рассуждений следует, что на одинаковых позициях образцов t₁ и t₂ могут располагаться либо символы переменных, либо равные символы из А B.

Рассмотрим второй случай. Покажем, что в этом случае d_i также является символом переменной и s_i = s_j тогда и только тогда, когда d_i = d_j. Первое из приведенных свойств верно, поскольку если d_i Î А B, то в кратчайших применениях t₂ символ с порядковым номером i всегда равен d_i, а в кратчайших применениях t₁ символ с тем же номером принимает значения всех символов из А B.

Проверим справедливость второго свойства. Пусть s_i ÎV и s_j, j < i,обозначают одну и ту же переменную в t₁. Тогда все применения t₁, получаемые заменой переменных на слова длины 1 в алфавите А È B, имеют одинаковые j-й и i-й символы. Если же d_i и d_j - разные символы переменных вt₂, то среди кратчайших по длине применений образца t₁ имеются такие, в которых j-й и i-й символы - разные. Поэтому Ut₁ ¹Ut₂. Последнее заключение противоречит предполагаемому равенству множеств Ut₁ и Ut₂.

Доказательство того, что если d_i = d_j, то s_i = s_j можно провести аналогичными рассуждениями.

Из доказательства свойств, имеющих место в случаях 1 и 2, следует, что t₁ и t₁ совпадают с точностью до переименования переменных.

Достаточность. (Ü) Пусть образцы t₁ и t₂ совпадают с точностью до переименования переменных. Тогда множества применений этих образцов совпадают.

Действительно, пусть подстановка Q₁ = задает переименование переменных из t₁ в переменные из t₂, которое преобразует t₁ в t₂.

Тогда, если слово является применением t₁, получаемым с помощью подстановки p, то является применением t₂ с помощью подстановки QQ₁, т.е. Ut₁ Í Ut_2. Обратное включение Ut₁ Í Ut₂ доказывается аналогично. Поэтому Ut₁ = Ut₂.

Следовательно, Ut₁ = Ut₂.