EDB — 06G

Esercizi

1. [06G] Sia $R\subseteq X\times X$ una relazione; presi $x,y\in X$ scriveremo $xRy$ invece di $(x,y)\in R$. Supponiamo che $R$ sia riflessiva cioè $xRx$ per ogni $x$, e che sia transitiva cioè per ogni $x,y,z\in X$ si abbia $xRy\wedge yRz\Rightarrow xRz$.

   $R$ non è necessariamente una relazione d’ordine, perché non abbiamo ipotizzato che sia antisimmetrica: possiamo però “costruire” una relazione d’ordine “identificando fra loro” gli elementi di $X$ su cui $R$ non è antisimmetrica. Vediamo la costruzione nel dettaglio.

   1. Sia ora $\sim$ la relazione data da

      $$x\sim y⟺xRy\wedge yRx$$

      si mostri che è una relazione di equivalenza.

   2. Si consideri il quoziente $Y=X/\sim$, vogliamo mostrare come $R$ passa al quoziente e produce una relazione $T$ su $Y$. Si mostri che se $x,y,\tilde{x},\tilde{y}\in X$ e si ha $x\sim \tilde{x},y\sim \tilde{y}$ allora $xRy⟺\tilde{x}R\tilde{y}$. Definiamo dunque $T$ come l’insieme di tutte le coppie di classi di equivalenza i cui prodotti sono contenuti in $R$ cioé $T=\{(z,w)\in Y^2:z\times w\subseteq R\}$; questo si può scrivere anche come

      $$zTw⟺(\forall x\in z,\forall y\in w,xRy)$$

      abbreviamo questa definizione come $[x]T[y]⟺xRy$ (che è una buona definizione perché il membro destro non dipende dalla scelta dei rappresentanti nelle classi).

   3. Si mostri infine che $T$ è una relazione d’ordine su $Y$.

   Soluzione 1

   [06H]↺↻