222
правки
Изменения
м
→Доказательство 0-1 принципа
Рассмотрим произвольный компаратор <tex> [i: j] </tex>, сортирующий элементы <tex> a_i </tex> и <tex> a_j </tex>. Применим его к последовательности <tex> f(a) </tex> и рассмотрим элемент с индексом <tex> i </tex>.
<tex> [i: j]f(a)_i </tex> <br> <tex>= [i: j](f(a_0), \dots, f(a_{n-1}))_i </tex> (по введенному нами определению) <br> <tex> = \min(f(a_i), f[i: j](a_ja)) _i </tex> (по введенному нами определению компаратора) <br> <tex> = f(\min(f(a_i), f(a_j)) </tex> (по уже доказанной леммеопределению компаратора) <br> <tex> = f([i: j](a)_i) </tex> (по определению компаратора) <br> <tex> = f([i: j]\min(aa_i, a_j))_i </tex>(по введенному нами определениюуже доказанной лемме).
То есть в результате <tex> i </tex>-й элемент не зависит от порядка применения компаратора <tex> [i: j] </tex> и функции <tex> f </tex>. Те же рассуждения можно провести для всех других индексов, то есть <tex> [i: j]f(a) = f([i: j](a)) </tex>, и также для всех компараторов в сети, то есть лемма доказана.
}}
