Relazioni d’ordine

Home » Relazioni d’ordine

Autori e revisori

Leggi...

Introduzione

Leggi...

Una relazione d’ordine su un insieme $A$ è, intuitivamente, un modo per confrontare i suoi elementi, stabilendone il maggiore e il minore. Ciò viene formalizzato considerando un sottoinsieme del prodotto cartesiano $A\times A$ soggetto a determinate proprietà, che ci aspettiamo qualsiasi ordinamento debba soddisfare.

In questo articolo presentiamo la definizione formale di relazione d’ordine, alcuni esempi, e vediamo come da tali concetti astratti ne seguano molti tra quelli noti.

Relazioni

Il concetto di relazione è tra i più importanti in matematica e comprende al suo interno il concetto stesso di funzione. Intuitivamente, una relazione tra un insieme $A$ e un insieme $B$ è una regola che lega gli elementi di $A$ agli elementi di $B$ secondo un certo principio.

Definizione 1. Una relazione $\mathcal{R}$ tra $A$ e $B$ è un sottoinsieme del prodotto cartesiano

$\mathcal{R} \subseteq A\times B.$

Una relazione tra $A$ e $A$ viene detta relazione binaria su $A$ .

$\quad$

Per dare un senso pratico alla definizione osserviamo che possiamo interpretare un elemento della relazione $(x,y) \in \mathcal{R}$ come l’affermazione “ $x$ è in relazione con $y$ ”, in simboli $x\mathcal{R}y$ .

Se la regola associa ad ogni elemento di $A$ qualche elemento di $B$ e se tale elemento è univocamente determinato, la relazione prende il nome di funzione tra $A$ e $B$ .

Definizione 2. Dati due insiemi $A$ e $B$ , una funzione $f: A \to B$ è una relazione $f \subset A\times B$ tale che $\forall x \in A \; \exists ! y \in B$ tale che $(x,y)\in f$ (in simboli $x f y$ , oppure più comunemente $y=f(x)$ ).

$\quad$

Esempio 3. Forniamo alcuni esempi di relazione binaria su un insieme $A$ .

$\quad$

$\mathcal{R}=\emptyset$ . In questo caso non c’è alcuna relazione e gli elementi di $A$ sono “sconnessi”;

$\mathcal{R}=A\times A$ . Anche questo è un caso degenere in cui la relazione non esprime nulla di significativo, in quanto tutto è nella relazione.

$\mathcal{R}=\Delta$ , dove $\Delta=\{ (x,x): x\in A \}$ è la diagonale di $A$ . Questa è la relazione di uguaglianza tra elementi, in simboli $x\mathcal{R}y \Leftrightarrow x=y$ . Osserviamo che quest’ultima relazione è una funzione $id_A:A \to A$ , detta identità di $A$ .

Relazioni d’ordine

Una particolare famiglia di relazioni su un insieme $A$ sono le cosiddette relazioni d’ordine su $A$ .

Definizione 4. Dato un insieme non vuoto $A$ una relazione binaria $\mathcal{R}$ è una relazione d’ordine (o relazione d’ordine parziale) se soddisfa le seguenti proprietà:

$\quad$

Proprietà riflessiva: $a\mathcal{R}a\qquad\forall a\in A$ ;

Proprietà antisimmetrica: Se $a\mathcal{R}b\text{ e }b\mathcal{R}a\Rightarrow a=b \qquad\forall a, b\in A$ ;

Proprietà transitiva: Se $a\mathcal{R}b\text{ e }b\mathcal{R}c\Rightarrow a\mathcal{R}c \qquad\forall a, b, c\in A$ .

Scriviamo $(A,\mathcal{R})$ per indicare l’insieme $A$ dotato della relazione d’ordine $\mathcal{R}$ .

Una relazione d’ordine $\mathcal{R}$ definita su un insieme non vuoto $A$ è detta d’ordine totale se $\forall \,(a,b)\in A\times A$ risulta che $a\mathcal{R}b$ oppure $b\mathcal{R}a$ . In questo caso l’insieme $A$ si dice totalmente ordinato da $\mathcal{R}$ .

$\quad$

L’aggettivo parziale nella definizione di relazione d’ordine sta a significare che non necessariamente tutte le coppie $(a,b)$ di elementi dell’insieme $A$ sono tra loro confrontabili, come ci mostra il seguente esempio.

Esempio 5. Sia $X$ un insieme non vuoto. Nell’insieme $\mathcal{P}(X)$ (l’insieme delle parti di $X$ , i cui elementi sono i sottoinsiemi di $X$ ) è possibile definire la relazione d’ordine

$\begin{equation*} A\mathcal{R} B\Leftrightarrow A\subseteq B, \end{equation*}$

Si controlla facilmente che è una relazione d’ordine parziale, ma non totale; consideriamo ad esempio l’insieme $X=\{a, b\}$ allora $\mathcal{P}(X)=\{\emptyset, \{a\},\{b\}, A\}$ . Ovviamente i due singleton non sono confrontabili ovvero

$\{a\}\cancel{\mathcal{R}} \{b\}\text{ e }\{b\}\cancel{\mathcal{R}} \{a\}.$

Solitamente le relazioni d’ordine vengono indicate con i simboli $\leq$ o $\geq$ e così faremo anche noi nel prosieguo.

Definizione 6. Sia $(A,\leq)$ un insieme parzialmente ordinato.

$\quad$

Un elemento $M\in A$ è detto massimo
$\begin{equation*} M=\max A\quad \Leftrightarrow \quad a\leq M\quad\forall a\in A. \end{equation*}$

Un elemento $m\in A$ è detto minimo
$\begin{equation*} m=\min A\quad \Leftrightarrow \quad m\leq a\quad\forall a\in A. \end{equation*}$

Proposizione 7. Se esistono il massimo e il minimo di un insieme parzialmente ordinato $(A,\leq )$ , allora essi sono unici.

$\quad$

Dimostrazione. Segue dalla proprietà di antisimmetria della relazione d’ordine. Supponiamo che esistano due massimi $M_1$ e $M_2$ . Allora, siccome $M_1$ è un massimo, $M_2 \leq M_1$ , ma poiché anche $M_2$ è un massimo, $M_1\leq M_2$ , dunque $M_1=M_2$ .

Di seguito elenchiamo alcune definizioni elementari nel contesto generale degli insiemi parzialmente ordinati.

Definizione 8. Sia $A\subseteq X$ un sottoinsieme di un insieme parzialmente ordinato $(X,\leq)$ .

$\quad$

Un elemento $x\in X$ è un maggiorante di $A$ se
$\begin{equation*} a\leq x\qquad\forall a\in A. \end{equation*}$

Un elemento $x\in X$ è un minorante di $A$ se
$\begin{equation*} x\leq a\qquad\forall a\in A. \end{equation*}$

Indicheremo rispettivamente con $M(A)$ e $m(A)$ l’insieme dei maggioranti e dei minoranti di $A$ :

$M(A)=\{ x\in X: \forall a \in A \;\, a\leq x \} \quad m(A)=\{ x\in X: \forall a \in A \;\, x\leq a\}.$

Definizione 9. Sia $A$ un sottoinsieme di un insieme totalmente ordinato $X$ . Diremo che

$\quad$

$A$ è limitato superiormente se $M(A)\neq\emptyset$ , ovvero se $\exists \, M \in X$ tale che $a\leq M\quad \forall a\in A$ ;

$A$ è limitato inferiormente se $m(A)\neq\emptyset$ , ovvero se $\exists \, m \in X$ tale che $m\leq a \quad \forall a\in A$ .

Menu

Chiudi

Relazioni d’ordine

Autori e revisori

Leggi...

Introduzione

Leggi...

Relazioni

Relazioni d’ordine

Suggerimenti, refusi ed errori

Cosa dicono di noi