Линеаризуемость: различия между версиями

Поэтому цикл должен включать вызовы методов как минимум двух объектов. Обозначим за <math>m_1</math> и <math>m_2</math> вызовы методов разных объектов (переиндексировав их при необходимости). Пусть x – объект, связанный с <math>m_1</math>. Ни один из <math>m_2, ..., m_n</math> не может быть вызовом метода x. Утверждение справедливо для <math>m_2</math> по построению. Пусть <math>m_i</math> – первый вызов метода в <math>m_3, ..., m_n</math>, связанный с x. Поскольку <math>m_{i-1}</math> и <math>m_i</math> не связаны по <math>\to_x</math>, они должны быть связаны по <math>\to_H</math>, поэтому ответ <math>m_{i-1}</math> предшествует вызову <math>m_i</math>. Вызов <math>m_2</math> предшествует ответу <math>m_{i-1}</math>, поскольку в противном случае имело бы место <math>m_{i-1} \to_H m_2</math>, что дает более короткий цикл <math>m_2, ..., m_{i-1}</math>. Наконец, ответ <math>m_1</math> предшествует вызову <math>m_i</math>, поскольку по построению <math>m_1 \to_H m_2</math>. Отсюда следует, что ответ на <math>m_1</math> предшествует вызову <math>m_i</math>, следовательно, <math>m_1 \to_H m_i</math>, что дает более короткий цикл <math>m_1, m_i, ..., m_n</math>.

Поскольку <math>m_n</math> не является вызовом метода x, а <math>m_n \to m_1</math>, из этого следует, что <math>m_n \to_H m_1</math>. Но <math>m_1 \to_H m_2</math> по построению, а так как <math>\to_H</math> транзитивно, то <math>m_n \to_H m_2</math>, что дает более короткий цикл <math>m_2, ..., m_n</math>, так что имеет место противоречие. <math>\square</math>