Join e meet

Relacións binarias transitivas
Simétrica Antisimétrica Conexa Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica Relación de equivalencia  Si  Non  Non  Non  Non  Non  Si  Non  Non Preorde (Cuasiorde)  Non  Non  Non  Non  Non  Non  Si  Non  Non Orde parcial  Non  Si  Non  Non  Non  Non  Si  Non  Non Preorde total  Non  Non  Si  Non  Non  Non  Si  Non  Non Orde total  Non  Si  Si  Non  Non  Non  Si  Non  Non Pre-Ben ordenada  Non  Non  Si  Si  Non  Non  Si  Non  Non Cuasi-Ben ordenada  Non  Non  Non  Si  Non  Non  Si  Non  Non Ben ordenada  Non  Si  Si  Si  Non  Non  Si  Non  Non Retícula  Non  Si  Non  Non  Si  Si  Si  Non  Non Semiretícula superior (join)  Non  Si  Non  Non  Si  Non  Si  Non  Non Semiretícula inferior (meet)  Non  Si  Non  Non  Non  Si  Si  Non  Non Orde estrita parcial  Non  Si  Non  Non  Non  Non  Non  Si  Si Orde estrita feble  Non  Si  Non  Non  Non  Non  Non  Si  Si Orde estrita total  Non  Si  Si  Non  Non  Non  Non  Si  Si Simétrica Antisimétrica Conexa Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica Definicións, para todo $a,b$ e $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{existe}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}$ $aRa$ ${\text{non }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{non }}bRa\end{aligned}}$
Si indica que a columna da propiedade é sempre verdadeira no termo da fila (na esquerda de todo), mentres que  Non indica que a propiedade non está garantida en xeral (pode cumprirse ou non). Por exemplo, toda relación de equivalencia é simétrica, mais non necesariamente antisimétrica, está indicada por  Si na columna "Simétrica" e  Non na columna "Antisimétrica". Todas as definicións requiren tacitamente que a relación homoxénea $R$ sexa transitiva: para todo $a,b,c,$ se $aRb$ e $bRc$ entón $aRc.$ Algunha definición dalgún termo pode requerir propiedades adicionais non recollidas na táboa.

Este diagrama de Hasse representa un conxunto parcialmente ordenado con catro elementos: a, b, o elemento máximal a $\vee$ b igual ao join de a e b, e o elemento mínimal a $\wedge$ b igual ao meet de a e b. O join/meet dun elemento maximal/minimal e outro elemento é o elemento maximal/minimal e, reciprocamente, o meet/join dun elemento maximal/minimal con outro elemento é o outro elemento. Así, cada parella deste poset ten tanto un meet como un join e o poset pódese clasificar como unha retícula.

En matemáticas, concretamente na teoría da orde, o join dun subconxunto $S$ dun conxunto parcialmente ordenado $P$ é o supremo (límite superior mínimo) de $S,$ denotado ${\textstyle \bigvee S,}$ e do mesmo xeito, o meet de $S$ é o infimo (maior límite inferior), denotado ${\textstyle \bigwedge S.}$ En xeral, o join e o meet dun subconxunto dun conxunto parcialmente ordenado poden non existir. Join e meet son duais entre si en relación á inversión de orde.

O join/meet dun subconxunto dun conxunto totalmente ordenado é simplemente o elemento maximal/minimal dese subconxunto, se tal elemento existe.

Definicións

Sexa $A$ un conxunto cunha orde parcial $\,\leq ,\,$ e sexan $x,y\in A.$ Un elemento $m$ de $A$ chámase o meet (ou maior límite inferior ou ínfimo) de $x{\text{ e }}y$ e denótase por $x\wedge y,$ se se cumpren as dúas condicións seguintes:

1. $m\leq x{\text{ e }}m\leq y$ (é dicir, $m$ é un límite inferior de $x{\text{ and }}y$ ).
2. Para calquera $w\in A,$ se $w\leq x{\text{ and }}w\leq y,$ entón $w\leq m$ (é dicir, $m$ é maior ou igual a calquera outro límite inferior de $x{\text{ and }}y$ ).

O meet non ten por que existir, xa sexa porque o par non ten límite inferior en absoluto, ou porque ningún dos límites inferiores é maior que todos os demais. No entanto, se hai un meet de $x{\text{ e }}y,$ entón é único, xa que se ambos os $m{\text{ e }}m^{\prime }$ son límites inferiores maiores de $x{\text{ e }}y,$ entón $m\leq m^{\prime }{\text{ e }}m^{\prime }\leq m,$ e así $m=m^{\prime }.$ Se non todos os pares de elementos de $A$ teñen un meet, entón o meet aínda pode verse como unha operación binaria parcial en $A.$

Se o meet existe, denótase $x\wedge y.$ Se todos os pares de elementos de $A$ teñen un meet, entón o meet é unha operación binaria en $A,$ e é fácil ver que esta operación cumpre as tres condicións seguintes: Para calquera elementos $x,y,z\in A,$

1. $x\wedge y=y\wedge x$ (conmutatividade),
2. $x\wedge (y\wedge z)=(x\wedge y)\wedge z$ (asociatividade), e
3. $x\wedge x=x$ (idempotencia).

Os join defínense dualmente como join de $x{\text{ e }}y,$ se existe, denótase por $x\vee y.$ Un elemento $j$ de $A$ é o join (ou menor límite superior ou supremo) de $x{\text{ e }}y$ en $A$ se se cumpren as dúas condicións seguintes:

1. $x\leq j{\text{ e }}y\leq j$ (é dicir, $j$ é un límite superior de $x{\text{ e }}y$).
2. Para calquera $w\in A,$ se $x\leq w{\text{ e }}y\leq w,$ entón $j\leq w$ (é dicir, $j$ é menor ou igual a calquera outro límite superior de $x{\text{ e }}y$ ).

Exemplos

Se algún conxunto de partes $\wp (X)$ está parcialmente ordenado da forma habitual (por $\,\subseteq$ ) entón os joins son unións e os joins son interseccións; en símbolos, $\,\vee \,=\,\cup \,{\text{ e }}\,\wedge \,=\,\cap \,$ (onde a semellanza destes símbolos pode usarse como regra mnemotécnica).

Máis xeral sería o seguinte. Subpoña ${\mathcal {F}}\neq \varnothing$ é unha familia de subconxuntos dun conxunto $X$ que é un conxunto parcialmente ordenado por $\,\subseteq .\,$ Se ${\mathcal {F}}$ é pechado baixo unións arbitrarias e interseccións arbitrarias e se $A,B,\left(F_{i}\right)_{i\in I}$ pertencen a ${\mathcal {F}}$ daquela $$A\vee B=A\cup B,\quad A\wedge B=A\cap B,\quad \bigvee _{i\in I}F_{i}=\bigcup _{i\in I}F_{i},\quad {\text{ e }}\quad \bigwedge _{i\in I}F_{i}=\bigcap _{i\in I}F_{i}.$$

Mais se ${\mathcal {F}}$ non é pechado baixo unións daquela $A\vee B$ existe en $({\mathcal {F}},\subseteq )$ se e só se existe un único $\,\subseteq$-máis-pequeno $J\in {\mathcal {F}}$ tal que $A\cup B\subseteq J.$

Por exemplo, se ${\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\mathbb {R} \}$ entón $\{1\}\vee \{2\}=\{1,2,3\}$ mentres que se ${\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\{0,1,2\},\mathbb {R} \}$ entón $\{1\}\vee \{2\}$ non existe porque os conxuntos $\{0,1,2\}{\text{ e }}\{1,2,3\}$ son límites superiores de $\{1\}{\text{ e }}\{2\}$ en $({\mathcal {F}},\subseteq )$ que poderían ser posíbelmente o menor límite superior $\{1\}\vee \{2\}$ mais $\{0,1,2\}\not \subseteq \{1,2,3\}$ e $\{1,2,3\}\not \subseteq \{0,1,2\}.$

Se ${\mathcal {F}}=\{\{1\},\{2\},\{0,2,3\},\{0,1,3\}\}$ entón $\{1\}\vee \{2\}$ non existe porque non existe un límite superior de $\{1\}{\text{ e }}\{2\}$ en $({\mathcal {F}},\subseteq ).$

Véxase tamén

Bibliografía

• Davey, B.A.; Priestley, H.A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge: Cambridge University Press. ISBN 0-521-78451-4. Zbl 1002.06001. 
• Vickers, Steven (1989). Topology via Logic. Cambridge Tracts in Theoretic Computer Science 5. ISBN 0-521-36062-5. Zbl 0668.54001. 

Outros artigos

• Orde parcial.