Kabirov Nikolay Nikolaevich, studente del secondo anno della Facoltà di Fisica, Matematica, Informatica dell'Istituto Taganrog intitolato ad A.P. Chekhov - ramo) dell'Università statale di economia di Rostov - RINH), Taganrog [e-mail protetta]

Lyakhova Natalya Evgenievna, candidata di scienze fisiche e matematiche, capo del dipartimento di matematica, Istituto Taganrog intitolato ad A.P. Chekhov - ramo) dell'Università statale di economia di Rostov - RINH), Taganrog [e-mail protetta]

Ordini stabili sul semigruppo moltiplicativo dei numeri naturali

Riassunto L'articolo è dedicato alla descrizione di tutti i modi possibili per specificare l'ordine di un semigruppo di numeri naturali mediante moltiplicazione o addizione, che hanno la proprietà di stabilità. Parole chiave: relazione d'ordine, algebra universale dei numeri naturali, relazione stabile.

Questo articolo esamina i sistemi algebrici in cui l'insieme principale è l'insieme dei numeri naturali, le operazioni sono l'addizione e la moltiplicazione e la relazione è una relazione d'ordine, associata alle operazioni dalla proprietà di stabilità. Nasce un compito naturale descrivere tutti i modi possibili per specificare l'ordine nell'algebra universale dei numeri naturali mediante moltiplicazione o addizione, che avrebbero la proprietà della stabilità. Esempi ben noti di queste relazioni d'ordine sono le relazioni di confronto dei numeri per grandezza e la relazione di divisibilità. Si scopre che non sono gli unici, esiste un numero infinito di tali ordini. In questo lavoro vengono esplicitamente indicati tutti gli ordini stabili nei semigruppi moltiplicativi e additivi dei numeri naturali e come esempio di tali ordini vengono forniti gli ordini generati da un insieme di coppie coprime.

1. Definizioni di base

Per relazione binaria su un insieme si intende un sottoinsieme di un prodotto cartesiano. Se, dove, allora scriveremo e diremo “cosa è in relazione con”. Un tipo importante di relazioni binarie sono le relazioni di ordinamento parziale, cioè relazioni binarie con le proprietà di riflessività, transitività e antisimmetria. Un insieme con un dato ordinamento parziale si dice parzialmente ordinato. Per registrare l'ordine, solitamente viene utilizzato un simbolo; se e, allora, a seconda delle circostanze, si dice che minore o uguale a, contenuto in, precede b. Sia dato un ordine parziale in un insieme. Gli elementi di e di questo insieme saranno chiamati comparabili se o. Non è necessario che tutti i due elementi siano confrontabili: è per questo motivo che possiamo parlare di ordinamento “parziale”. In questo modo si ottiene un banale ordinamento parziale di un insieme se assumiamo che solo se elementi diversi da sono incomparabili. Un insieme parzialmente ordinato in cui due elementi qualsiasi sono confrontabili è chiamato insieme ordinato o insieme o catena ordinata linearmente. rami della matematica, insiemi ordinati e parzialmente ordinati sono estremamente comuni. Esempi di insiemi ordinati includono l'insieme dei numeri naturali e l'insieme dei numeri reali, entrambi nel loro ordinamento naturale. Esempi di insiemi parzialmente (ma non linearmente) ordinati sono i seguenti insiemi: – insieme

tutti i sottoinsiemi di un dato insieme con la relazione di inclusione teorica degli insiemi come relazione di ordinamento parziale; – l'insieme di tutte le funzioni reali continue definite su un intervallo, se significa questo per tutti; – l'insieme di tutti i numeri naturali, se intesi nella senso che è interamente divisibile per Parziale Un ordine su un semigruppo è un ordine parziale che soddisfa la condizione di stabilità

Un semigruppo in cui è definito un ordine parziale stabile rispetto a un'operazione è chiamato semigruppo ordinato. Ovviamente ogni semigruppo può considerarsi ordinato rispetto all'ordine banale. Come esempi di ordini parzialmente stabili possiamo citare gli ordini su un semigruppo e su un semigruppo sopra menzionati.Come segue dalle definizioni, un ordine è una relazione binaria, cioè molte coppie. Ciò dà origine a un metodo per descrivere tutti gli ordini parziali su un semigruppo. Chiameremo un ordine generato da un certo insieme di coppie se è l'ordine minimo contenente questo insieme di coppie. Se è possibile trovare una forma generale di ordine generata da un insieme arbitrario di coppie, questa sarà la soluzione al problema posto. È chiaro che non per ogni insieme di coppie viene generato un ordine: ovviamente un insieme non può generare un ordine.

2. Ordini su N,· generati da un insieme finito di coppie

È facile vedere che ciascuna coppia di numeri naturali può essere rappresentata nella forma in cui n è un numero naturale e q è una frazione positiva. Ad esempio, una coppia può essere scritta. Permettere

un sottoinsieme finito arbitrario di un quadrato cartesiano. Quindi, secondo quanto sopra, può essere rappresentato come:

Definizione. Chiameremo antisimmetrico un insieme di coppie se per qualsiasi insieme di numeri dell'insieme

Allo stesso tempo non uguale a zero È chiaro che la definizione è una generalizzazione del noto concetto di antisimmetria.

Definizione.Let

insieme di coppie antisimmetriche. Qualsiasi numero naturale per il quale esistono due sequenze di questo tipo, dove e, dove tale che,

Dove il primo numero di una coppia di un set è chiamato numero e numeri

numeri dell'insieme.

Teorema 1. Se

insieme antisimmetrico finito di coppie, allora una relazione binaria tale che se e solo se o è un numero ed è il numero di un insieme, c'è un ordine generato da questo insieme.

Prova. Per dimostrare il teorema è necessario mostrare che, in primo luogo, la relazione d’ordine, e, in secondo luogo,

coincide con l'ordine generato dall'insieme.

Dimostriamo la prima parte del teorema, cioè dimostriamolo

riflessiva, transitiva, antisimmetrica e stabile rispetto alla moltiplicazione.1) La riflessività consegue dalla definizione di una relazione.2) Sia

E. Dalla condizione che abbiamo,

E dalla condizione che abbiamo,

Pertanto è possibile specificare due sequenze

e tale che,

Quelli. -numero e -numero del set. Quindi. Casi in cui o sono evidenti. La transitività è stata dimostrata.3) Sia e. Dalla condizione segue che. Dalla condizione segue che. La transitività è stata dimostrata sopra, quindi,

e allo stesso tempo Poiché tutto, queste uguaglianze possono essere scritte nella forma

Dall'ultima uguaglianza segue questo. Ma questo è possibile solo perché l’insieme è antisimmetrico. Considerando questo e, otteniamo. Quindi. L'antisimmetria è stata dimostrata 4) La stabilità rispetto alla moltiplicazione consegue ovviamente dalla stabilità della relazione di uguaglianza, che serve per determinare i numeri dell'insieme. Dimostriamo la seconda parte del teorema. Indichiamo con l'ordine generato dall'insieme. È necessario dimostrarlo. Lasciamo quindi una coppia arbitraria di, perché. ci sono sequenze e, tali che, cioè numero e

numero dell'insieme. Pertanto è un ordine contenente un insieme, ma

ordine minimo contenente, quindi.

Lasciamo, cioè è un numero ed è il numero dell'insieme. Significa che

, . (3) Mostriamo che la coppia. Poiché, allora. Pertanto, secondo 1) . () Considerando che

Otteniamo Quindi, secondo 2), . () Da ) e ) seguirà che. E così via, continuando questo processo, otteniamo. Oppure, tenendo conto di 3), cioè Così lo hanno dimostrato.

Il teorema è stato dimostrato.

Teorema2. Affinché un insieme finito di coppie possa essere un insieme generatore di un certo ordine, è necessario e sufficiente che sia antisimmetrico.

Dimostrazione: Se l'insieme delle coppie è antisimmetrico, allora per il Teorema 1 sarà un insieme generatore di ordine. Mostriamo il contrario. Lascia che ci siano molte coppie

crea ordine. Mostriamo che è antisimmetrico. Effettueremo la dimostrazione per assurdo. Supponiamo che non sia antisimmetrico, cioè c'è una serie di numeri

da un insieme che sono contemporaneamente diversi da zero, in modo tale che È facile vedere che se una coppia appartiene a qualche relazione d'ordine, allora le coppie devono appartenere ad essa e, quindi, la coppia. Allo stesso modo, qualsiasi coppia apparterrà a questo ordine.In base a questa osservazione, coppie

appartengono all'ordine. Poi.

Se un ordine contiene coppie, allora contiene coppie, .Quindi contiene una coppia. Applicando questo fatto all'ordine, possiamo scrivere.Quindi,

Abbiamo scoperto che l'ordine contiene contemporaneamente coppie

e. E questo contraddice ciò che è una relazione d'ordine. La contraddizione risultante dimostra il teorema.

3. Ordini generati da un insieme di coppie relativamente prime

In alcuni casi, a seconda della scelta del gruppo elettrogeno, la costruzione dell'ordine discusso nel paragrafo precedente viene notevolmente semplificata e diventa più chiara. Consideriamo uno di questi casi.

Definizione: L'insieme delle coppie tale che, dove, è detto insieme delle coppie coprime.

Teorema 3. Sia dato un certo insieme di coppie relativamente prime e indichiamo dove. Quindi sono rappresentati nella forma.Relazione binaria

Dov'è l'ordine parziale.

Dimostrazione Per dimostrare il teorema è necessario dimostrare la riflessività, transitività, antisimmetria e stabilità della relazione binaria specificata. 1. La condizione è soddisfatta, perché esistono tali che. La riflessività è stata dimostrata.2. Lascia stare. Dalla condizione consegue che, e dalla condizione consegue che, quindi

Per chiarezza, assumeremo che tutto sia tutto. Poi potremo scriverlo da qui

Esprimendo e, otteniamo, Sostituendo i valori

e nelle uguaglianze originali, troviamo che,. Di conseguenza,

e la transitività è dimostrata. Nel caso alcuni

Usiamo il fatto che e la dimostrazione sarà simile.3. Lascia fare. Mostriamolo. Dalle condizioni segue che,. Dalle condizioni segue che,.Chiudiamo transitivamente queste coppie, otteniamo,e per quanto dimostrato sopra.Ma poiché,.Di conseguenza, l'antisimmetria è dimostrata.4. La stabilità è evidente. Il teorema è stato dimostrato.

Teorema4. Affinché un ordine possa essere generato da un insieme di coppie coprime è necessario e sufficiente che sia quello descritto nel Teorema 3.

Prova. Indichiamo l'ordine generato dall'insieme delle coppie relativamente prime e dobbiamo dimostrarlo.

1. -minimo

2. Allora lasciamo

Mostriamo che questa coppia appartiene. Per fare ciò è sufficiente dimostrarlo da cosa

segue quello

appartiene, quindi,. Ne consegue che. Pertanto, l'inclusione vale per. Lascia che l'inclusione venga eseguita per, ad es. .Allora.Dal momento che.Di conseguenza, cioè. vale questa inclusione e le coppie appartengono, quindi significa e, quindi è dimostrato che.

Quindi, viene ricevuto e, quindi,

e il teorema è dimostrato.

È facile vedere che l'ordine generato da una coppia arbitraria è un caso speciale dell'ordine generato da un insieme di coppie coprime.

4. Ordini stabili sul semigruppo additivo dei numeri naturali, loro connessione con ordini sul semigruppo moltiplicativo dei numeri naturali.

Consideriamo l'ordine del semigruppo dei numeri naturali per addizione.

Una coppia arbitraria di numeri naturali può essere rappresentata come, o, o, dove. Consideriamo un insieme arbitrario di coppie, rappresentabili nella forma

e disporli in ordine crescente. Indichiamo un tale insieme, ad es. ,

Teorema 5. Affinché un ordine possa essere generato da un insieme di coppie è necessario e sufficiente che si tratti di una relazione binaria

Prova. Dimostriamo che una relazione binaria è una relazione d'ordine. Per fare questo dobbiamo mostrare quattro proprietà: 1. La riflessività segue dalla definizione 2. Dimostriamo la transitività. Sia E. Dalla condizione ne consegue che

Ne consegue la condizione che,

Da queste uguaglianze otteniamo

Quelli. e la transitività è dimostrata 3. Antisimmetria. Permettere

E. Allora valgono le uguaglianze (1). (2) Sostituisci 1) in 2) e ottieni. E questo significa che. Ma

e quindi. Quindi, cioè .Così,

antisimmetrico.4. La stabilità è evidente.

Quindi,

Relazione d'ordine. Resta da mostrare a cosa serve il gruppo elettrogeno.

Denotiamo

ordine generato da molte coppie. Proviamo che coincide con.1. Appartiene una coppia arbitraria dell'insieme. Allo stesso tempo, secondo la definizione

può essere scritto,

Quelli. .Di conseguenza, una coppia arbitraria di sarà contenuta in, perché contiene tutte le coppie del gruppo elettrogeno dell'ordine.Abbiamo scoperto che.2. Mostriamo il contrario. Lasciamo, cioè,

È necessario dimostrare che, tenendo conto delle uguaglianze scritte, eseguiamo il seguente ragionamento.

Da cosa ne consegue che allora le coppie appartengono. Da qui. Da ciò consegue che, cioè. Effettuando un ragionamento simile ai precedenti, si ottiene. Continuando questo processo, si arriva al seguente risultato:, cioè , che significa .

Otteniamo che, quindi,

Il teorema è dimostrato Allo stesso modo, il teorema può essere dimostrato per l'insieme delle coppie duali dell'insieme.

Teorema6. Affinché un insieme di coppie generi un ordine su un semigruppo additivo di numeri naturali, è necessario e sufficiente che si tratti di un insieme o di un suo insieme duale.

Prova. 1. Se un insieme ha uno dei tipi indicati, allora per il Teorema 5 genera ordine.

2. Lascia che generi ordine. Mostriamo che è così

plurale o duale ad esso. Effettueremo la dimostrazione con il metodo opposto. Lascia che l'insieme contenga coppie. Quindi anche queste coppie appartengono all'ordine generato.,

Quindi

Usando argomenti simili ai precedenti otteniamo che contiene contemporaneamente coppie

E questo contraddice l'ordine. Pertanto, non possono esserci coppie e allo stesso tempo, ad es. è una pluralità o il suo duale.

Il teorema è stato dimostrato.

È facile vedere che gli ordini stabili sul semigruppo additivo dei numeri naturali sono stabili anche sul semigruppo moltiplicativo dei numeri naturali. Anzi, lasciamo

ordine stabile. Le condizioni seguono le uguaglianze,

Quindi, moltiplicando entrambi i membri di ciascuna uguaglianza per un numero naturale arbitrario ed effettuando semplici trasformazioni, otteniamo,

Quindi, .

Pertanto, l'insieme di tutti gli ordini stabili sul semigruppo additivo dei numeri naturali è contenuto nell'insieme di tutti gli ordini stabili sul semigruppo moltiplicativo dei numeri naturali. Sorge la domanda sull'insieme generatore di questi ordini nel semigruppo

Consideriamo, ad esempio, l'ordine delle finestre generato da una coppia. Questo sarà il solito ordine. Si noti che oltre ad esso e al suo doppio ordine

Altri ordini lineari su

NO. L'insieme minimo di generatori di ordine in

ci sarà un insieme di coppie. Ciò deriva dal fatto che qualsiasi coppia contenuta nell'ordine può essere ottenuta dall'insieme specificato e, allo stesso tempo, nessuna di queste coppie può essere ottenuta dalle altre utilizzando una chiusura transitiva o stabile . Quindi, per un ordine di grandezza

ha un gruppo elettrogeno infinito. È facile vedere che tutti gli ordini generati da un insieme finito di coppie hanno on

gruppi elettrogeni infiniti.

5. Ordini generati da un insieme infinito di coppie

Teorema 7. Insieme infinito di coppie

crea ordine

su un po' di algebra

se e solo se qualsiasi suo sottoinsieme finito

genera un certo ordine

su questa algebra. È definito come segue:

se e solo se esiste un finito tale.

Prova. Lascia che crei ordine. Scegliamo un sottoinsieme finito arbitrario

moltitudini. Quindi il sottordine minimo

Mostriamo il contrario. Sia un sottoinsieme finito arbitrario

imposta

crea ordine. Consideriamo una relazione tale che.1. , Perché . Quindi riflessivo.2. Permettere

e.Allora, e allora?

e, in tal modo. Consideriamo. Allora possiamo scriverlo

E. Ce l'abbiamo. Perciò. Quindi, transitivo.3. Lascia fare. Quindi, così e così, ma c'è quello, e otteniamo. Quindi antisimmetrico.4.Sia dunque tale che. Pertanto, da dove.I.e. stabile.

Quindi soddisfa le proprietà di riflessività, transitività, antisimmetria e stabilità. Significa,

relazione d'ordine Proviamo che esiste un ordine generato da un insieme infinito. Denotiamo

ordine generato. Deve essere dimostrato che: 1. Una coppia arbitraria è contenuta in, perché. , che, quindi, . Ma l'ordine minimo contiene, quindi.

2. Sia quindi una coppia arbitraria di, cioè,

la coppia è contenuta nell'ordine minimo generato da, ma, da e, quindi,. Significa, .

Abbiamo ottenuto due inclusioni e quindi, ad es. il set sta generando per.

È dunque dimostrato che se ogni sottoinsieme finito di un insieme infinito genera un ordine, allora anche l'infinito stesso genera un ordine, che è l'ordine specificato.

Il teorema è stato dimostrato.

Dal teorema dimostrato seguono dei corollari.

Definizione. Un insieme infinito di coppie di numeri naturali si dice antisimmetrico se ogni suo sottoinsieme finito è antisimmetrico.

ordine generato

sul semigruppo moltiplicativo dei numeri naturali è necessario e sufficiente che sia antisimmetrico.

se e solo se esiste un insieme finito tale che, dove

– l’ordine generato dall’insieme antisimmetrico, descritto nel paragrafo 2.

Definizione. Un insieme infinito di coppie di numeri naturali si dice insieme se uno qualsiasi dei suoi sottoinsiemi finiti è un insieme.

Conseguenza. In ordine per un numero infinito di coppie

ordine generato

su un semigruppo additivo di numeri naturali è necessario e sufficiente che sia un insieme -o un suo insieme duale. Inoltre, se e solo se esiste un insieme finito tale che, dov'è l'ordine generato dall'insieme descritto al paragrafo 4.

M.: Nauka, 1970, 393 pagina 2. Lyapin, E.S. Ordine nel semigruppo delle trasformazioni/E.S. Lyapin //Atti del quarto congresso matematico pan-sindacale, Leningrado: Nauka.1964.T.2.S.1314.3.Krivenko, V.M. Relazioni di precedenza che determinano ordini stabili sul semigruppo moltiplicativo dei numeri naturali/V.M.Krivenko, N.E. . Lyakhova //XIX Conferenza algebrica di tutta l'Unione: abstract dei messaggi. –Istituto di problemi applicati di meccanica e matematica dell'Accademia delle scienze della SSR ucraina –Lvov, 1987, parte 1.S.148.

Ministero dell'Istruzione e della Scienza della Federazione Russa

Agenzia federale per l'istruzione

ISTITUTO MUNICIPALE DI NIZHNEKAMSK

Dipartimento di Informatica, Matematica e Scienze Naturali -

discipline scientifiche

Gruppo 561

ASTRATTO

nella disciplina "Algebra astratta"

Specialista del livello di istruzione

Argomento: insiemi ordinati

Responsabile ___________________ R.M. Munipov

Studente ___________________ A.V. Glazunov

Nizhnekamsk 2007

INTRODUZIONE…………………………..3

1. Insiemi parzialmente ordinati……………5

2. Insiemi ben ordinati……………..20

3. Gruppoidi parziali e loro proprietà……………..23

CONCLUSIONE………………..35

RIFERIMENTI…………………………….36

introduzione

Attualmente l'algebra è intesa principalmente come la teoria generale delle operazioni e delle relazioni algebriche. È caratterizzato da una grande naturalezza interna delle idee e dei compiti iniziali, dall'unità dei metodi e da un'ampia ampiezza dei concetti di base. La sua area è delineata in modo chiaro e chiaro. Eppure i confini esistenti della teoria non possono essere considerati fermamente e definitivamente stabiliti. Il desiderio di andare oltre i propri limiti comincia ad emergere sempre più spesso. Occorre considerare le operazioni non solo complete, ma anche parziali.

La teoria delle azioni parziali deve naturalmente continuare la teoria delle azioni complete. Quest'ultimo è attualmente estremamente esteso, ricco ed è nel suo periodo di massimo splendore. Naturalmente nasce l'idea di trasferire i concetti ed i risultati lì sviluppati in un nuovo ambito. Ciò è, ovviamente, necessario e in molti casi fruttuoso. Tuttavia, già dai primi passi nello sviluppo della teoria delle azioni parziali, si fa sentire la significativa specificità di questa direzione. Spesso il trasferimento diretto dei risultati della teoria delle azioni complete risulta difficile o addirittura impossibile. Il consueto materiale algebrico deve essere sottoposto a un'elaborazione o a un ripensamento significativo; inoltre sorgono concetti e problemi completamente nuovi che sono specifici della nuova direzione. Richiedono una propria metodologia di ricerca.

Non c'è stata ancora una presentazione sufficientemente completa e coerente della teoria delle azioni algebriche parziali. C'è incoerenza nei concetti iniziali e anche nelle notazioni e nella terminologia. Non ci sono abbastanza collegamenti tra le singole opere. Si fa sentire l'insufficienza dello sviluppo delle singole questioni necessarie alla costruzione di una teoria generale.

1 . Hinsiemi ordinati asticamente

Relazione binaria su un insieme UN chiamato antisimmetrico Se:

(AC UN) UN? V V? UN

UN chiamato riflettente Se:

( UN UN) UN UN

Relazione binaria su un insieme UN chiamato transitivo Se:

(UN,V,C UN) UN V V C>a Con

Esempio 1.

Relazione di divisibilità (interamente) sull'insieme dei numeri naturali N antisimmetrico. In effetti, se UN V, V UN, poi ci sono naturali Q1 ,Q N, tale che un=bQ1 , в=аQ Dove un=unQ1 Q , questo è Q1 Q = 1. Ma,

Q1 ,Q N,quindi Q1 = Q = 1, da cui consegue che un = b.

Relazione binaria riflessiva transitiva antisimmetrica su un insieme UN chiamato relazione d'ordine (ordine parziale) sul set UN.

Un mucchio di UN con una relazione di ordine parziale data su di esso? chiamano insieme parzialmente ordinato e denotare< UN; ? >.

Nel seguito, per comodità, utilizzeremo l'abbreviazione APPESTARE , che denota un insieme parzialmente ordinato.

Esempio 2.

< N, ? > ? disuguaglianza ordinaria e non rigorosa dei numeri (nel senso scolastico). È necessario dimostrare la transitività, la riflessività e l'antisimmetria di questa relazione?

UN)UN? UN,(2 ? 2) - riflessività,

b) se UN? V , V? Con, Quello UN ? C, (3 ? 4, 4 ? 5 > 3 ? 5) - transitività,

c) se UN ? V , V?UN, Quello UN= dentro,(3 ? 3, 3 ? 3 > 3=3) - antisimmetria.

Ne consegue che < N, ? > - AMICO.

Esempio 3.

< N, > .

a) Relazione di divisibilità sull'insieme dei numeri naturali N riflessivo, perché ogni numero è multiplo di se stesso, cioè perché per chiunque UN N Sempre UN = UN 1 (1 N), questo, nel senso della relazione, abbiamo UN UN. Pertanto è riflessivo.

B) Se il primo numero è divisibile per il secondo (cioè multiplo del secondo), e il secondo è multiplo del terzo, allora il primo è multiplo del terzo, il che significa che la relazione è transitiva, cioè Se UN V, V Con, UN,V,C N. Quindi, ce ne sono Q ,Q N, Che cosa

UN= polliciQ ,

in =C Q ,

UN = C (Q Q ).

Indichiamo: Q = Q Q N. Abbiamo

Dove Q N, cioè. UN Con- a priori . Pertanto la relazione è transitiva.

c) L'antisimmetria della relazione deriva dal fatto che due numeri naturali multipli tra loro sono uguali tra loro, cioè Se UN V, V UN, poi ci sono tali Q1 ,Q N, Che cosa

un=bQ1 ,

в=аQ ,

un=unQ1 Q ,

questo è Q1 Q = 1. Ma, Q1 ,Q N,quindi Q1 = Q = 1, da cui consegue che un = b. Quindi antisimmetrico.

Esiste quindi un ordine parziale e, quindi, < N, > - CHUM (insieme parzialmente ordinato).

Elementi UN,V Appestare UN sono chiamati incomparabile sono scritti

UN|| V, Se UN? V E V? UN.

Elementi UN,V Appestare UN sono chiamati paragonabile Se UN? V O V? UN.

Ordine parziale? SU UN chiamato lineare, ma la peste stessa linearmente - ordinato O catena, se ci sono due elementi da UN paragonabile, cioè per ogni UN,V UN, O UN ? V, O V? UN.

Esempio 4 .

< N, ? >, < R, ? > - sono una catena. Tuttavia<В(M) ; > ,dove B( M) - l'insieme di tutti i sottoinsiemi dell'insieme M o in( M) è chiamato Booleano su un set M, non è una catena, perché non per due sottoinsiemi qualsiasi dell'insieme M uno è un sottoinsieme dell'altro.

Permettere < UN, ? > - peste arbitraria.

Elemento M UN chiamato minimo, se per qualsiasi X UN da cosa X ? M Dovrebbe X = M.

Il significato di questo concetto è quello UN non contiene elementi strettamente più piccoli di questo elemento M. Dicono che X rigorosamente meno M e scrivi X< M, Se X ? M, ma allo stesso tempo X ? M. L'elemento massimo di questa piaga è determinato in modo simile. È chiaro che se M , M - diversi elementi minimi (massimi) della peste, quindi M || M .

Nella teoria del parzialmente ordinato imposta la condizione UN ? V a volte leggi così: elementoUN contenuto nell'elementoV O elementoV contiene un elementoUN .

Lemma.

Ogni elemento di una Piaga finita contiene un elemento minimo ed è contenuto in un elemento massimo di questa Piaga.

Prova:

Permettere UN- un elemento arbitrario della piaga finale S. Se UN - elemento minimo, quindi, per effetto della riflessività, il lemma è dimostrato. Se UN non è minimo, allora c'è un elemento UN tale che

UN < UN(1)

Se UN è minimo, allora tutto è dimostrato. Se l'elemento UN non è

minimo, quindi per alcuni UN noi abbiamo

UN < а (2)

Se UN è minimo, allora da (1), (2), grazie alla transitività, concludiamo che UN contiene l'elemento minimo UN . Se UN non è minimo, quindi

UN < UN (3)

per alcuni UN S. E così via. Questo processo non può essere infinito a causa della finitezza dell'insieme stesso S.

Così, da qualche tempo N- all'esimo passo del ragionamento il processo termina, il che equivale al fatto che l'elemento UN minimo. In cui

UN < а < < а < а < а

A causa della transitività, ne consegue che l'elemento UN contiene l'elemento minimo UN . Allo stesso modo, elemento UN contenuto nell'elemento massimo. Il lemma è dimostrato.

Conseguenza.

La piaga finale contiene almeno un elemento minimo.

Ora introduciamo il concetto che è importante per un'ulteriore presentazione diagrammi la piaga definitiva S.

Per prima cosa prendiamo tutti gli elementi minimi M , M , M V S. Secondo l'indagine, ci saranno persone del genere. Quindi nell'insieme parzialmente ordinato

S = S \ {M , M , M },

che, come S, è finito, prendiamo gli elementi minimi,

, , e consideriamo l'insieme

= S \ {, , }

Elementi della “prima riga” M , M , M raffigurato da punti. Un po' più in alto contrassegniamo gli elementi della “seconda fila” con punti, , e collega i punti con segmenti in quello e solo in quel caso se M <

Successivamente, troviamo gli elementi minimi della Peste, li rappresentiamo con punti della “terza fila” e li colleghiamo con punti della “seconda fila” nel modo sopra indicato. Continuiamo il processo finché tutti gli elementi di questa Piaga non saranno esauriti S. Il processo è finito a causa della finitezza dell'insieme S. Viene chiamato l'insieme risultante di punti e segmenti diagramma PLAGUE S. Allo stesso tempo UN < в se e solo se dal “punto” UN puoi andare su “punti” V lungo una linea spezzata “ascendente”. A causa di questa circostanza, qualsiasi piaga finita può essere identificata dal suo diagramma.

Esempio 5 .

Qui dato dal diagramma CHUM S = {M , M , , ), in cui M < , M < , M < M < , M < M < , M < .

Elemento M chiamato il più piccolo elemento della PESTE, se per qualcuno X UN Sempre M ? X.

È chiaro che l'elemento più piccolo è minimo, ma non è vero il contrario: non tutti gli elementi minimi sono il più piccolo. C'è solo un elemento più piccolo (se presente). L'elemento più grande è determinato in modo simile.

Esempio 6.

· · · ·

Questa è una piaga, i cui elementi sono incomparabili in coppia. Questi sono parzialmente

vengono chiamati gli insiemi ordinati anticatene.

Esempio 7 .

Questa è la catena con l'elemento più piccolo e quello più grande. Dove 0 è l'elemento più piccolo e 1 è l'elemento più grande.

Permettere M- sottoinsieme di un insieme ordinato parziale UN. Elemento UN UN chiamato bordo inferiore imposta M, Se UN? X per chiunque X M.

Il più grande di tutti gli inferiori dell'insieme M, se esiste, viene chiamato bordo inferiore esatto imposta M e denotare inf M.

