Primi esercizi sulle relazioni
Buongiorno a tutti,
sto iniziando a studiare le relazioni e ho il seguente quesito.
Se ho $A={-1,0}$ quante sono le possibili relazioni su $A$?Devo scriverle esplicitamente.
Ho ragionato nel seguente modo: Se $A$ possiede $n$ elementi, una relazione è un qualunque sottoinsieme di $A X A$, esso contiene $n^2$ elementi e un insieme di $n^2$ elementi ammette $2^(n^2)$ sottoinsiemi. Ho quindi $2^(n^2) $ relazioni.
Corretto?
Ho però problemi nel definirle...
sto iniziando a studiare le relazioni e ho il seguente quesito.
Se ho $A={-1,0}$ quante sono le possibili relazioni su $A$?Devo scriverle esplicitamente.
Ho ragionato nel seguente modo: Se $A$ possiede $n$ elementi, una relazione è un qualunque sottoinsieme di $A X A$, esso contiene $n^2$ elementi e un insieme di $n^2$ elementi ammette $2^(n^2)$ sottoinsiemi. Ho quindi $2^(n^2) $ relazioni.
Corretto?
Ho però problemi nel definirle...
Risposte
intanto, tutto quelo che hai scritto è corretto:
$A={0,-1}$ ha $n=2$ elementi. Dunque avremo $2^(n^2)=16$ possibili relazioni su $A$.
Esse sono tutti e soli i sottoinsiemi di $A times A={(0,0), (0, -1), (-1,0), (-1,-1)}$.
Se devi scriverli tutti esplicitamente, vai in ordine:
- il sottoinsieme di $A times A$ con $0$ elementi è $emptyset$;
- i sottoinsiemi di $A times A$ con $1$ elemento sono ${(0,0)}$, ${(0,-1)}$, ${(-1,0)}$ e ${(-1,-1)}$;
- i sottoinsiemi di $A times A$ con $2$ elementi sono... ;
- i sottoinsiemi di $A times A$ con $3$ elementi sono... ;
- il sottoinsieme di $A times A$ con $4$ elementi è $A times A$.
$A={0,-1}$ ha $n=2$ elementi. Dunque avremo $2^(n^2)=16$ possibili relazioni su $A$.
Esse sono tutti e soli i sottoinsiemi di $A times A={(0,0), (0, -1), (-1,0), (-1,-1)}$.
Se devi scriverli tutti esplicitamente, vai in ordine:
- il sottoinsieme di $A times A$ con $0$ elementi è $emptyset$;
- i sottoinsiemi di $A times A$ con $1$ elemento sono ${(0,0)}$, ${(0,-1)}$, ${(-1,0)}$ e ${(-1,-1)}$;
- i sottoinsiemi di $A times A$ con $2$ elementi sono... ;
- i sottoinsiemi di $A times A$ con $3$ elementi sono... ;
- il sottoinsieme di $A times A$ con $4$ elementi è $A times A$.
Quindi io li ho elencati così:
$R_1={(-1,1)}$
$R_2={(-1,0)}$
$R_3={(0,-1)}$
$R_4={(0,0)}$
$R_5={(-1,-1),(-1,0)}$
$R_6={(-1,-1),(0,-1)}$
$R_7={(-1,-1),(0,0)}$
$R_8={}(-1,-1),(-1,-1)$
$R_9={(-1,0),(-1,0)}$
$R_10={(0,-1),(0,-1)}$
$R_11={(0,0),(0,0)}$
$R_12={(-1,-1),(-1,0),(0,-1)}$
$R_13={(-1,-1),(0,-1),(0,0)}$
$R_14={(0,0),(-1,0),(0,-1)}$
$R_15={(-1,-1),(-1,0),(0,0)}$
$R_16={(-1,-1),(-1,0),(0,-1),(0,0)}$
ok?
$R_1={(-1,1)}$
$R_2={(-1,0)}$
$R_3={(0,-1)}$
$R_4={(0,0)}$
$R_5={(-1,-1),(-1,0)}$
$R_6={(-1,-1),(0,-1)}$
$R_7={(-1,-1),(0,0)}$
$R_8={}(-1,-1),(-1,-1)$
$R_9={(-1,0),(-1,0)}$
$R_10={(0,-1),(0,-1)}$
$R_11={(0,0),(0,0)}$
$R_12={(-1,-1),(-1,0),(0,-1)}$
$R_13={(-1,-1),(0,-1),(0,0)}$
$R_14={(0,0),(-1,0),(0,-1)}$
$R_15={(-1,-1),(-1,0),(0,0)}$
$R_16={(-1,-1),(-1,0),(0,-1),(0,0)}$
ok?
In effetti quello sopra era facile ma quest'altro non lo capisco.
Se $A$ è l'insieme di tutte le parole di un vocabolario e $R$ definita su $A$ è: $pRq$ sse $p=q$ oppure p precede q nel vocabolario.
Devo stabilire se $R$ è una relazione d'ordine.
Affinchè lo sia deve essere riflessiva, antisimmetrica e transitiva.
Riflessività: Una parola $p$ è sempre uguale a se stessa.
Antisimmetria: Prendo due parole $p$ e $q$, se $p$ precede $q$ e $q$ precede $p$ allora $p=q$
Transitività: Se $p=q$ e $q=r$ allora $p=r$
Come dimostrazione può andare?
Se $A$ è l'insieme di tutte le parole di un vocabolario e $R$ definita su $A$ è: $pRq$ sse $p=q$ oppure p precede q nel vocabolario.
Devo stabilire se $R$ è una relazione d'ordine.
Affinchè lo sia deve essere riflessiva, antisimmetrica e transitiva.
Riflessività: Una parola $p$ è sempre uguale a se stessa.
Antisimmetria: Prendo due parole $p$ e $q$, se $p$ precede $q$ e $q$ precede $p$ allora $p=q$
Transitività: Se $p=q$ e $q=r$ allora $p=r$
Come dimostrazione può andare?
Forse sarebbe bene chiamare la relazione di "precedere nel vocabolario o essere uguale" con $ <= $, così diventano chiare le relazioni.
Come le hai scritte tu infatti la antisimmetrica è sviluppata solo sul "precede nel vocabolario" e la transitiva solo sull'"essere uguale"
Come le hai scritte tu infatti la antisimmetrica è sviluppata solo sul "precede nel vocabolario" e la transitiva solo sull'"essere uguale"
Comunque nell'esercizio precedente $R_8, R_9, R_10, R_11$ non vanno bene.
Inoltre hai dimenticato tra le possibili relazioni l'insieme vuoto
Inoltre hai dimenticato tra le possibili relazioni l'insieme vuoto
Risolti e capiti entrambi gli esercizi.
Ora ho quest'altro in cui mi viene chiesto di determinare se la relazione $R$ è riflessiva, simmetrica, antisimmetrica e transitiva.
L'insieme $A$ è costituito da tutti i sottoinsiemi di $NN$ e la relazione $R$ è $X R Y$ se e soltanto se $|X|<=|Y|$.
La relazione è riflessiva perchè la cardinalità di un qulunque sottoinsieme di $A$ è uguale alla cardinalità dello stesso insieme.
Ho problemi però a dimostrare le altre proprietà adesso....
Ora ho quest'altro in cui mi viene chiesto di determinare se la relazione $R$ è riflessiva, simmetrica, antisimmetrica e transitiva.
L'insieme $A$ è costituito da tutti i sottoinsiemi di $NN$ e la relazione $R$ è $X R Y$ se e soltanto se $|X|<=|Y|$.
La relazione è riflessiva perchè la cardinalità di un qulunque sottoinsieme di $A$ è uguale alla cardinalità dello stesso insieme.
Ho problemi però a dimostrare le altre proprietà adesso....
Non credo sia simmetrica perchè se la cardinalità di $X$ è minore o uguale di $Y$ non è vero che la cardinalita di $Y$ è minore o uguale a quella di $X$ corretto?
Direi proprio di sì, corretto! Tieni a mente che le cardinalità non sono altro che numeri associati ad un particolare sottoinsieme e troverai tutto facile 
L'esercizio continua chiedendo di trovare una successione $X_0,X_1,...$ di insiemi tali che $X_i R X_(i+1)$ e una successione $Y_0,Y_1,...$ di insiemi tali che $Y_(i+1) R Y_i$.
Questo proprio non capisco cosa vuol dire....
Questo proprio non capisco cosa vuol dire....
La mia interpretazione sarebbe: devi trovare una successione di insiemi la cui cardinalità è crescente. Me ne viene in mente una base base... Per il secondo, l'inverso naturalmente!
Ad esempio $X_0={0}$ e $X_1={0,1}$ potrebbe andare?
Naturalmente, e a seguire tutti gli altri, anche se essendo in un insieme generico invece dei numeri userei degli el. generici, ad esempio $ a_0, a_1... $
Chiarissimo.
Ultima domanda su questo esercizio: mi viene chiesto se è possibile trovare una successione $Z_0,Z_1,...$ di insiemi tali che $Z_(i+1) R Z_i$ e $Z_(i+1) != Z_i AAi $ ?
Sbaglio o è possibile e quello fatto da me sopra ne è un esempio?
Ultima domanda su questo esercizio: mi viene chiesto se è possibile trovare una successione $Z_0,Z_1,...$ di insiemi tali che $Z_(i+1) R Z_i$ e $Z_(i+1) != Z_i AAi $ ?
Sbaglio o è possibile e quello fatto da me sopra ne è un esempio?
Parrebbe essere l'inverso di quello sopra (es. $ Z_0={A}, Z_1={A-a_1}... $) Però mi pare strana la domanda. Aspetterei delucidazioni da qualcuno più "alto" 
Nell'attesa di una conferma di quanto sopra chiedo la seguente cosa:
Ho $A=NN$ ed $R$ su $A$ definita da $xRy$ se $x$ è mulitplo di $y$ e $y$ è multiplo di $x$.
Sbaglio o a questa relazione fanno parte solo le coppie $(a,a)$ ?
Ho $A=NN$ ed $R$ su $A$ definita da $xRy$ se $x$ è mulitplo di $y$ e $y$ è multiplo di $x$.
Sbaglio o a questa relazione fanno parte solo le coppie $(a,a)$ ?
Esatto, e l'insieme quoziente delle classi di equivalenza è isomosrfo a $ NN $ stesso.
La relazione è riflessiva, simmetrica ma non transitiva...corretto?
Perchè transitiva no? Se $ a=kb ^^ b=ja =>a=b $ come hai detto tu, e la relazione di uguaglianza è transitiva sì!
posso dimostrarlo così?
$(1,1) in R ^^ (1,1) in R rarr (1,1) in R$
$(1,1) in R ^^ (1,1) in R rarr (1,1) in R$
Io lo dimostrerei con la relazione su elementi generici, dicendo appunto che $ a=kb ^^ b=ja => a=b $ e $ b=lc ^^ c=mb => b=c $, allora $ a=b ^^ b=c => a=c $ Aspetto conferme per la tua dimostrazione, ma non mi convince perché particolare e non generale.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo