Semi-zăbrele

În matematică, o semireticulă este o structură algebrică care poate fi definită ca un semigrup comutativ idempotent . O astfel de structură se găsește a fi izomorfă la așa-numitul set semi-reticulat , setat parțial ordonat în care fiecare set de două elemente are o minoritate maximă (în mod echivalent ar putea fi necesară existența majorantului minim ). De fapt, speciile de semi- rețele pot fi considerate ca o sărăcire a celor mai cunoscute și importante specii de rețele și fiecare dintre aceste structuri algebrice este criptomorfă la o structură relațională , tocmai la un întreg reticulat care are un semi- reticulat întreg ca o sărăcire.

Definiția semireticolo

Se spune semilatice o magmă (S, $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ ) pentru a cărui operație binară $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ cere elemente arbitrare $x,y,z\in S$ ${\ displaystyle x, y, z \ în S}$ ${\ displaystyle x, y, z \ în S}$

$x\wedge (y\wedge z)=(x\wedge y)\wedge z$ ${\ displaystyle x \ wedge (y \ wedge z) = (x \ wedge y) \ wedge z}$ ${\ displaystyle x \ wedge (y \ wedge z) = (x \ wedge y) \ wedge z}$ ( asociativitate )
$x\wedge y=y\wedge x$ ${\ displaystyle x \ wedge y = y \ wedge x}$ ${\ displaystyle x \ wedge y = y \ wedge x}$ ( comutativitate )
$x\wedge x=x$ ${\ displaystyle x \ wedge x = x}$ ${\ displaystyle x \ wedge x = x}$ ( idempotență )

Operația binară poate fi numită întâlnire , în engleză meet . Caracteristicile semi-rețelelor sunt mai bine clarificate prin introducerea pentru fiecare dintre ele a unei relații pe care o denotăm cu simbolul infixat $\leq$ ${\ displaystyle \ leq}$ $\ leq$ definit de cerere

x\leq y\quad \mathrm {se~e~solo~se} \quad x\wedge y=x

{\ displaystyle x \ leq y \ quad \ mathrm {if ~ and ~ only ~ if} \ quad x \ wedge y = x}

{\ displaystyle x \ leq y \ quad \ mathrm {if ~ and ~ only ~ if} \ quad x \ wedge y = x}

Pentru a detecta că depinde de funcționarea semireticulei, se poate scrie

\leq ~:=~rel(\wedge )~:=~\{(x,y)\in S\times S~\mathrm {tale~che} ~x\wedge y=x\}

{\ displaystyle \ leq ~: = ~ rel (\ wedge) ~: = ~ \ {(x, y) \ in S \ times S ~ \ mathrm {such ~ that} ~ x \ wedge y = x \}}

{\ displaystyle \ leq ~: = ~ rel (\ wedge) ~: = ~ \ {(x, y) \ in S \ times S ~ \ mathrm {such ~ that} ~ x \ wedge y = x \}}

Acum dovedim asta $\leq$ ${\ displaystyle \ leq}$ ${\ displaystyle \ leq}$ este o relație de ordine. Suntem de acord că $X, y$ ${\ displaystyle x, y}$ $X y$ Și $z$ ${\ displaystyle z}$ $z$ sunt elemente generice ale $S.$ ${\ displaystyle S}$ $S.$ .

$x\leq x~\mathrm {implica} ~x\wedge x=x$ ${\ displaystyle x \ leq x ~ \ mathrm {implică} ~ x \ wedge x = x}$ ${\ displaystyle x \ leq x ~ \ mathrm {implică} ~ x \ wedge x = x}$ , adică idempotența lui $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ implică reflexivitatea $\leq$ ${\ displaystyle \ leq}$ ${\ displaystyle \ leq}$ .

De sine $x\leq y~\mathrm {e} ~y\leq x$ ${\ displaystyle x \ leq y ~ \ mathrm {e} ~ y \ leq x}$ ${\ displaystyle x \ leq y ~ \ mathrm {e} ~ y \ leq x}$ , asa de $x\wedge y=x~\mathrm {e} ~y\wedge x=y$ ${\ displaystyle x \ wedge y = x ~ \ mathrm {e} ~ y \ wedge x = y}$ ${\ displaystyle x \ wedge y = x ~ \ mathrm {e} ~ y \ wedge x = y}$ iar pentru simetria lui $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ da ai $\,x=y\,$ ${\ displaystyle \, x = y \,}$ ${\ displaystyle \, x = y \,}$ . De aici simetria $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ implică antisimetria $\leq$ ${\ displaystyle \ leq}$ ${\ displaystyle \ leq}$ .

De sine $x\leq y~\mathrm {e} ~y\leq z$ ${\ displaystyle x \ leq y ~ \ mathrm {e} ~ y \ leq z}$ ${\ displaystyle x \ leq y ~ \ mathrm {e} ~ y \ leq z}$ , asa de $x\wedge y=x~\mathrm {e} ~y\wedge z=y$ ${\ displaystyle x \ wedge y = x ~ \ mathrm {e} ~ y \ wedge z = y}$ ${\ displaystyle x \ wedge y = x ~ \ mathrm {e} ~ y \ wedge z = y}$ ; să evaluăm întâlnirea $x\wedge z=(x\wedge y)\wedge z=*=x\wedge (y\wedge z)=x\wedge y=x$ ${\ displaystyle x \ wedge z = (x \ wedge y) \ wedge z = * = x \ wedge (y \ wedge z) = x \ wedge y = x}$ ${\ displaystyle x \ wedge z = (x \ wedge y) \ wedge z = * = x \ wedge (y \ wedge z) = x \ wedge y = x}$ . De aici și asociativitatea $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ implică tranzitivitatea $\leq$ ${\ displaystyle \ leq}$ ${\ displaystyle \ leq}$ .

Tragând corzile $\leq$ ${\ displaystyle \ leq}$ ${\ displaystyle \ leq}$ este reflexiv, antisimetric și tranzitiv. QED

Existența relației de ordine facilitează identificarea vizuală a semireticulelor importante. Fiecare contraarborescență , adică fiecare digraf echipat cu un nod (nod rădăcină ) la care pot fi atinse toți ceilalți cu o singură cale, oferă o semi-rețea: suportul său este setul de noduri și întâlnirea conduce de la două noduri către primul nod comun între cele două căi care duc de la nodurile operandului la nodul rădăcină. Toate acestea sunt evidente din reprezentarea digrafului.

Semi-rețelele pot fi obținute luând în considerare un set de puncte $G.$ ${\ displaystyle G}$ $G.$ ale planului cartezian și adăugându-le toate punctele obținute cu operația de întâlnire definită după cum urmează:

(a,b)\wedge (c,d):=(\min(a,c),\min(b,d)).

{\ displaystyle (a, b) \ wedge (c, d): = (\ min (a, c), \ min (b, d)).}

{\ displaystyle (a, b) \ wedge (c, d): = (\ min (a, c), \ min (b, d)).}

Întregul $G.$ ${\ displaystyle G}$ $G.$ se numește ansamblul generatoarelor de semi-rețea. De sine $G.$ ${\ displaystyle G}$ $G.$ este terminat există un singur punct descendent dintre toate celelalte. Acest punct se numește minim sau chiar zero din semireticolo. Este evident unic și constituie elementul neutru pentru operație $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ . Toate semi-grilele finite sunt echipate cu un minim. De sine $G.$ ${\ displaystyle G}$ $G.$ este infinit, minimul nu poate exista: tocmai minimul există și este egal cu punctul care are ca abscisă minimul absciselor punctelor de $G.$ ${\ displaystyle G}$ $G.$ și ca ordonată minimul ordonatelor punctelor din $G.$ ${\ displaystyle G}$ $G.$ dacă și numai dacă cele două minime există.

Prin urmare, se disting semi-rețele cu minim și semi-rețele fără minim. Primele se numesc semi-rețele unitare : sunt monoizii idempotenți .

Se observă că discursuri substanțial echivalente cu cele făcute pentru contrarescențe pot fi rostite pentru arborescențe. De fapt, relația asociată cu semireticula ar putea fi înlocuită cu reflectarea acesteia, datorită dualității relațiilor de ordine. În acest al doilea caz operația binară s-ar numi unire (în engleză join ) și în loc de minim sau zero am vorbi de maxim și unitate de semi-rețea.

În abstract, cele două cazuri nu se disting și se reduc la diferențe lexicale. Pe de altă parte, este recomandabil să alegeți cu atenție o limbă pentru semireticulele identificate ca subseturi de seturi ordonate cu propria lor terminologie consolidată pentru relația de ordine. Observăm în special că dintr-o rețea sunt identificate două semi-rețele, una cu operația de întâlnire, cealaltă cu operația de îmbinare.

Controlul autorității	LCCN (EN) sh85119924 · BNF (FR) cb14606891j (data)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică