Intersezione di partizioni

Problemi enumerativi, teoria dei grafi ...

Moderatore: Moderatori

Re: Intersezione di partizioni

Messaggioda jordan il mar 4 mar 2014, 16:37

[Questo mi pare ovvio, non capisco il punto della domanda :( ] Una partizione di un insieme $X$ è una collezioni di insiemi $\{P_j\}_{j \in J}$ tale che $P_i \cap P_j \neq \emptyset$ se e solo se $i=j$, e $\bigcup_{j \in J}{P_j}=X$ (quindi è una collezione di insiemi, si, ma a due a due distinti, nel senso che non ci sono doppioni, è qui che credo venga usato l'AC...)

Edit: si, il simbolo corretto sarebbe $\wedge$ :rolleyes:
The only goal of science is the honor of the human spirit.
Avatar utente
jordan
 
Messaggi: 330
Iscritto il: gio 19 giu 2008, 22:42

Re: Intersezione di partizioni

Messaggioda fry il mar 4 mar 2014, 17:44

ma_go ha scritto:esattamente allo stesso modo. c'è un ordine parziale sull'insieme delle partizioni di $X$ (cioè $P_1 \le P_2$ se per ogni $A\in P_1$ esiste $B\in P_2$ tale che $A\subset B$), e l'"intersezione" di una famiglia di partizioni è il massimo dei minoranti (ove esista).

Ah ecco, basta poco per intendersi. Quindi $P_1 \wedge P_2$ è l'estremo inferiore di $\{P_1, P_2\}$ rispetto l'ordine parziale sulle partizioni. Cioè, se non sbaglio, esplicitamente dovrebbe essere $P_1 \wedge P_2 = \{x_1 \cap x_2 : x_1 \in P_1,\, x_2 \in P_2\}$ per ogni $P_1, P_2 \in \mathscr{P}(X)$ e si verifica anche $P_1 \wedge P_2 \in \mathscr{P}(X)$, cioè $(\mathscr{P}(X), \leq)$ è un semi-reticolo. Analogamente mi verrebbe da dire che se $\{P_i\}_{i \in I} \subseteq \mathscr{P}(X)$ è una famiglia non vuota di partizioni allora
$$\bigwedge \{P_i\}_{i \in I} = \left\{\bigcap_{i \in I} x_i : x_i \in P_i \;\forall i \in I \right\}$$se mi date l'OK su questo posso controllare il resto.

jordan ha scritto:Una partizione di un insieme $X$ è una collezioni di insiemi $\{P_j\}_{j \in J}$ tale che $P_i \cap P_j \neq \emptyset$ se e solo se $i=j$, e $\bigcup_{j \in J}{P_j}=X$ (quindi è una collezione di insiemi, si, ma a due a due distinti, nel senso che non ci sono doppioni, è qui che credo venga usato l'AC...)

Sì può evitare di fare ricorso agli indici e definire una partizione di $X$ come un insieme $P$ di sottoinsiemi non vuoti di $X$ tale che $\bigcup P = X$ mentre per ogni $x_1, x_2 \in P$ si ha $x_1 \cap x_2 \neq \varnothing$ se e solo se $x_1 = x_2$. Sicuramente questa definizione non richiede l'assioma della scelta.
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Re: Intersezione di partizioni

Messaggioda jordan il mer 5 mar 2014, 13:11

Tutto ok, apparte quella $F$ calata dal cielo :P

Ps. Nella mia parentesi quando dico che viene usato l'AC si riferisce non alla definizione di partizione, ma a quella di "selezione" degli insiemi $A(x)$ di modo da non prendere "doppioni"..
The only goal of science is the honor of the human spirit.
Avatar utente
jordan
 
Messaggi: 330
Iscritto il: gio 19 giu 2008, 22:42

Re: Intersezione di partizioni

Messaggioda fry il mer 5 mar 2014, 18:48

jordan ha scritto:Ps. Nella mia parentesi quando dico che viene usato l'AC si riferisce non alla definizione di partizione, ma a quella di "selezione" degli insiemi $A(x)$ di modo da non prendere "doppioni"..

Non capisco questa cosa dei doppioni, comunque per provare che $P = \bigwedge \{P_i\}_{i \in I}$ è una partizione di $X$ non è necessario l'assioma della scelta, si procede come segue:

Fissato $x \in X$, per ogni $i \in I$ esiste unico $x_i \in P_i$ tale che $x \in x_i$, poichè $P_i$ è una partizione di $X$, quindi, senza l'assioma della scelta, si è provato che esiste (unica) una funzione $f : I \to \bigcup_{i \in I} P_i$ tale che per ogni $i \in I$ si ha $x \in f(i) \in P_i$. Segue che $x \in \bigcap_{i \in I} f(i) \in P$, da cui $\bigcup P = X$. D'altra parte siano $s, t \in P$, così $s = \bigcap_{i \in I} x_i$ e $t = \bigcap_{i \in I} y_i$ per alcuni $x_i, y_i \in P_i$ per ogni $i \in I$. Allora $s \cap t = \bigcap_{i \in I} (x_i \cap y_i) \neq \varnothing$ implica che $x_i \cap y_i \neq \varnothing$ per ogni $i \in I$, ovvero $x_i = y_i$ per ogni $i \in I$, ovvero $s = t$.
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Re: Intersezione di partizioni

Messaggioda ma_go il mer 5 mar 2014, 21:00

la cosa inquietante è questa:
fry ha scritto:[...] quindi, senza l'assioma della scelta, si è provato che esiste (unica) una funzione $f : I \to \bigcup_{i \in I} P_i$ tale che [...]

hai dimostrato che un prodotto infinito di insiemi non vuoti è non vuoto, e questo è equivalente alla scelta.
certo, l'insieme dei $P_i$ non è arbitrario, ma sembra davvero che ci sia qualcosa di strano qui sotto. non mi è evidente che uno non possa dimostrare che un prodotto arbitrario di insiemi non vuoti è non vuoto usando la proposizione sulle partizioni. o che uno non possa dimostrarci zorn, ad esempio.
non so, sono davvero confuso.
ma_go
 
Messaggi: 271
Iscritto il: gio 19 mag 2011, 13:24

Re: Intersezione di partizioni

Messaggioda fry il mer 5 mar 2014, 21:37

ma_go ha scritto:la cosa inquietante è questa:
fry ha scritto:[...] quindi, senza l'assioma della scelta, si è provato che esiste (unica) una funzione $f : I \to \bigcup_{i \in I} P_i$ tale che [...]

hai dimostrato che un prodotto infinito di insiemi non vuoti è non vuoto, e questo è equivalente alla scelta.
certo, l'insieme dei $P_i$ non è arbitrario, ma sembra davvero che ci sia qualcosa di strano qui sotto. non mi è evidente che uno non possa dimostrare che un prodotto arbitrario di insiemi non vuoti è non vuoto usando la proposizione sulle partizioni. o che uno non possa dimostrarci zorn, ad esempio.
non so, sono davvero confuso.

Non penso ci sia nulla di strano, in moltissimi casi senza appellarsi all'assioma della scelta si può provare che $\prod_{i \in I} X_i$ è non vuoto se ogni $X_i$ è non vuoto, basta che gli insiemi $X_i$ abbiano qualche struttura particolare. Ad esempio se ogni $X_i$ ha un buon ordine $\leq_i$ allora si ha che esiste $f : I \to \bigcup_{i \in I} X_i$ tale che $f(i) \in X_i$ per ogni $i \in I$, essa è data da $f(i) = \min_{\leq_i} X_i$. Nel nostro caso la struttura particolare degli $X_i = P_i$ è data dal fatto che essi sono partizioni di un insieme $X$ e che quindi fissato $x \in X$, per ogni $i \in I$ esiste unico $x_i \in P_i$ tale che $x \in P_i$. Nessuna di queste prove particolari di $\prod_{i \in I} X_i \neq \varnothing$ può implicare l'assioma della scelta perchè esse usano solo gli assiomi di ZF e l'assioma della scelta non è conseguenza di ZF, questo è un fatto non banale.
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Re: Intersezione di partizioni

Messaggioda ma_go il gio 6 mar 2014, 8:40

ok, ora sono convinto. grazie.
ma_go
 
Messaggi: 271
Iscritto il: gio 19 mag 2011, 13:24

Precedente

Torna a Combinatoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron