Relazioni d'ordine

[Pdirac]

Salve...

Riguardo teoria degli insiemi (dovrebbe essere logica matematica quindi è la sezione giusta spero), ho una questione in merito alla definizione di relazione d'ordine.

Dal mio testo di matematica leggo che:
"Una relazione R in un insieme A è detta relazione d'irdine largo se e solo se gode della proprietà riflessiva, transitiva, antisimmetrica, mentre è detta relazione d'ordine stretto se gode soltanto delle proprietà transitiva e antisimmetrica."

Dato che non è citata alcuna definizione vera e propria su come è definita in generale una relazione d'ordine ho cercato chiarimenti, in particolare sull'onnipresente wikipedia, prima sulla relativa pagina in italiano e poi su quella internazionale (normalmente più affidabile).
Il risultato è stata una confusione maggiore dato che ognuno dà una sua definizione: per dirne una, sulla wiki italiana cita a inizio pagina che in generale una relazione d'ordine è detta una relazione binaria che gode di riflessività, transitività e antisimmetria, mentre nella wiki inglese distingue tra relazione d'ordine totale e parziale, dove la prima gode di transitività, antisimmetria e "totalità", a differenza della relazione d'ordine stretto che invece di "totalità" gode di riflessività.

Chi ha ragione? Più in generale, questa è una discrepanza (almeno così è sembrata a me) particolare... sapreste indirizzarmi ad una fonte affidabile (online perché non posso reperire libri particolari allo stato attuale) riguardo questo argomento (o dirmi quale delle mie fonti attuali è affidabile il che è lo stesso)?

Grazie

[Martino]

Non c'è nessuna discrepanza tra le tue fonti.

non è citata alcuna definizione vera e propria su come è definita in generale una relazione d'ordine

Non capisco cosa vuoi dire. La definizione di una relazione d'ordine è semplicemente l'elenco delle sue proprietà caratterizzanti. Forse intendi dire che vorresti vedere degli esempi?

Cerco di farti un riassunto.

Una relazione su un insieme A è un sottoinsieme R del prodotto cartesiano [tex]A \times A[/tex]. Fissata una relazione R su A, dati [tex]a,b \in A[/tex] diremo che "[tex]a[/tex] è in relazione R con [tex]b[/tex]" o più semplicemente "[tex]a[/tex] è in relazione con [tex]b[/tex]" (ove R è sottintesa) se [tex](a,b) \in R[/tex].

Una relazione R su un insieme A si dice:

- riflessiva se [tex](a,a) \in R[/tex] per ogni [tex]a \in A[/tex], cioè se ogni elemento di A è in relazione con se stesso.

- simmetrica se ogni volta che [tex](a,b) \in R[/tex] allora anche [tex](b,a) \in R[/tex], in altre parole ogni volta che a è in relazione con b succede che anche b è in relazione con a.

- antisimmetrica se ogni volta che [tex](a,b) \in R[/tex] e [tex](b,a) \in R[/tex] si ha [tex]a=b[/tex]. Equivalentemente, se [tex](a,b) \in R[/tex] e [tex]a \neq b[/tex] allora [tex](b,a) \not \in R[/tex]. In altre parole non ci sono due elementi distinti che sono in relazione nei due versi.

- transitiva se ogni volta che [tex](a,b) \in R[/tex] e [tex](b,c) \in R[/tex] si ha [tex](a,c) \in R[/tex]. In altre parole se un primo elemento è in relazione con un secondo e questo secondo con un terzo allora il primo è in relazione col terzo.

- totale se per ogni [tex]a,b \in A[/tex] si ha [tex](a,b) \in R[/tex] oppure [tex](b,a) \in R[/tex]. In altre parole se ogni coppia di elementi è "confrontabile" (cioè il primo è in relazione col secondo oppure il secondo col primo) tramite la relazione R.

Per esempio dato l'insieme [tex]\mathbb{N}[/tex] dei numeri naturali, puoi considerare le seguenti relazioni su [tex]\mathbb{N}[/tex]:

- l'uguaglianza (cioè la relazione "[tex]=[/tex]" = [tex]\{(n,n)\ |\ n \in \mathbb{N}\}[/tex]) è una relazione riflessiva, simmetrica, antisimmetrica, transitiva, non totale.
- la diversità (cioè la relazione "[tex]\neq[/tex]" = [tex]\{(n,m) \in \mathbb{N}\ |\ n \neq m\}[/tex], l'insieme degli elementi di [tex]\mathbb{N} \times \mathbb{N}[/tex] fuori da [tex]=[/tex]) è una relazione non riflessiva, simmetrica, non antisimmetrica, non transitiva, non totale.
- [tex]\leq[/tex] (cioè la relazione "[tex]\leq[/tex]" = [tex]\{(n,m) \in \mathbb{N}\ |\ n \leq m\}[/tex]) è una relazione riflessiva, non simmetrica, antisimmetrica, transitiva, totale.
- [tex]<[/tex] (cioè la relazione "[tex]<[/tex]" = [tex]\{(n,m) \in \mathbb{N}\ |\ n - avere la stessa parità (cioè la relazione [tex]\{(n,m) \in \mathbb{N}\ |\ |n-m|\ è\ pari\}[/tex]) è una relazione riflessiva, simmetrica, non antisimmetrica, transitiva, non totale.

Ora, una relazione R su un insieme A si dice relazione d'ordine parziale se è riflessiva, antisimmetrica e transitiva. Per esempio di quelle elencate finora solo [tex]=[/tex] e [tex]\leq[/tex] sono relazioni d'ordine parziale.

Una relazione d'ordine parziale R su un insieme A che sia totale si dice relazione d'ordine totale. Per esempio [tex]\leq[/tex] di cui sopra è una relazione d'ordine totale, mentre [tex]=[/tex] non lo è.

PS. Per caso ti stai preparando per iscriverti a matematica?

[Pdirac]

Innanzitutto grazie per l'esauriente risposta. Solo alcune domande per capire bene:

I) La notazione $(a,b)$ sta a significare ovviamente una coppia di elementi; è intrinseco nella definizione che questa sia una coppia ordinata (ovvero che sia significante l'ordine in cui appaiono gli elementi)?

II) La definizione di relazione del mio testo dice genericamente che

una relazione binaria di A in B è un sottoinsieme del loro prodotto cartesiano. In simboli è un grafo G tale che: $G = { (x;y) in AxxB| x in A,y in B,xRy}$

Nella tua definizione hai specificato che R è un sottoinsieme di $AxxA$, mentre qui parla più genericamente di due insiemi, quale prendo per buona?

III) Riguardo il tuo esempio sulla relazione d'uguaglianza: considerando l'antisimmetria di tale relazione, non si entra in ridondanza? Intendo dire che in questo caso la relazione di uguaglianza è sia oggetto dell'analisi (non so se si può propriamente definire analisi) che strumento con il quale viene condotta... o si tratta di due eguaglianze di tipo diverso pur essendo il simbolo usato uguale (del tipo che una riguarda specificatamente i numeri naturali mentre l'altra è equivalenza tra insieme) ?
Come si interpreta questa proprietà antisimmetrica? "Se $a=b$ e $b=a$, allora $a != b$" ? Non è un assurdo?

IV)

(cioè la relazione "" = , che non è altro che ) è una relazione non riflessiva, non simmetrica, antisimmetrica, transitiva, non totale.

Come fa ad essere antisimmetrica? Non significherebbe forse che "Se $a
V)

- avere la stessa parità (cioè la relazione ) è una relazione riflessiva, simmetrica, non antisimmetrica, transitiva, non totale.

Ma lo 0 è considerato pari? Sarei propenso a dire di sì perché in effetti è divisibile per due (come per qualunque altro numero), e viene prima di un numero dispari, ma incredibilmente non mi era mai sorta la questione seriamente!

VI)

Ora, una relazione R su un insieme A si dice relazione d'ordine parziale se è riflessiva, antisimmetrica e transitiva. Per esempio di quelle elencate finora solo $<$ e $<=$ sono relazioni d'ordine parziale.

Ma prima hai fatto notare giustamente che la relazione $<$ è non riflessiva!

VII) Mi hai definito una relazione d'ordine parziale come riflessiva antisimmetrica e transitiva; nel mio testo leggo d'altra parte un'altra distinzione in relazione d'ordine largo per cui vigono le proprietà da te citate e in relazione d'ordine stretto per cui non vale la riflessività (il che tral'altro permetterebbe di includere la relazione $<$), mentre parla di "ordine parziale" quando esiste almeno una coppia di elementi x e y per cui non vale né xRy né yRx.


Ps. Per evitare incomprensioni: non voglio in alcun modo puntualizzare eventuali errori, semplicemente mi piace la precisione e il rigore nelle definizioni, e voglio averne un quadro chiaro =).

Pps. Un'ulteriore domanda (sperando di non esagerare) non direttamente inerente ma neanche troppo off topic: la proprietà di associatività, è definibile al di fuori degli insiemi numerici?

Ppps. Più direttamente mi sto preparando per tentare Fisica, ma il test è tanto di fisica quanto di matematica!

[Martino]

"Pdirac":I) La notazione $(a,b)$ sta a significare ovviamente una coppia di elementi; è intrinseco nella definizione che questa sia una coppia ordinata (ovvero che sia significante l'ordine in cui appaiono gli elementi)?

Sì, è intrinseco. O meglio, si può definire la coppia ordinata (a,b) in modo che si possa parlare di a come "primo elemento" e di b come "secondo elemento".

II) La definizione di relazione del mio testo dice genericamente che [quote]una relazione binaria di A in B è un sottoinsieme del loro prodotto cartesiano. In simboli è un grafo G tale che: $G = { (x;y) in AxxB| x in A,y in B,xRy}$

Nella tua definizione hai specificato che R è un sottoinsieme di $AxxA$, mentre qui parla più genericamente di due insiemi, quale prendo per buona?[/quote]Sono entrambe buone, quella con due insiemi è più generale. Quella che ti ho proposto io è un caso particolare, ed è comunque il caso più frequente.

III) Riguardo il tuo esempio sulla relazione d'uguaglianza: considerando l'antisimmetria di tale relazione, non si entra in ridondanza? Intendo dire che in questo caso la relazione di uguaglianza è sia oggetto dell'analisi (non so se si può propriamente definire analisi) che strumento con il quale viene condotta... o si tratta di due eguaglianze di tipo diverso pur essendo il simbolo usato uguale (del tipo che una riguarda specificatamente i numeri naturali mentre l'altra è equivalenza tra insieme) ?

Certo, ma bisogna distinguere tra uguaglianza "teorica" e uguaglianza "metateorica". Io dico semplicemente che la relazione di uguaglianza su A è per definizione l'insieme [tex]\{(a,a)\ |\ a \in A\}[/tex] (contenuto in [tex]A \times A[/tex]), e ne indago le proprietà.

Come si interpreta questa proprietà antisimmetrica? "Se $a=b$ e $b=a$, allora $a != b$" ? Non è un assurdo?

Scusami ho sbagliato, in realtà = è una relazione antisimmetrica (banalmente). Ho corretto.

IV) [quote] (cioè la relazione "" = , che non è altro che ) è una relazione non riflessiva, non simmetrica, antisimmetrica, transitiva, non totale.

Come fa ad essere antisimmetrica? Non significherebbe forse che "Se $a

V) [quote]- avere la stessa parità (cioè la relazione ) è una relazione riflessiva, simmetrica, non antisimmetrica, transitiva, non totale.

Ma lo 0 è considerato pari? Sarei propenso a dire di sì perché in effetti è divisibile per due (come per qualunque altro numero), e viene prima di un numero dispari, ma incredibilmente non mi era mai sorta la questione seriamente![/quote]Certo, 0 è pari, essendo divisibile per 2: $0=2*0$.

VI) [quote]Ora, una relazione R su un insieme A si dice relazione d'ordine parziale se è riflessiva, antisimmetrica e transitiva. Per esempio di quelle elencate finora solo $<$ e $<=$ sono relazioni d'ordine parziale.

Ma prima hai fatto notare giustamente che la relazione $<$ è non riflessiva![/quote]Hai ragione, scusa ho sbagliato, spero di non averti fatto confusione. $<$ non è una relazione d'ordine parziale, diciamo che lo è a meno della riflessività.

VII) Mi hai definito una relazione d'ordine parziale come riflessiva antisimmetrica e transitiva; nel mio testo leggo d'altra parte un'altra distinzione in relazione d'ordine largo per cui vigono le proprietà da te citate e in relazione d'ordine stretto per cui non vale la riflessività (il che tral'altro permetterebbe di includere la relazione $<$), mentre parla di "ordine parziale" quando esiste almeno una coppia di elementi x e y per cui non vale né xRy né yRx.

Ok, qui si tratta di accordarsi sulle convenzioni. Il tuo testo chiede a una relazione parziale di non essere totale. Io chiamo ordine totale un ordine parziale che sia anche totale. Si tratta di una lieve divergenza che comunque non crea problemi. Basta saperlo.

Ps. Per evitare incomprensioni: non voglio in alcun modo puntualizzare eventuali errori, semplicemente mi piace la precisione e il rigore nelle definizioni, e voglio averne un quadro chiaro =).

Certo lo so

Pps. Un'ulteriore domanda (sperando di non esagerare) non direttamente inerente ma neanche troppo off topic: la proprietà di associatività, è definibile al di fuori degli insiemi numerici?

Certo, in generale nelle strutture algebriche ci sono operazioni associative, e non riguardano necessariamente numeri. Per esempio la composizione di funzioni è associativa: se f,g,h sono tre funzioni allora [tex](f \circ g) \circ h = f \circ (g \circ h)[/tex] ogni volta che i due membri dell'uguaglianza hanno senso.

PS. Osserva che ho corretto il mio primo intervento: le uniche due relazioni d'ordine parziale tra quelle che ho elencato sono $=$ (non totale) e $\leq$ (totale).

[Pdirac]

Grazie mille per le delucidazioni...
Ecco la seconda ondata di domande!

I)

"Martino":Certo, ma bisogna distinguere tra uguaglianza "teorica" e uguaglianza "metateorica". Io dico semplicemente che la relazione di uguaglianza su A è per definizione l'insieme [tex]\{(a,a)\ |\ a \in A\}[/tex] (contenuto in [tex]A \times A[/tex]), e ne indago le proprietà.

I.1)Quando parli di insieme di coppie ordinate $(a,a)$ fai riferimento alla classe di equivalenza di a? in caso contrario questa definizione non escluderebbe dalla relazione vari elementi che sono uguali? (es: $A={1,1,2,3,4,4}$, se mi riferisco ad $a$ prendo in esame un singolo elemento, per esempio "il secondo 1 dell'insieme, mentre se mi riferisco alla classe di equivalenza dell'elemento a prendo in esame, per esempio, tutti gli uno dell'insieme. E' giusto?

I.2)E "metateoricamente" come si definisce la relazione di uguaglianza?

II)

La proposizione "se $a
Capisco che non può essere falsa, d'altra parte non capisco come può essere vera: le relazione di minoranza non include l'uguaglianza, dunque dire che $a4$"? Ma se questa proposizione è sempre falsa come si può parlare di antisimmetria o non antisimmetria, che nella definizione richiede che questa proposizione sia verificata?
In più hai specificato che $<$ non è totale, il che andrebbe a puntualizzare che $a
III)

Ok, qui si tratta di accordarsi sulle convenzioni. Il tuo testo chiede a una relazione parziale di non essere totale. Io chiamo ordine totale un ordine parziale che sia anche totale. Si tratta di una lieve divergenza che comunque non crea problemi. Basta saperlo.

Non mi riferivo direttamente a quello, ma al fatto che nel mio testo le proprietà di "parzialità" o "totalità" di una relazione d'ordine non sono definite a partire dalle proprietà di riflessività, transitività, antisimmetria o simmetria, ma a partire esclusivamente dalla proprietà di totalità della relazione; mentre parla di "ordine stretto" o "ordine largo" riferendosi al godere di antisimmetria, transitività, e in caso dell'ultimo riflessività.
Viveversa tu hai parlato di "ordine parziale" con più generico riferimento alle proprietà.
(sono troppo pignolo? =P )


IV)

Certo, in generale nelle strutture algebriche ci sono operazioni associative, e non riguardano necessariamente numeri. Per esempio la composizione di funzioni è associativa: se f,g,h sono tre funzioni allora [tex](f \circ g) \circ h = f \circ (g \circ h)[/tex] ogni volta che i due membri dell'uguaglianza hanno senso.

Il dubbio mi era sorto considerando ad esempio la proprietà di associatività in merito al tipo di relazioni quali quelle che hai citato nei tuoi esempi. La differenza principale mi sembra che sorga dal fatto che per relazioni di tipo $+$, o [tex]\circ[/tex] è "restituito" (si può dire così?) un valore di tipo numerico, o comunque un'altra funzione che a sua volta può essere relazionata ad altre funzioni. Viveversa in relazioni quali $<$ cio che è restituito è un valore booleano di tipo vero/falso, che difficilmente può a sua volta essere relazionato o considerato "minore" o "maggiore" di un altro numero.
Per questo immagino che esista una classificazione fondamentale di qualche tipo che suddivida le relazioni in quelle che sono solo "vere" o "false" e in quelle che invece non sono vere o false ma semplicemente restituiscono un numero o comunque un altro elemento ulteriormente relazionabile... solo che non ne ho mai avuto accenni.

[Martino]

"Pdirac":I.1)Quando parli di insieme di coppie ordinate $(a,a)$ fai riferimento alla classe di equivalenza di a?

No, faccio semplicemente riferimento a come è definita la relazione. La classe di uguaglianza di [tex]a \in A[/tex] (cioè la sua classe di equivalenza relativa alla relazione di uguaglianza, che è un'equivalenza) è ovviamente l'insieme [tex]\{a\}[/tex].

in caso contrario questa definizione non escluderebbe dalla relazione vari elementi che sono uguali? (es: $A={1,1,2,3,4,4}$, se mi riferisco ad $a$ prendo in esame un singolo elemento, per esempio "il secondo 1 dell'insieme, mentre se mi riferisco alla classe di equivalenza dell'elemento a prendo in esame, per esempio, tutti gli uno dell'insieme. E' giusto?

In teoria degli insiemi due elementi distinti di un insieme sono davvero distinti. In altre parole, stando sul tuo esempio, si ha che [tex]\{1,1,2,3,4,4\}[/tex] è uguale all'insieme [tex]\{1,2,3,4\}[/tex]. Se vuoi distinguere i due 1 e i due 4 devi chiamarli con nomi diversi. L'uguaglianza è relativa all'entità degli elementi, se due elementi sono uguali non è che non sono distinguibili, più semplicemente non sono due.

I.2)E "metateoricamente" come si definisce la relazione di uguaglianza?

Non si definisce. La relazione di uguaglianza è troppo primitiva per essere definita. Se vuoi puoi prendere questa come "definizione" (cf. il paragrafo di cui sopra): due elementi sono uguali se non sono due.

II)
[quote]La proposizione "se $a
Capisco che non può essere falsa, d'altra parte non capisco come può essere vera: le relazione di minoranza non include l'uguaglianza, dunque dire che $a4$"? Ma se questa proposizione è sempre falsa come si può parlare di antisimmetria o non antisimmetria, che nella definizione richiede che questa proposizione sia verificata?[/quote]Quello che dici riguarda la tabella di verità dell'implicazione logica (clic). Se la premessa è falsa e la conclusione è vera, l'implicazione è vera. Quindi "se 4<4 e 4>4 allora 4=4" è una proposizione vera. Infatti "4<4 e 4>4" è falsa, e "4=4" è vera.

In più hai specificato che $<$ non è totale, il che andrebbe a puntualizzare che $aEsatto, < non è totale appunto perché a

III)[quote]Ok, qui si tratta di accordarsi sulle convenzioni. Il tuo testo chiede a una relazione parziale di non essere totale. Io chiamo ordine totale un ordine parziale che sia anche totale. Si tratta di una lieve divergenza che comunque non crea problemi. Basta saperlo.

Non mi riferivo direttamente a quello, ma al fatto che nel mio testo le proprietà di "parzialità" o "totalità" di una relazione d'ordine non sono definite a partire dalle proprietà di riflessività, transitività, antisimmetria o simmetria, ma a partire esclusivamente dalla proprietà di totalità della relazione; mentre parla di "ordine stretto" o "ordine largo" riferendosi al godere di antisimmetria, transitività, e in caso dell'ultimo riflessività.
Viveversa tu hai parlato di "ordine parziale" con più generico riferimento alle proprietà.
(sono troppo pignolo? =P )[/quote]Anche fosse, fai bene ad essere pignolo.
Possiamo risolvere la cosa così:

Ordine parziale largo: è una relazione riflessiva, antisimmetrica e transitiva.
Ordine parziale stretto: è una relazione antisimmetrica e transitiva.
Ordine totale: è una relazione riflessiva, antisimmetrica, transitiva e totale.

Poi ovviamente ognuno parte da dove vuole per definire gli ordini, ma credo che possiamo essere d'accordo in partenza su queste tre definizioni.

La differenza principale mi sembra che sorga dal fatto che per relazioni di tipo $+$, o [tex]\circ[/tex] è "restituito" (si può dire così?) un valore di tipo numerico, o comunque un'altra funzione che a sua volta può essere relazionata ad altre funzioni. Viveversa in relazioni quali $<$ cio che è restituito è un valore booleano di tipo vero/falso, che difficilmente può a sua volta essere relazionato o considerato "minore" o "maggiore" di un altro numero.

No no attenzione! [tex]+[/tex] e [tex]\circ[/tex] non sono relazioni, sono operazioni. C'è una differenza fondamentale:

- una relazione su A è un sottoinsieme di [tex]A \times A[/tex];
- una operazione su A è una funzione [tex]A \times A \to A[/tex].

Non c'è nessun legame canonico tra relazioni e operazioni su un insieme A.
Come ho detto, [tex]+[/tex] e [tex]\circ[/tex] sono operazioni, mentre [tex]<,\leq,=,\neq[/tex] sono relazioni.

Una relazione ti dice solo se due elementi dati sono o meno "relazionati" (appunto), mentre una operazione prende due elementi e te ne restituisce un terzo. Capisci quindi che una relazione e una operazione sono due concetti distinti che non c'entrano nulla uno con l'altro.

Per questo immagino che esista una classificazione fondamentale di qualche tipo che suddivida le relazioni in quelle che sono solo "vere" o "false" e in quelle che invece non sono vere o false ma semplicemente restituiscono un numero o comunque un altro elemento ulteriormente relazionabile... solo che non ne ho mai avuto accenni.

Spero di averti chiarito questo punto qui sopra.

[Pdirac]

Possiamo risolvere la cosa così:

Ordine parziale largo: è una relazione riflessiva, antisimmetrica e transitiva.
Ordine parziale stretto: è una relazione antisimmetrica e transitiva.
Ordine totale: è una relazione riflessiva, antisimmetrica, transitiva e totale.

Mentre una relazione antisimmetrica, transitiva, non riflessiva e totale è impossibile perché se non è riflessiva posso prendere la coppia di elementi (a,a) che non sono relazionabili tra loro e quindi la relazione non è totale, giusto? (apparte che suonerebbe molto male "relazione d'ordine totale stretta"...)

- una relazione su A è un sottoinsieme di [tex]A \times A[/tex];
- una operazione su A è una funzione [tex]A \times A \to A[/tex].

Cito dal mio testo: "Esistono poi relazioni tra due insieme A e B che non sono né di ordine né di equivalenza: un caso particolare è la corrispondenza, dove si chiama corrispondenza tra due insiemi A e B una legge f che associa ad ogni elemento di A uno o più elementi di B". Mi definisce poi la funzione come una corrispondenza che ad ogni $x in A$ fa corrispondere in f uno e un solo $y in B$.
Da come è detto qui sembra che dica che un'applicazione, ovvero una funzione è un tipo particolare di relazione, ma pur sempre una relazione. Sbaglio io ad interpretare?

[Martino]

"Pdirac":una relazione antisimmetrica, transitiva, non riflessiva e totale è impossibile perché se non è riflessiva posso prendere la coppia di elementi (a,a) che non sono relazionabili tra loro e quindi la relazione non è totale, giusto?

Giusto.

[quote]
- una relazione su A è un sottoinsieme di [tex]A \times A[/tex];
- una operazione su A è una funzione [tex]A \times A \to A[/tex].

Cito dal mio testo: "Esistono poi relazioni tra due insieme A e B che non sono né di ordine né di equivalenza: un caso particolare è la corrispondenza, dove si chiama corrispondenza tra due insiemi A e B una legge f che associa ad ogni elemento di A uno o più elementi di B". Mi definisce poi la funzione come una corrispondenza che ad ogni $x in A$ fa corrispondere in f uno e un solo $y in B$.
Da come è detto qui sembra che dica che un'applicazione, ovvero una funzione è un tipo particolare di relazione, ma pur sempre una relazione. Sbaglio io ad interpretare?[/quote]Sapevo che avresti mosso questa obiezione. Il fatto è che io parlavo di relazioni e operazioni sullo stesso insieme A. Una operazione su A è una funzione [tex]A \to A \times A[/tex], quindi non è una relazione su A. Invece una funzione [tex]A \to A[/tex] è una relazione su A.

Se proprio vogliamo, una operazione su A è in particolare una relazione tra [tex]A \times A[/tex] e [tex]A[/tex].

Il discorso che facevi tu è legato al seguente fatto: puoi vedere una relazione su A come una funzione [tex]A \times A \to \{\text{vero},\ \text{falso}\}[/tex]. Ma questo semplicemente perché ogni sottoinsieme di un dato insieme B si può vedere come una funzione (per esempio) [tex]B \to \{0,1\}[/tex] (mandi un elemento di B in 0 se non sta nel sottoinsieme, in 1 se ci sta).

Quindi puoi vedere una relazione come una regola che ti associa ad ogni coppia un valore booleano ("vero" o "falso") ma attenzione: questo non è quello che fa un'operazione. Un'operazione prende due elementi di un insieme e ti restituisce un terzo elemento dello stesso insieme.

[ViciousGoblin]

Rispetto all'ultima risposta di Martino (che stavo cercando di scrivere anch'io, ma mi pare inutile ) vorrei aggiungere una cosa, che forse è quello che
viene adombrato nel testo di Pdirac

Presentare una relazione $r$ come un sottoinsieme $R$ di $A\times B$ (che è la cosa più pulita probabilmente) vuol dire che
$r(x,y)$ è vera se e solo se $(x,y)\in R$.

Nello stesso modo si dovrebbe introdurre una funzione $f$ da $A$ in $B$ mediante il suo "grafico", cioè l'insieme delle coppie
$(x,y)$ tali che $x\in A$, $y\in B$ e $y=f(x)$.

In questo senso le funzioni sono particolari relazioni $r$ tali che per ogni $x$ in $A$ esiste al più un elemento $y$ tale che $r(x,y)$ è vera
(e tale $y$ si chiama $f(x)$).

[Pdirac]

Per curiosità, ma esiste una definizione definita e "assoluta" o ogni autore dà la sua?

Cercando di sgrovigliare la matassa:

@martino

I) riguardo a relazioni e operazioni definite sullo stesso insieme $A$, dimmi se ho capito:
Un operazione è una funzione che ad ogni elemento di A associa una coppia ordinata appertenente al prodotto cartesiano $A^2$, e non è una relazione.
Viceversa una funzione che ad ogni elemento di A gliene associa un altro sempre appartente ad A è una relazione.

Se ne desume che una funzione può essere una relazione, ma può anche non esserlo.

Ma una funzione è definita come $AxxA$[tex]\longrightarrow[/tex]$A$ o come $A$[tex]\longrightarrow[/tex]$AxxA$ ?

II) Un operazione è una funzione definibile esclusivamente come associante un insieme a se stesso?

III) Un operazione è comunque interpretabile come una relazione, come lo è una funzione... ma allora l'operazione che associa ad un prodotto cartesiano $AxxA$ un altro elemento di $A$ è o non è una relazione?

@viciousgoblin

IV) Non sono sicuro di aver colto la differenza tra le tue prime due definizioni: non è allo stesso modo affermabile che una funzione f è vera se una coppiia di punti appartiene al suo grafo? Per esempio considerando la funzione y=2x, tale funzione è considerabile vera ad esempio per le coppie $(1,2),(2,4),...,(50,100),...$ e così via.

V)
Riepigolando:

Una relazione è un sottoinsieme del prodotto cartesiano degli insiemi su cui è definita (siano essi uno o più, divergenti o coincidenti).

Una corrispondenza è un particolare tipo di relazione in cui per ogni $x in D(R)$, $xRy$ dove y è un elemento del secondo insieme. Per una corrispondenza quindi ogni elemento del primo insieme deve essere associato ad almeno 1 elemento del secondo insieme.

Una funzione (o applicazione) è un particolare tipo di corrispondenza, e dunque di relazione, in cui ogni elemento del dominio deve essere associato a uno e un solo elemento del codominio.

Un operazione è un particolare tipo di funzione, e quindi di corrispondenza e di relazione, che è definita in un insieme in sé stesso, e che associa a ogni coppia ordinata del prodotto cartesiano dell'insieme in se stesso (ovvero $A^2$) un altro elemento sempre appartentente allo stesso insieme.
E' sempre definibile una relazione, vera per ogni terna (o più) di elementi che appartiene alla relazione (per esempio $y = x +b$ è vera per ogni terna del tipo $(1,2,3),(5,4,9)$ e così via).


E' corretto?

[ViciousGoblin]

Rispondo velocemente (perché devo uscire a fare la spesa ...), cercando di darti l'idea - dopo di che cercheremo di capire quale sia la definizione più soddisfacente.

Una relazione è qualcosa che restituisce vero/falso - quando dici che Giovanni è più alto di Giacomo non c'è nessuna corrispondenza tra Giovanni e Giacomo, ma appunto
una relazione tra i due che può essere vera o falsa.

Una funzione è qualcosa che restituisce un risultato, per esempio "PADRE di" è la funzione che a ogni essere umano fa corrispondere il suo genitore maschile.

Un'operazione di solito è una funzione definita a partire da coppie di "numeri", che restituisce come valore un altro numero.


Quando poi vai a formalizzare queste nozioni mostrano varie parentele.
Il discorso funzione - grafico nasce dall'esigenza di dire cos'è una "corrispondenza" - se per te è una nozione intuitiva no problem (e allora non ha grande importanza
definire una relazione come un sottoinsieme del prodotto o nel modo detto sopra); se invece cerchi un approccio "minimale" la questione cambia e, per quanto ne so, una funzione è
anche lei definita come il suo grafico (dopo aver introdotto la teoria degli insiemi , costruito le coppie ordinate ...)

[Martino]

"Pdirac":Per curiosità, ma esiste una definizione definita e "assoluta" o ogni autore dà la sua?

Riguardo questi concetti di cui stiamo parlando, esistono definizioni assolute ed accettate universalmente, e sono quelle che abbiamo detto.

I) riguardo a relazioni e operazioni definite sullo stesso insieme $A$, dimmi se ho capito:
Un operazione è una funzione che ad ogni elemento di A associa una coppia ordinata appertenente al prodotto cartesiano $A^2$, e non è una relazione.
Viceversa una funzione che ad ogni elemento di A gliene associa un altro sempre appartente ad A è una relazione.

Se ne desume che una funzione può essere una relazione, ma può anche non esserlo.

No, stai facendo un po' di confusione.

Allora cercherò di essere più preciso. Tieni conto che per capire bene questi concetti ci devi riflettere a lungo. Non pretendere di capire le cose in fretta, sono argomenti delicati.

Definizione: dati due insiemi A e B, una relazione tra A e B è un sottoinsieme R del prodotto cartesiano [tex]A \times B[/tex]. Se [tex]a \in A[/tex] e [tex]b \in B[/tex], diciamo che [tex]a[/tex] è in relazione con [tex]b[/tex] tramite R se [tex](a,b) \in R[/tex], e scriviamo anche [tex]aRb[/tex]. A si dice dominio della relazione R, B si dice codominio della relazione R. Se A=B (cioè se dominio e codominio coincidono) si parla di "relazione su A".

Definizione: dati due insiemi A e B, una funzione (o applicazione) tra A e B è una relazione [tex]f[/tex] tra A e B tale che:
1) per ogni [tex]a \in A[/tex] esiste [tex]b \in B[/tex] tale che [tex](a,b) \in f[/tex];
2) dati [tex]a \in A[/tex] e [tex]b_1,b_2 \in B[/tex], se [tex](a,b_1) \in f[/tex] e [tex](a,b_2) \in f[/tex] allora [tex]b_1=b_2[/tex].
In virtù di queste due proprietà, se [tex]a \in A[/tex] e [tex](a,b) \in f[/tex] ha senso scrivere [tex]b=f(a)[/tex]. Questa è la notazione comune che si usa universalmente. Se f è una funzione di dominio A e codominio B si scrive [tex]f:A \to B[/tex].

Osserva che per una generica relazione R tra A e B la scrittura [tex]b=R(a)[/tex] per significare [tex](a,b) \in R[/tex] non è ben posta, perché ci possono essere più elementi [tex]b \in B[/tex] tali che [tex](a,b) \in R[/tex]. Scrivere [tex]b=R(a)[/tex] per una relazione qualsiasi sarebbe in contraddizione con la proprietà transitiva dell'uguaglianza (per cui se [tex]b_1=R(a)=b_2[/tex] allora [tex]b_1=b_2[/tex], che se noti corrisponde alla proprietà 2 di cui sopra).

III) Un operazione è comunque interpretabile come una relazione, come lo è una funzione... ma allora l'operazione che associa ad un prodotto cartesiano $AxxA$ un altro elemento di $A$ è o non è una relazione?

Certo che è una relazione. Il suo dominio è [tex]A \times A[/tex], il suo codominio è [tex]A[/tex].

Invece una "relazione su A" è una relazione che ha A come dominio e A come codominio.

Quindi come vedi il dominio di una relazione su A e il dominio di una operazione su A sono diversi. Quindi è vero che operazione e relazione su A sono entrambe relazioni, ma avendo domini diversi sono oggetti diversi, non confrontabili, niente a che vedere l'uno con l'altro.

Una relazione è un sottoinsieme del prodotto cartesiano degli insiemi su cui è definita (siano essi uno o più, divergenti o coincidenti).

Una corrispondenza è un particolare tipo di relazione in cui per ogni $x in D(R)$, $xRy$ dove y è un elemento del secondo insieme. Per una corrispondenza quindi ogni elemento del primo insieme deve essere associato ad almeno 1 elemento del secondo insieme.

Una funzione (o applicazione) è un particolare tipo di corrispondenza, e dunque di relazione, in cui ogni elemento del dominio deve essere associato a uno e un solo elemento del codominio.

Sì, è corretto.

Un operazione è un particolare tipo di funzione, e quindi di corrispondenza e di relazione, che è definita in un insieme in sé stesso, e che associa a ogni coppia ordinata del prodotto cartesiano dell'insieme in se stesso (ovvero $A^2$) un altro elemento sempre appartentente allo stesso insieme

Un'operazione non è definita da "un insieme in sé stesso". Come ho detto qui sopra, una operazione su A è una funzione [tex]A \times A \to A[/tex].

[Pdirac]

@viciousgoblin@
non è la "comprensione intuitiva" il mio problema =). "Intuitivamente" i concetti li avevo anche prima (bene o male), ma quello che sto cercando è la loro costruzione rigorosa e formale.

@martino

ok, credo di aver compreso. rimangono solo alcune precisazioni:


I) Un operazione è definibile come una funzione avente come dominio il prodotto cartesiano di due insiemi diversi e come codominio genericamente un altro insieme (es. $AxxB$ [tex]\longrightarrow[/tex] $C$), oppure è esclusivamente definita come una funzione $f: AxxA$ [tex]\longrightarrow[/tex] $A$ ?

II)

Quindi è vero che operazione e relazione su A sono entrambe relazioni, ma avendo domini diversi sono oggetti diversi, non confrontabili, niente a che vedere l'uno con l'altro.

Il prodotto cartesiano di due insiemi $AxxB$ (o nel caso specifico di $AxxA$) è considerabile a sua volta un insieme?
Se sì, operazioni e relazioni non sono confrontabili notando che semplicemente un operazione è comunque sempre una relazione tra due insiemi (anche se meno generica, in quanto impone definite precisazioni su gli insiemi relazionati) ?

[Martino]

"Pdirac":I) Un operazione è definibile come una funzione avente come dominio il prodotto cartesiano di due insiemi diversi e come codominio genericamente un altro insieme (es. $AxxB$ [tex]\longrightarrow[/tex] $C$), oppure è esclusivamente definita come una funzione $f: AxxA$ [tex]\longrightarrow[/tex] $A$ ?

Dato un insieme A, un'operazione su A (osserva che quando si parla di un'operazione ci si riferisce sempre ad un insieme "base" in cui viene fatta l'operazione) è una funzione [tex]A \times A \to A[/tex]. Questa è la definizione universalmente accettata di operazione.

II)
[quote]Quindi è vero che operazione e relazione su A sono entrambe relazioni, ma avendo domini diversi sono oggetti diversi, non confrontabili, niente a che vedere l'uno con l'altro.

Il prodotto cartesiano di due insiemi $AxxB$ (o nel caso specifico di $AxxA$) è considerabile a sua volta un insieme?[/quote]Non è che è "considerabile" un insieme, è un insieme.

Se sì, operazioni e relazioni non sono confrontabili notando che semplicemente un operazione è comunque sempre una relazione tra due insiemi?

Sì, ma seguendo questo ragionamento è chiaro che si trova un collegamento tra due cose arbitrarie. Per esempio uno potrebbe dire che c'è un legame tra l'elevamento a potenza e la relazione di uguaglianza perché sono entrambe relazioni. Ma capisci che sono cose ben diverse.

O ancora più in generale: siccome tutti gli oggetti matematici sono interpretabili come insiemi, uno potrebbe dire che c'è un collegamento tra due qualsiasi oggetti matematici perché sono entrambi insiemi. Capisci che questo porta fuori strada.

(anche se meno generica, in quanto impone definite precisazioni su gli insiemi relazionati)

La "relazione" (faccio fatica a chiamarla così) di operazione non è "meno generica" di una qualche altra relazione (quale? non capisco). Non capisco nemmeno cosa intendi con "generica".

Qualsiasi relazione "impone definite precisazioni", non solo l'operazione.

Ma ti ripeto, pensare ad un'operazione come a una relazione non ha nessuna utilità. O meglio, se ne ha una illustramela, io non la vedo.

[ViciousGoblin]

Rispondo anch'io anche se forse ripeto quanto detto da martino.

Se il tuo problema sono le definizioni allora lascia perdere per un momento le "operazioni" in quanto sono delle particolari funzioni (da $A\times A$ in $A$ -e comunque secondo me
si usa il temine "operazione" quando $A$ è un insieme numerico , e quindi ci sono altre strutture).

Una relazione è un sottoinsieme $R$ di $A\times B$

Una funzione è un sottoinsieme $R$ di $A\times B$ tale che per ogni $a$ di $A$ esiste uno ed un solo $b$ di $B$ tale che $(a,b)\in R$.

EDIT Aggiungo due esempi.

La relazione "x ama y" è l'insieme di tutte le coppie di persone che si amano (quindi un sottoinsieme di $A\times A$ dove $A= "genere umano"$ ).
La funzione "l'altezza di x" è l'insieme di tutte le coppie (persona,numero) (contenute quindi nel prodotto cartesiano $A\times B$ dove $A= "genere umano"$ e $B="numeri reali"$ ) in cui il numero che occupa il secondo termine della coppia è l'altezza della persona che occupa il primo termine della coppia.

EDIT 2 Comunque (ho riletto la fine del tuo ultimo messaggio) è vero che le operazioni sono particolari relazioni (anche se questo , a parte questioni di minimalismo formale, non è particolarmente utile). Per esempio l'operazione di somma $s:RR\times RR\to RR$ (dove $RR$ è l'insieme dei numeri reali e $s(x,y)=x+y$) è la relazione definita dal sottoinsieme
$R$ di $(RR\times RR)\times RR$ dato da $R=\{((x,y),x+y) : x,y\in RR\}$

[Pdirac]

@martino
Intendevo per "meno generica" nel senso che mentre una relazione è un sottoinsieme di due insiemi arbitrari, l'operazione è un sottoinsieme di un solo insieme, ed inoltre è un tipo di relazione "più specifica" nel senso che il dominio deve essere il prodotto cartesiano $AxxA$ e il codominio $A$; impone cioè dei vincoli a quella che era la "più generica" definizione di relazione. Capisco che "generico" non sia il termine appropriato, ma non me ne vengono in mente di più adatti nel contesto.

@viciousgoblin
grazie per gli esempi, sono molto utili.
(Interessante notare come gli esempi su "relazione" e "funzione" vadano a presupporre che ogni "elemento" del genere umano possa amare svariate persone LoL... questa me la rigioco: una relazione non presuppone l'unicità... quindi viva la poligamia xD)