Passa al tema normale
Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Due forme dell'assioma di scelta

22/04/2020, 22:12

In una discussione di tempo fa, avevo utilizzato l'assioma di scelta, in entrambe le sue due forme equivalenti qui riportate (riprendo esattamente ciò che avevo scritto a suo tempo):

Per ogni famiglia $\mathcal{F}$ di insiemi $X$ non vuoti a coppie disgiunti, esiste un insieme $C$ di scelta.

e:

Per ogni famiglia $\mathcal{F}$ di insiemi $X$ non vuoti, esiste una funzione $g$ di scelta.

Dicendo di scelta significa che $C$ è tale che $C \bigcap X$ consiste in un solo elemento per ogni $X$ della famiglia, mentre nella seconda forma vuol dire che la funzione $g:\mathcal{F} \rightarrow \bigcup \mathcal{F}$ è tale che per ogni insieme $X$ della famiglia si abbia $g(X) \in X$.

Mi è venuto un dubbio di quelli classificabili come "pippa mentale", ma tant'è: provo ad esporlo.
Nel cercare di dimostrare che il primo enunciato implica il secondo, ho notato banalmente che dall'ipotesi esiste \(\displaystyle C \) tale che \(\displaystyle X\cap C \) è un singoletto \(\displaystyle \implies \) l'insieme delle coppie ordinate che vede come primo elemento un qualunque \(\displaystyle X\in \mathcal{F} \) e come secondo elemento l'unico oggetto dell'insieme \(\displaystyle C\cap X \) è ovviamente una relazione (sottoinsieme del prodotto cartesiano tra \(\displaystyle \mathcal{F} \) e \(\displaystyle \bigcup \mathcal{F} \)) di tipo funzionale.

Domanda: oltre a chiedere una conferma sulla correttezza della dimostrazione, vi domando come, formalmente, andrebbe definita la funzione sopra cercata? Nel seguente modo?
$$ \left\{(X,x)\in\mathcal{F}\times \bigcup\mathcal{F} \;\;|\;\; X\in\mathcal{F}, x\in X\cap C\right\} $$

Non avendo mai studiato seriamente la teoria degli insiemi mi è venuta anche questa curiosità su come andrebbe veramente scritta.

Grazie in anticipo.

Re: Due forme dell'assioma di scelta

22/04/2020, 23:39

Se \( C\cap X \) ha un solo elemento per ogni \( X\in\mathscr F \) allora puoi definire una funzione \( \mathscr F\to \bigcup\mathscr F \) come \( X\mapsto x \), dove \( x\in C\cap X \) è quell'unico elemento.

Un'altra forma ovvia di \( \sf{AC} \) è "il prodotto \( \prod_{i\in I}X_i \) di una famiglia \( \left(X_i\right)_{i\in I} \) di insiemi non vuoti non è mai vuoto". Questo perché per una famiglia tipo quella è
\[
\prod_{i\in I}X_i := \Big\{t\colon I\mapsto\bigcup_{i\in I}X_i : t(i)\in X_i\Big\}
\] praticamente per definizione.
Ultima modifica di marco2132k il 23/04/2020, 22:16, modificato 1 volta in totale.

Re: Due forme dell'assioma di scelta

23/04/2020, 21:34

marco2132k ha scritto:Un'altra forma ovvia di è "il prodotto di una famiglia di insiemi non vuoti non è mai vuoto".


:?:

Due insiemi disgiunti hanno intersezione vuota.

Re: Due forme dell'assioma di scelta

23/04/2020, 22:16

Intendevo "prodotto cartesiano".

Re: Due forme dell'assioma di scelta

25/04/2020, 09:03

Ah scusami, ho capito.

Chiedo una conferma. Nel secondo enunciato che ho riportato:

Silent ha scritto:Per ogni famiglia F di insiemi X non vuoti, esiste una funzione g di scelta.


manca che gli insiemi della famiglia devono essere a coppie disgiunti, vero?
L'ipotesi che siano a coppie disgiunti non va inserita solo nella prima forma, ma anche in questa seconda, è corretto?

Re: Due forme dell'assioma di scelta

25/04/2020, 17:31

\( \newcommand{\kerrel}{\mathrm{ker}} \)Ma le due forme non sono equivalenti?

Metti che per una famiglia \( \mathscr F \) di nonvuoti a due a due disgiunti esista sempre una funzione \( c\colon\mathscr F\to\bigcup\mathscr F \) di scelta. Da qui è immediato provare che ogni funzione suriettiva ha inversa destra. E da qui ricavare l'assioma della scelta "per-famiglie-di-non-necessariamente-disgiunti" ancora non dovrebbe essere difficile. Se \( \mathscr F \) è una tale famiglia, considera l'insieme \( \Phi = \left\{(x,X):\text{$ X\in\mathscr F $ e $ x\in X $}\right\} \) con le due proiezioni \( \pi_1\colon\Phi\to\bigcup\mathscr F \) e \( \pi_2\colon\Phi\to\mathscr F \): esiste l'inversa destra di entrambe, perché sono due funzioni suriettive; allora, detta \( \nu_2 \) l'inversa destra di \( \pi_2 \), (mi sa che) la funzione \( \pi_1\circ\nu_2\colon\mathscr F\to\bigcup\mathscr F \) è di scelta.

Poi. Ha senso in ZF(C) formare quell'insieme \( \Phi \)? Io non ne ho la minima idea, qui devi aspettare qualcun altro.

Re: Due forme dell'assioma di scelta

25/04/2020, 22:36

Quello che volevo dire è che, presa ad esempio questa famiglia di insiemi:

\(\displaystyle \mathcal{F}=\{X_1,X_2,X_3,X_4\} \) con \(\displaystyle X_1=\{1,2,3\},X_2=\{1,2\},X_3=\{2,3\},X_4=\{1,3\} \)

(che non sono ovviamente a coppie disgiunti) una funzione di scelta la trovo, ma non trovo mai un insieme $C$ tale che l'intersezione con ognuno degli $X_i$ sia un singoletto.

Dunque, l'enunciato nella seconda forma (dove non c'è scritto che gli insiemi della famiglia debbano essere a coppie disgiunti) non implica l'enunciato nella prima forma.

Da cui, la mia domanda:

Silent ha scritto:Chiedo una conferma. Nel secondo enunciato che ho riportato:

Silent ha scritto:
Per ogni famiglia F di insiemi X non vuoti, esiste una funzione g di scelta.


manca che gli insiemi della famiglia devono essere a coppie disgiunti, vero?
L'ipotesi che siano a coppie disgiunti non va inserita solo nella prima forma, ma anche in questa seconda, è corretto?

Re: Due forme dell'assioma di scelta

26/04/2020, 16:20

Ci ho pensato un attimo. È vero che le due
Assioma delle scelta. 1. Per ogni famiglia di non vuoti esiste una funzione di scelta.
Assioma di Zermelo. 2. Per ogni famiglia \( \mathscr F \) di insiemi nonvuoti e a due a due disgiunti esiste un insieme \( C \) tale che l'intersezione \( C\cap X \) è un singoletto per ogni \( X \) della famiglia.
sono equivalenti.
Testo nascosto, fai click qui per vederlo
Dimostrazione. ((1)\(\,\implies\,\)(2)). Se gli insiemi di \( \mathscr F \) sono \( {\neq\emptyset} \) e a due a due disgiunti, e \( c \) è di scelta \( \mathscr F\to\bigcup\mathscr F \), l'immagine \( c(\mathscr F) \) interseca tutti gli \( X\in F \) in un singoletto. ((2)\(\,\implies\,\)(1)). Dovrebbe farsi come ti ho mostrato (ossia: la (2) implica una versione apparentemente weak dell'assioma della scelta - per famiglie di a due a due disgiunti; e questa, invece, è equivalente ad AC). \( \square \)


Quello che invece non vale è che l'assioma della scelta (1) implichi che per ogni famiglia di insiemi non necessariamente disgiunti ci sia un \( C \) con la proprietà richiesta da (2).

Forse ora è meglio se aspetti anche il parere di qualcuno che ne sa più di me, però.

Re: Due forme dell'assioma di scelta

26/04/2020, 20:45

Grazie!

Re: Due forme dell'assioma di scelta

01/05/2020, 06:56

\(\newcommand\scrf{\mathscr F}\)
marco2132k ha scritto:[...] ricavare l'assioma della scelta "per-famiglie-di-non-necessariamente-disgiunti" ancora non dovrebbe essere difficile. Se \( \mathscr F \) è una tale famiglia, considera l'insieme \( \Phi = \left\{(x,X):\text{$ X\in\mathscr F $ e $ x\in X $}\right\} \) con le due proiezioni \( \pi_1\colon\Phi\to\bigcup\mathscr F \) e \( \pi_2\colon\Phi\to\mathscr F \): esiste l'inversa destra di entrambe, perché sono due funzioni suriettive; allora, detta \( \nu_2 \) l'inversa destra di \( \pi_2 \), (mi sa che) la funzione \( \pi_1\circ\nu_2\colon\mathscr F\to\bigcup\mathscr F \) è di scelta.


Oppure puoi (potete) prendere l'insieme \(\scrf \times \bigcup \scrf\), del quale ovviamente non mi serve tutto, ma solo il sottoinisieme degli insiemi puntati \[\scrf^\ast := \left\{ (X, a) \in \scrf \times \bigcup \scrf \mid a \in X \right\}\] partizionabile attraverso gli insiemi \[X^\ast := \{ (X, x) \mid x \in X \}\]. Applichi questa versione dell'assioma della scelta

Silent ha scritto:Per ogni famiglia $ \mathcal{F} $ di insiemi $ X $ non vuoti a coppie disgiunti, esiste un insieme $ C $ di scelta.


e hai finito: l'insieme-scelta è la funzione-scelta cercata.

Silent ha scritto:Domanda: oltre a chiedere una conferma sulla correttezza della dimostrazione, vi domando come, formalmente, andrebbe definita la funzione sopra cercata? Nel seguente modo?
\[ \left\{(X,x)\in\mathcal{F}\times \bigcup\mathcal{F} \;\;|\;\; X\in\mathcal{F}, x\in X\cap C\right\} \]


Come ti è stato fatto vedere da marco2132k, non ha senso visto he ti è sfuggita qualche evenienza nel primo post. Ma la domanda è: perché vuoi scriverla in formule? Hai assicurato solamente l'esistenza di una funzione scelta, non sai quale concretamente sia.

marco2132k ha scritto:Poi. Ha senso in ZF(C) formare quell'insieme \( \Phi \)?

Sì (se con "famiglia" intendi "insieme").
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.