Relație omogenă - Homogeneous relation

În matematică , o relație omogenă (numită endorelation ) peste un set X este o relație binară peste X și în sine, adică este un subset al produsului cartezian $X \times X$ . Este , de asemenea , pur și simplu numit (binar) relația peste X . Un exemplu de relație omogenă este relația de rudenie , în care relația este peste oameni.

O relație omogenă R asupra unei mulțimi X poate fi identificată cu un grafic simplu dirijat care permite bucle , sau dacă este simetrică , cu un grafic simplu nedirecționat care permite bucle , unde X este setul de vârf și R este setul de margine (există o margine de la un vârf x la un vârf y dacă și numai dacă $xRy$ ). Se numește relația de adiacență a graficului.

Mulțimea tuturor relațiilor omogene asupra unei mulțimi X este mulțimea $2$ $X$ $\times$ $X$ care este o algebră booleană mărită cu implicarea mapării unei relații cu relația sa inversă . Considerând compoziția relațiilor ca o operație binară pe , formează un semigrup cu involuție . ${\ displaystyle {\ mathcal {B}} (X)}$ ${\ displaystyle {\ mathcal {B}} (X)}$

Relații omogene deosebite

Unele relații omogene importante importante asupra unui set X (cu elemente arbitrare $x 1$ , $x 2$ ) sunt:

Relația goală: $E = \emptyset \subseteq X \times X$ , adică $x 1 Ex 2$ nu este valabil niciodată;
Relația universală: $U = X \times X$ , adică $x 1 Ux 2 se$ menține întotdeauna;
Relația de identitate: $I = {(x, x) | x \in X}$ , adică, $x 1 Ix 2$ este valabil dacă și numai dacă $x 1 = x 2$ .

Exemplu

Cincisprezece plăci tectonice mari ale scoarței terestre se contactează între ele într-o relație omogenă. Relația poate fi exprimată ca o matrice logică cu 1 indicând contact și 0 fără contact. Acest exemplu exprimă o relație simetrică.

Proprietăți

Unele proprietăți importante pe care le poate avea o relație omogenă $R$ asupra unui set $X$ sunt:

Reflexiv: pentru toate $x \in X$ , $xRx$ . De exemplu, ≥ este o relație reflexivă, dar> nu este.
Irreflexiv (sau strict ): pentru toate $x \in X$ , nu $xRx$ . De exemplu,> este o relație ireflexivă, dar ≥ nu.
Coreflexiv: pentru toate $x, y \in X$ , dacă $xRy$ atunci $x = y$ . De exemplu, relația dintre numerele întregi în care fiecare număr impar este legat de el însuși este o relație coreflexivă. Relația de egalitate este singurul exemplu de relație atât reflexivă, cât și coreflexivă, iar orice relație coreflexivă este un subset al relației identitare.
Cvasi-reflexiv stâng: pentru toate $x, y \in X$ , dacă $xRy$ atunci $xRx$ .
Drept cvasi-reflexiv: pentru toate $x, y \in X$ , dacă $xRy$ atunci $yRy$ .
Cvasi-reflexiv: pentru toate $x, y \in X$ , dacă $xRy$ apoi $xRx$ și $yRy$ . O relație este cvasi-reflexivă dacă și numai dacă este și cvasi-reflexivă la stânga și la dreapta.

Cele 6 alternative anterioare sunt departe de a fi exhaustive; de exemplu, relația binară roșie $y = x 2$ nu este nici ireflexivă, nici coreflexivă, nici reflexivă, deoarece conține perechea $(0, 0)$ și $(2, 4)$ , dar nu $(2, 2)$ , respectiv. Ultimele două fapte exclud, de asemenea, (orice fel de) cvasi-reflexivitate.

Simetric: pentru toate $x, y \in X$ , dacă $xRy$ atunci $yRx$ . De exemplu, „este o rudă de sânge a“ este o relație simetrică, deoarece $x$ este o rudă de sânge de $y$ dacă și numai dacă $y$ este o rudă de sânge de $x$ .
Antisimetric: pentru toate $x, y \in X$ , dacă $xRy$ și $yRx$ atunci $x = y$ . De exemplu, ≥ este o relație antisimetrică; la fel este>, dar vid (condiția din definiție este întotdeauna falsă).
Asimetric: pentru toate $x, y \in X$ , dacă $xRy$ atunci nu $yRx$ . O relație este asimetrică dacă și numai dacă este atât antisimetrică, cât și ireflexivă. De exemplu,> este o relație asimetrică, dar ≥ nu.

Din nou, cele 3 alternative anterioare sunt departe de a fi exhaustive; ca exemplu asupra numerelor naturale, relația $xRy$ definită de $x > 2$ nu este nici simetrică, nici antisimetrică, darămite asimetrică.

