Відношення толерантності

Визначення

Відношення толерантності (близькості, подібності) — рефлексивне, симетричне та не транзитивне бінарне відношення.

Відношення на множині називається толерантністю, або відношенням толерантності, якщо воно рефлексивне і симетричне.Відношення «бути другом», «бути знайомим», - відношення толерантності, так як вони рефлексивне, симетричне, але не транзитивне. Відношення «мати непорожній перетин» для множин - відношення толерантності. Множина із заданим на ній відношенням толерантності називається простором толерантності.

Клас толерантності

Якщо T - толерантність на множині $\mathrm {A}$ і $a\in \mathrm {A}$,то підмножина $~\{x|x,a\in T\}$називається класом толерантності.Класи толерантності утворюють покриття множини $A$. Якщо дано покриття $\{A_{i}\mid i\in I\}$ множини $A$ ,то відношення $T=\{(x,y)\mid x,y\in A,i\in I\}$ являється толерантністю.Однак класи цієї толерантності не обов'язково повинні співпадати з множиною $\{A_{i}\mid i\in I\}$. Наприклад,якщо толерантність $T$ являється покриттям $\{A_{1},A_{2},A_{3}\}$,де $A_{3}\subseteq A_{1}\cup A_{2}$ і $A_{1}\cap A_{2}\neq \varnothing$,то до числа класів толерантності належать об'єднання $A_{1}\cup A_{2}$ ,а $A_{3}$ класом толерантності не являється. Клас $K$ толерантності $T$ називається максимальним ,якщо $K\subseteq L$, де $L$ - деякий клас толерантності $T$,з чого виходить,що $K=L$.Покриття $\{A_{i}\mid i\in I\}$ множини $A$ співпадає з множиною всіх максимальних класів деякої толерантності тоді і тільки тоді,коли для будь-яких $i\in I$ та $\backprime I''\subseteq I$ включення $A_{i}\subseteq \bigcup _{x\in A}A_{x}$,з чого випливає,що $\bigcap _{x\in I}A_{x}\subseteq A_{i}$.

Т-толерантні алгебри, або TR-моделі

Процедура виділення t-розрізнюваних елементів із "реальної" сукупності A принципово неоднозначна: вона породжує сукупності $A_{t1},A_{t2},...$,елементи яких можна представити на склеєних аркушах багатолисті поверхні, причому кожен аркуш відповідає якійсь одній можливості виділення . Позначимо через $A_{(}t)$ об'єднання $UkA_{t}^{k}$, що допускає можливість "відклеювання" листів. При цьому елементи $A(t)$будуть визначатися "з точністю до толерантності t".

T-модель — сукупність $M(t)$ із заданим на ній відношенням толерантності $T$ (позначення: $[M(t),T]$), таким, що $xTy$ і $ytz$ тягне за собою $xTz$ для $x,y,z\in M(t)$.

Алгебраїчна система $\{A(t),R,T\}$ на носії $M(t)$ з сукупностями головних операцій$R\sim \{r_{k}:k\in I\}$ і головних предикатів $T\sim \{T_{j}:j\in J\}$називається Т-толерантною алгеброю, або TR-моделлю, якщо:

• алгебра $\{A_{t},R\}$$t$-замкнута, тобто для будь $n_{k}$-арной операції $r_{k}\in R$ і будь-яких $x_{1},...,x_{nk}\in A_{t}$існує елемент $y\in A_{t}$такий, що $(x_{1},...,x_{nk})$$rk$$t$$y$ (властивість t-замкненості);

• відношення $T_{j}\in T$ - толерантності на будь-якій$A_{t}^{k}$;

• операції $r_{k}$ і толерантності $T_{j}(k\in I,j\in J)$ узгоджені (або сумісні) на $A_{t}$, тобто для будь-яких $2n_{k}$елементів $x_{1},...,x_{nk},y_{1},...,y_{nk}\in A_{t}$ таких, що $x_{1}T_{j}y_{1},...,x_{nk}T_{j}y_{nk}$, виконується $(x_{1},...,x_{nk})r_{k}T_{j}(y_{1},...,y_{nk})r_{k}$ (властивість узгодженості Т з R).

Т-толерантну алгебру називатимемо t-локальною,якщо істинність будь-якого твердження $P$ відносно цієї алгебри не зміниться при зміні довільного $x\in A_{t}$ на елемент $y\in A_{t}$такий,що $xty$,тобто $P(...x...)-P(...y...)$(властивість t-локальності).

Теорема

Нехай $\{A_{t},R,T\}$ - t-локальна алгебра.Тоді:

1. $\{A_{t},R,T\}$ - t-незв'язана (тобто,для будь-яких$x,y\in A_{t}$ ні при яких $n$ не виконується $xt^{n}y$,якщо$x$$t$$y$ являється невірним).
2. Порядок $\{A_{t},R,T\}$ дифінітно-скінченний (тобто $|A_{t}|\in N_{t0}^{+}$.
3. Толерантний простір $[A_{t},T]$утворює T-модель.
4. Толерантність t узгоджена з алгеброю $\{A_{t},R\}$.

Доведення

Припустимо протилежне,тобто що для якихось $x,y\in A_{t}$ виконується $xt^{n}y$.Тоді,застосовуючи до носія $A_{t}$ алгебри $n-1$ разів властивість t-локальності ,з останнього отримаємо $xty$,у протиріччі з нашим припущенням,що $x,y\in A_{t}$.

Таким самим способом можна довести друге твердження.Припустимо,що являється невірним $|A_{t}|\in N_{t0}^{+}$.Тоді це означало б,що для якихось $A_{t1},A_{t2}\in A_{t}$ виконується $|A_{t1}t_{0}N$ та $|A_{t2}t_{0}(N+1)$ ,тобто що хоча б 2 елементи $x,y\in A_{t}$ t-розрізнювані в $A_{t2}$t-зв'язні та t-нерозрізнювані в $A_{t1}$.

Третя властивість випливає безпосередньо з t-локальності толерантної алгебри $\{A_{t},R,T\}$ ,що можна застосувати до $[A_{t},T]$.

Четверта властивість може бути доведена за допомогою властивостей t-замкненості та t-локальності.Дійсно,якщо $x_{1},..,x_{nk},y_{1},...,y_{nk}\in A_{t}$ і $x_{1}ty_{1},...,x_{nk}ty_{nk}$ ,то,в силу t-замкненості $(x_{1},...,x_{nk)}r_{k}tz,(y_{1},...,y_{nk})r_{k}tz'$,а в силу t-локальності $ztz'$ і $(x_{1},...,x_{nk})r_{k}t(y_{1},...,y_{nk})r_{k}$.

Приклади толерантності

Приклад 1

Множина складається з російських слів, що складаються з чотирьох букв — іменників у називному відмінку. Будемо називати такі слова подібними, якщо вони відрізняються не більше ніж на одну букву. Відома задача «Перетворення мухи в слона» в точних термінах формулюється так:

Знайти таку послідовність слів, що починається словом «муха» і закінчується словами «слон», будь-які два сусідніх слова в якій подібні (в сенсі тільки що даного визначення).

Наведемо рішення цієї задачі: «муха» — «мура» — «тура» — «тара» — «кара» — «каре» — «кафе» — «кафр» — «каюр» — «каюк» — «крюк» — «крок» — «срок» — «сток» — «стон» — «слон».

Від схожості до толерантності

Приклад 1

Наприклад, дві нові "Волги" одного випуску і кольору з точки зору покупця цілком однакові і, стало бути, синоніми. Але дві "Волги" різного випуску (або нова і стара "Волги" одного випуску) тільки схожі. При відсутності необхідного вибору одна може замінити іншу, якщо покупець готовий погодитися з подібною заміною.

Приклад 2

Двоє близнюків бувають настільки однаковими, що без усякого ризику можуть складати іспити один за одного. Якщо два студенти тільки схожі, то така шахрайська витівка, хоча і здійсненна, але ризиковою.

Пояснення

Якщо для об'єктів зазначено тільки схожість, то неможливо їх розбити на чіткі класи так, що всередині класу об'єкти схожі, а між об'єктами різних класів подібності немає. У разі подібності виникає розмита ситуація без чітких меж.

Кожен елемент множини несе певну інформацію про схожих на нього елементах. Але не всю інформацію), як у випадку однакових елементів. Тут вже немає дилеми: "Все або нічого" або "Повна інформація - відсутність інформації", Тут можливі різні ступені інформації, яку одні елемент містить відносно іншого.

Найвищий ступінь від подібності - непомітність, а зовсім не однаковість, як може здатися на перший погляд. Однаковість - властивість якісно інша. Справа в тому, чю нерозрізнені об'єкти (так само, як і подібні) не розбиваються на класи так, щоб у кожному класі елементи не розрізнялися, а елементи різних класів свідомо розрізнялися.

Справді,візьмемо множину точок на площині. Нехай величина лежить нижче порога разрешимости очі, тобто - Таку відстань, при якому точки, що знаходяться на цій відстані, невиразні візуально (при обраному видаленні площині від спостерігача). Візьмемо тепер точок, що лежать на одній прямій і віддалених (кожна від сусідніх) на відстані. Кожна пара сусідніх точок нерозрізнена, але якщо достатньо велика, то перша і остання точки будуть відстояти один від одного на метр і свідомо будуть помітні. Зрозуміло, однаковість є приватний випадки нерозрізненості і подібності.

Традиційний підхід до вивчення подібності або нерозрізненості полягає в тому, щоб спочатку визначити міру подібності, а потім дослідити взаємне розташування подібних об'єктів. Англійський математик Зиман, вивчаючи моделі зорового апарату, запропонував аксіоматичне визначення схожості. Тим самим властивості подібності стало можливим вивчати незалежно від того, як конкретно воно задано в тон чи іншій ситуації: відстанню між об'єктами, збігом якихось ознак чи суб'єктивною думкою спостерігача.

Так само, як перехід від розпливчастого поняття "однаковість" до точно визначеного тину відношенні супроводжувався запровадженням пового терміну "еквівалентність", математичне відношення, відповідне нашому інтуїтивному уявленню про подібність або нерозрізненості, отримало у Зимана назву "толерантність". Інакше кажучи, толерантність є експлікацією поняття подібності або нерозрізненості.