Relazione d'ordine

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Poset)

In matematica, più precisamente in teoria degli ordini, una relazione d'ordine su di un insieme è una relazione binaria tra elementi appartenenti all'insieme che gode delle seguenti proprietà:

Si definisce insieme parzialmente ordinato (oppure ordine) la coppia costituita da un insieme e da una relazione d'ordine su di esso.

Definizione[modifica | modifica wikitesto]

Dati due insiemi A e B, il loro prodotto cartesiano è l'insieme delle coppie ordinate definito nel modo seguente:[1]

A\times B :=\{(a,b) : a \in A \; \mathrm{e} \; b\in B\} \

Si definisce relazione binaria R su un insieme A un sottoinsieme di A \times A.[2] Due elementi x e y sono messi in relazione da R se:

(x,y) \in R \

ed in tal caso si scrive xRy.

Una relazione d'ordine \le è una relazione binaria tra elementi di un insieme A riflessiva, antisimmetrica e transitiva.[3]

Esplicitamente, tale relazione soddisfa le seguenti proprietà:

x \le x \quad \forall x \in A
x \le y e y \le x implica x=y \quad \forall x,y \in A
x \le y e y \le z implicano x \le z \quad \forall x,y,z \in A

Le relazioni d'ordine si indicano spesso con i simboli \leq, \subseteq, \sqsubseteq e \preccurlyeq.

La coppia (O,\leq) costituita da un insieme e da una relazione d'ordine su di esso si dice insieme parzialmente ordinato o semplicemente ordine, da non confondere con il termine più specifico insieme totalmente ordinato.

Da notare che in lingua inglese un insieme parzialmente ordinato è anche detto concisamente poset (Partially Ordered Set), e questo termine è usato gergalmente anche nella lingua italiana.

Alcuni autori definiscono anche la relazione d'ordine stretto una relazione  (O, <) che soddisfi le proprietà irriflessiva, antisimmetrica e transitiva (o, equivalentemente e più concisamente, le proprietà asimmetrica e transitiva), e quindi chiamano relazione d'ordine largo la relazione d'ordine  (O, \leq) definita sopra.

Primi esempi[modifica | modifica wikitesto]

Esempi ben noti di insiemi parzialmente ordinati sono:

  • gli insiemi numerici \mathbb N, \mathbb Z, \mathbb Q, \mathbb R muniti della relazione d'ordine totale standard a R b \Leftrightarrow a \leq b,
  • l'insieme \mathbb N \backslash \{0\} munito della relazione di divisibilità a R b \Leftrightarrow a | b (cioè a è un divisore di b)
  • Una qualunque famiglia di insiemi munita della relazione di inclusione a R b \Leftrightarrow a \subseteq b (cioè a è sottoinsieme di b)

Ordinamenti ben fondati[modifica | modifica wikitesto]

Una relazione d'ordine su un insieme S si dice ben fondata o buon ordinamento se ogni sottoinsieme Y   \subseteq  S non vuoto è dotato di minimo.

Un tipico esempio di buon ordinamento è quello che stabilisce la relazione d'ordine standard sull'insieme \mathbb N dei numeri naturali. L'affermazione che i naturali sono un insieme ben ordinato, ovvero che ogni sottoinsieme X di \mathbb N ha un minimo viene talvolta chiamata Principio del buon ordinamento e si può dimostrare essere equivalente al Principio di induzione.

Il teorema del buon ordinamento[modifica | modifica wikitesto]

Il teorema del buon ordinamento (da non confondere con il principio del buon ordinamento) asserisce che su ogni insieme non vuoto può essere definita una relazione d'ordine ben fondata (o buon ordinamento). Tale enunciato è equivalente all'assioma della scelta (cioè assumendolo vero si può dimostrare l'assioma della scelta e viceversa).

Curiosità[modifica | modifica wikitesto]

Se l'insieme S è un insieme numerico con cardinalità maggiore di uno (|S|>1) allora scegliendo un suo sottoinsieme S_2 \subseteq S con cardinalità pari a 2 (|S_2|=2), si può definire il minimo tra i due soli elementi, a e b con la seguente relazione:

\min\{a,b\}=\mathbf{1}_{\mathbb{R}^-}(a-b) \cdot (a-b)+b

Il massimo tra i due elementi si trova invece con la seguente espressione

\max\{a,b\}=\mathbf{1}_{\mathbb{R}^+}(a-b) \cdot (a-b)+b

Dove con \mathbf{1} si è indicata la funzione indicatrice.

Note[modifica | modifica wikitesto]

  1. ^ Reed, Simon, Pag. 1
  2. ^ Reed, Simon, Pag. 2
  3. ^ Reed, Simon, Pag. 3

Bibliografia[modifica | modifica wikitesto]

  • Michael Reed, Barry Simon, Methods of Modern Mathematical Physics, Vol. 1: Functional Analysis, 2ª ed., San Diego, California, Academic press inc., 1980, ISBN 0-12-585050-6.

Voci correlate[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica