Crea sito

A L G E B R A    A S T R A T T A

 

 

Le relazioni : Elementi di terminologia

Le relazioni : Grafi (non di rappresentazione) e relazioni

  Relazione associata ad un grafo .

  Immagine della relazione.

  Controimmagine della relazione.

  Eguaglianza tra relazioni .

  Casi particolari di relazioni .

  Le possibili proprietà di una relazione .

Le relazioni : Grafi (di rappresentazione). Alberi.

  Nozioni presupposte : Strutture

  Nozioni presupposte : Strutture multisorte

  Grafi ed alberi

Le relazioni : Le prime compatibilità

  Compatibilità di una relazione con la inclusione.

  Compatibilità di una relazione con la unione.

  Incompatibilità di una relazione con l'intersezione.

  Incompatibilità di una relazione con la complementazione.

Le relazioni : Prodotto per applicazione successiva. Prodotto cartesiano. Unione di due relazioni.

Le relazioni : Relazioni in un insieme

  Relazioni interne ad un insieme.

  Le possibili proprietà di una relazione in un insieme I.

  Relazione indotta.

Le relazioni : La relazione di preordine e di ordine. Il lemma di Zorn.

  Le definizioni di Mendelson e quelle degli altri autori

  Confronto di terminologia ordinata per autori

  Confronto di terminologia ordinata per termini

  Proprietà della relazione di ordine. Ordine totale e parziale. Compatibilità della relazione di ordine con altre relazioni.

  Elementi particolari in insiemi ordinati. Insiemi ben ordinati. Reticoli. Poset.

  Il lemma di Zorn

  Nozioni varie alla rinfusa.

Le relazioni>Le relazioni di equivalenza

  Relazione di equivalenza.

  Classe di equivalenza.

  Proprietà delle classi di equivalenza.

  Insieme quoziente.

  Proprietà degli elementi di I/ρ.

  Proiezione canonica.

  Proprietà della proiezione canonica.

  Uguaglianza tra relazioni di equivalenza.

  Finezza delle relazioni di equivalenza.

  Relazione indotta da una relazione di equivalenza.

  Proprietà della relazione indotta da una relazione di equivalenza.

Le relazioni>La relazione di eguaglianza

Le funzioni>Dizionario

Le funzioni>Generali

  Le funzioni composte

Le funzioni>Decomposizione canonica di una funzione

Le funzioni>Compatibilità di una funzione con due relazioni di equivalenza: funzione associata tra i quozienti.

Le funzioni>Compatibilità di una relazione con una relazione di equivalenza: la relazione quoziente

Le funzioni>Le relazioni di preordine e di ordine. Grafi ed Alberi delle relazioni di ordine. Buon ordine

Teoria  dei numeri

Operazioni e strutture>Le strutture in generale

  Strutture

  Strutture multisorte

Operazioni e strutture>La nozione di operazione interna

Operazioni e strutture>Le operazioni esterne

Operazioni e strutture>Operazioni n-arie generate da una operazione binaria interna

Operazioni e strutture>Principali proprietà di operazioni binarie interne

Operazioni e strutture>Classificazione delle proprietà delle operazioni binarie

Operazioni e strutture>Strutture algebriche

Operazioni e strutture>Sottoinsiemi stabili. Struttura algebrica indotta.

Operazioni e strutture>Similitudine tra strutture algebriche

Operazioni e strutture>Compatibilità di una funzione con operazioni corrispondenti: morfismi

Operazioni e strutture>Compatibilità di una relazione di equivalenza con una struttura: struttura quoziente

Operazioni e strutture>Decomposizione canonica di un morfismo. Teorema fondamentale.

Operazioni e strutture>Morfismo indotto tra i quozienti in presenza di più compatibilità

Operazioni e strutture>Prodotto di strutture algebriche

Operazioni e strutture > Funtori. Elementi universali (Mac Lane-Birkhoff)

Operazioni e strutture > Categorie concrete (Mac Lane-Birkhoff)

Semigruppi e monoidi>Semigruppi: definizione e prime proprietà

Semigruppi e monoidi>Sottosemigruppi

Semigruppi e monoidi>Omomorfismi tra semigruppi

Semigruppi e monoidi>Semigruppo quoziente. Prodotto di semigruppi

Semigruppi e monoidi>Semigruppi liberi

Semigruppi e monoidi>Monoidi: definizioni e e prime proprietà

Semigruppi e monoidi>Sottomonoidi

Semigruppi e monoidi > Omomorfismi tra monoidi

Semigruppi e monoidi > Monoide quoziente. Prodotto di monoidi. Monoidi liberi

Gruppi > Definizione e prime proprietà dei gruppi

Gruppi > Relazioni di definizione (Mac Lane-Birkhoff)

Gruppi > Esempi di gruppi

Gruppi > Sottogruppi

Gruppi > Intersezione e unione di sottogruppi di un gruppo

Gruppi > Omomorfismi tra gruppi

Gruppi > Prima definizione di gruppo quoziente

Gruppi > Laterali di un sottogruppo

Gruppi > Sottogruppi normali di un gruppo

Gruppi > Seconda definizione di gruppo quoziente. Equivalenza delle due definizioni

Gruppi > Teoremi sugli omomorfismi

Gruppi > Gruppi ciclici

Gruppi > Gruppi finiti

Gruppi > Gruppi di trasformazioni

Gruppi > Endomorfismi e automorfismi di un gruppo

Gruppi > Prodotti diretti e somme dirette di gruppi

Gruppi > Successioni esatte di gruppi e omomorfismi

Gruppi > Gruppi liberi

Gruppi > Il teorema di Jordan-Hölder

Gruppi > La categoria dei gruppi (Mac Lane-Birkhoff)

Anelli, domini di integrità, corpi, campi > Definizione di anello e prime proprietà

Anelli, domini di integrità, corpi, campi > Esempi di anelli

Anelli, domini di integrità, corpi, campi > Caratteristica di un anello

Anelli, domini di integrità, corpi, campi > Formula del binomio

Anelli, domini di integrità, corpi, campi > Sottoanelli

Anelli, domini di integrità, corpi, campi > Omomorfismi tra anelli

Anelli, domini di integrità, corpi, campi > Prima definizione di anello quoziente

Anelli, domini di integrità, corpi, campi > Ideali in un anello

Anelli, domini di integrità, corpi, campi > Seconda definizione di anello quoziente. Equivalenza delle due definizioni.

Anelli, domini di integrità, corpi, campi > Teoremi sugli omomorfismi

Anelli, domini di integrità, corpi, campi > Rappresentazione di un anello nell’anello degli endomorfismi del suo gruppo abeliano additivo

Anelli, domini di integrità, corpi, campi > Prodotti diretti e somme dirette di anelli

Anelli, domini di integrità, corpi, campi > Corpi e campi; definizioni e prime proprietà

Anelli, domini di integrità, corpi, campi > Un esempio di corpo non commutativo: i quaternioni reali

Anelli, domini di integrità, corpi, campi > Campo dei quozienti di un dominio di integrità con unità. Il campo razionale

Anelli, domini di integrità, corpi, campi > Campi primi. Corpi primi

Anelli, domini di integrità, corpi, campi > Campo delle frazioni di un dominio di integrità in un corpo

Anelli, domini di integrità, corpi, campi > Gli interi modulo n (Quintabà) (da smistare nella teoria dei numeri)

Anelli commutativi con unità > Avvertenze

Anelli commutativi con unità > Ideali principali. Ideali generati da un sottoinsieme

Anelli commutativi con unità > Operazioni binarie nella famiglia degli ideali

Anelli commutativi con unità > Ideali massimali ed ideali primi

Anelli commutativi con unità > Elementi unitari di un anello. Anelli locali

Anelli commutativi con unità > Nilradicale, radicale di Jacobson e radicale di un ideale

Anelli commutativi con unità > Anelli noetheriani

Anelli commutativi con unità > Anelli ad ideali principali.

Anelli commutativi con unità > Domini ad ideali principali (Mac Lane-Birkhoff)

Anelli commutativi con unità > Divisibilità in un dominio di integrità. Fattorizzazione

Anelli commutativi con unità > L’anello Z degli interi (Quintabà) (da smistare nella teoria dei numeri)

Anelli commutativi con unità > Anelli euclidei

Anelli commutativi con unità > Anelli quoziente commutativi (Mac Lane-Birkhoff)

Anelli commutativi con unità > Filtri. Ultrafiltri. Reti. (Quintabà)

Anelli di polinomi > Introduzione

Anelli di polinomi > Anello dei polinomi in una indeterminata

Anelli di polinomi > La notazione polinomiale

Anelli di polinomi > Proprietà di trasporto

Anelli di polinomi > Anelli di polinomi sopra un campo. Ideali di un anello di polinomi sopra un campo

Anelli di polinomi > Fattorizzazione nell’anello dei polinomi sopra un campo (Demaria)

Anelli di polinomi > Zeri di un polinomio definito sopra un campo

Anelli di polinomi > Estensioni semplici di un sottocampo di un campo

Anelli di polinomi > Estensioni semplici simboliche

Anelli di polinomi > Equazioni polinomiali (Mac Lane-Birkhoff)

Anelli di polinomi > Polinomi su (Mac Lane-Birkhoff)

Campi speciali > Domini ordinati (Mac Lane-Birkhoff)

Campi speciali > Il campo ordinato (Mac Lane-Birkhoff)

Campi speciali > Equazioni polinomiali (Mac Lane-Birkhoff)

Campi speciali > Convergenza nei campi ordinati (Mac Lane-Birkhoff)

Campi speciali > Il campo reale (Mac Lane-Birkhoff)

Campi speciali > Polinomi su (Mac Lane-Birkhoff)

Campi speciali > Il piano complesso (Mac Lane-Birkhoff)

Campi speciali > Irriducibilità su e su (Mac Lane-Birkhoff)

Campi speciali > Campi quadratici

Moduli su un anello, spazi vettoriali, algebre > Introduzione

  Sintesi & Nozioni importanti sui moduli

  Sintesi & Nozioni importanti sui moduli > Casi in cui i morfismi formano moduli. Casi in cui le funzioni sono morfismi di moduli.

  Sintesi & Nozioni importanti sui moduli > I morfismi più importanti. La dualità

  Sintesi & Nozioni importanti sui moduli > Base, generato, indipendenza lineare

  Sintesi & Nozioni importanti su spazi vettoriali

Moduli su un anello, spazi vettoriali, algebre > Definizione di modulo su un anello

Moduli su un anello, spazi vettoriali, algebre > Prime proprietà degli R-moduli

Moduli su un anello, spazi vettoriali, algebre > Esempi di moduli su un anello

Moduli su un anello, spazi vettoriali, algebre > Sottomoduli (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Sottostrutture per R-moduli, spazi vettoriali e algebre

Moduli su un anello, spazi vettoriali, algebre > R-modulo quoziente

Moduli su un anello, spazi vettoriali, algebre > Trasformazioni lineari (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Moduli liberi e moduli di funzioni (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Biprodotti (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Moduli duali (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Bimoduli (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Studio di HomR (A,B)

Moduli su un anello, spazi vettoriali, algebre > Combinazioni lineari, sistemi di generatori, basi in un R-modulo

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Fonti

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali (Gallo e Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Basi (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Dimensione (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Spazi a dimensione infinita (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Costruzioni di basi (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Spazi vettoriali accoppiati dualmente (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Operazioni elementari (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > Sistemi di equazioni lineari (Mac Lane-Birkhoff)

Sistemi di equazioni lineari > Trattazione standard

  Da smistare

  Generali

Moduli su un anello, spazi vettoriali, algebre > Spazi vettoriali > I quaternioni (Mac Lane-Birkhoff)

Moduli su un anello, spazi vettoriali, algebre > Algebre

  Esposizione Gallo

  Approfondimento sul concetto di algebra nella letteratura

Matrici > Trattazione standard (capitolo unico) (Gallo + Mac Lane-Birkhoff + Zwirner + Citrini)

  Nozioni importanti e sintetiche ritrascritte

  Nozioni varie e generali

  Formule utili del calcolo matriciale

  Sistemi di equazioni lineari

  Operazioni elementari su vettori e matrici

  Sistemi di equazioni lineari

  Matrici e trasformazioni lineari > Basi e vettori (nozioni prevalentemente di ripasso)

  Matrici e trasformazioni lineari > Matrici e trasformazioni lineari

  Matrici e trasformazioni lineari > Matrici di trasformazioni lineari duali t* : V* W*

  Matrici e trasformazioni lineari > Matrici e biprodotti

  Matrici e trasformazioni lineari > Autovettori e autovalori. Equazione caratteristica.

  Rango e nullità di una matrice

  Le operazioni tra matrici

  Principali tipi di matrici

  Matrici inverse. Matrici invertibili.

  Determinanti

  Forme bilineari. Forme quadratiche.

Algebra delle matrici (per lo studio di analisi, in attesa che la sintesi arrivi alle matrici)

Matrici > Mac Lane-Birkhoff > Matrici > Matrici e moduli liberi

Matrici > Mac Lane-Birkhoff > Matrici > Matrici e biprodotti

Matrici > Mac Lane-Birkhoff > Matrici > La matrice di una mappa

Matrici > Mac Lane-Birkhoff > Matrici > La matrice di un composto

Matrici > Mac Lane-Birkhoff > Matrici > Matrici invertibili

Matrici > Mac Lane-Birkhoff > Matrici > Cambiamento di basi

Matrici > Mac Lane-Birkhoff > Matrici > Autovettori e autovalori

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Funzioni multilineari e alternanti

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Determinanti di matrici

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Cofattori e regola di Cramer

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Determinanti di mappe

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Il polinomio caratteristico

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Il polinomio minimale

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Funzioni bilineari universali

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Prodotti tensoriali

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Sequenze esatte

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Identità per i prodotti tensoriali

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Cambiamento di anelli

Matrici > Mac Lane-Birkhoff > Determinanti e prodotti tensoriali > Algebre

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Moduli noetheriani

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Moduli ciclici

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Moduli torsione

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > La forma canonica razionale per matrici

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Moduli primari

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Moduli liberi

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Equivalenza di matrici

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Il calcolo dei fattori invarianti

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Moduli proiettivi e iniettivi

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Il teorema della base di Hilbert

Matrici > Mac Lane-Birkhoff > Matrici simili e gruppi abeliani finiti > Domini a fattorizzazione unica

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Forme bilineari

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Matrici simmetriche

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Forme quadratiche

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Forme quadratiche reali

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Prodotti interni

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Basi ortonormali

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Matrici ortogonali

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Il teorema dell’asse principale

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Spazi unitari

Matrici > Mac Lane-Birkhoff > Forme quadratiche > Matrici normali

Reticoli ed algebre di Boole > Definizione di reticolo (Demaria)

Reticoli ed algebre di Boole > Omomorfismi fra reticoli (Demaria)

Reticoli ed algebre di Boole > Particolari tipi di reticoli (Demaria)

Reticoli ed algebre di Boole > Algebre di Boole (Demaria)

Reticoli ed algebre di Boole > Funzioni booleane (Demaria)

Reticoli ed algebre di Boole > Anelli booleani (Demaria)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Le relazioni : Elementi di terminologia

 

 

RELAZIONE

  Una relazione n-aria è un sottoinsieme di A1 x...x An con A1,...,An insiemi qualsivoglia (Negri) ricorre all'escamotage di considerare ad es. una relazione ternaria come l'insieme delle coppie: <<y,z>,w>

 

RELATION on a set A .

Significa: "insieme di n-ple R che è incluso in An"

Si può parlare di una relazione con riferimento o senza riferimento ad un insieme.

Si può parlare di una relazione senza riferimento ad un insieme ("relazione R") o in riferimento ad un insieme ("relazione R su un insieme A") "Relazione R su A" vuol dire che RAXA

Le asserzioni circa le proprietà di una relazione hanno senso solo se si sta parlando di una relazione riferita ad un insieme.

Le asserzioni circa le proprietà simmetrica, transitiva, riflessiva, antisimmetrica, di essere un ordine parziale o totale, di essere connected o strongly connected non hanno significato se non riferite ad un dato insieme A. Infatti, ad es. nel caso della riflessività, una relazione R si definisce simmetrica in relazione ad un insieme A perché, per ogni aA, si ha aRa, ma si definisce non simmetrica in B A perché non per tutti gli elementi bB si ha bRb.

Si può tuttavia dare senso ad asserzioni di proprietà di una relazione non riferita ad un insieme considerandola riferita al suo campo.

Si parla anche di relazioni n-arie e non solo binarie. Se si parla di “relazione” senza altre precisazioni si intende “relazione binaria”

 

CAMPO (field) di una relazione su un insieme X (cioè interna)

Given a binary relation R on a set X, the domain of R is defined to be the set of all y such  that <y,z> R for some z; the range of R is the set of all z such that <y,z> R for some y; and the field of R is the union of the domain and range of R

La nozione di campo è molto usata da diversi autori nelle definizioni, come ad es. quelle di relazione di ordine etc.:

(a,b F (R))…

dove F (R) è il campo di R

 

relazioni confrontabili

Siano dati un insieme I ed una relazione σ di preordine, o di ordine, in I. Due elementi a e b di I si dicono confrontabili nella σ sse a σ b oppure b σ a

Importante: gli elementi devono essere diversi tra loro (cioè è ancora connessa una relazione che non sia riflessiva)

E’ sinonimo di “relazione connessa” (Negri) o di relazione “totale” (ordine totale, preordine totale)

 

relazione connessa

Siano dati un insieme I ed una relazione σ di preordine, o di ordine, in I. Due elementi a e b di I si dicono confrontabili nella σ sse a σ b oppure b σ a

Importante: gli elementi devono essere diversi tra loro (cioè è ancora connessa una relazione che non sia riflessiva)

E’ sinonimo di “relazione connessa” (Negri) o di relazione “totale” (ordine totale, preordine totale)

 

relazione quoziente

Data una relazione di equivalenza σ su un insieme I e una relazione R qualunque compatibile con σ, si può definire nell'insieme quoziente I/σ una relazione quoziente R/σ definita come segue:

{a}σR/σ{b}σ aRb

 

 

 

Le relazioni : Grafi (non di rappresentazione) e relazioni

 

Relazione associata ad un grafo .

Immagine della relazione.

Controimmagine della relazione.

Eguaglianza tra relazioni .

Casi particolari di relazioni .

Le possibili proprietà di una relazione .

 

 

   Relazione associata ad un grafo .

Chiamiamo relazione associata al grafo F la legge che associa un elemento a A ed un elemento b B se, e solo se (a,b) F Se chiamiamo f tale relazione, scriviamo "f: A B" per indicare che opera dall'insieme A (dominio) all'insieme B (codominio) e scriveremo: “a  b” oppure equivalentemente: b = f(a) per indicare che "a è in relazione con b nella f", che "b corrisponde ad a nella f". In questo caso diciamo che "b è immagine di a" Ancora equivalente è la scrittura: a = f-1(b) che leggiamo dicendo "a controimmagine di b"

Una relazione è quindi definita quando si siano dati dominio, codominio e grafo. Spesso, invece di dare il grafo, si dà la legge che lega gli elementi che si corrispondono.

Dalla definizione di relazione di A in B segue che esse sono tante quanti sono i sottoinsiemi di AxB, cioè gli elementi di P(AxB)

 

   Immagine della relazione.

Il sottoinsieme di B costituito da tutte e sole le immagini degli elementi di A nella f è detto immagine della relazione ed è  indicato con "f(A)": f(A) = {bB/( aA) b=f(a)}

 

   Controimmagine della relazione.

Il sottoinsieme di A costituito da tutte e sole le controimmagini degli elementi di B nella f è detto controimmagine della relazione ed è indicato con "f-1(B)":

f-1(B) = {aA/( bB) a=f-1(b)} = {aA/( bB) f(a)=b} = π1(F)

Data una relazione f:AB si può definire l'immagine di un qualunque sottoinsieme I di A, come l'insieme:

f(I) = {bB/( xI) f(x)=b} B

e la controimmagine di un qualunque sottoinsieme I' di B come l'insieme

f-1(I') = {aA/( x'I') f(a)=x'} A

Dato un sottoinsieme I di A si può sempre costruire f(I) e f-1

In generale si ha:

I f-1(f(I))

perché   possono esserci degli elementi di I che non appartengono a f-1(f(I)), cioè quelli privi di immagine in f:

I f–1(f(I))

Possono anche esserci elementi che non appartengono ad I; sono quelli che si trovano come "ulteriori" controimmagini di elementi di f(I):

f–1(f(I)) I

 

   Eguaglianza tra relazioni .

Se f è una relazione di A in B, avente grafo F e f' è  una relazione di A' in B' avente grafo f', esse si dicono relazioni uguali se e solo se coincidono tra loro dominio, codominio e grafo: (f = f') (A=A' ^ B=B' ^ F=F')

 

   Casi particolari di relazioni .

Relazione vuota.

La relazione che ha come grafo è detta "relazione vuota" ed in essa non vi sono coppie di elementi che si corrispondono

 

Relazione banale

La relazione che ha AxB come grafo è detta "relazione banale" ed in essa ogni elemento di A è in relazione con tutti gli elementi di B.

 

   Le possibili proprietà di una relazione .

relazione riflessiva

a (a R a)

relazione simmetrica

a b (a R b b R a)

relazione transitiva .

a b c (a R b ^ b R c a R c)

Altre proprietà

Una relazione binaria può avere infinite altre proprietà non indicate con nomi specifici.

 

 

 

Le relazioni : Grafi (di rappresentazione). Alberi.

Nozioni presupposte>Strutture

Nozioni presupposte>Strutture multisorte

Grafi ed alberi

 

 

   Nozioni presupposte : Strutture

Un tipo è una quadrupla {{Ri}iI,{Fj}jJ,{ck}kK,ar} contenente rispettivamente un insieme di simboli di relazione, un insieme di simboli di funzione, un insieme di simboli di costanti e una funzione ar che assegna ad ogni simbolo di relazione e funzione un numero naturale detto “arietà” del simbolo.

Se τ (tau) è un tipo, definiamo struttura di tipo τ la coppia A = (A,I), dove A è un insieme non vuoto, detto dominio della struttura, e I è una funzione, detta interpretazione, che assegna ad ogni simbolo di relazione una relazione su A, ad ogni simbolo di funzione una funzione su A e ad ogni simbolo di costante un elemento di A in modo che le arietà dei simboli di relazione e di funzione corrispondano a quelle delle relazioni e funzioni loro assegnate.

 

   Nozioni presupposte : Strutture multisorte

Esistono alcune realtà che per essere rappresentate come strutture nel modo più naturale richiedono la presenza di un certo numero di domini differenti. L’esempio classico è il piano euclideo, dove le rette, i punti e la relazione di incidenza possono essere visti come una struttura a due sorte costituita dagli insiemi B0 e B1, rispettivamente l’insieme dei punti p e delle rette l, munita di una relazione I B0 x B1: leggeremo I(p,l ) come “p giace sulla retta l “ oppure “il punto p e la retta l sono incidenti” oppure “l passa per p”. Una struttura a due sorte di questo tipo è detta piano di incidenza. Si possono fornire facilmente esempi specifici di piani d’incidenza considerando come B0 l’insieme di tutti i punti del piano cartesiano, ossia l’insieme di tutte le coppie (x,y), dove x,y R e considerando come B1 l’insieme di tutte le rette dal piano cartesiano, ossia l’insieme di tutti gli insiemi di coppie:

{(x,y) | x,y } R ax + by + c = 0}

dove a,b,c R e a e b non sono entrambi nulli.

La relazione di incidenza è l’appartenenza: I((x,y),l) sse (x,y) l

Passiamo ora a cogliere gli aspetti generali di questo discorso: un tipo multisorte si ottiene da un tipo usuale aggiungendovi l'insieme I delle sorte e tre funzioni ψ0, ψ1, ψ2 che associano rispettivamente ai simboli di relazione, di funzione e di costante, successioni finite di elementi di I secondo i criteri seguenti:

     se Ri è un simbolo relazionale n-ario, ψ (Ri) è una successione (i0,...,in-1)

     se Fj è un simbolo funzionale n-ario, ψ (Fj) è una successione (i0,...,in-1)

     se ck è un simbolo di costante, ψ(ck) è un elemento di I.

I valori attribuiti dalle varie ψi sono detti ranghi delle funzioni di un tipo multisorte. Se un simbolo di relazione Ri ha rango (i0,...,in-1) ciò significa che la relazione denotata da Ri vale tra n-ple di oggetti a0,...,an-1 tali che, per ogni j<n, aj appartiene alla sorta di indice ij e un significato analogo hanno i ranghi dei simboli di funzione e di costante

Una struttura multisorte di tipo τ (che chiameremo A) è costituita dalla successione di domini {Ai}iI dove Ai è detto sorta i-esima. Inoltre, per ogni simbolo relazionale R, tale che ψ0(Ri)=(i0,...,in-1), la struttura contiene una relazione R Ai0 x Ai1 x...x Ain-1; per ogni simbolo funzionale Fj tale che ψ1(Fj)=(i0,...,in) la struttura contiene una funzione F: Ai0 x Ai1 x...x Ain-1 Ain; per ogni simbolo di costante ck tale che ψ2(ck)=i, la struttura contiene una costante c A.

In pratica, in una struttura multisorte, relazioni e funzioni, invece che avere come argomenti elementi appartenenti ad un unico insieme, hanno come argomenti elementi presi da insiemi diversi. I ranghi indicano, per ciascun posto di una relazione o funzione n-aria, da quale insieme vada preso l’elemento che occupa quel posto.

Un esempio di strutture multisorte è costituito dai grafi, concepito come strutture A = (A0, A1,δ0,δ1), dove A0 = V, l’insieme dei punti e A1 = F, l’insieme delle frecce del grafo. Le funzioni δ0: F V e δ1: F V assegnano ad ogni freccia un punto, detto rispettivamente dominio e codominio, in modo da poterne stabilire la direzione.

 

   Grafi ed alberi

 

Per visualizzare le relazioni binarie si usano grafi. Un grafo (di rappresentazione) è una coppia (V,F) di insiemi in cui il primo elemento contiene i punti del grafo e il secondo le frecce: ogni freccia collega due punti non necessariamente distinti del grafo. Se Q è una relazione binaria su A, porremo A=V e introdurremo un insieme F che contenga, per ogni coppia a,bA tale che valga Q(a,b), una freccia che unisca a con b. La collocazione spaziale dei punti non ha importanza, perché ciò che conta in un grafo sono solo le connessioni stabilite dalle frecce. Quando vale sia Q(a,b) che A(b,a), invece di unire i punti a e b con due frecce di direzioni opposte, conveniamo di rappresentare questa situazione collegandoli semplicemente con un segmento.

Un ordine totale è detto anche lineare

I grafi di una relazione di ordine totale sono sempre linearizzabili

I grafi di una relazione di ordine totale sono sempre linearizzabili, anche se possono assumere una forma non lineare. Vedi anche figure 

Dimostrazione pratica di come alberi non linearizzati di una relazione di ordine totale possono essere linearizzati e come l'albero di una relazione simmetrica non possa essere linearizzato. Da tali alberi si nota anche che, se l'ordine non è totale, non è possibile la linearizzazione.

Un esempio di strutture multisorte è dato dai grafi, concepiti come strutture A=(A0,A1,α0,α1) dove A0=V, l'insieme dei punti e A1 = F, l'insieme delle frecce del grafo. Le funzioni α0:FV e α1:FV assegnano ad ogni freccia un punto, detto rispettivamente dominio e codominio, in modo da poterne stabilire la direzione.

Un particolare tipo di grafo è l'albero. Invece di concepirlo come grafo preferiamo pensarlo come una struttura multisorte (A,ω ,R,ϕ) dove A è un insieme, R è una relazione 2-aria su A, ϕ è una funzione da A verso ω e inoltre:

     esiste un unico a A tale che ϕ(a)=0;

     per ogni aA, se ϕ(a) è diverso da 0 allora esiste un unico bA tale che R(b,a);

     per ogni a,b A, R(a,b) implica ϕ(b)=φ(a)+1.

Gli elementi di A sono detti "punti" o "nodi" dell'albero. Se A è finito l'albero è un albero finito, altrimenti è un albero infinito.

La a) stabilisce che c'è un unico punto di livello 0: tale punto è detto "vertice". Se vale R(a,b) diciamo che a precede b, che b segue a.

La b) stabilisce che ogni punto diverso dal vertice ha un unico predecessore. Un punto può avere un numero qualsiasi di successori e se non ne ha è detto punto terminale di un albero.

La c) comporta che nel passaggio ai successori di un punto il livello cresca di una unità.

Chiamiamo ramo una successione di punti di A, finita o infinita, tale che:

il suo primo elemento sia il vertice

presi comunque due suoi punti consecutivi ai e ai+1 valga R(ai,ai+1).

Diremo che un ramo è un ramo massimale se è infinito oppure il suo ultimo nodo è  terminale. Dati due punti distinti a e b di un albero, diremo che a è sopra b, o b è sotto a se esiste un ramo cui appartengono sia a che b e φ(a) < φ(b).

Se supponiamo che i successori di ogni singolo punto siano ordinati allora otteniamo un albero ordinato. Formalmente ciò si ottiene dotando un albero di una funzione π:A⇒ω che assegna ad ogni punto un numero che ne costituisce il numero d'ordine (tra i successori del suo predecessore) e tale che vale:

se φ(a) = 0 allora π(a)=0, ossia si attribuisce convenzionalmente al vertice il numero d'ordine zero;

per ogni a,b A, se a è diverso da b ed esiste cA tale che R(c,a) è R(c,b), allora π(a) è diverso da π(b), ossia i numeri d'ordine di due successori differenti dello stesso punto debbono essere differenti;

Per ogni aA, se esiste un bA tale che R(a,b), allora esiste anche un bA tale che R(a,b) e π(b)=0, ossia se un punto ha successori ha anche un successore di numero d'ordine zero;

per ogni aA, per ogni n ω , se esiste un bA tale che R(a,b) e π(c)=n, ossia se un punto ha un successore di numero d'ordine n+1, ne deve avere anche uno di numero d'ordine n.

Da quanto detto si evince che i numeri d'ordine sono assegnati come nella figura:

Diremo che un albero è n-ario se n è il massimo dei valori assunti da π. Un albero è un albero finitario se Im(π)∈ω .

Diremo che sup φ è l'altezza dell'albero, ossia il limite dei livelli dei nodi. Un albero finito ha necessariamente altezza finita, un albero infinito può avere altezza finita o infinita.

Dalla condizione 2) di π si evince che la relazione R non è transitiva; senonché poi dice che "un punto può avere un numero qualsiasi di successori. Pare di poter concludere che si tratta della relazione "successore immediato", come è confermato da Una relazione tra due insiemi A e B si dice relazione ovunque definita se ogni elemento di A ha almeno una immagine in B: (aA) ( xB) b=f(a)

Una relazione f: AB si dice relazione funzionale se ogni elemento di A ha al più una immagine di B

Una relazione f:AB si dice funzione (o applicazione) se è ovunque definita e funzionale.

Una relazione f:AB si dice relazione suriettiva se ogni elemento di B ha almeno una controimmagine

Una funzione suriettiva si dice una suriezione

Una relazione f:AB si dice relazione iniettiva se ogni elemento di B ha al più una controimmagine.

Una funzione iniettiva si dice iniezione

Fare quindi attenzione: in una "iniezione" gli elementi di ciascuna coppia immagine-controimmagine non compaiono in nessun'altra coppia del grafo; in una "relazione iniettiva", se questa non è funzionale, possiamo avere un elemento del dominio che ha più di una immagine.

Chiamiamo funzione bijettiva o bijezione una relazione ovunque definita, funzionale, suriettiva e iniettiva.

Bijezioni tra insiemi

Nel caso di insiemi finiti non si può definire una bijezione tra un insieme ed un suo sottoinsieme proprio

Notiamo che, quando non si può parlare di "numero" di elementi di un insieme, cioè quando gli insiemi sono infiniti, si possono invece definire delle bijezioni tra un insieme e il suo sottoinsieme proprio.

Si parla di trasformazioni per indicare le bijezioni, cioè le corrispondenze biunivoche tra un insieme e se stesso.

Dato un insieme A, chiamiamo identità in A e la denotiamo col simbolo "iA", la relazione tra A ed A che ha come grafo la diagonale di AxA

 

 

 

Le relazioni : Le prime compatibilità

 

Compatibilità di una relazione con la inclusione.

Compatibilità di una relazione con la unione.

Incompatibilità di una relazione con l'intersezione.

Incompatibilità di una relazione con la complementazione.

 

 

Parleremo in questo capitolo della compatibilità di una relazione con le operazioni insiemistiche

 

   Compatibilità di una relazione con la inclusione.

Sia f:AB una relazione qualunque e X,Y A:

XY f(X) f(Y)

 

   Compatibilità di una relazione con la unione.

Sia f:AB una relazione qualunque e X,Y A:

f(XUY) = f(X) U f(Y)

Tale proprietà vale anche per la unione generalizzata.

 

   Incompatibilità di una relazione con l'intersezione.

Si ha unicamente:

f(XY) f(X) f(Y)

ma non:

f(X) f(Y) f(XY)

e quindi non:

f(XY) = f(X) f(Y)

Tale proprietà vale anche per la unione generalizzata.

Tuttavia, se f è iniettiva, allora: f(XY) = f(X) f(Y)

 

   Incompatibilità di una relazione con la complementazione.

Si ha unicamente:

X Y f(Y)-f(X) f(Y-X)

ma non:

X Y f(Y-X) f(Y)-f(X)

e quindi non:

X Y f(Y-X) = f(Y)-f(X)

Tuttavia, se f è iniettiva, allora:

X Y f(Y-X) = f(Y)-f(X)

 

 

 

Le relazioni : Restrizione e inversa di una relazione

 

Restrizione di una relazione.

Iniezione canonica.

Inversa di una relazione

 

 

   Restrizione di una relazione.

Se f: A B è una relazione di grafo F e se C A, l'insieme F ⋂ (CxB) è il grafo di una nuova relazione, che denotiamo con f/C e chiamiamo restrizione di una relazione f a C

Sono proprietà della restrizione di una relazione

Se f è ovunque definita, allora anche f/C è ovunque definita

Se f è funzionale, allora f/C è funzionale

Se f è iniettiva, allora f/C è iniettiva

Invece, se f è suriettiva, non è detto che f/C sia sempre suriettiva

Da quanto sopra, segue che la restrizione di una funzione è una funzione

La restrizione di una iniezione è una iniezione

La restrizione di una biezione è una iniezione

 

   Iniezione canonica.

Dati due insiemi A e C, tali che CA, chiamiamo iniezione canonica di C in A, e la denotiamo con "j", la iniezione ottenuta restringendo a C l'identità iA in A:

(xC) j(x) = iA/C(x) = iA(x) = x

Essa fa corrispondere a ogni elemento x di C ancora l'elemento x pensato come elemento di A.

 

   Inversa di una relazione

Chiamiamo grafo simmetrico di F l'insieme F-1 così definito:

F-1 = {(b,a) | (a,b)F}

Proprietà del passaggio al simmetrico ()

π1(F-1) = π2(F) π2(F-1) = π1(F)

(F-1)-1 = F

Compatibilità del passaggio al simmetrico con l'unione:

(FUG)-1 = F-1 U G-1

Compatibilità del passaggio al simmetrico con l'intersezione:

(F⋂G)-1 = F-1⋂G-1

Compatibilità del passaggio al simmetrico con la complementazione:

(AxB-F)-1 = BxA-F-1

Caso particolare (di grafo R sottoinsieme) del prodotto di un insieme I per se stesso: R IxI

Il grafo simmetrico R-1 è anch'esso contenuto in IxI: R-1IxI

Le coppie comuni a R ed R-1 si dice che "si corrispondono in doppio modo" Se R = R-1 si dice tutte le coppie si corrispondono in doppio modo e il grafo R si dice grafo simmetrico (rispetto alla diagonale)

Dalla definizione data di F-1 segue che F-1 BxA: allora esso è il grafo di una relazione di B in A, f-1:BA che chiamiamo relazione inversa di f, dove f è la relazione di grafo F.

Proprietà della relazione inversa di f.

 

(f-1) -1 = f

f ovunque definita f-1 suriettiva e viceversa

f funzionale f-1 iniettiva e viceversa

f suriettiva f-1 ovunque definita e viceversa

f iniettiva f-1 funzionale e viceversa

f bijettiva f-1 bijettiva

L'inversa di una funzione è una relazione suriettiva e iniettiva, e quindi non è necessariamente ancora una funzione; lo è soltanto se la funzione data è suriettiva e iniettiva, e cioè se è una bijezione.

 

 

 

Le relazioni : Prodotto per applicazione successiva. Prodotto cartesiano. Unione di due relazioni.

 

Grafo prodotto dei grafi F e G.

Siano dati due grafi FAxB e GBxC. Chiamiamo grafo prodotto di due relazioni F e G l'insieme denotato GF e così definito:

GF = {(a,c)/( b B)Compatibilità col passaggio al simmetrico:

(GF)-1 = F-1 G-1

Proprietà associativa:

(FAxB ^ GBxC ^ HCxD) (HG)F = H(GF)

La proprietà associativa ci permette di parlare (univocamente) di "prodotto di tre grafi"; la sua generalizzazione di estendere il prodotto a un numero finito di grafi.

Il prodotto non è commutativo: GF FG

Qualunque sia il grafo FAxB, si ha: FΔA = ΔBF = F dove ΔA è la diagonale di AxA e ΔB è la diagonale di BxB

 

Prodotto di un grafo col suo simmetrico.

Dato un grafo FAxB, è sempre possibile farne i prodotti con il suo simmetrico F-1BxA, ottenendo così i due grafi:

F-1F AxA

FF-1 BxB

In generale è: F-1F FF-1 in quanto, ovviamente, mentre l'uno appartiene ad AxA, l'altro appartiene a BxB.

In generale è:

F-1F ΔB

FF-1 ΔA

Infatti, se il grafo non è ovunque definito, si avranno coppie con termini identici, ma non TUTTE le coppie componenti ΔB o ΔA

 

Relazione prodotto per applicazione successiva.

Al grafo FAxB è associata una relazione f:AB e al grafo GBxC è associata una relazione G:BC; dalla definizione data di GF segue che GF AxC: allora esso è il grafo di una relazione di A in C, gf:AC, che chiamiamo relazione prodotto (per applicazione successiva) di due relazioni f e g

 

Proprietà della relazione prodotto per applicazione successiva.

(gf)-1 = f-1 g-1

Proprietà associativa:

(hg)f = h(gf)

La proprietà associativa ci consente di parlare di prodotto per applicazione successiva di tre relazioni e, generalizzando, di un numero finito di relazioni.

Il prodotto di relazioni non è commutativo

Qualunque sia la relazione f: A B si ha:

f iA = iB f = F

dove iA: A A e iB: B B sono le identità rispettivamente in A ed in B

(f ovunque definita ^ g ovunque definita) gf ovunque definita

(f funzionale ^ g funzionale) gf funzionale

(f suriettiva ^ g suriettiva) gf suriettiva

(f iniettiva ^ g iniettiva) gf iniettiva

Il prodotto di due funzioni è una funzione

Il prodotto di due suriezioni è una suriezione

Il prodotto di due iniezioni è una iniezione

Il prodotto di due bijezioni è una bijezione

Diagrammi lineari di insiemi e relazioni

Si può schematizzare una relazione prodotto nel seguente modo:

 

A  B  C

 

Prodotti di una relazione con la sua inversa.

In generale è:

ff-1 f-1f

ff-1 ΔA

f-1f ΔB

 

Funzione prodotto (per applicazione successiva).

Se f: A B e g: B C sono due funzioni, chiamiamo funzione prodotto (per applicazione successiva) di due funzioni f e g la funzione gf tra A e C che opera nel modo seguente:

(xA)  gf(x) = g

 

Proprietà del prodotto di funzioni.

Non gode della proprietà commutativa

Proprietà associativa

Questo permette di definire il prodotto di un numero finito di funzioni, che è ancora una funzione.

Se f è una bisezione, allora f-1f è una bisezione

Se f è una bijezione allora ff-1 è una bijezione

Inoltre, poiché: f-1f(a) = f-1= a si ha: f-1f = iA e poiché ff-1(b) = b si ha: ff-1 = iB

Se f e g sono due funzioni e gf è iniettiva, allora f è iniettiva

Se f e g sono due funzioni e gf è suriettiva, allora g è suriettiva

Se f e g sono due funzioni, gf è iniettiva e f suriettiva, allora g è  iniettiva

Se f e g sono due funzioni, gf è suriettiva e g iniettiva, allora f è  suriettiva

Se gf = iA e fg = iB, allora f e g sono due bijezioni, l'una inversa dell'altra

 

Prodotto cartesiano di due relazioni.

Date due relazioni f:AB e g:CD costruiamo il prodotto cartesiano (AxC)x(BxD); in esso possiamo individuare il sottoinsieme:

{((a,c),(b,d)) | b = f(a) ^ d = f(c)}

che è un grafo. La relazione associata a tale grafo, che si denota con f x g e opera tra AxC e BxD, si chiama prodotto cartesiano di due relazioni f e g. In altre parole, in fxg l'insieme delle immagini di una coppia (a,c)AxC è  l'insieme {f(a)}x{g(c)}, dove {f(a)} è l'insieme delle immagini di a nella f e {f(c)} l'insieme delle immagini di c nella g.

Nel caso in cui f e g siano funzioni, la funzione prodotto cartesiano di due funzioni risulta definita ponendo:

((a,c)AxC)  fxg= (f(a),g(c))

 

Proprietà del prodotto cartesiano di due relazioni.

Se f e g sono ovunque definite, allora fxg è ovunque definito

Se f e g sono funzionali, allora fxg è funzionale

Se f e g sono iniettive, allora fxg è iniettivo

Se f e g sono suriettive, allora fxg è suriettivo

Il prodotto cartesiano di due funzioni è una funzione

Il prodotto cartesiano di due iniezioni è una iniezione

Il prodotto cartesiano di due suriezioni è una suriezione

Il prodotto cartesiano di due bijezioni è una bijezione

 

Unione di due relazioni.

Date due relazioni f:AB e g:CD, costruiamo AUC, BUD ed il prodotto cartesiano (AUC)x(BUD); in esso possiamo individuare il sottoinsieme:

{(x,y) | xAUC ^ yBUD ^ (y=f(x) v y=g(x))}.

 

Proprietà della unione di due relazioni.

Se f e g sono ovunque definite, allore fUg è ovunque definita

Se f e g sono suriettive, allora fUg è suriettiva

Se f e g sono funzionali e AC = φ, allora fUg è funzionale

Se f e g sono iniettive e B= φ allora fUg è iniettiva

L'unione di due bijezioni f:AB e g:CD, con AC = φ e B= φ è una  bijezione

 

 

 

Le relazioni : Relazioni in un insieme

 

Relazioni interne ad un insieme.

Le possibili proprietà di una relazione in un insieme I.

Relazione indotta.

 

 

   Relazioni interne ad un insieme.

 

Si parla di "relazioni interne in un insieme dato" per indicare quelle relazioni il cui dominio e il cui codominio coincidono.

Se r è una relazione interna in un insieme I, il suo grafo R sarà un sottoinsieme di IxI e, sse (a,b)RIxI, diremo che a è in relazione ρ con b. Non useremo più la notazione "funzionale" fin qui usata, ma scriveremo: aρb (a,b)R.

Date due relazioni ρ e σ nello stesso insieme I, di grafi rispettivi R ed S, si ha:

ρ = σ R = S e cioè: (a,b)R (a,b)S equivalente a: aρb aσb

ρ σ R S che si legge: "ρ è una relazione più fine di σ" o "σ è meno fine di ρ"

 

   Le possibili proprietà di una relazione in un insieme I.

 

Riflessiva.

Ogni elemento a di I è in relazione con se stesso: aI aρa

Simmetrica.

a I b I (a ρ b)(b ρ a)

Transitiva.

a I b I c I (a ρ b ^ b ρ c) a ρ c

Antisimmetrica.

a I b I (a ρ b ^ b ρ a) (a = b)

 

   Relazione indotta.

 

Dato I' I, si ha che I' x I' I x I. Possiamo allora costruire l'insieme R' = R⋂(I' x I'), che è un grafo in I' x I': a tale grafo è associata una relazione ρ' che diciamo " relazione indotta da ρ in I' "

Proprietà di trasporto (della relazione indotta).

Se ρ in I è una relazione riflessiva, allora la relazione ρ' indotta da ρ in I'I è riflessiva

Se ρ in I è una relazione simmetrica, allora la relazione ρ' indotta da ρ in I'I è simmetrica

Se ρ in I è una relazione transitiva, allora la relazione ρ' indotta da ρ in I'I è transitiva

Se ρ in I è una relazione antisimmetrica, allora la relazione ρ' indotta in I'I è antisimmetrica

 

 

 

Le relazioni : La relazione di preordine e di ordine. Il lemma di Zorn.

 

Le definizioni di Mendelson e quelle degli altri autori

Confronto di terminologia ordinata per autori

Confronto di terminologia ordinata per termini

Proprietà della relazione di ordine. Ordine totale e parziale. Compatibilità della relazione di ordine con altre relazioni.

Elementi particolari in insiemi ordinati. Insiemi ben ordinati. Reticoli. Poset.

Il lemma di Zorn

Nozioni varie alla rinfusa.

 

 

   Le definizioni di Mendelson e quelle degli altri autori

 

(Mendelson, Introduction to Mathematical Logic) A partial order is a binary relation R such that R is transitive and, for every x in the field of R, xRx is false.

If R is a partial order, then the relation R’ that is the union of R and the set of all ordered pairs <x,x>, where x is in the field of R, we shall call reflexive partial order.

La relazione di ordine irriflesivo di Mendelson è necessariamente a-simmetrica

Richiede cioè che non esistano coppie di elementi che si corrispondono in doppio modo (non-simmetria), perché diversamente risulterebbe riflessiva

“(aRb and bRa) is impossible if R is a partial order, whereas (aRb and bRa) implies a = b if R is a reflexive partial order”.

La relazione di ordine irriflessivo di Mendelson è antisimmetrica

Paradossalmente, non essendoci coppie come <a,b> e <b,a> in Mendelson, non è mai verificata la condizione (x R y) & (y R x) e perciò la relazione di ordine parziale irriflessivo di Mendelson è antisimmetrica.

La definizione di preordine implica la non-simmetria e la non-antisimmetria oppure è possibile dire ad es. che una relazione di equivalenza è al contempo una relazione di preordine?

La relazione di preordine di Gallo è non antisimmetrica e non simmetrica, perché altrimenti sarebbe rispettivamente di ordine o di equivalenza. A meno di non convenire che una relazione di ordine o di equivalenza possono anche essere considerate relazioni di ordine

Gallo non offre indicazioni al riguardo.

Demaria mostra di credere che una relazione può essere concepita contemporaneamente come di preordine e di ordine: “Una relazione di preordine è detta relazione di ordine, se per essa vale pure la proprietà antisimmetrica”

Può esistere una relazione (di preordine) che sia né simmetrica né antisimmetrica

Consideriamo l’insieme dei punti del piano ordinario e sia O un punto fissato. Diciamo che P è in relazione ρ con Q sse il segmento OP è del segmento OQ.

Si verifica facilmente che la relazione ρ è riflessiva e transitiva.

Non è simmetrica, perché da OP < OQ segue PρQ ma non QρP

Non è antisimmetrica, perché da PρQ & QρP segue che OP = OQ ma non che P = Q

Una relazione di ordine è per Mendelson transitiva e antisimmetrica ma non necessariamente riflessiva, mentre per Gallo, Negri, Mac Lane è transitiva, antisimmetrica e (sempre) riflessiva

L’ordine parziale di Mendelson, sia riflessivo che irriflessivo, è sempre antisimmetrico, quindi possiamo dire che per Mendelson una relazione d’ordine è caratterizzata dalla transitività e dalla antisimmetria, ma non dalla riflessività, che può esserci o non esserci, mentre per Gallo e Negri e Mac Lane-Birkhoff è caratterizzata da transitività, riflessività e antisimmetria.

L’ordine riflessivo parziale o totale di Mendelson coincide con l’ordine parziale o totale (riflessivo) di Gallo, Negri, Mac Lane-Birkhoff

Quando Mendelson parla di “ordine parziale riflessivo” egli intende una relazione di ordine parziale irriflessivo addizionata con il grafo delle coppie del tipo <x,x>, quindi di una relazione parimenti antisimmetrica.

Tuttavia, qualsiasi relazione antisimmetrica e transitiva, non importa se parziale o totale, non può avere coppie di coppie del tipo <a,b>,<b,a> nel grafo, perché altrimenti si avrebbe:

xRy & yRx

ma non:

x=y

e risulterebbe violata la condizione di antisimmetria

Quindi la relazione di ordine riflessivo di Mendelson coincide pienamente con la relazione di ordine di Gallo e con quella di ordine di Negri e Mac Lane-Birkhoff

E’ possibile una relazione di ordine totale irriflessiva come sembra proporre Mendelson? Cioè, può essere transitiva e antisimmetrica ma irriflessiva?

E’ possibile. Non devono aversi coppie che si corrispondono in doppio modo, altrimenti, per la transitività, si avrebbero coppie riflessive

E’ senz’altro antisimmetrica, per falsità dell’antecedente: xRy & yRx non è mai verificato, neanche se x=y=a

 

 

   Confronto di terminologia ordinata per autori

   Gallo

Preordine parziale (sempre riflessivo)

Relazione riflessiva e transitiva che ordina parzialmente un insieme

Preordine totale (sempre riflessivo)

Relazione riflessiva e transitiva che ordina totalmente un insieme

Ordine parziale (sempre riflessivo)

Relazione riflessiva, transitiva e antisimmetrica, che ordina parzialmente un insieme

Ordine totale (sempre riflessivo)

Relazione riflessiva, transitiva e antisimmetrica, che ordina totalmente un insieme

   Mendelson

Ordine parziale irriflessivo

Relazione transitiva, irriflessiva e antisimmetrica che ordina parzialmente un insieme

L’antisimmetria è particolare: la condizione è verificata perché manca l’antecedente: xRy & yRx

Ordine parziale riflessivo

Relazione transitiva, riflessiva, antisimmetrica che ordina parzialmente un insieme

Ordine totale irriflessivo

Relazione transitiva, irriflessiva, antisimmetrica, che ordina totalmente un insieme

E’ possibile una relazione di ordine totale irriflessiva come sembra proporre Mendelson? Cioè, può essere transitiva e antisimmetrica ma irriflessiva?

E’ possibile. Non devono aversi coppie che si corrispondono in doppio modo, altrimenti, per la transitività, si avrebbero coppie riflessive

E’ senz’altro antisimmetrica, per falsità dell’antecedente: xRy & yRx non è mai verificato, neanche se x=y=a

Ordine totale riflessivo

Relazione transitiva, riflessiva, antisimmetrica, che ordina totalmente un insieme

   Negri

Ordine parziale (sempre riflessivo)

Vedi Gallo

Ordine totale (sempre riflessivo)

Vedi Gallo

Ordine parziale stretto (sempre irriflessivo)

Vedi Mendelson

Ordine totale stretto (sempre irriflessivo)

Anche se non ne parla è implicito che lo ammetta

Vedi Mendelson

   Mac Lane-Birkhoff

Ordine parziale (sempre riflessivo)

Vedi Gallo

 

   Confronto di terminologia ordinata per termini

Nota bene: quando un carattere della relazione compare tra parentesi (es. “Preordine parziale (riflessivo)”) vuol dire che non è utilizzato nella terminologia dell’autore in quanto implicito nella definizione del termine non tra parentesi

 

   Preordine parziale (riflessivo)

(Gallo, Algebra) Relazione riflessiva e transitiva ma che può essere anche non antisimmetrica in cui non tutti gli elementi sono confrontabili (Gallo)

Un esempio di relazione transitiva e riflessiva ma non antisimmetrica è quello della relazione che oltre alle coppie del tipo <a,a> contiene almeno una coppia di coppie del tipo <a,b>, <b,a> con a b

Nel caso di questa coppia di coppie non si potrà dire che, scelti arbitrariamente un x e un y si ha:

( x R y & y R x ) y = x

Se ci fosse una sola coppia di coppie del tipo citato, si tratterebbe di una relazione riflessiva, transitiva, non-simmetrica e non-antisimmetrica

La definizione di preordine implica la non-simmetria e la non-antisimmetria oppure è possibile dire ad es. che una relazione di equivalenza è al contempo una relazione di preordine?

La relazione di preordine di Gallo è non antisimmetrica e non simmetrica, perché altrimenti sarebbe rispettivamente di ordine o di equivalenza. A meno di non convenire che una relazione di ordine o di equivalenza possono anche essere considerate relazioni di ordine

Gallo non offre indicazioni al riguardo.

Mostra di credere che una relazione può essere concepita contemporaneamente come di preordine e di ordine: “Una relazione di preordine è detta relazione di ordine, se per essa vale pure la proprietà antisimmetrica”

 

   Preordine totale (riflessivo)

Relazione riflessiva e transitiva ma che può essere anche non antisimmetrica e in cui tutti gli elementi sono confrontabili (Gallo)

 

   Ordine parziale (riflessivo)

Relazione riflessiva, transitiva e antisimmetrica, in cui non tutti gli elementi sono confrontabili (Gallo) (Negri) (Mac Lane-Birkhoff) (Mendelson riconosce che in letteratura può anche voler dire questo)

Dice Mendelson che generalmente nella letteratura logico-matematica "ordine parziale" è usato sia per l'ordine parziale che per l'ordine parziale riflessivo

 

   Ordine parziale irriflessivo o stretto

(Mendelson, Negri, Citrini)

Relazione transitiva e antisimmetrica col grafo privo di coppie <x,x>

L'ordine parziale non riflessivo di Mendelson coincide con l'"ordine parziale stretto" di Negri, definito come "relazione transitiva e irriflessiva"

Una relazione come questa non può avere coppie che si corrispondono in doppio modo: aRb e bRa perché allora seguirebbe aRa per la transitività

Potrebbe, pare, essere antisimmetrica, perché l’antecedente della condizione di antisimmetria non è mai verificato:

a,b F (I) (aRb & bRa) a=b

dove F (I) è il campo della relazione

Sicuramente è asimmetrica (non è simmetrica), perché una relazione simmetrica non può soddisfare la condizione di assenza di coppie (x,x); infatti per la transitività si ha:

aRb & bRa aRa

Questa definizione non richiede che dati due elementi qualsiasi, a e b, diversi da loro, si abbia aRb o bRa (cioè si possono verificare una, entrambe o nessuna delle condizioni indicate)

 

   Ordine parziale riflessivo

(Mendelson, Negri, Citrini)

Relazione transitiva, riflessiva e antisimmetrica in cui tutti gli elementi sono confrontabili (Gallo) (Negri) (Mac Lane-Birkhoff, probabilmente, anche se non parlano in alcun punto di ordine totale)

Il fatto che l’ordine sia totale vuol dire che si ha :

( x,y) (x R y) (y R x) (y = x)

 

   Ordine totale (riflessivo)

(Negri, Elementi di logica)

Relazione transitiva, riflessiva e antisimmetrica in cui tutti gli elementi sono confrontabili (Gallo) (Negri) (Mac Lane-Birkhoff, probabilmente, anche se non parlano in alcun punto di ordine totale)

Il fatto che l’ordine sia totale vuol dire che si ha :

( x,y) (x R y) (y R x) (y = x)

 

   Ordine totale irriflessivo o stretto

(Mendelson, Citrini)

Relazione transitiva, riflessiva e antisimmetrica in cui si ha anche: (∀ x,y) (x R y) (y R x) (y = x) (Mendelson)

Il fatto che l’ordine sia totale vuol dire che si ha :

( x,y) (x R y) (y R x) (y = x)

Questa condizione, con semplici passaggi diviene :

( x,y) (y = x) (x R y) (y R x)

da cui :

( x,y) (y = x) [(x R y) (y R x)]

da cui :

( x,y) [(x R y) (y R x)] y = x

da cui :

( x,y) [ (x R y) (y R x)] y = x

Sinonimo di “ordine totale” = relazione riflessiva, transitiva, antisimmetrica e connessa (Gallo) (Negri) (Mac Lane-Birkhoff)

 

   Proprietà della relazione di ordine. Ordine totale e parziale. Compatibilità della relazione di ordine con altre relazioni.

 

Compatibilità di un morfismo con una relazione di ordine parziale

Un morfismo tra insiemi parzialmente ordinati che conservi l’ordinamento è detto morfismo di ordine parziale.

 

compatibilità di una relazione con una relazione di equivalenza

In pratica, deve essere una relazione che possa passare al quoziente: nell'insieme quoziente deve poter valere tra due classi di equivalenza senza che influisca il cambiamento di rappresentante delle classi.

Le relazioni di ordine sono compatibili solo con la relazione di equivalenza discreta

Ad ogni relazione di preordine è associata una relazione quoziente che è una relazione di ordine

Date una relazione di preordine R e una relazione di equivalenza σ in un insieme I, definiamo una relazione di equivalenza σ nel seguente modo: aσb (aRb & bRa) la relazione quoziente R/σ è una relazione d'ordine

 

Relazione (di preordine o di ordine) parziale

“Una relazione di preordine o di ordine si dice parziale se esiste almeno una coppia di elementi di I non confrontabili”

 

Relazioni connesse e non connesse, totali e parziali .

Siano dati un insieme I e una relazione ρ di preordine, o di ordine, in I. Due elementi a e b di I si dicono "elementi confrontabili in una relazione di preordine o di ordine ρ" sse a ρ b, oppure b ρ a; altrimenti si dice che a e b non sono confrontabili

La relazione ρ si dice "relazione (di preordine o di ordine) totale" se tutte le coppie di elementi di I sono confrontabili; altrimenti si dice "relazione (di preordine o di ordine) parziale", e questo significa che esiste almeno una coppia di elementi di I non confrontabili.

usa il termine "relazione connessa" per indicare una relazione totale

 

Proprietà delle relazioni di preordine.

La relazione indotta da una relazione di preordine è di preordine

 

Proprietà delle relazioni di ordine.

La relazione indotta da una relazione di ordine è di ordine

Le relazioni di ordine (non quelle di preordine) sono compatibili solo con la relazione di equivalenza discreta.

Ad ogni relazione di preordine si può associare una relazione quoziente che è  una relazione di ordine.

Sia data una relazione σ di preordine in un insieme I. Definiamo mediante la σ la relazione ρ che segue:

a ρ b (aσb ^ bσa)

Valgono le seguenti proprietà:

  La relazione σ è una relazione di equivalenza

  La relazione σ è compatibile con ρ

  La relazione σ/ρ è una relazione di ordine

In conclusione, ad ogni relazione di preordine è  associata una relazione quoziente che è una relazione di ordine.

 

Grafi ed alberi delle relazioni di ordine.

I grafi di una relazione di ordine totale sono sempre linearizzabili, anche se possono assumere una forma non lineare. Vedi figure appunti manoscritti

 

siamo qui

 

 

   Elementi particolari in insiemi ordinati. Insiemi ben ordinati. Reticoli. Poset.

  Mentre Gallo (Un elemento β' di I appartenente ad S è detto "massimale in S" se: aS, a e β' non sono confrontabili oppure a β'

Elemento massimo e massimale coincidono se S è totalmente ordinato, mentre sono distinti se S lo è solo parzialmente.

maggiorante di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale)

Un elemento m' di I, non necessariamente appartenente ad S, si dice "maggiorante di S" se:

aS a m'

Il maggiorante è lo stesso che il confine superiore

confine superiore di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale)

E’ lo stesso che il maggiorante.

estremo superiore di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale)

Un elemento α' denotato con "sup S", non necessariamente appartenente ad S, si dice "estremo superiore di S" se:

aS a α'

aS (am') (α' m')

In altre parole, l’estremo superiore è il minimo dell’insieme dei maggioranti di S.

Se esiste un elemento m che è il massimo elemento di S, allora esso è anche l’estremo superiore di S

  Se esiste sup a allora è unico Un elemento α' di I è detto "massimo" o "ultimo elemento" di S se:

α' = sup S α' S

Tale elemento è spesso denotato come “max S

Se esiste un elemento m che è il massimo elemento di S, allora esso è anche l’estremo superiore di S

reticolo

Un insieme parzialmente ordinato è un reticolo se:

a,b A inf(a,b) A & sup(a,b) A.

buon ordine .

Un insieme nel quale ogni sottoinsieme non vuoto sia dotato di minimo (o primo elemento) lo diremo bene ordinato.

ogni suo sottoinsieme dispone di un elemento minimo

ogni sottoinsieme di un insieme ben ordinato è  ben ordinato

Se A è bene ordinato e B è simile ad A, anche B è  bene ordinato

L'unione di una famiglia di insiemi ben ordinati disgiunti due a due è ben ordinata

Tutti gli insiemi finiti totalmente ordinati, con uno stesso numero di elementi, sono bene ordinati e simili fra loro

Le first order theories with equality consentono di descrivere adeguatamente la antisimmetria della relazione di ordine non stretto?

Nozione di first order theory with equality Presupponiamo l'accettazione della semantica tarskiana. Non pare che una first order theory with equality possa descrivere esattamente una relazione antisimmetrica nel dominio di un modello

Un insieme è un insieme ben ordinato se ogni sottoinsieme ha un primo elemento (minimo)

Un insieme ordinato come quello sottostante non è ben ordinato, perché il sottoinsieme {g,h} non ha un primo elemento (minimo)

 

 

Un insieme ordinato come quello sottostante non è ben ordinato, perché l’insieme {h,c,d} non ha un primo elemento (minimo)

 

 

Rispetto alla relazione matematica "" l'insieme ω è un buon ordine, mentre non lo sono né R né Q

insieme parzialmente ordinato o “poset

Un insieme S è un insieme parzialmente ordinato o “poset” se esiste una relazione binaria R tale che:

(1) a S       a R a

(2) a,b S    a R b & b R a a = b

(3) a,b,c S   a R b & b R c a R c

Si noti che mentre la (2) e la (3) sussistono anche se tra gli elementi non esiste alcuna relazione (grafo vuoto) invece, in base alla (1), la relazione deve comunque essere riflessiva, e questo è richiesto anche da una definizione di ordine parziale come quella di Gallo:

 

   Il lemma di Zorn

  Lemma di Zorn

Un insieme non vuoto parzialmente ordinato S ammette almeno un elemento massimale, se ogni catena di suoi elementi ammette un elemento maggiorante in S

Per “catena” si intende un sottoinsieme di S totalmente ordinato

catena

Per catena si intende un sottoinsieme di S totalmente ordinato

 

   Nozioni varie alla rinfusa.

  complete lattice

Se vale inf{ai}iI A per ogni successione {ai}iI allora diremo che è un reticolo completo

Attenzione: non si dice che

inf{ai}iI {ai}iI

il minimo (massimo) confine superiore (inferiore) appartiene ad A ma non al sottoinsieme: altrimenti non si parlerebbe di confine, ma di massimo (minimo)

confine inferiore m di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale) .

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Si tratta del minorante

confine superiore m di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale) .

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Si tratta del maggiorante

confini universali

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Gli elementi minimo e massimo (unici) di tutto l'insieme parzialmente ordinato P, quando esistono, sono chiamati "confini universali" di P e verranno rappresentati rispettivamente con O ed I.

elementi confrontabili

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Due elementi di un insieme I si dicono confrontabili, data una relazione α di preordine o di ordine, se aσb o bσa

estremo inferiore (massimo confine inferiore) di un sottoinsieme S in un insieme I con una relazione di ordine (totale o parziale)

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Valgono le due condizioni:

(a S) ma

((a S) ba) (bm)

Non necessariamente m S

parla invece di massimo confine inferiore

Se esiste inf a allora è unico

relazioni confrontabili

Siano dati un insieme I ed una relazione σ di preordine, o di ordine, in I. Due elementi a e b di I si dicono confrontabili nella σ sse a σ b oppure b σ a

relazione connessa

Una relazione R è connessa se, per ogni a,b A, vale R(a,b) o R(b,a). La disgiunzione "o" non esclude il verificarsi di entrambi i disgiunti.

(x)(y) (x,yA & xy) xRy V yRx

(Suppes) 

Poiché AB equivale a B V A la condizione di Suppes equivale a: xRy V yRx V x=y

(x)(y) x,yA xRy V yRx

(Negri) Dice che talvolta per "connessa" si intende piuttosto una relazione di questo tipo e non del tipo precedente

relazione indotta da una relazione R in un sottoinsieme dell'insieme di riferimento

Dato un sottoinsieme I' dell'insieme di riferimento I, si dice che R induce una relazione R' in I' che collega due elementi di I' sse sono collegati in R

La relazione indotta da una relazione di preordine è di preordine; la relazione indotta da una relazione di ordine è di ordine Un insieme parzialmente ordinato (A,) è detto reticolo se per ogni a,b A, inf(a,b)A e sup(a,b)A. Attenzione: non si dice che inf(a,b) (a,b): il minimo (massimo) confine superiore (inferiore) appartiene ad A ma non alla coppia: altrimenti non si parlerebbe di confine, ma di massimo (minimo). Non è impossibile che un reticolo non sia totalmente ordinato: basti pensare al caso in cui due elementi a,b non hanno rapporto tra loro, ma sono primo termine di un rapporto con uno degli altri elementi e secondo termine di un rapporto con uno degli altri elementi.

massimo confine inferiore (estremo inferiore) di un sottoinsieme S in un insieme I con una relazione di ordine (totale o parziale)

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Valgono le due condizioni:

(a S) ma

((a S) ba) (bm)

Non necessariamente m S

parla invece di massimo confine inferiore

elemento minimale di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale)

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

E' un elemento m tale che:

mS

(aS) ma o non è confrontabile con a

Per ogni aS si ha che a ed m non sono confrontabili oppure che ma

Un elemento m S è detto minimale in S se non esiste un a S tale che a<m

minimo (primo elemento) di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale)

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Un elemento minimo m di S è tale che si hanno le tre condizioni:

mS

ma

per ogni aS + se esiste un elemento b tale che ba per ogni elemento di S allora si ha bm

Definizione a partire dal concetto di estremo inferiore

Si tratta di un estremo inferiore che appartiene ad S

Definizione a partire dal concetto di elemento minimale

Se m è un elemento minimale, e è confrontabile con tutti gli elementi di S si dice minimo

minorante (confine inferiore) m di un sottoinsieme S di un insieme I con una relazione di ordine (totale o parziale)

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

Elemento m tale che si ha:

(aS) ma

Non necessariamente m S

parla invece di confine inferiore

relazione di ordine lineare

Un ordine totale è detto anche lineare perché nella sua rappresentazione grafica è possibile disporre tutti i punti su una retta.

Vedi in proposito il quadro "Grafi (di rappresentazione) e alberi".

E’ sinonimo di Ordine totale

relazione di ordine parziale (riflessivo)

Vedi intestazione Ordering relation, che contiene la definizione completa di tutta la terminologia

relazione di ordine parziale irriflessivo

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

relazione di ordine parziale riflessivo

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

relazione di ordine parziale stretto

Sinonimo di Ordine parziale irriflessivo

relazione di ordine totale (riflessivo)

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

relazione di ordine totale irriflessivo

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

relazione di ordine totale riflessivo

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

relazione di ordine totale stretto

Sinonimo di Ordine totale riflessivo

relazione di ordine (preordine) parziale

Una relazione σ di preordine o di ordine si dice totale se tutte le coppie di dlementi di I sono confrontabili; altrimenti si dice parziale

relazione di preordine (riflessivo)

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

Questo nome è usato ad es. in Chiamiamo "relazione di preordine" una relazione in un insieme che sia riflessiva e transitiva

relazione di preordine parziale (riflessivo)

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

relazione di preordine totale (riflessivo)

Vedi Ordering relation, che contiene la definizione completa di tutta la terminologia

reflexive relation in a set A

(x) (xAxRx)

(Suppes) Qui c’è un problema: la definizione di Arangno differisce da tutte le altre perché utilizza la biimplicazione anziché l’implicazione. Penso che sia un refuso di stampa

(aRb & bRa) a=b

(Arangno)

(a)(b) (a,b A & aRb & bRa) a=b

(Negri)

(a)(b) (a,b A & aRb & bRa) a=b

(Suppes) Nei modelli "contracted to a normal model", come elementi si considerano le classi di equivalenza rispetto alla relazione di eguaglianza

relazione transitiva

(x)(y)(z) (x,y,zA & xRy & yRz) xRz

(Suppes) La relazione si dice totale, se tutte le coppie di elementi di I sono confrontabili; altrimenti si dice parziale

r-intersezione e r-unione

Vedi anche ALGEBRA ASTRATTA > Approfondimenti & Riepiloghi > Minorante, elemento minimale, massimo confine inferiore, estremo inferiore etc

In certi insiemi parzialmente ordinati si possono definire delle operazioni binarie di "r-intersezione" e di "r-unione". Siano x ed y due elementi di un insieme parzialmente ordinato X. Un elemento b X è un "confine inferiore" di x e y in X quando si ha bx e by. Un elemento m X è una "r-intersezione di x ed y" quando è un confine inferiore di x e y che contiene tutti i confini inferiori b. In altre parole, m è una r-intersezione di x e y se è:

(mx, my) & ((bx & by)  (bm))

Tale r-intersezione viene anche chiamata "massimo confine inferiore" (M.C.I.) di x e y.

r-intersezione e r-unione nel significato di minimo sottogruppo AB contenente la intersezione di due sottogruppi A e B e il minimo sottogruppo AB contenente la unione di due sottogruppi A e B

 

Un elemento u X è un "confine superiore" di x e y in X quando si ha xu e yu.

Un elemento l X è una "r-unione di x ed y" quando è un confine superiore di x e y ed è contenuto in tutti i confini superiori di x e y. In altre parole, l è una r-unione di x e y se è:

(x l, y l) & ((x l & y l)(l u))

Tale r-unione viene anche chiamata "minimo confine superiore" (m.c.s.) di x e y.

strict ordering relation

La relazione di ordine parziale stretto è una relazione transitiva e irriflessiva. Coincide con la definizione di ordine parziale di

può essere identificata con la relazione ">"

relazione di preordine (ordine) totale

Una relazione σ di preordine o di ordine si dice totale se tutte le coppie di dlementi di I sono confrontabili; altrimenti si dice parziale

well founded relation

Un insieme parzialmente ordinato da una relazione è  un insieme ben fondato se ogni sottoinsieme non vuoto di A ha un elemento minimale rispetto a

Una condizione equivalente per avere un insieme parzialmente ordinato ben fondato consiste nel richiedere che non esistano successioni {an}n∈ω tali che an>an+1

well ordered set

Un insieme nel quale ogni sottoinsieme non vuoto sia dotato di minimo (o primo elemento) lo diremo bene ordinato.

ogni suo sottoinsieme dispone di un elemento minimo

ogni sottoinsieme di un insieme ben ordinato è  ben ordinato

Se A è bene ordinato e B è simile ad A, anche B è  bene ordinato

L'unione di una famiglia di insiemi ben ordinati disgiunti due a due è ben ordinata

Tutti gli insiemi finiti totalmente ordinati, con uno stesso numero di elementi, sono bene ordinati e simili fra loro

Le first order theories with equality consentono di descrivere adeguatamente la antisimmetria della relazione di ordine non stretto?

Nozione di first order theory with equality Presupponiamo l'accettazione della semantica tarskiana. Non pare che una first order theory with equality possa descrivere esattamente una relazione antisimmetrica nel dominio di un modello

Un insieme è un insieme ben ordinato se ogni sottoinsieme ha un primo elemento (minimo)

Un insieme ordinato come quello sottostante non è ben ordinato, perché il sottoinsieme {g,h} non ha un primo elemento (minimo)

 

 

Un insieme ordinato come quello sottostante non è ben ordinato, perché l’insieme {h,c,d} non ha un primo elemento (minimo)

 

 

 

 

 

Le relazioni>Le relazioni di equivalenza

   Relazione di equivalenza.

   Classe di equivalenza.

   Proprietà delle classi di equivalenza.

   Insieme quoziente.

   Proprietà degli elementi di I/ρ.

   Proiezione canonica.

   Proprietà della proiezione canonica.

   Uguaglianza tra relazioni di equivalenza.

   Finezza delle relazioni di equivalenza.

   relazione indotta da una relazione di equivalenza.

   Proprietà della relazione indotta da una relazione di equivalenza.

 

 

   Relazione di equivalenza.

Chiamiamo "relazione di equivalenza" una relazione in un insieme che sia riflessiva, transitiva, simmetrica

 

   Classe di equivalenza.

Fissato a I chiamiamo "classe di equivalenza rappresentata da a", e la denotiamo con il simbolo "{a}ρ", l'insieme degli elementi di I in relazione ρ con a. L'elemento a si chiama "rappresentante di {a}ρ" Si usa dire che due elementi in relazione nella ρ sono tra loro "equivalenti ad a (nella ρ)".

Pensiamo all'uguaglianza in un insieme I; le classi di equivalenza sono tutte unitarie, essendo un elemento uguale solo a se stesso. Per questo l'uguaglianza si chiama "relazione di equivalenza discreta"

 

   Proprietà delle classi di equivalenza.

Gli elementi di {a}ρ sono tutti tra loro equivalenti

Una classe di equivalenza può essere rappresentata da uno qualunque dei suoi elementi

Nessuna classe è vuota

Ogni elemento di I appartiene ad almeno una classe

Due classi di equivalenza con un elemento comune coincidono (ossia ogni elemento di I appartiene al più ad una classe)

 

   Insieme quoziente.

Chiamiamo "insieme quoziente di I rispetto a ρ" e lo denotiamo con "I/ρ", l'insieme di tutte le classi di equivalenza di I rispetto aρ: I/ρ = {{a}ρ}aI

Dalla definizione segue I/ρ P(I)

Data una funzione f:XS la relazione Ef definita come:

z Ef X ⇐⇒ f(z) = f(x)

è una relazione di equivalenza,  chiamata nucleo di equivalenza di una funzione f

 

   Proprietà degli elementi di I/ρ.

{a}ρ φ aI

UaJ {a}ρ = I

({a}ρ ⋂ {b}ρ = φ, per {a}ρ {b}ρ) a ∼ρ b

I/ρ è una partizione di I Tale partizione è chiamata "partizione di I nelle classi di equivalenza rispetto a ρ"

Viceversa, data una partizione di I, si può definire una relazione in I nella quale due elementi di I sono in relazione se e solo se appartengono allo stesso insieme della partizione. Si dimostra che tale relazione è di equivalenza e che le sue classi di equivalenza sono proprio gli insiemi che costituiscono la partizione. Il passaggio da una relazione di equivalenza ad una partizione e viceversa è una bijezione. Sono allora fatti equivalenti dare una relazione di equivalenza in I o una partizione di I.

 

   Proiezione canonica.

Chiamiamo "proiezione canonica" la relazione π tra I e I/ρ definita ponendo:

π(x) = {x}ρ x I

 

   Proprietà della proiezione canonica.

La proiezione canonica è una suriezione

 

   Uguaglianza tra relazioni di equivalenza.

Due relazioni di equivalenza ρ e σ di grafi rispettivi R ed S, sono uguali sse : R = S e cioè: (a,b)R(a,b)S e cioè: aρb aσb e cioè: {a}ρ = {a}σ e cioè: I/ρ = I/σ

 

   Finezza delle relazioni di equivalenza.

Se "ρ è più fine di σ" si può scrivere: ρ σ ovvero: R S ovvero: (a,b)R (a,b)S ovvero: aρb aσb ovvero: {a}ρ {a}σ

La relazione di equivalenza discreta è più fine di ogni altra relazione di equivalenza

 

   relazione indotta da una relazione di equivalenza.

Se ρ è una relazione di equivalenza definita in un insieme I ed I' è un qualunque sottoinsieme non vuoto di I, ρ induce in I' una relazone ρ' nella quale due elementi di I' si corrispondono se, e solo se, sono legati da ρ, pensati come elementi di I.

 

   Proprietà della relazione indotta da una relazione di equivalenza.

La relazione indotta da una relazione di equivalenza è  di equivalenza

{a}ρ' = {a}ρ ⋂ I'

 

 

 

Le relazioni>La relazione di eguaglianza

Vedi TEORIA DEGLI INSIEMI > AXIOMATIC SET THEORY > APPROFONDIMENTI

 

 

 

Le funzioni>Dizionario

   FIXED point

   MONOTONE function .

 

 

   FIXED point

 

   MONOTONE function .

 

 

Le funzioni>Generali

   Le funzioni composte

 

  Funzione (o applicazione) .

Una relazione f:AB si dice "funzione (o applicazione)" se è ovunque definita e funzionale.

Diremo anche che f è una funzione su S verso T, oppure che f è una mappa o una trasformazione su S con insieme di arrivo T

Una relazione R XY è il grafico di una funzione XY sse per ciascun x X vi è uno ed un solo y Y tale che si abbia xRy

  Immagine e controimmagine

L’immagine di una funzione Im f è l’insieme di tutti i valori f() per s S

Dato un sottoinsieme S di U e una funzione f: U V si dice immagine per la f e si simboleggia f*(S) o f(S) l’immagine di S

Dato un sottoinsieme S di U e una funzione f: U V si dice controimmagine per la f e si simboleggia f*(S) o f-1(S) la controimmagine di S.

La f-1 è essa stessa una funzione

Si ha:

f(f-1(S)) U

f-1(f(S)) S

E’ commutativo il seguente diagramma:

 

 

 

 

 

Simbolismo di rappresentazione di una funzione

 

Uguaglianza tra funzioni

Due funzioni si dicono funzioni eguali quando sono eguali dominio, codominio e grafo

Relazione suriettiva

Una relazione f:AB si dice relazione suriettiva se ogni elemento di B ha almeno una controimmagine

Una funzione suriettiva si dice una "suriezione"

Relazione iniettiva .

Una relazione f:AB si dice “iniettiva” se ogni elemento di B ha al più una controimmagine.

Una funzione iniettiva si dice "iniezione"

Fare quindi attenzione: in una "iniezione" gli elementi di ciascuna coppia immagine-controimmagine non compaiono in nessun'altra coppia del grafo; in una "relazione iniettiva" possiamo avere un elemento del dominio che ha più di una immagine.

  Funzione bijettiva .

Chiamiamo "funzione bijettiva" o "bijezione" una relazione ovunque definita, funzionale, suriettiva e iniettiva.

  Bijezioni tra insiemi .

Nel caso di insiemi finiti non si può definire una bijezione tra un insieme ed un suo sottoinsieme proprio

Notiamo che, quando non si può parlare di "numero" di elementi di un insieme, cioè quando gli insiemi sono infiniti, si possono invece definire delle bijezioni tra un insieme e il suo sottoinsieme proprio.

Il simbolo f|A’ indica la restrizione della funzione f al sottoinsieme A’ del dominio A

“Map”

“Composite map” o “product map”

  Inversa destra,  inversa sinistra e inversa di una funzione

Si supponga che si abbiano le funzioni g:TS ed f: ST in modo tale che la funzione composta fg risulti definita. Se tale composta è l’identità 1T = fg si chiamerà f un’inversa sinistra di g e la g un’inversa destra della f. Quando le funzioni composte in entrambi gli ordini sono l’identità, cioè quando si ha fg = 1T e gf = 1S la f verrà chiamata inversa bilatera di g (e quindi g inversa bilatera di f.

Non necessariamente l’inversa f-1di f è il grafo inverso di quello di f; il grafo inverso di f potrebbe non essere una funzione, e quindi non essere un’inversa

Quale dominio ha l’inversa?

Il dominio di f–1 non è limitato a f(S) dove S è il dominio di f, ma comprende tutto il codominio di f

Può esistere più di un’inversa?

f ha un’unica inversa sinistra sse f è iniettiva;

Una inversa destra di f può essere definita sse f è suriettiva.

Infatti ff-1 = IA implica che f sia suriettiva, altrimenti non c’è modo che, arrivati al dominio con f-1, possa essere raggiunto qualsiasi elemento del codominio.

Una inversa bilatera di f può essere definita solo se f è una biiezione

Una funzione avente dominio non vuoto è una iniezione sse ha un’inversa sinistra ed è una suriezione sse ha un’inversa destra.

La dimostrazione dell’ultima parte di questo teorema impiega l’assioma di scelta

(Stralcio della dimostrazione) …Viceversa, si supponga che la f: ST sia suriettiva; ciò significa che per ogni t T vi è almeno un sS con f(s) = t. Si scelga un s siffatto per ciascun t e si definisca la g: tS prendendo per g(t) l’s scelto. Allora è f(g(t)) = t, per cui si ha fg=1T e la g è l’inversa destra richiesta.

Questa dimostrazione dipende dal fatto di poter fare un numero (eventualmente) infinito di scelte (un s S con f(s) = t per ciascun t T). In una trattazione assiomatica della teoria degli insiemi, quando tutte le operazioni sugli insiemi sono derivate da una lista comkpleta di assiomi formali sulla relazione di appartenenza x S, uno degli assiomi enuncia che si può fare un tale insieme di scelte. Questo assioma, chiamato “assioma di scelta” afferma che per ciascun insieme , i cui elementi siano insiemi disgiunti non vuoti, esiste un insieme C tale che ciascun CS, con S , ha esattamente un elemento. In effetti questo assioma è equivalente all’ipotesi che ogni suriezione abbia un’inversa destra.

Le seguenti proprietà di una funzione g: TS sono equivalenti:

g è una biiezione

g ha sia un’inversa sinistra f che un’inversa destra h

g ha un’inversa bilatera

  Trasformazioni .

Si parla di "trasformazioni" per indicare le bijezioni, cioè le corrispondenze biunivoche tra un insieme e se stesso.

Identità in un insieme .

Dato un insieme A, chiamiamo "identità in A" e la denotiamo col simbolo "iA", la relazione tra A ed A che ha come grafo la diagonale di AxA

La funzione vuota .

|Quando C = si ha f/C = , dove f/C è la restrizione di f a C. Infatti anche è una funzione, la funzione vuota.

Ciò accade perché degli elementi di , in quanto non esistenti, si può predicare qualsiasi proprietà. Infatti ogni asserzione del genere avrà la forma:

x  x P(x)

Poiché l'antecedente dell'implicazione è sempre falso, l'asserzione nel suo complesso sarà sempre vera. L'insieme vuoto di cani coincide con l'insieme vuoto di gatti che a sua volta è identico a un insieme vuoto di coppie ordinate che soddisfino la condizione di univocità tipica di una funzione: in ogni caso si tratta sempre di .

Non si può neanche dire che "la funzione vuota è quella tale che nessun elemento del dominio ha un'immagine", perché, come dice La funzione S con S è iniettiva ma non ha inversa sinistra

  Insiemi di funzioni

L’insieme di funzioni SX è definito come l’insieme consistente di tutte le funzioni da X verso S:

SX = {f | f:XS}

Gli elementi di un insieme S possono essere considerati funzioni 1 S