Tranzitiv: pentru toate $x, y, z \in X$ , dacă $xRy$ și $yRz$ atunci $xRz$ . O relație tranzitivă este ireflexivă dacă și numai dacă este asimetrică. De exemplu, „este strămoșul lui” este o relație tranzitivă, în timp ce „este părintele lui” nu este.
Antitransitiv: pentru toate $x, y, z \in X$ , dacă $xRy$ și $yRz,$ atunci niciodată $xRz$ .
Co-tranzitiv: dacă complementul lui R este tranzitiv. Adică, pentru toate $x, y, z \in X$ , dacă $xRz$ , atunci $xRy$ sau $yRz$ . Aceasta este utilizată în pseudo-ordine în matematică constructivă.
Cvasitransitiv: pentru toate $x, y, z \in X$ , dacă $xRy$ și $yRz,$ dar nici $yRx,$ nici $zRy$ , atunci $xRz,$ dar nu $zRx$ .
Tranzitivitatea incomparabilității: pentru toate $x, y, z \in X$ , dacă $x$ și $y$ sunt incomparabil cu privire la $R$ și dacă același lucru este valabil $y$ și $z$ , atunci $x$ și $z$ sunt de asemenea incomparabil cu privire la $R$ . Aceasta este folosită în ordonări slabe .

Din nou, cele 5 alternative anterioare nu sunt exhaustive. De exemplu, relația $xRy$ dacă ( $y = 0$ sau $y = x +1$ ) nu îndeplinește niciuna dintre aceste proprietăți. Pe de altă parte, relația goală le satisface în mod banal pe toate.

Dens: pentru toate $x, y \in X$ astfel încât $xRy$ , există unele $z \in X$ astfel încât $xRz$ și $zRy$ . Acesta este utilizat în ordine dense .
Conectat: pentru toate $x, y \in X$ , dacă $x \neq y$ atunci $xRy$ sau $yRx$ . Această proprietate este uneori numită „total”, care este distinctă de definițiile „stânga / dreapta-total” date mai jos.
Strâns conectat: pentru toate $x, y \in X$ , $xRy$ sau $yRx$ . Și această proprietate este uneori numită „total”, care este distinctă de definițiile „stânga / dreapta-total” date mai jos.
Tricotomă: pentru toate $x, y \in X$ , exact una dintre $valorile xRy$ , $yRx$ sau $x = y$ . De exemplu,> este o relație trichotomică, în timp ce relația „împarte” peste numerele naturale nu este.
Euclidian corect (sau doar euclidian ): pentru toate $x, y, z \in X$ , dacă $xRy$ și $xRz$ atunci $yRz$ . De exemplu, = este o relație euclidiană deoarece dacă $x = y$ și $x = z$ atunci $y = z$ .
Euclidian stâng: pentru toate $x, y, z \in X$ , dacă $yRx$ și $zRx$ atunci $yRz$ .
Bine întemeiat: fiecare subset nevid $S$ al $X$ conține un element de minimal în ceea ce privește $R$ . Fundamentarea implică condiția lanțului descendent (adică nu există un lanț infinit ... $x n R ... Rx 3 Rx 2 Rx 1 nu$ poate exista). Dacă se presupune axioma alegerii dependente , ambele condiții sunt echivalente.

Mai mult, toate proprietățile relațiilor binare, în general, se pot aplica și relațiilor omogene:

Set-like: pentru toate $x \in X$ , clasa tuturor $y$ astfel încât $yRx$ este un set. (Acest lucru are sens numai dacă sunt permise relațiile peste clase adecvate.)
Stâng-unic: pentru toate $x, z \in X$ și toate $y \in Y$ , dacă $xRy$ și $zRy$ atunci $x = z$ .
Drept-unic: pentru toate $x \in X$ și toate $y, z \in Y$ , dacă $xRy$ și $xRz$ atunci $y = z$ .
Serial (numit și stânga-total): pentru toate $x \in X$ există un $y \in Y$ astfel încât $xRy$ . Această proprietate, deși denumită și totală de unii autori, este diferită de definiția conexiunii (numită și totală de unii autori).
Surjectiv (numit și dreapta-total): pentru toate $y \in Y$ , există un $x \in X$ astfel încât xRy .

O precomandă este o relație care este reflexivă și tranzitivă. O precomandă totală , numită și precomandă liniară sau ordine slabă , este o relație care este reflexivă, tranzitivă și conectată.

O ordine parțială , numită și ordine , este o relație care este reflexivă, antisimetrică și tranzitivă. O ordine parțială strictă , numită și ordine strictă , este o relație care este ireflexivă, antisimetrică și tranzitivă. O ordine totală , numită și ordine liniară , ordine simplă sau lanț , este o relație care este reflexivă, antisimetrică, tranzitivă și conectată. O ordine totală strictă , numită și ordine liniară strictă , ordine simplă strictă sau lanț strict , este o relație ireflexivă, antisimetrică, tranzitivă și conectată.

O relație de echivalență parțială este o relație simetrică și tranzitivă. O relație de echivalență este o relație care este reflexivă, simetrică și tranzitivă. Este, de asemenea, o relație simetrică, tranzitivă și serială, deoarece aceste proprietăți implică reflexivitate.

Implicații și conflicte între proprietățile relațiilor binare omogene
Implicații (albastru) și conflicte (roșu) între proprietăți (galbene) ale relațiilor binare omogene. De exemplu, fiecare relație asimetrică este ireflexivă ( " ASym ⇒ Irrefl " ) și nicio relație pe un set ne-gol nu poate fi atât ireflexivă, cât și reflexivă ( " Irrefl # Refl " ). Omiterea marginilor roșii duce la o diagramă Hasse .

Operațiuni

Dacă R este o relație omogenă peste un set X, atunci fiecare dintre următoarele este o relație omogenă peste X :

Închidere reflexivă , R ⁼: Definit ca $R = = {(x, x) | x \in X} \cup R$ sau cea mai mică relație reflexivă peste X conținând R . Acest lucru poate fi dovedit a fi egală cu intersecția tuturor relațiilor reflexive care conțin R .
Reducere reflexivă , R ^≠: Definit ca $R ≠ = R \ {( x , x ) | x ∈ X }$ sau cea mai mare irreflexive relația peste X conținută în R .
Închidere tranzitivă , R ⁺: Definită ca cea mai mică relație tranzitivă peste X conținând R . Acest lucru poate fi văzut ca fiind egală cu intersecția tuturor relațiilor tranzitive care conțin R .
Închidere tranzitivă reflexivă , R *: Definită ca $R * = (R +) =$ , cel mai mic precomanda conținând R .
Închidere simetrică tranzitivă reflexivă , R ^≡: Definită ca cea mai mică relație de echivalență peste X conținând R .

Toate operațiile definite în relația binară § Operațiile asupra relațiilor binare se aplică și relațiilor omogene.

Relații omogene după proprietate
	Reflexivitate	Simetrie	Tranzitivitate	Conectivitate	Simbol	Exemplu
Grafic direcționat					→
Grafic nedirectat		Simetric
Dependenţă	Reflexiv	Simetric
Turneu	Irreflexiv	Antisimetric				Ordinul de ciocănire
Pre-comanda	Reflexiv		Tranzitiv		≤	Preferinţă
Preordonare totală	Reflexiv		Tranzitiv	Conectat	≤
Ordine parțială	Reflexiv	Antisimetric	Tranzitiv		≤	Subset
Ordin parțial strict	Irreflexiv	Antisimetric	Tranzitiv		<	Subset strict
Comandă totală	Reflexiv	Antisimetric	Tranzitiv	Conectat	≤	Ordine alfabetică
Ordinea totală strictă	Irreflexiv	Antisimetric	Tranzitiv	Conectat	<	Ordinea alfabetică strictă
Relația de echivalență parțială		Simetric	Tranzitiv
Relația de echivalență	Reflexiv	Simetric	Tranzitiv		∼, ≡	Egalitate

Enumerare

Numărul de relații omogene distincte pentru un set de elemente n este $2 n 2$ (secvența A002416 în OEIS ):

Numărul de relații binare n -element de diferite tipuri
Elemente	Orice	Tranzitiv	Reflexiv	Pre-comanda	Ordine parțială	Preordonare totală	Comandă totală	Relația de echivalență
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65.536	3.994	4.096	355	219	75	24	15
n	2 ^{n ²}		2 ^{n ² - n}			${\ textstyle \ sum _ {k = 0} ^ {n} k!}$	n !	${\ textstyle \ sum _ {k = 0} ^ {n}}$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Note:

Numărul relațiilor ireflexive este același cu cel al relațiilor reflexive.
Numărul de ordine parțiale stricte (relații tranzitive ireflexive) este același cu cel al ordinelor parțiale.
Numărul de ordine stricte stricte este același cu cel al pre-comenzilor totale.
Comenzile totale sunt comenzile parțiale care sunt, de asemenea, precomenzi totale. Numărul de precomenzi care nu sunt nici o comandă parțială și nici o precomandă totală este, prin urmare, numărul de precomenzi, minus numărul de comenzi parțiale, minus numărul de precomenzi totale, plus numărul de comenzi totale: 0, 0, 0, 3, respectiv 85.
Numărul de relații de echivalență este numărul de partiții , care este numărul Bell .

Relațiile omogene pot fi grupate în perechi (relație, complement ), cu excepția faptului că pentru $n = 0$ relația este propriul său complement. Cele nesimetrice pot fi grupate în cvadrupluri (relație, complement, invers , complement invers).

Exemple

Relații de ordine , inclusiv ordine stricte :
- Mai mare ca
- Mai mare sau egal cu
- Mai puțin decât
- Mai mic sau egal cu
- Împarte (uniform)
- Subset de
Relații de echivalență :
- Egalitate
- Paralel cu (pentru spații afine )
- Equinerozitatea sau "este în bijecție cu"
- Izomorf
Relația de toleranță , o relație
reflexivă și simetrică:
- Relația de dependență , o relație de toleranță finită
- Relația de independență , complementul unei relații de dependență
Relațiile de rudenie

Generalizări

O relație binară în general , nu este nevoie să fie omogen, acesta este definit ca fiind un subset R ⊆ X × Y pentru seturile arbitrare X și Y .
O relație finitară este un subset R ⊆ X ₁ × ... × X _n pentru un număr natural n și mulțimi arbitrare X ₁ , ..., X _n , se mai numește și o relație n -ary.

Languages

In other projects