Permettere < UN, ? > - peste arbitraria. Elemento Con UN chiamato bordo inferiore esatto elementi UN,V UN, Se Con= inf( UN,V}.

Nota 1.

Non in ogni piaga c'è un minimo esatto per due elementi qualsiasi.

Mostriamolo con un esempio.

Esempio 8 .

Per ( UN;C},{D;e) non c'è bordo inferiore,

inf( UN;V}=D, inf( V;C}=e.

Esempio 9 .

Facciamo l'esempio di una peste, che ha un minimo esatto per ogni elemento.

inf( UN;V}=D, inf( UN;D}=D, inf( UN;0 }=0 , inf( UN;C}=0 , inf( UN;e}=0 ,

inf( V;C}=e, inf( V;e}=e, inf( V;D}=D,

inf( C;e}=C, inf( C;0 }=0 , inf( C;D}=0 ,

inf( D;e}=0 , inf( D;0 }=0 ,

inf( e;0 }=0 .

Definizione: Si dice un insieme parzialmente ordinato in cui per due elementi qualsiasi esiste un minimo semi-reticolo.

Esempio 10 .

Facciamo l'esempio di una peste, che non è un semireticolo.

Permettere < N, ? > - insieme ordinato linearmente di numeri naturali e e , e N. Sul set N = N { e , e ) definire una relazione binaria? , supponendo che X ? sì, Se X, sì N, Dove X ? sì, o se X N, sì { e , e ). Consideriamo inoltre per definizione: e ? e , e ? e .

Lo schema di questa piaga è il seguente:

Qualsiasi numero naturale n ? e e n? e , ma in N non esiste un elemento più grande, quindi, N - CHUM, ma non un mezzo reticolo.

Quindi, per sua stessa definizione, un semireticolo è un modello (come un insieme con una relazione?). Come vedremo ora, è possibile un altro approccio al concetto di semireticolo, ovvero un semireticolo può essere definito come una certa algebra.

Per fare ciò introduciamo alcuni concetti algebrici aggiuntivi. Come è noto, semigruppoè un insieme non vuoto su cui è definita un'operazione algebrica binaria associativa.

Di solito viene indicato un semigruppo arbitrario S(semigruppo).

Definizione. Elemento eS chiamato idempotente, Se

e = e, questo è e · e = e.

Esempio 11 .

Semigruppo< N; · > ? ha un solo idempotente 1.

Semigruppo< Z; + > ? ha un singolo 0 idempotente.

Semigruppo< N; + > ? non ha idempotente, perché 0 N.

Per ogni insieme non vuoto X, come al solito, denota l'insieme di tutti i sottoinsiemi dell'insieme X - il booleano dell'insieme X.

Semigruppo<В;>- è tale che ciascuno dei suoi elementi è idempotente.

UN IN, UN = UN UN.

Viene chiamato il semigruppo semigruppo idempotente O grappolo, se ciascuno dei suoi elementi è idempotente. Pertanto, un esempio di connettivo è qualsiasi booleano relativo a un'unione.

Esempio 12 .

Permettere X- insieme arbitrario.

B- l'insieme di tutti i sottoinsiemi dell'insieme X.

B- è chiamato booleano sul set X.

Se X= (1,2,3) , quindi

B = (O,(1),(2),(3),(1,2),(2,3),(1,3),(1,2,3)).

Dall'intersezione di due sottoinsiemi dell'insieme Xè ancora una volta un sottoinsieme di X, allora abbiamo un gruppoide< В;>, inoltre, è un semigruppo e anche un connettivo, poiché UN In e UN = UN UN=UN.

Esattamente allo stesso modo, abbiamo la connessione<; В > .

Si dice il connettivo commutativo semi-reticolo.

Esempio 13 .

Permettere X= (1,2,3), costruiamo un diagramma< В ; >.

Diamo esempi di piaghe, ma non di semireticoli.

Esempio 14 .

CHUM con due facce inferiori e E D , che non sono paragonabili tra loro: e|| D. Pertanto inf( UN;Con) non esiste.

Esempio 15.

CHUM con due facce inferiori Con E D, che sono incomparabili tra loro: Con|| D. Pertanto inf( UN;V) non esiste.

Diamo esempi di semireticoli.

Esempio 16 .

Diagramma:

UN

inf( UN;V}=V, inf( UN;Con}=Con, inf( UN;D}=D,

inf( V;C}=D, inf( V;D}=D,

inf( C;D}=D.

Esempio 17 .

È un semireticolo, perché per due elementi qualsiasi c'è un minimo, cioè

inf( UN;V}=V, inf( UN;Con}=Con, inf( V;C}=Con.

Teorema 1.

Permettere<S ; ? > - semireticolo. Poi<S ; > connettivo commutativo, dove

UN V=inf( UN,V} (*).

Prova:

È necessario dimostrarlo<S ; > valgono le seguenti identità:

(1) X y = y X

(2) (X sì) z = x (sì z)

(3) X X = X

1) Secondo l'uguaglianza(*)

X y = inf( X,sì) = inf ( sì,X) = sì X

2) Indichiamo UN = (X sì) z, in =X ( sì z)

Dimostriamolo UN = V.

Per fare ciò è sufficiente dimostrarlo

UN ? V (4)

V ? UN(5) (a causa dell'antisimmetria)

Denotiamo

Con = X sì , D = sì z

Ai sensi di, UN l'esatto limite inferiore tra Con E z

UN? Con , UN ? z , C ? X, quindi, a causa della transitività UN ? X.

Allo stesso modo, UN? sì, cioè. UN- limite inferiore comune per sì E z. UN D- il loro esatto limite inferiore.

Quindi, UN ? D, Ma V=inf( X, D}.

Dalla disuguaglianza UN ? X , UN ? D segue quello UN X E D, UN Vè il loro esatto minimo, quindi,

UN? V(4) dimostrato.

(5) si dimostra in modo analogo.

Da (4) e (5), vista l'antisimmetria, concludiamo che

un = b.

Con questo abbiamo dimostrato l'associatività dell'operazione ().

3) Abbiamo X X=inf( X,X} = X.

L’uguaglianza si ottiene attraverso la riflessività: X? X.

Quello. algebra costruita<S ; > sarà un semigruppo commutativo idempotente, cioè legame commutativo.

Teorema 2.

Permettere<S ; · > è un semigruppo idempotente commutativo, quindi una relazione binaria? SU S, definito dall'uguaglianza

? = UN·в = а,

è un ordine parziale. Allo stesso tempo, PESTE<S ; ? > è un semireticolo.

Prova:

1) riflessività?.

Per condizione<S ; · > soddisfa tre identità:

(1) X = X

(2)x y = yx

(3) (xy)· z = x(sì· z)

Poi xx = x =x- in virtù di (1). Ecco perché X? X.

2) antisimmetria? .

Permettere X? A E sì? X, quindi per definizione,

(4) xy = x

quindi, grazie alla commutatività, abbiamo x = y.

3) transitività?.

Permettere X? A E sì?z quindi, per definizione,

(6) xy = x

(7) sì z= sì

Abbiamo X· z = (X· sì)· z X· (sì· z) xy X

COSÌ, X· z = X, questo è X?z.

Quindi, abbiamo CHUM<S ; ? >. Resta da dimostrare che per ogni ( UN,V)S esiste inf( AC}.

Prendiamo arbitrario UN,V S e dimostrare che l'elemento c = un bè inf( AC), cioè. Con= inf( AC}.

Infatti,

c un =(AC)·UN UN·(AC) (aa)· V a·b = c,

Quello. Con? UN.

Allo stesso modo, s·v =(AC)·V UN·(nel · nel) a·b = c,

quelli. Con? V.

COSÌ, Con- limite inferiore comune ( AC}.

Dimostriamo la sua accuratezza.

Permettere D- alcuni limiti inferiori comuni per UN E V:

(8) D? UN

(9)d? V

(10) d un = d

(11) d in =D

D· C = D· (AC) (D·UN)· V D·V D,

D· C = D, quindi, D ? C.

Conclusione: c = inf( UN,V}.

I teoremi 1 e 2 dimostrati ci permettono di guardare ai semireticoli da due punti di vista: come CUM e come in algebra (semigruppi commutativi idempotenti).

2. Insiemi ben ordinati

La teoria degli insiemi ordinati è stata formulata da G. Cantore . Shatunovsky . Hausdorff (1914).

Insiemi ben ordinati - Un insieme ordinato si dice ben ordinato se ciascuno dei suoi sottoinsiemi ha un primo elemento (cioè un elemento seguito da tutti gli altri). Tutti gli insiemi ordinati finiti sono completamente ordinati. La serie naturale, ordinata in ordine crescente (così come in altri modi), forma un insieme completamente ordinato. L'importanza degli insiemi completamente ordinati è determinata principalmente dal fatto che per essi vale il principio di induzione transfinita.

Gli insiemi ordinati che hanno lo stesso tipo ordinale hanno anche la stessa cardinalità, quindi possiamo parlare della cardinalità di un dato tipo ordinale. D'altra parte, insiemi ordinati finiti della stessa cardinalità hanno lo stesso tipo ordinale, quindi ciascuna cardinalità finita corrisponde a un certo tipo ordinale finito. La situazione cambia quando si passa a insiemi infiniti. Due insiemi ordinati infiniti possono avere la stessa cardinalità ma tipi di ordine diversi.

3. Gruppoidi parziali e loro proprietà

Come è noto, un'operazione algebrica binaria su un insieme Sè una mappatura da un quadrato cartesiano S?S. In questo caso, si dice che l'azione sia impostata su S. In questo paragrafo lo chiameremo pieno effetto.

Qualsiasi mappatura da un sottoinsieme S?S V S chiamato effetto parziale SU S. In altre parole, azione parziale Sè una funzione da S?S > S.

Si può dire così S viene specificata un'azione parziale (moltiplicazione parziale) se per qualsiasi elemento AC S lavoro AC né indefinito né definito in modo inequivocabile. In poche parole, non tutti gli elementi vengono moltiplicati qui.

Un mucchio di S con una moltiplicazione parziale specificata in esso viene chiamato gruppoide parziale ed è indicato con ( S ; · ) in contrasto con un gruppoide completo< S ; · >.

Se per un gruppoide completo possiamo parlare di una tabella Cayley, allora per un gruppoide parziale possiamo parlare di un analogo della tabella Cayley, vale a dire una tabella in cui alcune celle sono vuote - questo è il caso quando il prodotto degli elementi è indefinito.

Esempio 1.

	UN

UN· dentro = dentro, Ma V· UN non definito, cioè V· UN= O. Simbolo " O" non appartenere S, cioè. non è un elemento di S.

Esempio 2.

Consideriamo la peste ( S ; ? ).

S = {UN,V,C, D), Dove UN? UN, V? V, Con? Con, D ? D, Con? UN, Con? V, D? UN, D? V.

In una piaga arbitraria ( S ; ? ) concordiamo nel denotare:

UN V= inf( UN,V}.

Allora la piaga indicata nell'esempio rispetto a questa azione parziale è un gruppoide parziale ( S;), la cui tabella Cayley è la seguente

				D
UN
				D
	C
			-

In questa sezione esamineremo tre tipi di associatività: associatività forte, associatività media, associatività debole.

Definizione 1.

Gruppoide parziale ( S ; · ) è chiamato debolmente associativo , Se

(X,y,z S) (X· sì)· z O X·( sì· z) > (X· sì)· z= X·( sì· z) (*)

Definizione 2.

Gruppoide parziale ( S ; · ) è chiamato moderatamente associativo , Se

(X,y,z S) (X· sì)· z O sì· z > (X· sì)· z= X·( sì· z)

Definizione 3.

Gruppoide parziale ( S ; · ) è chiamato fortemente associativo , Se

(X,y,z S) [(X· sì)· z O X·( sì· z) O> (X· sì)· z= X·( sì· z)] (*)

Un gruppoide parziale fortemente associativo soddisfa le proprietà di associatività moderata e debole. Tuttavia, il contrario non è affatto necessario.

Esempio 3.

Dato UN = {UN, dentro, con). Impostiamolo su UN operazione parziale di moltiplicazione per “tavola parziale di Cayley”.

Otteniamo qualche gruppoide parziale. Controlliamo se il gruppoide è fortemente associativo.

Permettere ( X· sì)· z O Perché X UN, allora neanche x = c x = b

1) lascia x = c, Poi y = pollici y = c

a) lascia y = pollici, Poi z = UN

(Con· V)· UN O Con·( V· UN) definito

(Con· V)· un = c·( V· UN) l'uguaglianza è soddisfatta

b) lascia y = c, Poi z= pollici z=c

e se z= pollici, Poi

(Con· Con)· V O Con·( Con· V) definito

(Con· Con)· dentro = c·( Con· V) l'uguaglianza è soddisfatta

b") se z=c, Poi

(Con· Con)· Con O Con·( Con· Con) definito

(Con· Con)· c = c·( Con· Con) l'uguaglianza è soddisfatta

2) lascia x = b, Poi y = a, UN z= pollici z = C

e se y = a E z= pollici

(V· UN)· V O= pollici·( UN· V) non definito

(V· UN)· V V·( UN· V) l'uguaglianza non è soddisfatta

b) lascia y = a E z=c

(V· UN)· Con O= pollici·( UN· Con) non definito

(V· UN)· Con V·( UN· Con) l'uguaglianza non è soddisfatta

Quindi, per definizione, un gruppoide parziale non è fortemente associativo. Ma questo non significa che ( S ; · ) non è debolmente associativo.

Scopriamolo.

Permettere (X· sì)· z O X·( sì· z) O .

A X UN, A UN, vale a dire, quando

x = b x = c

y = pollici y = c

questo gruppoide parziale è debolmente associativo.

Esempio 4.

Permettere A ={UN, dentro, con), può essere impostato su UN la seguente tabella di Cayley. Otteniamo qualche gruppoide parziale. Controlliamo se questo gruppoide è moderatamente associativo.

Permettere ( X· sì)· z O Perché X V, Poi x = a x = c

1) lascia x = a, Poi y = a y = pollici

a) lascia y = a, Poi z = UN, z= pollici

e se z= un, Poi

(UN· UN)· UN O UN· UN definito

(UN· UN)· UN UN·( UN· UN) l'uguaglianza non è soddisfatta

b") se z= pollici, Poi

(UN· UN)· V O UN· V definito

(UN· UN)· V UN·( UN· V) l'uguaglianza non è soddisfatta

Quindi, vediamo che il gruppoide non è associativo medio. Scopri se è debolmente associativo.

Permettere ( X· sì)· z O X·( sì· z) O, Perché X V, Poi x = a x = c

1) lascia x = a, Poi y = a y = pollici

a) lascia y = a, Poi z = UN, z= pollici

e se z= un, Poi

(UN· UN)· UN O= un·( UN· UN) non definito

(UN· UN)· UN UN·( UN· UN)

b") se z= pollici, Poi

(UN· UN)· V O UN·( UN· V) definito

(UN· UN)· in = a·( UN· V) l'uguaglianza è soddisfatta

b) lascia y = pollici, Poi z = UN, z= pollici

e se z= un, Poi

(UN· V)· UN O= un·( V· UN) non definito

(UN· V)· UN UN·( V· UN)

b") se z= pollici, Poi

(UN· V)· V O UN·( V· V) non definito

(UN· V)· V UN·( V· V) l'uguaglianza non è soddisfatta

2) lascia x = c, Poi y = a,y = pollici

a) lascia y = a, Poi z = UN, z= pollici

e se z= un, Poi

(Con· UN)· UN O=c·( UN· UN) non definito

(Con· UN)· UN Con·( UN· UN) l'uguaglianza non è soddisfatta

b") se z= pollici, Poi

(Con· UN)· V O Con·( UN· V) definito

(Con· UN)· dentro = c·( UN· V) l'uguaglianza è soddisfatta

Quindi, vediamo che un gruppoide parziale è debolmente associativo per x = a E z= pollici o quando x = c Se y = a E z= pollici.

Definizione 4.

Gruppoide parziale ( S ; · ) è chiamato commutativo , Se

(X,sì S) X· sì = sì· X

Definizione 5.

Gruppoide parziale ( S ; · ) è chiamato catenaria , Se

(X,y,z S) (X· sì O sì· z) > [(X· sì)· z O X·( sì· z)]

Definizione 6.

Gruppoide parziale ( S ; · ) è chiamato idempotente , Se

(X S) X = X

Facciamo un esempio di gruppoide parziale non catenario.

Esempio 5.

				D
UN
				D
	C
			-

Abbiamo Con un = c O, UN D = D O. Tuttavia, ( Con UN) D = C D O. Pertanto, il CG indicato non è catenaria.

È chiaro cosa intendiamo con il termine “limite superiore comune” degli elementi UN E V qualche peste.

Definizione 7.

Si chiama peste categorico , se due qualsiasi dei suoi elementi che hanno un limite superiore hanno un limite inferiore esatto.

Esempio 6.

Esempio 7.

Un insieme parzialmente ordinato definito da una tabella Cayley:

Esempio 8.

Set parzialmente ordinato

avendo la seguente tabella Cayley:

				-
				-
				-

È chiaro che ogni semireticolo è una piaga categorica (ma non viceversa), perché due elementi qualsiasi hanno un minimo esatto. In altre parole, la classe di tutte le piaghe categoriche contiene la classe di tutti i semireticoli, ma non coincide con essa. Quello. ogni proposizione provata per le piaghe categoriali comporta come ovvia conseguenza un certo teorema riguardante i semireticoli.

Diamo esempi di semireticoli.

Esempio 9.

Diagramma:

chiamato diamante

				D
UN
			D
	C

Esempio 10.

Diagramma:

chiamato Pentagono, ed è definito da un semireticolo avente la seguente tabella di Cayley:

Esempio 11.

Il semireticolo definito dalla tabella Cayley:

ha uno schema:

Teorema 1.

Permettere ( S ; ? ) - peste categorica, quindi ( S;) - catenaria idempotente commutativa debolmente associativa gruppoide parziale.

Prova:

Per chiunque UN S Sempre

UN UN= inf( UN, UN} = UN quindi gruppoide parziale S idempotente.

Abbiamo UN V= inf( UN,V) = inf( V,UN} = V UN, e quindi S commutativo

Controlliamo l'associatività debole.

Permettere ( UN V) Con O UN (V Con) , denota

UN V = D, V Con = e, (UN V) Con= D Con = F, UN (V Con) = UN e= G

Dimostriamolo F = G.

Per definizione abbiamo F ? D ? UN F ? UN,

F ? D? V F? V (1)

F ? C (2)

Perché e= inf( dentro, con), allora da (1), (2) segue che F ? e. Quello. F - qualche limite inferiore comune per UN E e, UN G è il loro esatto minimo, quindi

F ? G (3)

Allo stesso modo,

G ? F (4)

Disuguaglianza (3), (4) e antisimmetria della relazione? fornire F = G. È stata dimostrata una debole associatività.

Controlliamo la catenaria S.

Permettere UN V O V Con, denota UN b = x, V Con = sì, da qui X? V, sì? V, cioè.

V- limite superiore comune X E A. Perché APPESTARE S categoricamente, allora esiste inf( x,y), cioè. esiste in S X A. Denotiamo X y = z, lo mostreremo

UN (V Con) = X Con= z. Abbiamo z ? X, z ? sì (Perché z = inf( x,y}), sì ? z z ? X, z ? C,

z - bordo inferiore per X E Con.

Garantiremo la precisione.

Permettere T ? X , T ? C (T- qualsiasi limite inferiore), perché T ? X , Quello T ? UN, T? V, per condizione T? Con, cioè. T- limite inferiore comune per V E Con. Ne consegue per definizione A, T ? sì.

COSÌ, T ? X, T? A quindi T ? z (a-prior z).

La catenaria è stata dimostrata.

Teorema 2.

Se ( S ; · ) è un gruppoide parziale catenaria idempotente commutativa debolmente associativa, quindi la relazione

? = (AC) S?S (2)

È una relazione d'ordine. Allo stesso tempo, PESTE<S ; ? > - è catenaria.

Prova:

Dimostriamo la riflessività della relazione? . Perché gruppoide parziale S Idem-tenten, quindi UN· UN = UN quindi, per definizione (2) UN? UN.

Controlliamo l'antisimmetria.

Se UN? dentro, dentro? UN, Quello а·в = а, в·а = в, i lati sinistri sono uguali per commutatività, il che significa che i lati destri sono uguali, quindi un = b.

Resta da dimostrare la transitività.

Permettere UN? V, V? Con, Poi a·b = a, vs = pollici, а·с =(AC)· Con. A causa della catenaria abbiamo ( UN· V)· Con O , UN·( V· Con) O, quindi a causa della debole associatività

(AC)·c = un·(contro s), e quindi, a·c = a·(contro s) = a·b = a.

COSÌ, a·c = a, cioè. UN? Con.

Quello. abbiamo una piaga<S ; ? > .

Permettere z- limite superiore comune per X E A. Quindi, X?z, sì ? z, da qui X·z = X, sì· z = sì, Poi z· sì = sì. A causa della catenaria ( X· sì)· z O X· sì O.

Denotiamo xy =S, dimostriamolo S bordo inferiore esatto.

Abbiamo S· X = (X· sì)· X = X· (X· sì) = (X· X)· sì = X· sì = S (a causa della catenaria e della debole associatività), quindi, S ? X, cioè. S- limite inferiore comune.

Da questi teoremi discendono due corollari ben noti nella teoria dei semireticoli.

Corollario 1.

Se<S ; · > è un semigruppo commutativo idempotente, allora la relazione? , definito dall'uguaglianza (2), è un ordine parziale. Inoltre, per due elementi qualsiasi in S esiste un limite inferiore esatto.

Corollario 2.

Se<S ; · > è un insieme parzialmente ordinato in cui esiste un minimo di due elementi qualsiasi, quindi rispetto all'operazione

UN V= inf( UN,V} (3)

un mucchio di Sè un semigruppo commutativo idempotente.

CONCLUSIONE

In conclusione, si può notare che la teoria degli insiemi ordinati è stata creata da G. Cantore . Nel 1883 introdusse il concetto di insieme completamente ordinato e di numero ordinale, e nel 1895 il concetto di insieme ordinato e di tipo ordinale. Nel 1906-07 S.O. Shatunovsky formulò le definizioni di un insieme diretto (in Shatunovsky - un complesso localizzato) e il limite su un insieme diretto (dai matematici americani E . G. Moore e G. L. Smith considerarono questi stessi concetti indipendentemente da Shatunovsky, ma molto più tardi - nel 1922). Il concetto generale di insieme parzialmente ordinato appartiene a F. Hausdorff (1914).

Pertanto, la teoria delle azioni algebriche parziali, essendo una continuazione della teoria delle azioni complete, sfruttando i suoi risultati, ad essa associati idee ed esperienza di applicazioni al di fuori dell'algebra, dovrebbe ancora formarsi come una direzione indipendente nel vasto campo di algebra moderna.

Ad oggi sono stati pubblicati centinaia di lavori specificatamente dedicati allo studio delle azioni parziali. Per quanto riguarda le opere in cui si verificano alcune azioni parziali nel corso dello studio, il loro numero non può essere stimato. Le azioni parziali vengono trattate anche in alcune opere di algebrica generale, ma sempre molto brevemente.

Bibliografia

A.K. Clifford, G. Preston. Teoria algebrica dei semigruppi. 1972.

Greitzer. Teoria generale dei reticoli Mosca.-284 p.

Kozhevnikov O.B. Insiemi parzialmente ordinati di gruppoidi parziali. Mosca, 1998. - 680.

E.S. Lyapin. Semigruppi. Mosca: Fizmat, 1960.- 354 p.

Lyapin E.S. Algebra e teoria dei numeri. Mosca, 1980.-589p.

Come sai, l'insieme dei numeri naturali può essere ordinato utilizzando la relazione “minore di”. Ma le regole per costruire una teoria assiomatica richiedono che questa relazione non sia solo definita, ma anche fatta sulla base di concetti già definiti in questa teoria. Questo può essere fatto definendo la relazione “minore di” attraverso l’addizione.

Definizione. Il numero a è inferiore al numero b (a< b) тогда и только тогда, когда существует такое натуральное число с, что а + с = B.

In queste condizioni si dice anche che il numero B Di più UN e scrivi b > a.

Teorema 12. Per qualsiasi numero naturale UN E B vale una ed una sola delle tre relazioni: a = b, a > b, UN < B.

Omettiamo la dimostrazione di questo teorema.. Da questo teorema segue che se

a¹b, O UN< b, O a > b, quelli. la relazione “meno” ha la proprietà della connessione.

Teorema 13. Se UN< b E B< с. Quello UN< с.

Prova. Questo teorema esprime la proprietà di transitività della relazione “minore di”.

Perché UN< b E B< с. quindi, per la definizione della relazione “minore di”, ci sono i numeri naturali A E allora b = a + k e c = b + I. Ma allora c = (a + k)+ / e in base alla proprietà di associatività dell'addizione otteniamo: c = a+(k+/). Perché il k + io - numero naturale, quindi, secondo la definizione di “minore di”, UN< с.

Teorema 14. Se UN< b, non è vero questo B< а. Prova. Questo teorema esprime la proprietà antisimmetria rapporto "meno".

Dimostriamolo prima per nessun numero naturale UN non tu-!>! ■ )il suo atteggiamento UN< UN. Supponiamo il contrario, cioè Che cosa UN< а si verifica. Quindi, per la definizione della relazione “minore di”, esiste un numero naturale Con, Che cosa UN+ Con= UN, e questo contraddice il Teorema 6.

Dimostriamo ora che se UN< B, allora non è vero B < UN. Supponiamo il contrario, cioè cosa succede se UN< b , Quello B< а eseguita. Ma da queste uguaglianze, per il Teorema 12 abbiamo UN< а, il che è impossibile.

Poiché la relazione “minore di” da noi definita è antisimmetrica e transitiva e possiede la proprietà di connessione, è una relazione di ordine lineare, e l’insieme dei numeri naturali insieme ordinato linearmente.

Dalla definizione di “minore di” e dalle sue proprietà si possono dedurre le proprietà conosciute dell'insieme dei numeri naturali.

Teorema 15. Di tutti i numeri naturali, uno è il numero più piccolo, cioè IO< а для любого натурального числа a¹1.

Prova. Permettere UN - qualsiasi numero naturale. Allora sono possibili due casi: un = 1 e a¹ 1. Se un = 1, allora esiste un numero naturale B, seguito da a: a = b " = b + io = 1+ B, cioè, per definizione della relazione “minore di”, 1< UN. Pertanto, qualsiasi numero naturale è uguale a 1 o maggiore di 1. Oppure, uno è il numero naturale più piccolo.

La relazione “minore di” è associata all'addizione e alla moltiplicazione dei numeri per le proprietà della monotonicità.

Teorema 16.

a = b => a + c = b + c e a c = b c;

UN< b =>a+c< b + с и ас < bс;

a > b => a + c > b + c e ac > bc.

Prova. 1) La validità di questa affermazione deriva dall'unicità dell'addizione e della moltiplicazione.

2) Se UN< b, allora esiste un numero così naturale K, Che cosa UN + k = b.
Poi B+ c = (a + k) + c = a + (k + c) = a + (c+ A)= (a+c)+k. Uguaglianza B+ c = (a + c) + k significa che a+c< b + Con.

Allo stesso modo è dimostrato UN< b =>AC< bс.

3) La dimostrazione è simile.

Teorema 17(il contrario del Teorema 16).

1) UN+ c = b + c O ac ~ bc-Þ un = b

2) a+c< Ь + с O AC< avanti CristoÞ UN< Ь:

3) a + c > b+ con o ac > acÞ a > b.

Prova. Proviamo, ad esempio, che da AC< bс Dovrebbe UN< b Supponiamo il contrario, cioè che la conclusione del teorema non regge. Allora non può essere quello un = b. da allora l'uguaglianza sarebbe soddisfatta ac = ac(Teorema 16); non può essere UN> B, perché allora lo sarebbe ac > bñ(Teorema!6). Pertanto, secondo il Teorema 12, UN< b.

Dai Teoremi 16 e 17 possiamo derivare le ben note regole per l'addizione e la moltiplicazione termine per termine delle disuguaglianze. Li lasciamo fuori.

Teorema 18. Per qualsiasi numero naturale UN E B; esiste un numero naturale n tale che p b> a.

Prova. Per chiunque UN c'è un tale numero P, Che cosa n > a. Per fare questo è sufficiente prendere n = un+ 1. Moltiplicare le disuguaglianze termine per termine P> UN E B> 1, otteniamo pb > UN.

Dalle proprietà considerate della relazione “minore di” seguono importanti caratteristiche dell'insieme dei numeri naturali, che presentiamo senza dimostrazione.

1. Non per nessun numero naturale UN non esiste un numero naturale del genere P, Che cosa UN< п < а + 1. Questa proprietà si chiama proprietà
discrezione insiemi di numeri naturali e numeri UN E un+ 1 è chiamato limitrofo.

2. Qualsiasi sottoinsieme non vuoto di numeri naturali contiene
numero più piccolo.

3. Se M- sottoinsieme non vuoto dell'insieme dei numeri naturali
e c'è un tale numero B, quello per tutti i numeri x da M non eseguito
uguaglianza x< B, poi in abbondanza Mè il numero più grande.

Illustriamo le proprietà 2 e 3 con un esempio. Permettere M- un insieme di numeri a due cifre. Perché Mè un sottoinsieme di numeri naturali e per tutti i numeri in questo insieme la disuguaglianza x< 100, то в множестве Mè il numero più grande 99. Il numero più piccolo contenuto in un dato insieme M, - numero 10.

Pertanto, la relazione “minore di” ha permesso di considerare (e in alcuni casi dimostrare) un numero significativo di proprietà dell’insieme dei numeri naturali. In particolare, è ordinato linearmente, discreto e ha il numero più piccolo 1.

