Relazioni ordinate. Relazione d'ordine

La parola "ordine" è spesso usata in una varietà di questioni. L'ufficiale dà il comando: "Secondo l'ordine dei numeri, calcola", le operazioni aritmetiche vengono eseguite in un certo ordine, gli atleti sono classificati in base all'altezza, c'è un ordine per eseguire le operazioni quando si fa una parte e l'ordine delle parole in una frase.

Cosa è comune in tutti i casi quando si parla di ordine? Il fatto è che la parola "ordine" ha il seguente significato: significa quale elemento di questo o quell'insieme segue quale (o quale elemento precede quale).

Atteggiamento " X segue A" transitivo: se " X segue A" E " A segue z", Quello " X segue z" Inoltre, questa relazione deve essere antisimmetrica: per due diversi X E A, Se X segue A, Quello A non segue X.

Definizione. Atteggiamento R su un set X chiamato rapporto di ordine rigoroso, se è transitivo e antisimmetrico.

Scopriamo le caratteristiche del grafico e del grafico delle relazioni di ordine rigoroso.

Diamo un'occhiata a un esempio. Sul set X= (5, 7, 10, 15, 12) dato rapporto R: « X < A" Definiamo questa relazione elencando le coppie
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Costruiamo il suo grafico. Vediamo che il grafico di questa relazione non ha cicli. Non ci sono doppie frecce sul grafico. Se da X la freccia va a A, e da A- V z, quindi da X la freccia va a z(Fig. 8).

Il grafico costruito consente di disporre gli elementi dell'insieme X in questo ordine:

{5, 7, 10, 12, 15}.

Nella Fig. 6 (§ 6 di questo capitolo), le colonne VII, VIII sono grafici di rapporti di ordine rigoroso.

Relazione non stretta

L’opposto della relazione “meno di” nell’insieme dei numeri reali è la relazione “non meno”. Non è più una relazione di ordine rigoroso. Il punto è quando X = A, le relazioni sono soddisfatte X ³ A E A ³ X, cioè. l’atteggiamento “niente meno” è riflessivo.

Definizione. Atteggiamento R su un set X chiamato relazione non stretta, se è riflessiva, antisimmetrica e transitiva.

Tali relazioni sono unioni di una relazione di ordine stretto con una relazione di identità.

Consideriamo la relazione “non più” (£) per l'insieme

X= (5, 7, 10, 15, 12). Costruiamo il suo grafico (Fig. 9).

Un grafo con relazioni di ordine non rigoroso, a differenza di un grafo con relazioni di ordine rigoroso, ha cicli su ciascun vertice.

Nella fig. 6 (§ 6 del presente capitolo) le colonne V, VI sono grafici di rapporti di ordine non rigoroso.

Set ordinati

Un insieme può risultare ordinato (si dice anche completamente ordinato) da qualche relazione d'ordine, mentre un altro insieme può essere non ordinato o parzialmente ordinato da tale relazione.

Definizione. Un mucchio di X chiamato ordinato qualche relazione d'ordine R, se per due elementi qualsiasi x, y da X:

(X, A) Î R O ( y, x) Î R.

Se Rè una relazione di ordine rigoroso, quindi l'insieme X ordinato da questa relazione fornita: se X, A due elementi qualsiasi disuguali dell'insieme X, Quello ( X, A) Î R O ( y, x) Î R o due elementi qualsiasi x, y imposta X sono uguali.

Dal corso di matematica scolastica è noto che i numeri sono insiemi N , Z , Q , R ordinato dalla relazione “minore di” (<).

L'insieme dei sottoinsiemi di un certo insieme non è ordinato introducendo la relazione di inclusione (I), o inclusione rigorosa (S) nel senso sopra, perché ci sono sottoinsiemi, nessuno dei quali è incluso nell'altro. In questo caso diciamo che l'insieme dato è parzialmente ordinato dalla relazione Í (o Ì).

Considera l'insieme X= (1, 2, 3, 4, 5, 6) e contiene due relazioni “minore di” e “diviso per”. È facile verificare che entrambe queste relazioni sono relazioni d'ordine. Il grafico della relazione “minore di” può essere rappresentato come un raggio.

Il grafico della relazione “diviso per” può essere rappresentato solo su un piano.

Inoltre, il grafico della seconda relazione ha vertici che non sono collegati da una freccia. Ad esempio, non c'è alcuna freccia che collega i numeri 4 e 5 (Fig. 10).

La prima relazione" X < A"si chiama lineare. In generale, se la relazione è d'ordine R(severo e non severo) sul set X ha la proprietà: per qualsiasi X, AÎ X O xRy, O yRx, allora si chiama relazione di ordine lineare e insieme X– un insieme ordinato linearmente.

Se l'insieme X ovviamente, e consiste in N elementi, quindi ordinamento lineare X si riduce a numerare i suoi elementi con i numeri 1,2,3, ..., N.

Gli insiemi ordinati linearmente hanno una serie di proprietà:

1°. Permettere a, b, c– elementi dell'insieme X, ordinato dalla relazione R. Se lo si sa aRв E in RC, quindi dicono che l'elemento V si trova tra gli elementi UN E Con.

2°. Un mucchio di X, ordinato linearmente dalla relazione R, si dice discreto se tra due qualsiasi dei suoi elementi giace solo un insieme finito di elementi di questo insieme.

3°. Un insieme ordinato linearmente si dice denso se per due elementi distinti di questo insieme esiste un elemento dell'insieme compreso tra di loro.

Relazione di equivalenza. Il legame tra la relazione di equivalenza e la partizione di un insieme in classi

Definizione. Atteggiamento R su un set X si dice relazione di equivalenza se è riflessiva, simmetrica e transitiva.

Esempio. Considera la relazione " X compagna di classe A"su molti studenti della Facoltà di Scienze della Formazione. Ha le seguenti proprietà:

1) riflessività, perché ogni studente è il suo compagno di classe;

2) simmetria, perché se studente X A, poi lo studente Aè un compagno di classe dello studente X;

3) transitività, perché se studente X- compagna di classe A e lo studente A- compagna di classe z, poi lo studente X sarà il compagno di classe dello studente z.

Pertanto, questa relazione ha le proprietà di riflessività, simmetria e transitività, e quindi è una relazione di equivalenza. Allo stesso tempo, molti studenti della Facoltà di Scienze della Formazione possono essere suddivisi in sottoinsiemi costituiti da studenti che studiano nello stesso corso. Otteniamo 5 sottoinsiemi.

Le relazioni di equivalenza sono anche, ad esempio, la relazione di parallelismo delle rette, la relazione di uguaglianza delle figure. Ciascuna di queste relazioni è associata alla partizione dell'insieme in classi.

Teorema. Se sul set X data una relazione di equivalenza, divide questo insieme in sottoinsiemi disgiunti a coppie (classi di equivalenza).

È vera anche l'affermazione contraria: se qualsiasi relazione è definita sull'insieme X, genera una partizione di questo insieme in classi, allora è una relazione di equivalenza.

Esempio. Sul set X= (1; 2; 3; 4; 5; 6; 7; 8) viene specificata la relazione “hanno lo stesso resto quando diviso per 3”. È una relazione di equivalenza?

Costruiamo un grafico di questa relazione: (indipendentemente)

Questa relazione ha le proprietà di riflessività, simmetria e transitività, quindi è una relazione di equivalenza e divide l'insieme X alle classi di equivalenza. In ogni classe di equivalenza ci saranno numeri che, divisi per 3, danno lo stesso resto: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Si ritiene che la classe di equivalenza sia determinata da uno qualsiasi dei suoi rappresentanti, ad es. un elemento arbitrario di questa classe. Pertanto, è possibile specificare una classe di frazioni uguali specificando qualsiasi frazione appartenente a questa classe.

Nel corso iniziale di matematica si incontrano anche relazioni di equivalenza, ad esempio “espressioni X E A hanno gli stessi valori numerici", "figura X uguale alla figura A».

Definizione. Atteggiamento R su un set X si chiama relazione d'ordine se è transitiva e asimmetrica o antisimmetrica.

Definizione. Atteggiamento R su un set X si dice relazione d'ordine stretto se è transitiva e asimmetrica.

Esempi relazioni di ordine rigoroso: "più" sull'insieme dei numeri naturali, "più alto" sull'insieme delle persone, ecc.

Definizione. Atteggiamento R su un set X si dice relazione d'ordine non stretta se è transitiva e antisimmetrica.

Esempi relazioni di ordine non rigoroso: “non più” sull'insieme dei numeri reali, “sii un divisore” sull'insieme dei numeri naturali, ecc.

Definizione. Un mucchio di X si dice ordinato se su di esso è specificata una relazione d'ordine.

Esempio. Sul set X= (1; 2; 3; 4; 5) sono date due relazioni: “ X £ A" E " X- divisore A».

Entrambe queste relazioni hanno le proprietà di riflessività, antisimmetria e transitività (costruisci grafici e controlla tu stesso le proprietà), cioè sono rapporti di ordine non rigoroso. Ma la prima relazione ha la proprietà della connessione, mentre la seconda no.

Definizione. Relazione d'ordine R su un set X si dice relazione d'ordine lineare se possiede la proprietà di connessione.

Nella scuola elementare si studiano molte relazioni d'ordine. Già in prima elementare esistono le relazioni “meno”, “più” sull’insieme dei numeri naturali, “più corto”, “più lungo” sull’insieme dei segmenti, ecc.

Domande di controllo

1. Definire una relazione binaria su un insieme X.

2. Come scrivere una dichiarazione che gli elementi X E A sono in una relazione R?

3. Elencare i modi per definire le relazioni.

4. Formulare le proprietà che le relazioni possono avere. Come si riflettono queste proprietà nel grafico?

5. Quali proprietà deve avere una relazione affinché sia ​​una relazione di equivalenza?

6. In che modo la relazione di equivalenza è correlata alla partizione di un insieme in classi?

7. Quali proprietà deve avere una relazione affinché sia ​​una relazione d'ordine?

X (\displaystyle X) chiamato rapporto di ordine parziale non stretto (relazione d'ordine, relazione riflessiva), se ci sono

Un mucchio di X (\displaystyle X), su cui è introdotta la relazione di ordine parziale, viene chiamata parzialmente ordinato. Una relazione di ordine parziale non stretta è spesso indicata con ≼ (\displaystyle \preccurlyeq ).

Opzioni

Relazione d'ordine parziale R (\displaystyle R) chiamato ordine lineare, se la condizione è soddisfatta

∀ X ∀ y (x R y ∨ y R x) (\displaystyle \forall x\forall y(xRy\lor yRx)).

Un mucchio di X (\displaystyle X), su cui viene introdotta una relazione di ordine lineare, viene chiamato ordinati linearmente, O catena.

Atteggiamento R (\displaystyle R), che soddisfa solo le condizioni di riflessività e transitività viene chiamato pre-ordine o quasi-ordine.

Ordine rigoroso

Se la condizione di riflessività è sostituita dalla condizione di antiriflessività:

∀ x ¬ (x R x) (\displaystyle \forall x\neg (xRx)),

quindi otteniamo la definizione rigoroso, O ordinanza parziale antiriflessiva(solitamente indicato dal simbolo ≺ (\displaystyle \prec )).

Commento. La simultanea antiriflessività e transitività di una relazione comporta l'antisimmetria. Quindi la relazione è rapporto di ordine rigoroso se e solo se è antiriflessivo e transitivo.

In generale, se R (\displaystyle R)è quindi una relazione transitiva e antisimmetrica

R ≼ = R ∪ ( (x , x) | x ∈ X ) (\displaystyle R_(\preccurlyeq)=R\cup \((x,x)|x\in X\))- ordine riflessivo R ≺ = R ∖ ( (x , x) | x ∈ X ) (\displaystyle R_(\prec )=R\setminus \((x,x)|x\in X\))- ordine rigoroso.

Esempi

• Nell'insieme dei numeri reali, le relazioni “maggiore di” e “minore di” sono relazioni di ordine rigoroso, mentre “maggiore o uguale a” e “minore o uguale a” non sono relazioni di ordine rigoroso.
• La relazione di divisibilità su un insieme di numeri interi è una relazione di ordine non stretto.

Dimensione di Dushnik-Miller

Storia

Segni < {\displaystyle <} E > (\displaystyle >) inventato

Sia R una relazione binaria sull'insieme A.

DEFINIZIONE. Una relazione binaria R su un insieme A è detta relazione d'ordine su A o ordine su A se è transitiva e antisimmetrica.

DEFINIZIONE. Una relazione di ordine R su un insieme A si dice non stretta se è riflessiva su A, cioè per ciascuno di A.

Una relazione d'ordine R si dice stretta (su A) se è antiriflessiva su A, cioè per qualsiasi di A. Tuttavia, dall'antiriflessività della relazione transitiva R, segue che è antisimmetrica. Pertanto si può dare la seguente definizione equivalente.

DEFINIZIONE. Una relazione binaria R su un insieme A si dice ordine stretto su A se è transitiva e antiriflessiva su A.

Esempi. 1. Sia l'insieme di tutti i sottoinsiemi dell'insieme M. La relazione di inclusione su un insieme è una relazione di ordine non stretto.

2. Le relazioni sull'insieme dei numeri reali sono, rispettivamente, relazioni di ordine stretto e non stretto.

3. La relazione di divisibilità nell'insieme dei numeri naturali è una relazione di ordine non stretto.

DEFINIZIONE. Una relazione binaria R su un insieme A è detta relazione di preordine o preordine su A se è riflessiva e transitiva.

Esempi. 1. La relazione di divisibilità nell'insieme degli interi non è un ordine. Tuttavia, è riflessivo e transitivo, il che significa che è un preordine.

2. La relazione di implicazione logica è un preordine sull'insieme delle formule logiche proposizionali.

Ordine lineare. Un importante caso speciale di ordine è l'ordine lineare.

DEFINIZIONE. Una relazione d'ordine su un insieme è chiamata relazione d'ordine lineare o ordine lineare su se è connessa su , cioè per qualsiasi x, y da A

Una relazione d'ordine che non è lineare è solitamente chiamata relazione d'ordine parziale o ordine parziale.

Esempi. 1. La relazione “minore di” sull'insieme dei numeri reali è una relazione di ordine lineare.

2. La relazione d'ordine adottata nei dizionari di lingua russa è chiamata lessicografica. L'ordine lessicografico dell'insieme delle parole in lingua russa è un ordine lineare.

La parola “ordine” è spesso utilizzata in un’ampia varietà di questioni. L'ufficiale dà il comando: "Calcola in ordine numerico", le operazioni aritmetiche vengono eseguite in un certo ordine, gli atleti sono classificati in base all'altezza, tutti i principali giocatori di scacchi sono disposti in un certo ordine secondo i cosiddetti coefficienti Elo (professore americano che ha sviluppato i coefficienti del sistema, che consentono di tenere conto di tutti i successi e i fallimenti dei giocatori), dopo il campionato, tutte le squadre di calcio si trovano in un certo ordine, ecc. Esiste un ordine di operazioni durante la produzione di una parte, il ordine delle parole in una frase (cerca di capire cosa significa la frase “sul vecchio” non ho piantato l’asino!”

Disponendo uno dopo l'altro gli elementi di un certo insieme, li ordiniamo o stabiliamo una relazione tra loro al fine. L'esempio più semplice è l'ordine naturale dei numeri naturali. La sua naturalezza sta nel fatto che per ogni due numeri naturali sappiamo quale segue l'altro o quale è maggiore dell'altro, quindi possiamo disporre i numeri naturali in una sequenza tale che il numero più grande si trovi, ad esempio, in a destra di quello più piccolo: 1, 2, 3, ... . Naturalmente la sequenza degli elementi può essere scritta in qualsiasi direzione, non solo da sinistra a destra. Il concetto stesso di numeri naturali contiene già l’idea di ordine. Stabilendo una disposizione relativa degli elementi di qualsiasi insieme, definiamo in tal modo su di esso una relazione di ordine binario, che in ciascun caso specifico può avere il proprio nome, ad esempio "essere inferiore", "essere più vecchio", "essere più vecchio". essere contenuto in ", "follow", ecc. È anche possibile variare le designazioni simboliche dell'ordine, ad esempio Í, ecc.

La principale caratteristica distintiva di una relazione d'ordine è che possiede la proprietà di transitività. Quindi, se abbiamo a che fare con una sequenza di alcuni oggetti x1, x2, ..., xn,..., ordinato, ad esempio, per relazione, quindi da ciò che viene eseguito x1x2... x n..., dovrebbe seguirlo per qualsiasi coppia x io, x j anche gli elementi di questa sequenza sono soddisfatti x iox j:

Per una coppia di elementi x ioJ nel grafico delle relazioni disegniamo una freccia dal vertice x io verso l'alto x j, cioè dall'elemento più piccolo a quello più grande.

Il grafico delle relazioni d'ordine può essere semplificato utilizzando il cosiddetto metodo Diagrammi di Hasse. Il diagramma di Hasse è costruito come segue. Gli elementi più piccoli vengono posizionati più in basso e quelli più grandi vengono posizionati più in alto. Poiché tale regola da sola non è sufficiente per la rappresentazione, vengono tracciate delle linee che indicano quale dei due elementi è più grande e quale è più piccolo dell'altro. In questo caso è sufficiente tracciare solo linee per gli elementi immediatamente successivi. Esempi di diagrammi di Hasse sono mostrati nella figura:

Non è necessario includere le frecce in un diagramma di Hasse. Il diagramma di Hasse può essere ruotato su un piano, ma non arbitrariamente. Quando si gira, è necessario mantenere la posizione relativa (sopra - sotto) dei vertici del diagramma:

Atteggiamento R in abbondanza X chiamato atteggiamento di ordine rigoroso, se è transitivo e asimmetrico.

Viene chiamato un insieme in cui è definita una relazione d'ordine rigorosa ordinato. Ad esempio, l'insieme dei numeri naturali è ordinato secondo la relazione “minore di”. Ma questo stesso insieme è ordinato anche da un'altra relazione: "diviso in" e "altro".

Il grafico della relazione “minore di” nell’insieme dei numeri naturali può essere rappresentato come un raggio:

Atteggiamento R V X chiamata relazione ordine non rigoroso (parziale)., se è transitivo e antisimmetrico. Qualsiasi relazione di ordine non stretto è riflessiva.

L'epiteto “parziale” esprime il fatto che forse non tutti gli elementi di un insieme sono paragonabili sotto un dato aspetto.

Esempi tipici di relazioni di ordine parziale sono le relazioni “non maggiore di”, “non inferiore a” e “non maggiore di”. La particella “non” nei nomi delle relazioni serve a esprimere la loro riflessività. La relazione “non più di” coincide con la relazione “minore o uguale” e la relazione “non meno” è uguale a “maggiore o uguale”. A questo proposito viene anche chiamato ordine parziale non severo al fine. Spesso una relazione d'ordine parziale (non stretta) è denotata dal simbolo "".

Anche la relazione di inclusione Í tra sottoinsiemi di un certo insieme è un ordine parziale. Ovviamente, non tutti i due sottoinsiemi sono comparabili sotto questo aspetto. La figura seguente mostra l'ordine di inclusione parziale sull'insieme di tutti i sottoinsiemi dell'insieme (1,2,3). Le frecce sul grafico che dovrebbero puntare verso l'alto non vengono visualizzate.

Vengono chiamati gli insiemi su cui è dato l'ordine parziale parzialmente ordinato, o semplicemente ordinato imposta.

Elementi X E A viene chiamato insieme parzialmente ordinato confrontare con noi Se XA O AX. Altrimenti non sono paragonabili.

Viene chiamato un insieme ordinato in cui due elementi qualsiasi sono confrontabili ordinati linearmente e l'ordine è lineare. L'ordine lineare è anche detto ordine perfetto.

Ad esempio, l'insieme di tutti i numeri reali con ordine naturale, così come tutti i suoi sottoinsiemi, sono ordinati linearmente.

Si possono ordinare oggetti della natura più varia gerarchicamente. Ecco alcuni esempi.

Esempio 1: le parti di un libro sono disposte in modo tale che un libro contenga capitoli, i capitoli contengano sezioni e le sezioni contengano sottosezioni.

Esempio 2. Le cartelle nel file system del computer sono annidate l'una nell'altra, formando una struttura ramificata.

Esempio 3. La relazione tra genitori e figli può essere descritta come la cosiddetta albero genealogico, che mostra chi è il cui antenato (o discendente).

Andiamo sul set UN viene dato un ordine parziale. Elemento X chiamato massimo (minimo) elemento dell'insieme A, se dal fatto che XA(AX), segue l'uguaglianza X= tu. In altre parole, l'elemento Xè massimo (minimo) se per qualsiasi elemento A oppure non è vero XA(AX), o viene eseguito X=tu. Pertanto, l'elemento massimo (minimo) è maggiore (minore) di tutti gli elementi distinti da esso con cui è in relazione.

Elemento X chiamato più grande (più piccolo), se per qualcuno AÎ UN eseguita A< х (х< у).

Un insieme parzialmente ordinato può avere diversi elementi minimi e/o massimi, ma non può esserci più di un elemento minimo e massimo. L'elemento più piccolo (più grande) è anche il minimo (massimo), ma non è vero il contrario. La figura a sinistra mostra un ordine parziale con due elementi minimi e due massimi, e a destra un ordine parziale con gli elementi più piccoli e più grandi:

In un insieme finito parzialmente ordinato ci sono sempre elementi minimi e massimi.

Si dice un insieme ordinato che ha gli elementi più grandi e più piccoli limitato. La figura mostra un esempio di insieme infinito limitato. Naturalmente, è impossibile rappresentare un insieme infinito su una pagina finita, ma è possibile mostrare il principio della sua costruzione. Qui i loop vicino ai vertici non sono mostrati per semplificare il disegno. Per lo stesso motivo non vengono mostrati gli archi che forniscono la visualizzazione della proprietà di transitività. In altre parole, la figura mostra il diagramma di Hasse della relazione d'ordine.

Gli insiemi infiniti potrebbero non avere elementi massimi o minimi o entrambi. Ad esempio, l'insieme dei numeri naturali (1,2, 3, ...) ha un elemento minimo pari a 1, ma nessun massimo. L'insieme di tutti i numeri reali con ordine naturale non ha né un elemento più piccolo né uno più grande. Tuttavia, il suo sottoinsieme è costituito da tutti i numeri X< 5, ha l'elemento più grande (il numero 5), ma non ha il più piccolo.