Częściowa relacja równoważności - Partial equivalence relation

W matematyce , o częściowy relacją równoważności (często skracane jako PER , w starszej literaturze zwany także ograniczona relacja równoważności ) na zestawie jest binarna relacja , która jest symetryczna i przechodnia . Innymi słowy, dotyczy to wszystkiego : ${\ Displaystyle R}$${\ Displaystyle X}$${\displaystyle a,b,c\w X}$

1. jeśli , to (symetria)${\displaystyle aRb}$${\ Displaystyle bra}$
2. if i , to (przechodniość)${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle arc}$

Jeśli jest również zwrotny , to jest relacją równoważności . ${\ Displaystyle R}$${\ Displaystyle R}$

Właściwości i aplikacje

Jeśli relacja na zbiorze to PER, to jest to relacja równoważności na podzbiorze . Jednak biorąc pod uwagę zbiór i podzbiór , relacja równoważności on nie musi być równa PER on ; na przykład, biorąc pod uwagę zbiór , relacja ponad scharakteryzowana przez zbiór jest relacją równoważności na , ale nie na PER na , ponieważ nie jest ani symetryczna, ani przechodnia na . ${\ Displaystyle R}$${\ Displaystyle X}$${\ Displaystyle R}$${\ Displaystyle Y = \ {x \ w X \ mid x \, R \, x \} \ subseteq X}$${\ Displaystyle X}$${\displaystyle Y\subseteq X}$${\ Displaystyle Y}$${\ Displaystyle X}$${\displaystyle E=\{a,b,c,d\}}$${\ Displaystyle E}$${\ Displaystyle R = \ {a, b, c \} ^ {2} \ filiżanka \ {(d, a) \}}$${\displaystyle \{a,b,c\}}$${\ Displaystyle E}$${\ Displaystyle E}$

Każda cząstkowa relacja równoważności jest relacją dwufunkcyjną , ale odwrotnie nie zachodzi.

Każda cząstkowa relacja równoważności jest właściwą relacją euklidesową . Przeciwnie nie obowiązuje: na przykład xRy na liczbach naturalnych, określonych przez 0 ≤ x ≤ y +1 ≤ 2, jest prawostronnym Euklidesem, ale ani symetrycznym (ponieważ np. 2 R 1, ale nie 1 R 2) ani przechodnim (ponieważ np. 2 R 1 i 1 R 0, ale nie 2 R 0). Podobnie, każda częściowa relacja równoważności jest lewą relacją euklidesową, ale nie odwrotnie. Każda cząstkowa relacja równoważności jest quasi-zwrotna , w konsekwencji bycia euklidesowym.

W ustawieniach niezwiązanych z teorią mnogości

W teorii typów , matematyce konstruktywnej i ich zastosowaniach w informatyce konstruowanie analogów podzbiorów jest często problematyczne — w tych kontekstach PER są zatem częściej używane, szczególnie do definiowania setoidów , czasami nazywanych częściowymi setoidami. Tworzenie częściowego setoidu z typu i PER jest analogiczne do tworzenia podzbiorów i ilorazów w klasycznej matematyce z zakresu teorii mnogości.

Algebraiczne pojęcie kongruencji można również uogólnić na częściowe równoważności, dając pojęcie podkongruencji , tj. homomorficznej relacji, która jest symetryczna i przechodnia, ale niekoniecznie zwrotna.

Przykłady

Prostym przykładem PER, który nie jest relacją równoważności, jest pusta relacja , jeśli nie jest pusta. ${\displaystyle R=\pusty zestaw}$${\ Displaystyle X}$

Jądra funkcji częściowych

Jeżeli jest funkcją częściową na zbiorze , to relacja określona przez ${\displaystyle f}$${\ Displaystyle A}$${\displaystyle \ok}$

${\displaystyle x\ok r}$jeśli jest zdefiniowana w , jest zdefiniowana w , i${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle y}$${\ Displaystyle f (x) = f (y)}$

jest relacją częściowej równoważności, ponieważ jest wyraźnie symetryczna i przechodnia.

Jeśli jest nieokreślony na niektórych elementach, to nie jest relacją równoważności. Nie jest zwrotna, bo jeśli nie jest zdefiniowane, to — w rzeczywistości dla takiego a nie ma takiego, że . Wynika z tego natychmiast, że największy podzbiór, w którym występuje relacja równoważności, jest dokładnie tym podzbiorem, w którym jest zdefiniowany. ${\displaystyle f}$${\displaystyle \ok}$${\displaystyle f(x)}$${\ Displaystyle x \ nie \ w przybliżeniu x}$${\displaystyle x}$${\ Displaystyle y \ w A}$${\displaystyle x\ok r}$${\ Displaystyle A}$${\displaystyle \ok}$${\displaystyle f}$

Funkcje respektujące relacje równoważności

Niech X i Y będą zbiorami wyposażonymi w relacje równoważności (lub PERs) . Dla , zdefiniuj jako oznaczające: ${\ Displaystyle \ około _ {X} \ około _ {Y}}$${\displaystyle f,g:X\do Y}$${\displaystyle f\ok.g}$

${\ Displaystyle \ forall x_ {0} \; x_ {1} \ quad x_ {0} \ około _ {X} x_ {1} \ prawa strzałka f (x_ {0}) \ około _ {Y} g (x_ {1})}$

Następnie oznacza, że F wywołuje dobrze określoną funkcję ilorazów . W ten sposób PER ujmuje zarówno ideę zdefiniowania na ilorazach, jak i dwóch funkcji indukujących tę samą funkcję na iloraz. ${\displaystyle f\ok f}$${\ Displaystyle X/{\ około _ {X}} \; \ do \; Y/ {\ około _ {Y}}}$${\displaystyle \ok}$

Równość IEEE zmiennoprzecinkowych wartości

Standard zmiennoprzecinkowy IEEE 754:2008 definiuje relację „EQ” dla wartości zmiennoprzecinkowych. Ten predykat jest symetryczny i przechodni, ale nie jest zwrotny z powodu obecności wartości NaN , które nie są dla siebie EQ.

Uwagi

Bibliografia

• Mitchell, John C. Podstawy języków programowania. MIT Press, 1996.
• DS Scott. „Typy danych jako kraty”. SIAM Dziennik. Komputer. , 3:523-587, 1976.