6 de noviembre de 2012

El retículo de los subconjuntos difusos de un conjunto


Desde hace unos días he estado leyendo sobre conjuntos difusos y me encontré con un teorema que me gustó; no sé por qué: más bien no me lo he querido responder todavía.
     En un artículo de 1937, Vagueness: An exercise in logical analysis, el filósofo y matemático Max Black escribió sobre lo que llamó los conjuntos vagos, ahora llamados conjuntos difusos. Su artículo comienza como sigue: “Es paradójico [...] que las teorías científicas más útiles y más altamente desarrolladas están expresadas aparentemente en términos de objetos con los que uno nunca se encuentra en la experiencia. La línea trazada por un dibujante técnico, sin importar qué tan precisa la haga, se ve, bajo el microscopio, como una zanja ondulada, algo muy alejado de la línea ideal de la geometría pura. Y el planeta puntual de la astronomía, el gas perfecto de la termodinámica o las especies puras de la genética están igualmente muy alejados de la realización exacta. [...] Mientras el matemático construye una teoría en términos de objetos perfectos, el científico experimental observa objetos cuyas propiedades exigidas por la teoría son y sólo pueden ser, por la naturaleza misma de la medición, aproximadamente ciertas”.
     Posteriormente, en un artículo de 1965, Fuzzy sets. Information and Control, Lotfali Askar Zadeh retoma las ideas formuladas más o menos 30 años atrás por Black, y nace entonces la teoría de los conjuntos difusos.
     Los conceptos vagos (o difusos), predicados que modelan propiedades difíciles de discernir de manera clara o precisa pueden ser (se propone, en esos artículos, que sean) representados mediante subconjuntos difusos. Esta nueva manera de ver las cosas tiene, por supuesto, consecuencias filosóficas, como considerar una nueva categoría de determinación.

Definición. Dados un conjunto $U$ y $C$ un retículo completo, se define un subconjunto $C$-difuso de $U$ como una función $A:U\rightarrow C$ (que va de $U$ a $C$). Si $C=[0,1]$, a $A$ se lo llama simplemente subconjunto difuso de $U$.

Por ejemplo, el concepto “ser joven” o la pertenencia al conjunto de las personas jóvenes puede ser modelado por la función $A:[0,\infty)\rightarrow[0,1]$ definida como $$A(e):= \begin{cases} 1 &\text{si $e < 25$;}\\ \frac{50-e}{25} &\text{si $25\leq e\leq 50$;}\\ 0 &\text{si $50 < e$;} \end{cases} $$ donde $[0,\infty)$ representa el conjunto de todas las posibles edades de las personas.


La total pertenencia al conjunto de las personas jóvenes está representado por que se obtenga 1 en $A$. El grado de pertenencia a este conjunto va disminuyendo conforme se empieza a envejecer, hasta que finalmente, a partir de los 50, ya no se pertenece. Por supuesto, se pueden proponer otros tipos de subconjuntos difusos para representar tal concepto, los cuales dependerán del contexto y de lo que interese.
     Hay aplicaciones más interesantes que la anterior, como al control difuso, pero esas quizá las deje para otra entrada.
     El teorema que me gustó forma parte de la teoría de los conjuntos difusos.

Teorema. Sea $C$ un retículo completo y sea $U$ un conjunto cualquiera. Sea $\mathcal{F}(U)$ el conjunto de todas las funciones que van de $U$ a $C$, y sea $\mathcal{L}(U)$ el conjunto de todas las funciones $g:C\rightarrow\mathcal{P}(U)$ tales que para todo subconjunto $D$ de $C$ se cumple la siguiente igualdad: $$g\left(\bigvee D\right)=\bigcap_{d\in D}g(d).$$ Entonces la función $\Phi:\mathcal{F}(U)\rightarrow\mathcal{L}(U)$ dada por $\Phi(A)=A^{-1}\uparrow$ es biyectiva.

Demostración. Primero veamos que para $A^{-1}\uparrow$ se cumple la igualdad anterior. Sea $A:U\rightarrow C$ una función, así que $$\forall\,D\subseteq C\quad A^{-1}(\uparrow\vee D)=\bigcap_{d\in D}A^{-1}(\uparrow d).$$ En efecto, $u\in A^{-1}(\uparrow\vee D)\Leftrightarrow A(u)\geq\vee D\Leftrightarrow \forall\,\alpha\in D\; A(u)\geq\alpha\Leftrightarrow u\in\bigcap_{\alpha\in D}A^{-1}(\uparrow\alpha)$. En efecto $\Phi$ es inyectiva. Sean $A,B\in\mathcal{F}(U)$ tales que $A^{-1}\uparrow=B^{-1}\uparrow$; es decir, que $\forall\,\alpha\in [0,1]\;A_{\alpha}=B_{\alpha}$. Ahora, tenemos que $$A^{-1}(\alpha)=A_{\alpha}\bigcap(\bigcup_{\beta > \alpha}A_{\beta})',$$ así que $A^{-1}(\alpha)=B^{-1}(\alpha)$ para todo $\alpha\in [0,1]$; luego, $A=B$. Ahora veamos que $\Phi$ es suprayectiva. Sea $g\in\mathcal{L}(U)$. Veamos que $g$ es una función antítona. Sean $a,b\in C$ tales que $a\leq b$. Entonces, $a\vee b=b$; así que, por conmutatividad, $$g(b)=g(a\vee b)=g(a)\cap g(b);$$ de aquí, $g(b)\subseteq g(a)$. Luego, $g$ es antítona. Ahora definamos $h:U\rightarrow\mathcal{P}(C)$ como sigue: $$h(u):=\{d\in C\mid u\in g(d)\}.$$ Sea $A:=\bigvee\circ h:U\rightarrow C$. Veamos que $A^{-1}\uparrow(c)=g(c)$ para todo $c\in C$. Sea $u\in A^{-1}\uparrow(c)$; entonces, $A(u)=\bigvee h(u)\geq c$. Por otro lado, $\forall\,d\in h(u)\quad u\in g(d)$; de aquí, $$u\in\bigcap_{d\in h(u)}g(d)=g(\bigvee h(u))=g(A(u)).$$ Por otro lado, $g$ es antítona y $A(u)\geq c$; por lo tanto, $u\in g(A(u))\subseteq g(c)$. Así que $A^{-1}\uparrow(c)\subseteq g(c)$.
     Recíprocamente, sea $u\in g(c)$; entonces, $c\in h(u)$; de aquí, $A(u)=\bigvee h(u)\geq c$; por lo tanto, $u\in A^{-1}\uparrow (c)$. Así que $g(c)\subseteq A^{-1}\uparrow(c)$. Luego, $g=A^{-1}\uparrow$, y resulta que $\Phi$ es suprayectiva. ■

Pero más aún, se tiene que $\Phi$ es un isomorfismo de conjuntos parcialmente ordenados. En efecto, claramente, dadas dos funciones $A,B:U\rightarrow C$ tales que $A(u)\leq B(u)$ para todo $u\in U$, se tiene que $A^{-1}\uparrow(x)\subseteq B^{-1}\uparrow(x)$ para $x\in C$.
     Recíprocamente, supongamos que $$\forall\,x\in C\ A^{-1}\uparrow(x)\subseteq B^{-1}\uparrow(x).$$ Sea entonces $u\in U$; se tiene que $A^{-1}\uparrow(A(u))\subseteq B^{-1}\uparrow(A(u))$, así que $A(u)\leq B(u)$.
     Luego, $A\leq B$ si y sólo si $A^{-1}\uparrow\leq B^{-1}\uparrow$: $\mathcal{F}(U)\cong\mathcal{L}(U)$.

El siguiente teorema no lo encontré como tal, sino como una observación en el A First Course in Fuzzy Logic, su segunda edición. Sin embargo, a mí me pareció un teorema, o quizá un corolario, ya que no me pareció tan evidente la afirmación: por eso escribí su demostración. Este teorema también me gustó. Por cierto, resulta que $\mathcal{F}(U)$ (más bien $(\mathcal{F}(U),\vee,\wedge,0,1)$) es un retículo completo, y cuando $C=[0,1]$, $\mathcal{F}(U)$ es un álgebra De Morgan completa.

Teorema. $\mathcal{L}(U)$ es subretículo de $\mathcal{P}(U)^C$ si y sólo si $C$ es una cadena.

Demostración. En general, se tiene que si $A,B\in C^U$ entonces $$\forall\,c\in C\ A^{-1}\uparrow(c)\cup B^{-1}\uparrow(c)\subseteq(A\vee B)^{-1}\uparrow(c).$$ En efecto, sea $u\in A^{-1}\uparrow(c)\cup B^{-1}\uparrow(c)$; entonces, $A(u)\geq c$ o $B(u)\geq c$. Sin pérdida de generalidad, supongamos que $A(u)\geq c$. Entonces, $$A(u)\vee B(u)\geq A(u)\geq c.$$ Luego, $u\in (A\vee B)^{-1}\uparrow(c)$. Supóngase ahora que $C$ es una cadena. Sea $c\in C$ y $u\in (A\vee B)^{-1}\uparrow(c)$. Entonces, $A(u)\leq B(u)$ o $B(u)\leq A(u)$. Si $A(u)\leq B(u)$ entonces $B(u)=A(u)\vee B(u)$, y, de aquí, $u\in B^{-1}\uparrow(c)$. Si $B(u)\leq A(u)$ entonces $u\in A^{-1}\uparrow(c)$. Luego, $u\in A^{-1}\uparrow(c)\cup B^{-1}\uparrow(c)$. Por lo tanto, $(A\vee B)^{-1}\uparrow=A^{-1}\uparrow\cup B^{-1}\uparrow$.
     Recíprocamente, supóngase que $$\forall\,A,B\in C^U\ (A\vee B)^{-1}\uparrow=A^{-1}\uparrow\cup B^{-1}\uparrow;$$ es decir, que $\mathcal{L}(U)$ es subretículo de $\mathcal{P}(U)^C$. Veamos que $C$ es una cadena. Sean $c,d\in C$. Definamos $A_c,A_d:U\rightarrow C$ como $A_c(u)=c$ y $A_d(u)=d$ para todo $u\in U$. Tenemos que $$U=(A_c\vee A_d)^{-1}\uparrow(c\vee d)=A_c^{-1}\uparrow(c\vee d)\cup A_d^{-1}\uparrow(c\vee d).$$ De aquí, $\exists\,u\in U\ A_c(u)\geq c\vee d$ o $A_d(u)\geq c\vee d$; por lo tanto, $c\geq c\vee d$ o $d\geq c\vee d$; es decir, $c\geq d$ o $d\geq c$. Luego, $C$ es una cadena. ■

5 de noviembre de 2012

Joining the meeting


Behind a fence, where chains are more useful than antichains, a downset and an upset were eating an ambrosial De Morgan lattice salad when the downset said to the upset unexpetedly: “I feel very, very down, my friend, very, very down.” After a final big bite of that incomplete lattice salad, the upset dually said: “And that makes me maximally upset, my dear friend.”