freidom | Дата: Понедельник, 28.12.2009, 18:18 | Сообщение # 1 |
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| Если отношение R обладает ромбовидным свойством, то его транзитивное замыкание Z=R^ также обладает ромбовидным свойством. Должно быть у всех в листках Штукенберга, стр. 39-40. Я вряд ли смогу объяснить лучше, чем там.
|
|
| |
джужинатор | Дата: Понедельник, 28.12.2009, 22:24 | Сообщение # 2 |
Рядовой
Группа: Пользователи
Сообщений: 11
Статус: Offline
| Леммаю Если отношение R обладает р.с, то его транзитивное замыкание R^ тоже обладает р.с. Доказательство: Д-во будет состоять из 2-х утверждений. Утв 1. Возьмём некоторые a,b и c? что aR^b и aRc, то есть существует такая последовательность х1,х2,...,хn, что х1=а, xn=b и xiRxi+1 для 1=<i<n. Тогда найдется d, что bRd и cR^d, а точнее, сушествует последовательность y1,y2,...yn, где y1=c, yn=d и yiRyi+1. Доказательство будет вестись индукцией по n. Бза: n=1. По р.с отношения R должен существовать такой d, что bRd и cRd. Значит, bR^d и cR^d. Переход: Пусть утверждение справедливо для n-1. Покажем, что оно справедливо и для n. То есть, возьмемм некоторые элементы b и c, такие, что aR^b и aRc, при этом существует такая последовательность х длины n, что х1,х2,...хn, где x1=a, xn=b, xiRxi+1. Из индукцишнного предположения следует, что для хn-1 существует d, что bRd и последовательность y длины n-1: y1,y2,...yn-1, где y1=c, yn-1=d, yiRyi+1. Т.к хn-1Rxn и xn-1Rd, то по р.с должен найтись такой t, что xnRt и dRt. Тогда этот t и будет искомым: возьмем новую последовательность: y1,y2,..yn-1,t Поскольку yn-1=d, то yn-1Rt и, значит y1R^t, т.е сR^t. Кроме того, мы уже установили, что xnRt (т.е bRt)ю Отсюда следует, что bR^t и сR^t. Утв 2. Возьмем некоторые а,b и с, что aR^b И aR^c, т.е существуют такие последовательности: x1,x2,...xn, что х1=а, xn=b и xiRxi+1 для 1=<i<m p1,p2,...pm, что p1=а, pm=c и piRpi+1 для 1=<i<m Тогда найдется такое d, что bR^d и cR^d, точнее, существуют такие последовательности q1,q2,...qm, что q1=b, qm=d и qiRqi+1 для 1=<i<m y1,y2,...yn, что y1=c, yn=d и yiRyi+1 для 1=<i<m Доказательство аналогично предыдущему случаю, только вместо р.с нужно напрямую использовать утв 1. Получив по предположению индукции , что для а,b и pm-1 (aR^B и aR^pm-1) найдется такой t, что bR^t и pm-1R^t, применим к pm-1R^t и pm-1Rpm утверждение и получим, что существует d, что bR^d и cR^d. Формально это рассуждение проводить не будем, а ограничимся лишь соответствующей ему картинкой (дальше приводится картинка и д-во заканчивается).
|
|
| |
freidom | Дата: Понедельник, 28.12.2009, 22:41 | Сообщение # 3 |
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| Не впадлу было?
|
|
| |
джужинатор | Дата: Вторник, 29.12.2009, 09:57 | Сообщение # 4 |
Рядовой
Группа: Пользователи
Сообщений: 11
Статус: Offline
| надо было на плеер закачать...
|
|
| |