Relazioni tra insiemi

Una relazione mette in corrispondenza coppie di elementi. A seconda delle proprietà di cui gode — riflessiva, simmetrica, antisimmetrica, transitiva — si ottengono le due grandi famiglie: le relazioni di equivalenza, che partizionano un insieme in classi, e le relazioni d’ordine, totali o parziali, che si visualizzano con il diagramma di Hasse.

• Che cos’è una relazione
• Proprietà delle relazioni
• Relazioni di equivalenza e classi
• Relazioni d’ordine, totale e parziale
• Il diagramma di Hasse

A relation puts pairs of elements into correspondence. Depending on the properties it enjoys — reflexive, symmetric, antisymmetric, transitive — one obtains the two great families: equivalence relations, which partition a set into classes, and order relations, total or partial, which are visualised with the Hasse diagram.

• What a relation is
• Properties of relations
• Equivalence relations and classes
• Order relations, total and partial
• The Hasse diagram

Una relazione tra due insiemi mette in corrispondenza coppie di elementi: è il primo passo verso il concetto di funzione.

Definizione — Relazione

Una relazione è un insieme di “frecce” che collegano elementi di un insieme (insieme di partenza) a elementi di un altro insieme (insieme di arrivo).

Esempio — La relazione "ha avuto un cucciolo con"

Sia $A=\{\text{George, Rufus, Albert, Jack}\}$ e $B=\{\text{Susie, Prilly, Jay, Jill, Nerina}\}$. La relazione $f\colon A\to B$ definita da ”$a$ ha avuto un cucciolo con $b$” si rappresenta con delle frecce:

Ogni freccia collega un elemento di $A$ a un elemento di $B$.

La stessa relazione si può scrivere in modi equivalenti:

• Coppie ordinate: $\{(\text{George, Susie}),\,(\text{George, Prilly}),\,(\text{Rufus, Jay}),\,(\text{Jack, Jay}),\,(\text{Jack, Jill})\}$.
• Rappresentazione cartesiana: ogni freccia corrisponde a un punto del piano, con $A$ sull’asse orizzontale e $B$ sull’asse verticale.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Coppia ordinata · Piano cartesiano · Relazione

A relation between two sets puts pairs of elements into correspondence: it is the first step towards the concept of a function.

Definition — Relation

A relation is a set of “arrows” that connect elements of one set (the domain set) to elements of another set (the codomain set).

Example — The relation "had a puppy with"

Let $A=\{\text{George, Rufus, Albert, Jack}\}$ and $B=\{\text{Susie, Prilly, Jay, Jill, Nerina}\}$. The relation $f\colon A\to B$ defined by ”$a$ had a puppy with $b$” is represented by arrows:

Each arrow connects an element of $A$ to an element of $B$.

The same relation can be written in equivalent ways:

• Ordered pairs: $\{(\text{George, Susie}),\,(\text{George, Prilly}),\,(\text{Rufus, Jay}),\,(\text{Jack, Jay}),\,(\text{Jack, Jill})\}$.
• Cartesian representation: each arrow corresponds to a point of the plane, with $A$ on the horizontal axis and $B$ on the vertical axis.

Links

Topics: Set theory
Concepts: Ordered pair · Cartesian plane · Relation

Quando una relazione lega un insieme a sé stesso ($R\colon A\to A$) può godere di alcune proprietà notevoli, che la classificano in famiglie importanti.

Proprietà — Proprietà di una relazione

Una relazione $R$ su un insieme $A$ può essere:

• Riflessiva: per ogni $a\in A$, $a\mathbin{R} a$ (ogni elemento è in relazione con sé stesso).
• Simmetrica: se $a\mathbin{R} b$ allora $b\mathbin{R} a$ (a ogni freccia corrisponde la freccia opposta).
• Antisimmetrica: se $a\mathbin{R} b$ e $b\mathbin{R} a$ allora $a=b$ (frecce di andata e ritorno solo sul cappio).
• Transitiva: se $a\mathbin{R} b$ e $b\mathbin{R} c$ allora $a\mathbin{R} c$.

Una relazione riflessiva, simmetrica e transitiva è una relazione di equivalenza; una riflessiva, antisimmetrica e transitiva è una relazione d’ordine.

Le due combinazioni danno origine alle due grandi famiglie di relazioni che studieremo: le equivalenze, che raggruppano gli elementi simili, e gli ordini, che li mettono in fila.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Relazione · Relazione d ordine · Relazione di equivalenza

When a relation links a set to itself ($R\colon A\to A$) it may enjoy some notable properties, which classify it into important families.

Property — Properties of a relation

A relation $R$ on a set $A$ can be:

• Reflexive: for every $a\in A$, $a\mathbin{R} a$ (every element is related to itself).
• Symmetric: if $a\mathbin{R} b$ then $b\mathbin{R} a$ (every arrow has a corresponding opposite arrow).
• Antisymmetric: if $a\mathbin{R} b$ and $b\mathbin{R} a$ then $a=b$ (arrows there and back only on the loop).
• Transitive: if $a\mathbin{R} b$ and $b\mathbin{R} c$ then $a\mathbin{R} c$.

A reflexive, symmetric and transitive relation is an equivalence relation; a reflexive, antisymmetric and transitive one is an order relation.

The two combinations give rise to the two great families of relations we shall study: equivalences, which group together similar elements, and orders, which line them up.

Links

Topics: Set theory
Concepts: Relation · Order relation · Equivalence relation

Le relazioni di equivalenza “raggruppano” gli elementi che condividono una proprietà. Ogni elemento $a$ identifica la sua classe di equivalenza $[a]=\{x\in A : x\mathbin{R} a\}.$ L’insieme delle classi forma una partizione di $A$: ogni elemento appartiene a esattamente una classe.

Esempio — Resto della divisione per $3$

Su $\mathbb{Z}$ poniamo $a\mathbin{R} b$ se $a-b$ è multiplo di $3$. È una relazione di equivalenza (si verificano le tre proprietà). Le classi sono tre: $[0]=\{\ldots,-3,0,3,6,\ldots\},\quad [1]=\{\ldots,-2,1,4,7,\ldots\},\quad [2]=\{\ldots,-1,2,5,8,\ldots\}.$ Ogni intero appartiene a una sola classe, individuata dal resto ($0$, $1$ o $2$) nella divisione per $3$. È il primo passo dell’aritmetica modulare.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Classe di equivalenza · Partizione · Relazione di equivalenza

Equivalence relations “group together” the elements that share a property. Each element $a$ identifies its equivalence class $[a]=\{x\in A : x\mathbin{R} a\}.$ The set of classes forms a partition of $A$: each element belongs to exactly one class.

Example — Remainder of division by $3$

On $\mathbb{Z}$ we set $a\mathbin{R} b$ if $a-b$ is a multiple of $3$. It is an equivalence relation (the three properties can be checked). There are three classes: $[0]=\{\ldots,-3,0,3,6,\ldots\},\quad [1]=\{\ldots,-2,1,4,7,\ldots\},\quad [2]=\{\ldots,-1,2,5,8,\ldots\}.$ Every integer belongs to exactly one class, determined by the remainder ($0$, $1$ or $2$) upon division by $3$. This is the first step of modular arithmetic.

Links

Topics: Set theory
Concepts: Equivalence class · Partition · Equivalence relation

L’altra grande famiglia di relazioni utili è quella dell’ordine: ci permette di dire ”$a$ viene prima di $b$”. La proprietà chiave è l’antisimmetria: se $a\le b$ e $b\le a$ allora $a=b$ (al posto della simmetria delle equivalenze).

Definizione — Ordine totale e parziale

Una relazione $R$ su $A$ è una relazione d’ordine (parziale) se è riflessiva, antisimmetrica e transitiva. Si dice d’ordine totale se in aggiunta, per ogni $a,b\in A$, vale $a\mathbin{R} b$ oppure $b\mathbin{R} a$ (ogni coppia è confrontabile). Altrimenti l’ordine si dice parziale.

Esempio — Ordine totale su $\mathbb{R}$

La relazione $\le$ su $\mathbb{R}$ è di ordine totale: dati due reali, sai sempre qual è il più piccolo. La retta è un’immagine fisica dell’ordine totale, in cui ogni punto è confrontabile con ogni altro.

Esempio — Ordine parziale: "divide" su $\mathbb{N}$

Su $\mathbb{N}=\{1,2,3,\ldots\}$ poniamo $a\preceq b$ se $a$ divide $b$ (cioè $b=ka$ per qualche $k\in\mathbb{N}$).

• Riflessiva: $a$ divide $a$.
• Antisimmetrica: se $a\mid b$ e $b\mid a$ (con $a,b>0$) allora $a=b$.
• Transitiva: se $a\mid b$ e $b\mid c$ allora $a\mid c$.

Però $2$ non divide $3$ e $3$ non divide $2$: le coppie di “primi diversi” non sono confrontabili. È un ordine parziale.

Esempio — Ordine parziale: inclusione $\subseteq$ tra insiemi

La relazione "$A\subseteq B$" sull’insieme delle parti $\mathcal{P}(X)$ è un ordine parziale. Per esempio $\{1\}\subseteq\{1,2\}$, ma $\{1\}$ e $\{2\}$ non sono confrontabili.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Inclusione · Ordine parziale · Ordine totale · Relazione d ordine

The other great family of useful relations is that of order: it lets us say ”$a$ comes before $b$”. The key property is antisymmetry: if $a\le b$ and $b\le a$ then $a=b$ (in place of the symmetry of equivalences).

Definition — Total and partial order

A relation $R$ on $A$ is an (partial) order relation if it is reflexive, antisymmetric and transitive. It is called a total order if, in addition, for every $a,b\in A$, either $a\mathbin{R} b$ or $b\mathbin{R} a$ holds (every pair is comparable). Otherwise the order is called partial.

Example — Total order on $\mathbb{R}$

The relation $\le$ on $\mathbb{R}$ is a total order: given two reals, you always know which is the smaller. The line is a physical picture of the total order, in which every point is comparable with every other.

Example — Partial order: "divides" on $\mathbb{N}$

On $\mathbb{N}=\{1,2,3,\ldots\}$ we set $a\preceq b$ if $a$ divides $b$ (that is, $b=ka$ for some $k\in\mathbb{N}$).

• Reflexive: $a$ divides $a$.
• Antisymmetric: if $a\mid b$ and $b\mid a$ (with $a,b>0$) then $a=b$.
• Transitive: if $a\mid b$ and $b\mid c$ then $a\mid c$.

However $2$ does not divide $3$ and $3$ does not divide $2$: pairs of “distinct primes” are not comparable. It is a partial order.

Example — Partial order: inclusion $\subseteq$ between sets

The relation "$A\subseteq B$" on the power set $\mathcal{P}(X)$ is a partial order. For instance $\{1\}\subseteq\{1,2\}$, but $\{1\}$ and $\{2\}$ are not comparable.

Links

Topics: Set theory
Concepts: Inclusion · Partial order · Total order · Order relation

Osservazione — Diagramma di Hasse

Per visualizzare un ordine parziale finito si disegna il diagramma di Hasse: ogni elemento è un punto e si tracciano archi tra $a$ e $b$ solo se $a\prec b$ e non esiste alcun $c$ tale che $a\prec c\prec b$ (relazioni di copertura). Sotto, il diagramma dei divisori di $12$ con la relazione “divide”:

I divisori di $12$ ordinati per divisibilità: $1$ in basso, $12$ in alto.

L’$1$ sta in basso (divide tutti), il $12$ in alto (multiplo di tutti). I rami che si separano — per esempio $2$ e $3$ sopra $1$ — dichiarano l’incomparabilità: la relazione è parziale.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Diagramma di hasse · Ordine parziale
Persone: Hasse

Observation — Hasse diagram

To visualise a finite partial order one draws the Hasse diagram: each element is a point and edges are drawn between $a$ and $b$ only if $a\prec b$ and there exists no $c$ such that $a\prec c\prec b$ (covering relations). Below, the diagram of the divisors of $12$ with the relation “divides”:

The divisors of $12$ ordered by divisibility: $1$ at the bottom, $12$ at the top.

The $1$ sits at the bottom (it divides everything), the $12$ at the top (a multiple of everything). The branches that separate — for example $2$ and $3$ above $1$ — declare incomparability: the relation is partial.

Links

Topics: Set theory
Concepts: Hasse diagram · Partial order
People: Hasse