Gli scolari della scuola primaria vengono introdotti alla relazione “minore di” (“maggiore di”) per i numeri naturali fin dall'inizio della loro istruzione. E spesso, insieme alla sua interpretazione teorica degli insiemi, viene utilizzata implicitamente la definizione da noi data nel quadro della teoria assiomatica. Ad esempio, gli studenti possono spiegare che 9 > 7 perché 9 è 7+2. È comune anche l'uso implicito delle proprietà di monotonicità dell'addizione e della moltiplicazione. Ad esempio, i bambini spiegano che “6 + 2< 6 + 3, так как 2 < 3».

Esercizi

1, Perché l’insieme dei numeri naturali non può essere ordinato utilizzando la relazione “segui immediatamente”?

Definire l'atteggiamento a > b e dimostrare che è transitiva e antisimmetrica.

3. Dimostrare che se a, b, c sono numeri naturali, allora:

UN) UN< b Þ ас < bс;

B) UN+ Con< b + сÞ> UN< Ь.

4. Quali teoremi sulla monotonicità dell'addizione e della moltiplicazione possono
utilizzo da parte degli scolari più piccoli durante il completamento dell'attività "Confronta senza eseguire calcoli":

a) 27 + 8 ... 27 + 18;

b) 27-8...27-18.

5. Quali proprietà dell'insieme dei numeri naturali vengono utilizzate implicitamente dagli scolari primari quando eseguono i seguenti compiti:

A) Annota i numeri maggiori di 65 e minori di 75.

B) Nominare i numeri precedenti e successivi in ​​relazione al numero 300 (800.609.999).

C) Nomina il numero di tre cifre più piccolo e quello più grande.

Sottrazione

Nella costruzione assiomatica della teoria dei numeri naturali, la sottrazione è solitamente definita come l'operazione inversa dell'addizione.

Definizione. La sottrazione dei numeri naturali aeb è un'operazione che soddisfa la condizione: a - b = c se e solo se b + c = a.

Numero un-b si chiama differenza tra i numeri a e B, numero UN– minuendo, numero B- deducibile.

Teorema 19. Differenza dei numeri naturali UN- B esiste se e solo se B< а.

Prova. Lascia che la differenza UN- B esiste. Quindi, per definizione di differenza, esiste un numero naturale Con, Che cosa b + c = un, che significa che B< а.

Se B< а, allora, per la definizione della relazione “minore di”, esiste un numero naturale c tale che b + c = a. Quindi, per definizione della differenza, c = un - b, quelli. differenza un-b esiste.

Teorema 20. Se la differenza dei numeri naturali UN E B esiste, allora è unico.

Prova. Supponiamo che ci siano due diversi valori della differenza tra numeri UN E B;: a – b= s₁ E un-b= s₂, E s₁ ¹ s₂ . Quindi, per definizione di differenza, abbiamo: a = b + c₁, E a = b + c₂ : . Ne consegue che B+ c₁ = b + c₂ : e sulla base del Teorema 17 concludiamo, с₁ = с₂.. Siamo arrivati ​​​​a una contraddizione con l'ipotesi, il che significa che è falsa, ma questo teorema è corretto.

Sulla base della definizione della differenza dei numeri naturali e delle condizioni per la sua esistenza, è possibile giustificare le note regole per sottrarre un numero da una somma e una somma da un numero.

Teorema 21. Permettere UN. B E Con- numeri interi.

e se a > c, allora (a + b) - c = (a - c) + b.

b) Se b > c. quindi (a + b) - c - a + (b - c).

c) Se a > c e b > c. quindi puoi utilizzare una qualsiasi di queste formule.
Prova. Nel caso a) la differenza di numeri UN E C esiste perché a > s. Indichiamolo con x: a - c = x. Dove a = c+x. Se (UN+ b) - c = y. quindi, per definizione della differenza, UN+ B = Con+ A. Sostituiamo invece questa uguaglianza UN espressione c+x:(c + x) + b = c + y. Usiamo la proprietà di associatività dell'addizione: c + (x + b) = c+ A. Trasformiamo questa uguaglianza in base alla proprietà di monotonicità dell'addizione e otteniamo:

x+b = tu..Sostituendo x in questa uguaglianza con l'espressione AC, avrà (UN - G) + b = y. Pertanto, abbiamo dimostrato che se a > c, allora (a + b) - c = (a - c) + b

La dimostrazione si svolge analogamente nel caso b).

Il teorema dimostrato può essere formulato sotto forma di una regola comoda da ricordare: per sottrarre un numero da una somma, è sufficiente sottrarre questo numero da un termine della somma e aggiungere un altro termine al risultato risultante.

Teorema 22. Permettere a, b e c - numeri interi. Se a > b+s, allora UN- (b + c) = (a - b) - c O un - (b + c) = (a - c) - b.

La dimostrazione di questa teoria è simile alla dimostrazione del Teorema 21.

Il Teorema 22 può essere formulato come regola: per sottrarre la somma dei numeri da un numero, è sufficiente sottrarre da questo numero ogni termine uno per uno.

Nell'insegnamento della matematica primaria, la definizione di sottrazione come inverso dell'addizione, di regola, non è data in forma generale, ma viene costantemente utilizzata, a partire dall'esecuzione di operazioni su numeri a una cifra. Gli studenti dovrebbero comprendere chiaramente che la sottrazione è correlata all'addizione e utilizzare questa relazione nei calcoli. Sottraendo, ad esempio, il numero 16 dal numero 40, gli studenti ragionano così: “Sottrarre il numero 16 da 40 significa trovare un numero tale che sommato al numero 16, il risultato è 40; questo numero sarà 24, poiché 24 + 16 = 40. Quindi. 40 - 16 = 24."

Le regole per sottrarre un numero da una somma e una somma da un numero in un corso iniziale di matematica costituiscono la base teorica per varie tecniche di calcolo. Ad esempio, il valore dell'espressione (40 + 16) - 10 può essere trovato non solo calcolando la somma tra parentesi e poi sottraendo da essa il numero 10, ma anche in questo modo;

a) (40 + 16) - 10 = (40 - 10) + 16 = 30 + 16 = 46:

b) (40 + 16) - 10 = 40 + (16- 10) = 40 + 6 = 46.

Esercizi

1. È vero che ogni numero naturale si ottiene da quello immediatamente successivo sottraendo uno?

2. Cosa c'è di speciale nella struttura logica del Teorema 19? Si può formulare con le parole “necessario e sufficiente”?

3. Dimostrare che:

e se b > c, Quello (a + b) - c = a + (b - c);

b) se a > b + c, Quello un - (b+ c) = (a-b)-c.

4. È possibile, senza eseguire calcoli, dire quali espressioni avranno gli stessi valori:

a) (50+16)-14; d) 50 + (16 -14 ),

b) (50 - 14) + 16; e) 50 - (16 - 14);
c) (50 - 14) - 16, f) (50 + 14) - 16.

a) 50 - (16 + 14); d) (50 - 14) + 16;

b) (50 - 16) + 14; e) (50 - 14) - 16;

c) (50 - 16) - 14; e) 50 - 16-14.

5. Quali proprietà della sottrazione sono la base teorica per le seguenti tecniche di calcolo studiate nel corso iniziale di matematica:

12 - 2-3 12 -5 = 7

b) 16-7 = 16-6 - P;

c) 48 - 30 = (40 + 8) - 30 = 40 + 8 =18;

d) 48 - 3 = (40 + 8) - 3 = 40 + 5 = 45.

6. Descrivere possibili modi per valutare il valore di un'espressione della forma. un-b- Con e illustrarli con esempi specifici.

7. Dimostralo quando B< а e qualsiasi c naturale l'uguaglianza è vera (a – b) c = ac - bc.

Nota. La dimostrazione si basa sull’assioma 4.

8. Determinare il valore di un'espressione senza eseguire calcoli scritti. Motiva le tue risposte.

a) 7865 × 6 – 7865 ×5: b) 957 × 11 – 957; c) 12×36 – 7×36.

Divisione

Nella costruzione assiomatica della teoria dei numeri naturali, la divisione è solitamente definita come l'operazione inversa della moltiplicazione.

Definizione. La divisione dei numeri naturali a e b è un'operazione che soddisfa la condizione: a: b = c se e solo se A quando b× c = a.

Numero a:b chiamato privato numeri UN E B, numero UN divisibile, numero B- divisore.

Come è noto, non sempre esiste la divisione sull'insieme dei numeri naturali, e non esiste un segno così conveniente dell'esistenza di un quoziente come esiste per una differenza. Esiste solo una condizione necessaria per l'esistenza del particolare.

Teorema 23. Affinché ci sia un quoziente di due numeri naturali UN E B, è necessario che B< а.

Prova. Sia il quoziente dei numeri naturali UN E B esiste, cioè esiste un numero naturale c tale che ac = a. Poiché per ogni numero naturale 1 la disuguaglianza 1 £ Con, quindi moltiplicando entrambe le sue parti per un numero naturale B, noi abbiamo B£ avanti Cristo. Ma bc = un, quindi, B£ UN.

Teorema 24. Se il quoziente dei numeri naturali UN E B esiste, allora è unico.

La dimostrazione di questo teorema è simile alla dimostrazione del teorema sull'unicità della differenza dei numeri naturali.

Sulla base della definizione del quoziente dei numeri naturali e delle condizioni per la sua esistenza, è possibile giustificare le note regole per dividere una somma (differenza, prodotto) per un numero.

Teorema 25. Se i numeri UN E B divisibile per un numero Con, poi la loro somma a+b diviso per c, e il quoziente ottenuto dividendo la somma UN+ B per numero Con, pari alla somma dei quozienti ottenuti dividendo UN SU Con E B SU Con, cioè. (a+b):c = a:c + b:Con.

Prova. Dal numero UN diviso per Con, allora esiste un numero naturale x = UN;è così a = cx. Allo stesso modo, esiste un numero così naturale y = b:Con, Che cosa

