Пример 11. Аn £ bn

К каким типам отношений относятся следующие отношения?

1) отношение равносильности на множестве формул, описывающих элементарные функции (формулы равносильны, если они задают одну и ту же функцию, например (а + b)´ (а - b) = a²- b², sin² a + cos² a = 1);

2) отношение, определяемое на множестве всех программ {(а, b): а и b вычисляют одну и ту же функцию на определенной машине};

3) отношения £ и < на множестве векторов длины п с ко­понентами из N, определяемые следующим образом:

а) (а₁,..., а_п)£ (b₁,..., b_п), если а₁ £ b₁,..., а_n £ b_n;

б) (а₁,..., а_п)< (b₁,..., b_п), если (а₁,..., а_п)£ (b₁,..., b_п) и хотя бы в одной координате i выполняется а_i < b_i;

Ø Отношения, заданные в п. 1 и 2, являются отношениями эквивалентности на соответствующих множествах; отношения, заданные в п.3, являются отношениями порядка; при этом отношение £, определенное в п. 3, есть отношение нестрого порядка, а отношение < в п. 3, - отношение строго порядка.