Teoria assiomatica degli insiemi
Sto cercando di studiare gli aspetti basilari della teoria assiomatica degli insiemi, nello specifico gli assiomi di ZF, ma ho diverse difficoltà in proposito.
1) L'assioma di estensionalità dice che $\forall x\forall y[x=y\leftrightarrow\forall z(z\in x\leftrightarrow z\in y)]$; l'assioma dell'esistenza dell'insieme vuoto afferma invece che $\exists x\forall y(y\notin x)$; a partire da questi soli due assiomi come si fa a dimostrare che l'insieme vuoto è unico?
2) E' possibile riscrivere l'assioma di estensionalità evitando di utilizzare il predicato di uguaglianza? Qui (http://en.wikipedia.org/wiki/Zermelo%E2 ... The_axioms) c'è scritto che l'espressione $x=y$ può essere considerata come un'abbreviazione della formula $\forall z(z\in x\leftrightarrow z\in y)\wedge\forall z(x\in z\leftrightarrow y\in z)$, che sostanzialmente dice che $x=y$ se e soltanto se $x$ e $y$ contengono gli stessi elementi e fanno parte dei medesimi insiemi. Mi chiedo: è proprio necessaria la seconda parte (e cioè che $\forall z(x\in z\leftrightarrow y\in z)$)? Non basta scrivere che $\forall z(z\in x\leftrightarrow z\in y)$?
3) Cosa si intende esattamente con $\bigcup x$? ad esempio cosa si intende per $\bigcup {a,b}$?
Grazie.
1) L'assioma di estensionalità dice che $\forall x\forall y[x=y\leftrightarrow\forall z(z\in x\leftrightarrow z\in y)]$; l'assioma dell'esistenza dell'insieme vuoto afferma invece che $\exists x\forall y(y\notin x)$; a partire da questi soli due assiomi come si fa a dimostrare che l'insieme vuoto è unico?
2) E' possibile riscrivere l'assioma di estensionalità evitando di utilizzare il predicato di uguaglianza? Qui (http://en.wikipedia.org/wiki/Zermelo%E2 ... The_axioms) c'è scritto che l'espressione $x=y$ può essere considerata come un'abbreviazione della formula $\forall z(z\in x\leftrightarrow z\in y)\wedge\forall z(x\in z\leftrightarrow y\in z)$, che sostanzialmente dice che $x=y$ se e soltanto se $x$ e $y$ contengono gli stessi elementi e fanno parte dei medesimi insiemi. Mi chiedo: è proprio necessaria la seconda parte (e cioè che $\forall z(x\in z\leftrightarrow y\in z)$)? Non basta scrivere che $\forall z(z\in x\leftrightarrow z\in y)$?
3) Cosa si intende esattamente con $\bigcup x$? ad esempio cosa si intende per $\bigcup {a,b}$?
Grazie.
Risposte
Siano $A,B$ due insiemi vuoti: allora $A=B$.
Avviene quanto sopra sse $\forall z, z \in A <=> z \in B$, ma $A$ e $B$ sono vuoti, sicché $z \in A$ è falso così come $z \in B$, quindi, per qualunque scelta di $z$, $z \in A <=> z \in B$ è vero. #
Avviene quanto sopra sse $\forall z, z \in A <=> z \in B$, ma $A$ e $B$ sono vuoti, sicché $z \in A$ è falso così come $z \in B$, quindi, per qualunque scelta di $z$, $z \in A <=> z \in B$ è vero. #
dunque sono riuscito a mettere giù la seguente dimostrazione:
IPOTESI
Siano $A$ e $B$ due insiemi vuoti. Questo equivale a dire che $\forall x(x\notin A)\wedge\forall x(x\notin B)$
TESI
$A=B$, cioè $\forall x(x\in A\leftrightarrow x\in B)$
DIMOSTRAZIONE
$\forall x(x\notin A)\wedge\forall x(x\notin B)\iff$ (per le proprietà di $\forall$)
$\iff\forall x(x\notin A\wedge x\notin B)\Rightarrow$ (per le proprietà dei connettivi logici)
$\Rightarrow\forall x(x\in A\leftrightarrow x\in B)$
mi pare giusta, però non mi sembra abbastanza rigorosa, cioè non si riconduce mai esattamente all'enunciato di alcuno dei due assiomi introdotti finora... credo proprio che debba lavorarci ancora sopra...
IPOTESI
Siano $A$ e $B$ due insiemi vuoti. Questo equivale a dire che $\forall x(x\notin A)\wedge\forall x(x\notin B)$
TESI
$A=B$, cioè $\forall x(x\in A\leftrightarrow x\in B)$
DIMOSTRAZIONE
$\forall x(x\notin A)\wedge\forall x(x\notin B)\iff$ (per le proprietà di $\forall$)
$\iff\forall x(x\notin A\wedge x\notin B)\Rightarrow$ (per le proprietà dei connettivi logici)
$\Rightarrow\forall x(x\in A\leftrightarrow x\in B)$
mi pare giusta, però non mi sembra abbastanza rigorosa, cioè non si riconduce mai esattamente all'enunciato di alcuno dei due assiomi introdotti finora... credo proprio che debba lavorarci ancora sopra...
per quanto riguarda l'unione, credo di aver capito che cosa si intenda. ad esempio se $A={{1,2},{2,3,4}}$ allora $\bigcup A={1,2,3,4}$, cioè data una collezione $A$ di insiemi, per $\bigcup A$ si intende l'insieme di tutti quegli elementi che fanno parte di almeno uno degli insiemi di cui è costituito $A$.
altra domanda... è corretto utilizzare la notazione $A={x:P(x)}$ o bisogna sempre scrivere qualcosa del tipo $A={x\in B:P(x)}$?
La dimostrazione è corretta.
Per quanto riguarda le notazioni, esse sono equivalenti, anche se la seconda notazione è più precisa;
la prima la puoi usare se B è chiaro dal contesto.
Per quanto riguarda le notazioni, esse sono equivalenti, anche se la seconda notazione è più precisa;
la prima la puoi usare se B è chiaro dal contesto.
"qxtr01":
IPOTESI
Siano $A$ e $B$ due insiemi vuoti. Questo equivale a dire che $\forall x(x\notin A)\wedge\forall x(x\notin B)$
TESI
$A=B$, cioè $\forall x(x\in A\leftrightarrow x\in B)$
quello che non mi piace di questa impostazione sono le ipotesi. sarebbe preferibile scrivere direttamente qualcosa come $\exists A\forall x(x\notin A)\wedge\exists B\forall x(x\notin B)$ (in questo modo utilizzo integralmente l'enunciato dell'assioma di esistenza dell'insieme vuoto, due volte).
a questo punto però il mio problema è scrivere la tesi... $A=B$? non credo, perchè le ipotesi sono due proposizioni del tipo $P\wedge Q$ mentre la tesi è una predicato del tipo $R(A,B)$ (e quindi non riuscirò mai ad arrivarci tramite passaggi logici). $\forall A\forall B(A=B)$? sarebbe come dimostrare che dati due insiemi qualunque questi sono uguali... (il che è ovviamente falso). come posso fare allora?
Credo che ti stia concentrando troppo sui quantificatori. Per utilizzarli in modo così formale e rigoroso credo ti occorra un corso di logica full immersion.
dunque secondo wikipedia l'assioma di estensionalità può essere riformulato evitando l'uso del predicato di uguaglianza nel seguente modo: $\forall a\forall b[\forall c(c\in a\leftrightarrow c\in b)\rightarrow\forall c(a\in c\leftrightarrow b\in c)]$. in prosa questo vuol dire che dati due insiemi $a$ e $b$ se questi contengono gli stessi elementi allora essi appartengono ai medesimi insiemi. se per convenzione scrivo $a=b$ al posto di $\forall c(c\in a\leftrightarrow c\in b)$ l'assioma di estensionalità può essere riscritto in modo più conciso come: $\forall a\forall b[a=b\rightarrow\forall c(a\in c\leftrightarrow b\in c)]$.
ora mi chiedo: vale anche il contrario? vale cioè che se due insiemi $a$ e $b$ appartengono ai medesimi insiemi allora $a=b$? in simboli, vale che $\forall a\forall b[\forall c(a\in c\leftrightarrow b\in c)\rightarrow a=b]$? intuitivamente direi di si, ma non riesco in alcun modo a dimostrarlo. sarebbe come dire che da $\forall a\forall b(P(x,y)\rightarrow Q(x,y))$ implica che $\forall a\forall b(Q(x,y)\rightarrow P(x,y))$.
secondo me anche questo fatto dovrebbe essere incluso nell'assioma di estensionalità, che diverrebbe pertanto $\forall a\forall b[a=b\leftrightarrow\forall c(a\in c\leftrightarrow b\in c)]$.
cosa ne pensate?
ora mi chiedo: vale anche il contrario? vale cioè che se due insiemi $a$ e $b$ appartengono ai medesimi insiemi allora $a=b$? in simboli, vale che $\forall a\forall b[\forall c(a\in c\leftrightarrow b\in c)\rightarrow a=b]$? intuitivamente direi di si, ma non riesco in alcun modo a dimostrarlo. sarebbe come dire che da $\forall a\forall b(P(x,y)\rightarrow Q(x,y))$ implica che $\forall a\forall b(Q(x,y)\rightarrow P(x,y))$.
secondo me anche questo fatto dovrebbe essere incluso nell'assioma di estensionalità, che diverrebbe pertanto $\forall a\forall b[a=b\leftrightarrow\forall c(a\in c\leftrightarrow b\in c)]$.
cosa ne pensate?
Hai pienamente ragione, infatti nel caso di Wikipedia in italiano (http://it.wikipedia.org/wiki/Assioma_di ... alit%C3%A0) la definizione è proprio quella che hai dato tu!
scusa ma a me non sembra che nella pagina che hai indicato ci sia la mia definizione, bensì la stessa che c'è sul wikipedia in inglese...
comunque parlando su irc mi hanno detto che la proposizione "opposta" è ridondante perchè può essere ricavata utilizzando gli altri assiomi, ma non sono riuscito a capire la dimostrazione (troppo difficile considerando il livello in cui mi trovo).
comunque parlando su irc mi hanno detto che la proposizione "opposta" è ridondante perchè può essere ricavata utilizzando gli altri assiomi, ma non sono riuscito a capire la dimostrazione (troppo difficile considerando il livello in cui mi trovo).
Mi sto scontrando con un altro problema: non riesco infatti a definire per bene il concetto di n-upla.
Ho provato nel seguente modo.
Siano $a$ e $b$ due insiemi qualunque. Innanzitutto definisco $ = {{a},{a,b}}$ e la chiamo coppia ordinata (notare le parentesi angolari e il termine coppia ordinata).
A questo punto definisco il concetto di n-upla ponendo che:
- la 0-upla è l'insieme $()={}$
- la 1-upla è l'insieme $(a_1)={<1,a_1>}$
- la 2-upla è l'insieme $(a_1,a_2)={<1,a_1>,<2,a_2>}$
e così via (notare le parentesi tonde ed il termine n-upla).
Come è possibile notare la coppia ordinata $$ risulta diversa dalla 2-upla $(a,b)$ in quanto ${{a},{a,b}}\ne{{{1},{1,a}},{{2},{2,b}}}$, ma questo di per se non sembra costituire un problema.
Problematica è invece la definizione di n-upla per $n>=3$, in quanto dire "e così via" non è affatto cosa rigorosa.
Come posso passare al caso con $n$ arbitrario, avendo a mia disposizione il concetto di insieme dei numeri naturali, quello di funzione e quello di operazione?
Ho provato nel seguente modo.
Siano $a$ e $b$ due insiemi qualunque. Innanzitutto definisco $
A questo punto definisco il concetto di n-upla ponendo che:
- la 0-upla è l'insieme $()={}$
- la 1-upla è l'insieme $(a_1)={<1,a_1>}$
- la 2-upla è l'insieme $(a_1,a_2)={<1,a_1>,<2,a_2>}$
e così via (notare le parentesi tonde ed il termine n-upla).
Come è possibile notare la coppia ordinata $
Problematica è invece la definizione di n-upla per $n>=3$, in quanto dire "e così via" non è affatto cosa rigorosa.
Come posso passare al caso con $n$ arbitrario, avendo a mia disposizione il concetto di insieme dei numeri naturali, quello di funzione e quello di operazione?
Credo di esserci riuscito.
Basta definire:
- $()={}$
- $(a_1)={<1,a_1>}$
- $(a_1,\ldots,a_n)=\bigcup_{i\in N_n}(a_i)$
dove $N_n={m\in N\setminus{0}:m<=n}$.
Ad esempio per $n=4$ si ha che $N_4={1,2,3,4}$, $\bigcup_{i\in N_4}(a_i)=(a_1)\cup(a_2)\cup(a_3)\cup(a_4)=(a_1,a_2,a_3,a_4)$.
Che ne pensate? E' corretto?
Basta definire:
- $()={}$
- $(a_1)={<1,a_1>}$
- $(a_1,\ldots,a_n)=\bigcup_{i\in N_n}(a_i)$
dove $N_n={m\in N\setminus{0}:m<=n}$.
Ad esempio per $n=4$ si ha che $N_4={1,2,3,4}$, $\bigcup_{i\in N_4}(a_i)=(a_1)\cup(a_2)\cup(a_3)\cup(a_4)=(a_1,a_2,a_3,a_4)$.
Che ne pensate? E' corretto?
"qxtr01":
Problematica è invece la definizione di n-upla per $n>=3$, in quanto dire "e così via" non è affatto cosa rigorosa.
Sto studiando proprio (una generalizzazione di) questo, parlandone nel topic "Principio del massimo e principio di induzione". Dire "e così via" non sarà rigoroso, ma fa riferimento ad un principio che rigoroso è, eccome:
- Principio della definizione ricorsiva.
Sia $A$ un insieme, $a_0$ un suo elemento. Chiamiamo $F={f:{1...n}\toA\ :\ n\inNN}$ l'insieme delle funzioni definite sulle sezioni di naturali a valori in $A$. Se $rho$ è una funzione $F\toA$, allora la relazione
${(h(1)=a_0), (h(n+1)=rho(h|_{{1,...,n}})):}$ definisce un'unica funzione $h:NN\toA$.[/list:u:3cbx5jmf]
Qual'è il principio? Nient'altro che il principio di induzione, scritto in una maniera un po' più incasinata (l'insieme $F$ all'inizio mi faceva gelare il sangue), proprio per inseguire il celebrato "rigore".
In pratica tu dici: se io fisso un valore iniziale per la mia funzione $h$, e costruisco una relazione tra il valore di $h$ all'istante $n+1$ e quello agli istanti precedenti, allora la mia $h$ è ben definita su tutti i numeri naturali.
O ancora, se preferisci: io definisco quanto vale $h(1)$. Quindi l'"insieme di definizione" di $h$ contiene $1$. Ma d'altro canto l'insieme di definizione di $h$ è induttivo, nel senso che se contiene ${1, ..., n}$ allora contiene anche $n+1$. Hai mai studiato il principio di induzione forte? Dice esattamente questo: un insieme fatto in questa maniera coincide con tutto $NN$. Quindi l'insieme di definizione di $h$ coincide con tutto $NN$.
Naturalmente non c'è bisogno di esplicitare ogni volta la funzione $rho$, anzi secondo me non c'è mai bisogno di farlo. Basta sapere che le definizioni ricorsive, quelle che terminano con "e così via..." per intenderci, sono delle vere definizioni: volendo, uno le può scrivere in una forma rigorosa usando il principio di sopra.
Hope this helps, e tieni conto che anche io non sono un esperto di questa materia, alla quale anzi ho iniziato ad appassionarmi proprio in questi giorni!
"qxtr01":
ora mi chiedo: vale anche il contrario? vale cioè che se due insiemi $a$ e $b$ appartengono ai medesimi insiemi allora $a=b$?
Tralasciando le questioni formali, direi di no.
Mi basta prendere un insieme $A$, la sua potenza $wp(A)$ e avere che, se $|A|>1$, posso trovare $X_1, X_2 in wp(A)$ con $X_1 != X_2$.
Almeno se questo è quello che intendi.
Mi posteresti il link ad irc cui fai riferimento nel tuo terzultimo post?
Per quanto riguarda il concetto di n-upla, puoi procedere in due modi equivalenti: tieni presente che quello che ti dico ha come background il fatto che la n-upla è più propriamente un oggetto ordinato.
Il primo consiste in una definizione ricorsiva, i.e. $(a,b):={{a},{a,b}}$ per $n=2$ ( e se proprio vuoi definire la n-upla anche per $0$ e $1$, allora poni come hai fatto tu $()={}$ e $(a_1)={a_1}$), quindi $(a_1, a_2, ldots, a_n), a_(n+1))=:(a_1, a_2, a_3, ldots, a_n)$.
Altrimenti poni per $n=2$ quanto già detto, i.e. $(a,b):={{a},{a,b}}$, quindi definisci cos'è una applicazione (parte del prodotto cartesiano et cetera et cetera... questo è il motivo per cui devi definire prima la coppia), quindi poni $(a_1, a_2, a_3, ldots, a_n):= f: ccI_n ( :={1,2,3,ldots,n}) to A$ ove $A:={a_1, a_2, a_3, ldots, a_n}$.
A questo punto è facile convincersi che le definizioni sono equivalenti: data la n-upla definita come applicazione, basta prendere la restrizione $f_{ccI_(n-1)}$ per avere la n-1-upla, quindi prendere la coppia $((f_{ccI_{n-1}}),a_n)$ per avere la n-upla induttiva.
Viceversa, data la n-upla induttiva, basta creare l'applicazione che manda $1$ in $a_1$, $2$ in $a_2$ e $i$ in $a_i$.
A tal proposito, ne discutemmo a suo tempo, qui.
"WiZaRd":
[quote="qxtr01"]ora mi chiedo: vale anche il contrario? vale cioè che se due insiemi $a$ e $b$ appartengono ai medesimi insiemi allora $a=b$?
Tralasciando le questioni formali, direi di no.
Mi basta prendere un insieme $A$, la sua potenza $wp(A)$ e avere che, se $|A|>1$, posso trovare $X_1, X_2 in wp(A)$ con $X_1 != X_2$.
Almeno se questo è quello che intendi.[/quote]
Dunque facciamo un esempio concreto. Sia $A={1,2}$ ($|A|>1$), trovo $X_1=\emptyset$ e $X_2={1}$ tali che $X_1,X_2\in P_A$ ma ovviamente $X_1\ne X_2$. Il fatto è che $X_1$ e $X_2$ devono appartenere al medesimo insieme $P$ per qualunque $P$ affinchè valga che $X_1=X_2$, cosa che nel nostro caso non è verificata (ad esempio $X_1\in{\emptyset}$ ma $X_2\notin{\emptyset}$).
"WiZaRd":
Mi posteresti il link ad irc cui fai riferimento nel tuo terzultimo post?
irc non è un sito ma è una chat. in particolare il server è chat.freenode.net e il canale è #math. ti lascio uno stralcio della conversazione (che non sono riuscito a seguire):
2009-03-06 14:41:35We have that for all z, x is in z if and only if y is in z, yeah? So we apply pairing to get a set s' such that x is in z, and then comprehension/specification to restrict s' to a set s such that forall y. y is in s => (forall u. u is in x <=> u is in y)
2009-03-06 14:42:08er, "such that x is in s'"
2009-03-06 14:42:40and then note that x is still in s, because u is in x <=> u is in x
2009-03-06 14:43:07but then y (our original y) is in s as well
2009-03-06 14:43:27and so forall u. u is in x <=> u is in y
2009-03-06 14:43:45Does that make sense?
2009-03-06 14:45:26Cale, sorry i can't follow you... you apply pairing to get a set s'... but what s' is made of?
2009-03-06 14:45:27qxtr01: It's not wrong to choose axioms which are a little redundant if you like.
2009-03-06 14:45:36x and x
2009-03-06 14:45:47(and maybe some other elements)
2009-03-06 14:46:17That is, pairing says: forall x. forall y. exists z (x in z and y in z)
2009-03-06 14:46:35we specialise that with x -> x and y -> x
2009-03-06 14:46:51and it says exists z. (x in z and x in z)
2009-03-06 14:47:02(it's just a way to get a set with x in it)
2009-03-06 14:47:31and then we restrict that set with comprehension to a set whose only members are sets which have the same elements as x
2009-03-06 14:47:56and of course, x has the same members as x, so x is in the set
2009-03-06 14:48:06But then by our original assumption, y is in the set as well
2009-03-06 14:48:15and so y must have the same members as x
2009-03-06 14:48:31Clearer?
2009-03-06 14:48:49Cale, i need to think about it a bit more sorry
2009-03-06 14:51:22Cale: ok i got that z={x}
2009-03-06 14:51:31Cale: now how can restrict z?
2009-03-06 14:52:36qxtr01: pairing only guarantees that the set it gives you *contains* x
2009-03-06 14:53:09qxtr01: You need to apply comprehension to get a set that contains *only* x, or in this case, only sets which have the same members as x.
2009-03-06 14:57:59Once you have a set which contains x as a member, and such that any of its members have the same members as x, then because any set which has x as a member also has y as a member, y must belong to this set, and so must have the same members as x.
Ho un altro problema, stavolta per quanto riguarda la definizione di prodotto cartesiano.
Con $A\times B$ si intende l'insieme delle 2-uple del tipo $(a,b)$ con $a\in A$ e $b\in B$. Fin qui ok.
Ma allora con $A\times B\times C$ si intende $(A\times B)\times C$, e cioè l'insieme delle 2-uple del tipo $((a,b),c)$. Peccato però che $((a,b),c)$, con la definizione che ho dato precedentemente, non sia uguale a $(a,b,c)$, che è invece ciò che mi aspetto.
L'unica soluzione che mi viene in mente a questo problema è quella di evitare di considerare il prodotto cartesiano come un'operazione binaria, e considerarlo invece come un'operazione $n$-aria, dove $n$ è il numero di insiemi di cui si vuole ottenere il prodotto.
Con $A\times B$ si intende l'insieme delle 2-uple del tipo $(a,b)$ con $a\in A$ e $b\in B$. Fin qui ok.
Ma allora con $A\times B\times C$ si intende $(A\times B)\times C$, e cioè l'insieme delle 2-uple del tipo $((a,b),c)$. Peccato però che $((a,b),c)$, con la definizione che ho dato precedentemente, non sia uguale a $(a,b,c)$, che è invece ciò che mi aspetto.
L'unica soluzione che mi viene in mente a questo problema è quella di evitare di considerare il prodotto cartesiano come un'operazione binaria, e considerarlo invece come un'operazione $n$-aria, dove $n$ è il numero di insiemi di cui si vuole ottenere il prodotto.
Inoltre comunque non riesco a definire $\prod_{i\in I}A_i$...
Guarda un poco di casi della vita... una quindicina di giorni fa discutevo sul foro delle n-uple (link nel mio precedente post) e fino a l'altro ieri discutevo di questa "anomalia" del prodotto cartesiano: guarda un poco qui.
Ad ogni modo il problema sono sempre le n-uple. Bisogna fermarsi a riflettere prima su quelle. Il prodotto cartesiano non è associativo, quindi serve identificare per biezione i vari cartesiani.
In generale, $prod_{i=1}^{n} A_{i} = {f : I_n to bigcup_{i=1}^{n} \ \ t.c. \ \ f(i) in A_i, forall i in I_n}$ ove $I_n={1,2,ldots,n}$, oppure, il che è lo stesso $prod_{i=1}^{n}A_i={(a_1,a_2,ldots,a_n) \ \ t.c. \ \ a_i in A_i, forall i}$.
In generale, $prod_{i=1}^{n} A_{i} = {f : I_n to bigcup_{i=1}^{n} \ \ t.c. \ \ f(i) in A_i, forall i in I_n}$ ove $I_n={1,2,ldots,n}$, oppure, il che è lo stesso $prod_{i=1}^{n}A_i={(a_1,a_2,ldots,a_n) \ \ t.c. \ \ a_i in A_i, forall i}$.
"qxtr01":
Credo di esserci riuscito.
Basta definire:
- $()={}$
- $(a_1)={<1,a_1>}$
- $(a_1,\ldots,a_n)=\bigcup_{i\in N_n}(a_i)$
dove $N_n={m\in N\setminus{0}:m<=n}$.
Ad esempio per $n=4$ si ha che $N_4={1,2,3,4}$, $\bigcup_{i\in N_4}(a_i)=(a_1)\cup(a_2)\cup(a_3)\cup(a_4)=(a_1,a_2,a_3,a_4)$.
Che ne pensate? E' corretto?
La precedente definizione contiene un errore. La definizione corretta dovrebbe essere:
- $()={}$
- $(a_1,\ldots,a_n)=\bigcup_{i\in N_n}{
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo