3.3. Opzionale: Contare le topologie finite

Sia $X$ un insieme: ricordiamo che $R$ una relazione (binaria) su $X$ è una forma proposizionale su $X\times X$, cioè una funzione $R\from X\times X \to \{ 0,1\} $ (o Vero/Falso), indicata nei due modi $R(x,y) = xRy$. La relazione è riflessiva se per ogni $x\in X$ si ha che $xRx=1$ (è vero), e transitiva se per ogni $x,y,z\in X$ si ha che $xRy=yRz=1 \implies xRz=1$. Una relazione binaria riflessiva e transitiva è detta relazione di preordine parziale.

(3.16) Nota. Sia $X$ un insieme finito, con una topologia $\mathcal{A}$. Allora $\mathcal{A}$ definisce una relazione di preordine parziale $R$ su $X$ (che possiamo indicare con $R_{\mathcal{A}}$) nel modo seguente: se $x,y\in X$, si definisce

\[ xRy \iff \left( \text {\begin{minipage}{0.4\textwidth }“ogni aperto $U$ di $X$ che contiene $x$ contiene anche $y$”\end{minipage}} \right) \]

che è una relazione riflessiva e transitiva (perché?).

(3.17) Nota. Se $R$ è una relazione di preordine parziale su $X$, allora definiamo una topologia $\mathcal{A}$ su $X$ nel modo seguente: sia, per ogni $x\in X$, $U_ x$ l’insieme definito da

\[ U_ x = \{ y \in X : xRy \} . \]

Se $x_1$ e $x_2$ sono due elementi di $X$ e $z\in U_{x_1} \cap U_{x_2}$, allora $x_1Rz$ e $x_2Rz$, e quindi

\[ U_ z = \{ y \in X : zRy \} \subset U_{x_1} \cap U_{x_2} = \{ y \in X : x_1Ry \wedge x_2 Ry \} , \]

dato che $zRy \wedge x_1Rz \implies x_1Ry$, $zRy \wedge x_2Rz \implies x_2Ry$. Inoltre $x\in U_ x$ (perché riflessiva), e dunque gli $U_ x$ costituiscono una base per una topologia di $X$, la topologia associata alla relazione $R$.

Utilizzando (3.16) e (3.17), si può mostrare che le topologie su $X$ sono in corrispondenza biunivoca con le relazioni riflessive e transitive su $X$. Problema: come elencare tutte le relazioni riflessive e transitive su un insieme finito $X$? È possibile scrivere un algoritmo che le elenca? Vediamo per $X=\{ 1,2\} $ si hanno le seguenti topologie.

  1. Matrice (relazione binaria): $\displaystyle \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $

    \[ \mathcal{A} = \left\{ \left\{ \right\} , \left\{ 1\right\} , \left\{ 2\right\} , \left\{ 1, 2\right\} \right\} \subset 2^ X \]
  2. Matrice (relazione binaria): $\displaystyle \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} $

    \[ \mathcal{A} = \left\{ \left\{ \right\} , \left\{ 1\right\} , \left\{ 1, 2\right\} \right\} \subset 2^ X \]
  3. Matrice (relazione binaria): $\displaystyle \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} $

    \[ \mathcal{A} = \left\{ \left\{ \right\} , \left\{ 2\right\} , \left\{ 1, 2\right\} \right\} \subset 2^ X \]
  4. Matrice (relazione binaria): $\displaystyle \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} $

    \[ \mathcal{A} = \left\{ \left\{ \right\} , \left\{ 1, 2\right\} \right\} \subset 2^ X \]