B= su. Ma allora a + b = cx+ cy = - c(x + y). Significa che a+bè diviso per c, e il quoziente ottenuto dividendo la somma UN+ B dal numero c, pari a x + sì, quelli. ascia + b: c.

Il teorema dimostrato può essere formulato come regola per dividere una somma per un numero: per dividere la somma per un numero è sufficiente dividere ogni termine per questo numero e sommare i risultati risultanti.

Teorema 26. Se numeri naturali UN E B divisibile per un numero Con E a > b, poi la differenza un-bè diviso per c, e il quoziente ottenuto dividendo la differenza per il numero c è uguale alla differenza dei quozienti ottenuti dividendo UN SU Con E B su c, cioè (a - b):c = a:c - b:c.

La dimostrazione di questo teorema è simile alla dimostrazione del teorema precedente.

Questo teorema può essere formulato come regola per dividere la differenza per un numero: Per Per dividere la differenza per un numero basta dividere il minuendo e il sottraendo per questo numero e sottrarre il secondo dal primo quoziente.

Teorema 27. Se un numero naturale UNè divisibile per un numero naturale c, quindi per qualsiasi numero naturale B lavoro ab diviso per s. In questo caso il quoziente ottenuto dividendo il prodotto ab al numero s , uguale al prodotto del quoziente ottenuto dividendo UN SU Con, enumeri b: (a × b):c - (a:c) × b.

Prova. Perché UN diviso per Con, allora esiste un numero naturale x tale che AC= x, dove a = cx. Moltiplicando entrambi i membri dell'uguaglianza per B, noi abbiamo ab = (cx)b. Poiché la moltiplicazione è associativa, allora (cx)b = c(xb). Da qui (a b):c = x b= (a:c) b. Il teorema può essere formulato come regola per dividere un prodotto per un numero: per dividere un prodotto per un numero è sufficiente dividere uno dei fattori per questo numero e moltiplicare il risultato risultante per il secondo fattore.

Nell'educazione matematica elementare, la definizione di divisione come operazione inversa di moltiplicazione, di regola, non viene data in forma generale, ma viene costantemente utilizzata, a partire dalle prime lezioni di familiarità con la divisione. Gli studenti dovrebbero comprendere chiaramente che la divisione è correlata alla moltiplicazione e utilizzare questa relazione quando eseguono i calcoli. Nel dividere, ad esempio, 48 per 16, gli studenti ragionano così: “Dividere 48 per 16 significa trovare un numero che, moltiplicato per 16, dia 48; tale numero sarebbe 3, poiché 16×3 = 48. Pertanto, 48: 16 = 3.

Esercizi

1. Dimostrare che:

a) se il quoziente dei numeri naturali aeb esiste, allora è unico;

b) se i numeri aeb sono divisi in Con E a > b, Quello (a - b): c = a: c - b: c.
2. È possibile dire che tutte queste uguaglianze sono vere:
a) 48:(2×4) = 48:2:4; b) 56:(2×7) = 56:7:2;

c) 850:170 =850:10:17.

Quale regola generalizza questi casi? Formulatelo e dimostratelo.

3. Quali proprietà della divisione costituiscono la base teorica
portare a termine i seguenti compiti offerti agli studenti della scuola primaria:

È possibile, senza eseguire la divisione, dire quali espressioni avranno gli stessi valori:

a) (40+8):2; c) 48:3; e) (20+28):2;

b) (30+16):3; g)(21+27):3; f) 48:2;

Le uguaglianze sono vere:

a) 48:6:2 = 48:(6:2); b) 96:4:2 = 96:(4-2);

c) (40 - 28): 4 = 10-7?

4. Descrivere i possibili modi per calcolare il valore di un'espressione
tipo:

UN) (UN+ avanti Cristo; B) UN:B: Con; V) ( a×b): Con .

Illustrare i metodi proposti con esempi specifici.

5. Trovare il significato dell'espressione in modo razionale; loro
giustifica le tue azioni:

a) (7 × 63):7; c) (15 × 18):(5× 6);

b) (3 × 4× 5): 15; d) (12 × 21): 14.

6. Giustificare i seguenti metodi di divisione per un numero a due cifre:

a) 954:18 = (900 + 54): 18 = 900:18 + 54:18 =50 + 3 = 53;

b) 882:18 = (900 - 18): 18 = 900:18 - 18:18 = 50 - 1 =49;

c) 480:32 = 480: (8 × 4) = 480:8:4 = 60:4 = 15:

d) (560 × 32): 16 = 560(32:16) = 560×2 = 1120.

7. Senza dividere con un angolo, trova il più razionale
in modo quoziente; Giustificare il metodo scelto:

a) 495:15; c) 455:7; e) 275:55;

6) 425:85; d) 225:9; e) 455:65.

Lezione 34. Proprietà dell'insieme degli interi non negativi

1. L'insieme degli interi non negativi. Proprietà dell'insieme degli interi non negativi.

2. Il concetto di segmento di una serie naturale di numeri ed elementi di conteggio di un insieme finito. Numeri naturali ordinali e cardinali.

Quando abbiamo introdotto le operazioni con i superset, non abbiamo tenuto conto del fatto che gli insiemi stessi possono avere una propria struttura interna, cioè abbiamo presupposto che tutti gli elementi dell'insieme fossero uguali. Tuttavia, in matematica tali insiemi “puri” sono di scarso interesse, e molto più spesso vengono studiati insiemi, tra i cui elementi ci sono alcuni relazione . Una delle relazioni più importanti tra gli elementi di un insieme è relazione d'ordine .

Relazione d'ordine non è altro che, di regola, stabilire l'ordine di “sequenza” degli elementi dell'insieme.

Permettere UN- alcuni sistemati, impostati UN chiamato insieme ordinato , se per due qualsiasi dei suoi elementi un, bè installato uno dei seguenti rapporti d'ordine :

O a ≤ b (UN non eccede B),

O b ≤ a (B non eccede UN),

avente le seguenti proprietà:

1) riflessività:

nessun elemento è superiore a se stesso;

2) antisimmetria:

Se UN non eccede B, UN B non eccede UN, poi gli elementi UN E B abbinare;

3) transitività:

Se UN non eccede B,UN B non eccede Con, Quello UN non eccede Con.

Si è convenuto che il set vuoto fosse considerato ordinato. Nella definizione di cui sopra di un insieme ordinato, i cui elementi possono essere oggetti di qualsiasi natura, il segno ≤ si legge “non eccede”. Questo segno (come il segno “minore o uguale”) acquista la sua lettura e significato abituali nel caso in cui gli elementi dell'insieme UN- numeri.

Due insiemi composti dagli stessi elementi, ma con rapporti d'ordine diversi, sono considerati insiemi ordinati diversi.

Lo stesso set può essere ordinato in diversi modi, ottenendo così set ordinati diversi.

Esempio

Consideriamo un insieme i cui elementi sono vari poligoni convessi: triangolo, quadrilatero, pentagono, esagono, ecc. Un modo per formare un insieme ordinato da un dato insieme non ordinato potrebbe, ad esempio, essere quello di prendere un triangolo come primo elemento dell'insieme ordinato , il secondo è un quadrilatero, il terzo è un pentagono, ecc., cioè disponiamo l'insieme in ordine crescente in base al numero di angoli interni dei poligoni. L'insieme dei poligoni può essere ordinato in altro modo, ad esempio elencando i poligoni in ordine crescente di area, quando si seleziona per primo il poligono con area più piccola, quello con area non superiore a quella di tutti altri tranne quello già selezionato viene selezionato come secondo, ecc.

Gli insiemi ordinati (finiti o numerabili) sono spesso scritti disponendo i loro elementi in un dato ordine tra parentesi.

Esempio

Le notazioni (1; 2; 3) e (2; 1; 3) rappresentano diversi insiemi finiti ordinati che possono essere ottenuti dallo stesso insieme (1; 2; 3) ordinandolo in due modi diversi.

Per scrivere un insieme ordinato numerabile, è necessario indicare il primo elemento dell'insieme ordinato e indicare l'ordine (regola) di disposizione degli elementi successivi.

Set ordinati

Definizione 1. Un mucchio di M chiamato ordinato, se si stabilisce qualche relazione tra i suoi elementi UN B(" UN preceduto B"), avente le seguenti proprietà: 1) tra due elementi qualsiasi UN E B esiste una ed una sola delle tre relazioni: UN = B, UN B, B UN; 2) per tre elementi qualsiasi UN, B E C da UN B, B segue c UN C.

Un insieme vuoto è considerato ordinato.

Commento. Intendiamo sempre il segno = nel senso di identità, coincidenza di elementi. Documentazione UN = B significa semplicemente che in lettere UN E B denota lo stesso elemento dell'insieme M. Pertanto dalla proprietà 1) segue che tra due elementi diversi vale una ed una sola delle due relazioni UN b o B UN.

Se UN preceduto B, poi lo dicono B segue UN e scrivi: B > UN.

Atteggiamento UN > B Ha, come è facilmente verificabile, proprietà simili a 1) e 2). Può essere preso come principale, definendo poi attraverso di esso la relazione UN B.

Se in un set ordinato M cambiare i ruoli della relazione, cioè invece UN b scrivere UN > B, e viceversa, otteniamo un nuovo insieme ordinato M", il cui ordine si dice inverso all'ordine M. Ad esempio, per l'ordine sopra riportato nell'insieme dei numeri naturali, l'ordine verrà invertito:

Due insiemi ordinati composti dagli stessi elementi, ma disposti in ordini diversi, sono considerati diversi. Pertanto, quando si definisce un insieme ordinato attraverso i suoi elementi, è necessario indicarne l'ordine. Assumeremo che la notazione da sinistra a destra corrisponda all'ordine degli elementi e manterremo la notazione precedente con parentesi graffe. Lo stesso set può essere ordinato in diversi modi (se contiene almeno due elementi). Pertanto, l'insieme dei numeri naturali può essere ordinato nel modo consueto o in ordine inverso; i numeri dispari possono essere anteposti ai numeri pari o viceversa, disponendoli entrambi in ordine ascendente o discendente. Otteniamo insiemi ordinati