Rapporto tra ordine rigoroso e non rigoroso. Le loro proprietà, esempi. Relazioni d'ordine Relazioni d'ordine strette

L'ultimo esempio introduce il concetto di ordine alfabetico.

Alfabetoè una tupla di caratteri distinti a coppie chiamati lettere dell'alfabeto. Un esempio è l'alfabeto di qualsiasi lingua europea, nonché l'alfabeto dei 10 numeri arabi. Su un computer, la tastiera e alcuni strumenti di supporto determinano l'alfabeto dei caratteri validi.

Parola nell'alfabetoUN - tupla di caratteri alfabetici UN. La parola è scritta in simboli alfabetici consecutivi, da sinistra a destra, senza spazi. Un numero naturale è una parola dell'alfabeto digitale. Una formula non è sempre una parola a causa della disposizione non lineare dei simboli; della presenza di simboli dell'apice (esponenti) e del pedice (indici di variabili, basi dei logaritmi), barra frazionaria, segni radicali, ecc.; tuttavia, secondo alcune convenzioni, può essere scritto in una stringa, che viene utilizzata, ad esempio, nella programmazione dei computer (ad esempio, il segno di esponenziazione è scritto come 2 segni di moltiplicazione di seguito: 5**3 significa la terza potenza della numero 5.

Ordinamento lessicografico (alfabetico) - per le diverse parole dell'alfabeto con ordinato

i simboli impostano l'ordine: , if

presentazione possibile , a cui neanche

(la sottoparola può essere vuota) oppure - la sottoparola vuota

In questa definizione - un prefisso (sottoparola iniziale) uguale per entrambe le parole - oppure le prime a sinistra sono diverse

caratteri, o - l'ultimo carattere della parola - coda

sottoparole.

Pertanto, l'ordine alfabetico delle parole è determinato dal primo simbolo a sinistra che le distingue (ad esempio, la parola KONUS precede la parola COSENO perché differiscono prima nella terza lettera, e N precede S nell'alfabeto russo). Si considera anche che il carattere spazio preceda qualsiasi carattere dell'alfabeto - nel caso in cui una delle parole sia il prefisso di un'altra (ad esempio CON e CONE)

Esercizio. Verificare che l'ordinamento alfabetico dei numeri naturali che hanno lo stesso numero di cifre decimali coincida con il loro ordinamento per grandezza.

Permettere UN - insieme parzialmente ordinato. L'elemento viene chiamato massimo V UN, se non esiste alcun elemento per il quale UN< b. Elemento UN chiamato il più grande V UN, se per tutti diverso da UN elemento completato B<а-

Determinato simmetricamente minimo e più piccolo elementi. I concetti di elemento più grande e massimo (rispettivamente, più piccolo e minimo) sono diversi - vedi. esempio in Fig. 14. L'insieme in Fig. 14,a ha l'elemento più grande R,è anche il massimo, ci sono due elementi minimi: s e t, non esiste il più piccolo. Nella Fig. 14b, invece, esiste un insieme avente due elementi massimali / e J, non esiste il più grande, il minimo, ovvero il più piccolo: T.

In generale, se un insieme ha l'elemento più grande (rispettivamente più piccolo), allora ce n'è solo uno (potrebbe non essercene nessuno).

Possono esserci diversi elementi massimi e minimi (potrebbe non essercene affatto - in un insieme infinito; nel caso finale - deve esserci).

Diamo un'occhiata ad altri due esempi. - relazione su un insieme N:

"Y divide X", O "Xè un divisore di un numero Sì"(Per esempio,

) è riflessivo e transitivo. Consideriamolo su un insieme finito di divisori del numero 30.

La relazione è una relazione di ordine parziale (non stretta)

ed è rappresentato dalla seguente matrice di ordine 8, contenente 31 caratteri

Il circuito corrispondente con 8 vertici deve contenere 31 collegamenti. . Tuttavia la visione sarà più comoda escludendo 8

anelli connettivi che descrivono la riflessività della relazione (elementi diagonali della matrice) e connettivi transitivi, cioè legamenti

Se esiste un numero intermedio Z tale che

(ad esempio il connettivo since). Quindi nello schema

Rimarranno 12 legamenti (Fig. 15); i collegamenti mancanti sono impliciti "per transitività". Il numero 1 è il più piccolo e il numero 30

elementi più grandi in . Se escludiamo dal numero 30 e

consideriamo quindi lo stesso ordine parziale sull'insieme

non esiste un elemento massimo, ma ci sono 3 elementi massimi: 6, 10, 15

Ora costruiamo lo stesso circuito per una relazione su un booleano

(l'insieme di tutti i sottoinsiemi) di un insieme di tre elementi

Contiene 8 elementi:

Controllalo se combini gli elementi a, b, c, rispettivamente, i numeri 2, 3, 5, e le operazioni di combinazione degli insiemi sono moltiplicazioni dei numeri corrispondenti (cioè, ad esempio, il sottoinsieme corrisponde

prodotto 2 5 = 10), allora la matrice delle relazioni sarà esattamente così

come per la relazione; diagrammi di queste due relazioni con quelle descritte

le abbreviazioni dei cicli e dei connettivi transitivi coincidono fino alla notazione (vedi Fig. 16). L'elemento più piccolo è

E il più grande -

Relazioni binarie R su un set UN E S su un set IN sono chiamati isomorfo, se tra A e Bè possibile stabilire una corrispondenza biunivoca Г, nella quale, se (cioè

gli elementi sono in relazione R), poi (immagini

questi elementi sono in relazione S).

Pertanto, gli insiemi parzialmente ordinati sono isomorfi.

L’esempio considerato consente la generalizzazione.

Una relazione booleana è un ordine parziale. Se

Quelli. un mucchio di E contiene P elementi, quindi ciascuno

corrisponde al sottoinsieme P vettore bidimensionale con

componenti, dove è la funzione caratteristica

impostare A/ . L'insieme di tutti questi vettori può essere considerato come un insieme di punti P spazio aritmetico bidimensionale con coordinate 0 o 1, o, in altre parole, come vertici P-dimensionale

cubo unitario, indicato con , cioè cubo con spigoli di lunghezza unitaria. Per n = 1, 2, 3 punti indicati rappresentano, rispettivamente, le estremità di un segmento, i vertici di un quadrato e di un cubo - da qui il nome comune. Per /7=4, una rappresentazione grafica di questa relazione è in Fig. 17. Vicino a ciascun vertice di un cubo quadridimensionale il corrispondente

sottoinsieme dell'insieme di 4 elementi e quadridimensionale

un vettore che rappresenta la funzione caratteristica di questo sottoinsieme. I vertici corrispondenti a sottoinsiemi che differiscono per la presenza di esattamente un elemento sono collegati tra loro.

In Fig. 17, un cubo quadridimensionale è rappresentato in modo tale che su uno

livello, gli elementi incomparabili si trovano a coppie, contenenti lo stesso numero di unità nel record (da 0 a 4), o, in altre parole, lo stesso numero di elementi nei sottoinsiemi rappresentati.

In Fig. 18a, b - altre rappresentazioni visive di un cubo quadridimensionale;

in Fig. 18a l'asse della prima variabile OH diretto verso l'alto (deviazione intenzionale dalla verticale in modo che i diversi bordi del cubo non si uniscano):

in questo caso il sottocubo tridimensionale corrispondente a X= 0 si trova sotto e per X= 1 - più alto. Nella fig. 186 stesso asse OH diretto dall'interno del cubo verso l'esterno; il sottocubo interno corrisponde a X= Oh, e quello esterno lo è X = 1.

IN
Il file dei materiali mostra un'immagine di un cubo unitario a 5 dimensioni (p. 134).

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 determinato ordine, ecc. Esiste un ordine di operazioni durante la produzione di una parte, l'ordine di 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 rigoroso è 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 ordinato 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.

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

Opzioni

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

Un mucchio di X (\displaystyle X), su cui viene introdotta una relazione di ordine lineare, viene chiamato ordinato 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à:

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

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

Proprietà delle relazioni:

1) riflessività;

2) simmetria;

3)transitività.

4) connessione.

Atteggiamento R su un set X chiamato riflessivo, se su ciascun elemento dell'insieme X possiamo dire che ha una relazione R Con me stesso: XRx. Se la relazione è riflessiva, allora c'è un ciclo in ogni vertice del grafico. Al contrario, un grafo in cui ogni vertice contiene un ciclo è un grafo relazionale riflessivo.

Esempi di relazioni riflessive sono la relazione “multiplo” sull’insieme dei numeri naturali (ogni numero è multiplo di se stesso), la relazione di somiglianza dei triangoli (ogni triangolo è simile a se stesso), e la relazione di “uguaglianza” ( ogni numero è uguale a se stesso), ecc.

Esistono relazioni che non hanno la proprietà della riflessività, ad esempio la relazione di perpendicolarità dei segmenti: ab, ba(non esiste un singolo segmento che possa dirsi perpendicolare a se stesso) . Pertanto, non esiste un singolo ciclo nel grafico di questa relazione.

La relazione “più lungo” per i segmenti, “più per 2” per i numeri naturali, ecc. non ha la proprietà della riflessività.

Atteggiamento R su un set X chiamato antiriflesso, se per qualsiasi elemento dell'insieme X sempre falso XRicezione: .

Ci sono relazioni che non sono né riflessive né antiriflessive. Un esempio di tale relazione è la relazione “punto X simmetrico al punto A relativamente dritto l", definito su un insieme di punti del piano. In effetti, tutti i punti di una linea retta l sono simmetrici a se stessi e i punti che non giacciono su una linea retta io, essi stessi non sono simmetrici.

Atteggiamento R su un set X chiamato simmetrico, se la condizione è soddisfatta: dal fatto che l'elemento Xè in relazione all'elemento sì, ne consegue che l'elemento sìè in relazione R con elemento X:xRyyRx.

Il grafico delle relazioni simmetriche ha la seguente caratteristica: insieme a ciascuna freccia proveniente da X A sì, il grafico contiene una freccia che va da sì A X(Fig. 35).

Esempi di relazioni simmetriche possono essere i seguenti: la relazione di “parallelismo” di segmenti, la relazione di “perpendicolarità” di segmenti, la relazione di “uguaglianza” di segmenti, la relazione di somiglianza di triangoli, la relazione di “uguaglianza” di frazioni, ecc.

Ci sono relazioni che non hanno la proprietà della simmetria.

Infatti, se il segmento X più lungo del segmento A, quindi il segmento A non può essere più lungo del segmento X. Il grafico di questa relazione ha una particolarità: la freccia che collega i vertici è diretta solo in una direzione.

Atteggiamento R chiamato antisimmetrico, se per qualsiasi elemento X E sì dalla verità xRy dovrebbe essere falso yRx: : xRyyRx.

Oltre alla relazione “più lunga”, esistono altre relazioni antisimmetriche su molti segmenti. Ad esempio, la relazione "maggiore di" per i numeri (if X Di più A, Quello A non può esserci di più X), l’atteggiamento “more on”, ecc.

Ci sono relazioni che non hanno né la proprietà della simmetria né la proprietà dell'antisimmetria.

Relazione R su un insieme X chiamato transitivo, se da quell'elemento Xè in relazione R con elemento sì, ed elemento sìè in relazione R con elemento z, ne consegue che l'elemento Xè in relazione R con elemento z: xRy E yRzxRz.

Grafico delle relazioni transitive da cui proviene ciascuna coppia di frecce X A sì e da sì A z, contiene una freccia che va da X A z.

Anche la relazione “più lunga” su un insieme di segmenti ha la proprietà di transitività: se il segmento UN più lungo del segmento B, segmento B più lungo del segmento Con, quindi il segmento UN più lungo del segmento Con. La relazione di “uguaglianza” su un insieme di segmenti ha anche la proprietà di transitività: (a=b, b=c)(a=c).

Ci sono relazioni che non hanno la proprietà di transitività. Tale relazione è, ad esempio, la relazione di perpendicolarità: se un segmento UN perpendicolare al segmento B e il segmento B perpendicolare al segmento Con, quindi i segmenti UN E Con non perpendicolare!

Esiste un'altra proprietà delle relazioni, che è chiamata proprietà di connessione, e una relazione che la possiede è chiamata connessa.

Atteggiamento R su un set X chiamato collegato, se per qualsiasi elemento X E sì da questo insieme è soddisfatta la seguente condizione: se X E sì sono diversi, allora neanche Xè in relazione R con elemento sì o elemento sìè in relazione R con elemento X. Usando i simboli questo può essere scritto in questo modo: xyxRy O yRx.

Ad esempio, la relazione “maggiore di” per i numeri naturali ha la proprietà di connessione: per ogni numero diverso x e y si può affermare: x>y, O y>x.

In un grafo relazionale connesso, due vertici qualsiasi sono collegati da una freccia. È vera anche l’affermazione opposta.

Ci sono relazioni che non hanno la proprietà della connessione. Tale relazione, ad esempio, è la relazione di divisibilità sull'insieme dei numeri naturali: possiamo nominare tali numeri x e sì qualunque sia il numero X non è un divisore di un numero sì, nessun numero sì non è un divisore di un numero X(numeri 17 E 11 , 3 E 10 eccetera.) .

Diamo un'occhiata ad alcuni esempi. Sul set X=(1, 2, 4, 8, 12)è data la relazione “numero”. X multiplo del numero sì" Costruiamo un grafico di questa relazione e formuliamo le sue proprietà.

La relazione di uguaglianza delle frazioni si dice che sia una relazione di equivalenza.

Atteggiamento R su un set X chiamato relazione di equivalenza, se ha contemporaneamente le proprietà di riflessività, simmetria e transitività.

Esempi di relazioni di equivalenza includono: relazioni di uguaglianza di figure geometriche, relazioni di parallelismo di linee (a condizione che le linee coincidenti siano considerate parallele).

Nella relazione di “uguaglianza delle frazioni” discussa sopra, l'insieme X suddiviso in tre sottoinsiemi: ( ; ; }, {; } , (). Questi sottoinsiemi non si intersecano e la loro unione coincide con l'insieme X, cioè. abbiamo una partizione dell'insieme in classi.

COSÌ, se una relazione di equivalenza è data su un insieme X, allora genera una partizione di questo insieme in sottoinsiemi disgiunti a coppie - classi di equivalenza.

Pertanto, abbiamo stabilito che la relazione di uguaglianza sul set
X=( ;; ; ; ; ) corrisponde alla partizione di questo insieme in classi di equivalenza, ciascuna delle quali è costituita da frazioni uguali tra loro.

Il principio di partizionare un insieme in classi utilizzando una relazione di equivalenza è un principio importante della matematica. Perché?

In primo luogo, equivalente significa equivalente, intercambiabile. Pertanto, gli elementi della stessa classe di equivalenza sono intercambiabili. Pertanto, le frazioni che si trovano nella stessa classe di equivalenza (; ; ), sono indistinguibili dal punto di vista del rapporto di uguaglianza e della frazione può essere sostituito da un altro, ad esempio . E questa sostituzione non cambierà il risultato dei calcoli.

In secondo luogo, poiché la classe di equivalenza contiene elementi indistinguibili dal punto di vista di qualche relazione, si ritiene che la classe di equivalenza sia determinata da uno qualsiasi dei suoi rappresentanti, ad es. un elemento arbitrario della classe. Pertanto, qualsiasi classe di frazioni uguali può essere specificata specificando qualsiasi frazione appartenente a questa classe. La classe di equivalenza per un rappresentante consente di studiare un insieme di rappresentanti delle classi di equivalenza invece di tutti gli elementi dell'insieme. Ad esempio, la relazione di equivalenza “avere lo stesso numero di vertici”, definita su un insieme di poligoni, genera una partizione di questo insieme in classi di triangoli, quadrangoli, pentagoni, ecc. le proprietà inerenti a una determinata classe sono considerate su uno dei suoi rappresentanti.

In terzo luogo, il partizionamento di un insieme in classi utilizzando una relazione di equivalenza viene utilizzato per introdurre nuovi concetti. Ad esempio, il concetto di “fascio di linee” può essere definito come ciò che le linee parallele hanno in comune tra loro.

Un altro tipo importante di relazione è la relazione d'ordine. Consideriamo il problema Sul set X={3, 4, 5, 6, 7, 8, 9, 10 ) la relazione “ha lo stesso resto quando divisa per 3 " Questa relazione genera una partizione dell'insieme X in classi: tutti i numeri cadranno in uno, se divisi per 3 risulta essere il resto 0 (questi sono numeri 3, 6, 9 ). Nel secondo - numeri, se divisi per 3 il resto lo è 1 (questi sono numeri 4, 7, 10 ). Il terzo conterrà tutti i numeri che, una volta divisi per 3 il resto lo è 2 (questi sono numeri 5, 8 ). Gli insiemi risultanti infatti non si intersecano e la loro unione coincide con l'insieme X. Pertanto, la relazione “ha lo stesso resto quando divisa per 3 ", definito sul set X, è una relazione di equivalenza.

Per fare un altro esempio, i numerosi studenti di una classe possono essere ordinati per altezza o età. Si noti che questa relazione ha le proprietà di antisimmetria e transitività. Oppure tutti conoscono l'ordine delle lettere nell'alfabeto. È fornito dall’atteggiamento “dovrebbe”.

Atteggiamento R su un set X chiamato rapporto di ordine rigoroso, se possiede contemporaneamente le proprietà di antisimmetria e transitività. Ad esempio, la relazione " X< sì».

Se la relazione ha le proprietà di riflessività, antisimmetria e transitività, allora sarà tale relazione non stretta. Ad esempio, la relazione " Xsì».

Esempi di relazioni d'ordine includono: la relazione “minore di” su un insieme di numeri naturali, la relazione “più breve” su un insieme di segmenti. Se una relazione d'ordine ha anche la proprietà di connessione, allora si dice che lo sia relazione d'ordine lineare. Ad esempio, la relazione “minore di” sull’insieme dei numeri naturali.

Un mucchio di X chiamato ordinato, se su di esso è specificata una relazione d'ordine.

Ad esempio, molti X={2, 8, 12, 32 ) può essere ordinato utilizzando la relazione “minore di” (Fig. 41), oppure può essere fatto utilizzando la relazione “multiplo” (Fig. 42). Ma, essendo relazioni d'ordine, le relazioni “minore di” e “multiplo” ordinano l'insieme dei numeri naturali in modi diversi. La relazione “minore di” consente di confrontare due numeri qualsiasi di un insieme X, ma la relazione “multiplo” non gode di questa proprietà. Ok, un paio di numeri. 8 E 12 non ha niente a che vedere con la relazione “multiplo”: non si può dire questo 8 multiplo 12 O 12 multiplo 8.

Non si deve pensare che tutte le relazioni si dividano in relazioni di equivalenza e relazioni di ordine. Esiste un numero enorme di relazioni che non sono né relazioni di equivalenza né relazioni di ordine.

Relazione di equivalenza. Il collegamento 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?