Se [tex]|A|=\infty[/tex] allora [tex]|A \times A|=|A|[/tex]

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

Se [tex]|A|=\infty[/tex] allora [tex]|A \times A|=|A|[/tex]

Messaggioda Feanor il gio 11 giu 2009, 0:56

Definizione 1. Sia \big(A_i\big)_{i \in I} una famiglia di insiemi, indicizzata da I. Si definisce unione disgiunta il seguente insieme: \displaystyle \coprod_{i \in I} A_i := \bigcup_{i \in I}(A_i \times \{i\}) .

Definizione 2. Un insieme (parzialmente) ordinato (A, \leq) si dice induttivo se ogni catena (cioè ogni sottoinsieme totalmente ordinato) di A possiede maggioranti.

Definizione 3. Sia (A, \leq) un insieme (parzialmente) ordinato. Un elemento m \in A si dice massimale se non esiste alcun elemento a \in A che lo superi, cioè tale che m<a (dove la scrittura va intesa come m \leq a \wedge m \neq a).

Outline. Si conviene indicare \mathbb{N}:=\{0, 1, 2, \ldots,\} per indicare l'insieme dei numeri naturali.

Assioma 1. (Lemma di Zorn). Sia (A, \leq) un insieme (parzialmente) ordinato induttivo. Per ogni a \in A esiste un elemento massimale a \leq m.
\bigl(È, forse, più comune la seguente, equivalente, formulazione. Sia (A, \leq) un insieme (parzialmente) ordinato induttivo. Allora esiste almeno un elemento a \in A massimale, cioè tale che \forall\ b \in A, a e b non sono confrontabili oppure b \leq a\, . \bigr)

Proposizione 1. |\{1, 2\} \times \mathbb{N}| = |\mathbb{N}\ \mathcal{t}\ \mathbb{N}| = |\mathbb{N}|

Dim. Definite le applicazioni
    f(\cdot): \mathbb{N} \to \{1, 2\} \times \mathbb{N}: n \mapsto \begin{cases} \Big(1, \frac{1}{2}n\Big) &,\ \text{se } 2 \mid n \\
\\
\Big(2, \frac{1}{2}(n-1)\Big) &,\ \text {se } 2 \nmid n 
\end{cases},}\qquad g(\cdot): \{1, 2\} \times \mathbb{N} \to \mathbb{N}\ \mathcal{t}\ \mathbb{N}: (i, n) \mapsto (n, i)\ ;
è immediato notare che esse sono biiezioni; perciocché anche (g \circ f)(\cdot) lo è. \square


Proposizione 2. |\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|

Dim. Si definisce la funzione coppia di Cantor:
    \pi : \mathbb{N} \times \mathbb{N} \to \mathbb{N} : (n_1, n_2) \mapsto \dfrac{1}{2}(n_1+n_2)(n_1+n_2+1)+n_1\ .
Essa è una biiezione. \square


Proposizione 3. Siano X un insieme di cadinalità infinità e A un insieme tale che \exists\ n \in \mathbb{N}:\ |A|=n. Allora |X \mathcal{t} A|=|X|.

Dim. Poiché X è infinito, esiste un suo sottoinsieme \mathbb{M}\subseteq X tale che |\mathbb{M}|=|\mathbb{N}|. Considerando la funzione f(\cdot): \mathbb{N} \to \big(A\mathcal{t}\mathbb{N}\big) tale che associa \mathcal{D}_n:=\{0, 1, \ldots, n-1\} biettivamente ad A; inoltre f_{|\mathbb{N}\setminus\mathcal{D}_n}(\cdot): \big(\mathbb{N}\setminus\mathcal{D}_n\big) \to \mathbb{N}: m \mapsto (m-n) è pure biettiva, perciò lo è anche f(\cdot). Infine, |\mathbb{M}|=|\mathbb{M}\mathcal{t} A| e quindi la tesi. \square


Lemma 1. Sia X un insieme infinito. Allora |\{1, 2\} \times X|=|X|

Dim. Si definisca la seguente famiglia: \mathfrak{F} := \Bigl\{\bigl(A, f(\cdot)\bigr): A \subseteq X,\ f(\cdot): \{1, 2\} \times A \to A,\ \forall\ a, b \in A\ f(a)=f(b) \Rightarrow a = b\Bigr\}.
Poiché ogni insieme infinito contiene almeno un sottoinsieme numerabile, \mathfrak{F} non è vuoto, infatti |\{1, 2\} \times \mathbb{N}|=|\mathbb{N}|.
Si definisce una relazione di ordine (\mathfrak{F}, \leq) in questo modo: \bigl(A, f(\cdot)\bigr) \leq \bigl(B, g(\cdot)\bigr) \text{ se } A \subseteq B \wedge\ g|_{\{1, 2\} \times A}(\cdot) := f(\cdot).
Sia \bigl(A_i, f_i(\cdot)\bigr), con i \in \mathcal{I} famiglia di indici, una catena in \mathfrak{F}, e si definisca C := \bigcup_{i\in\mathcal{I}}A_i e la funzione \displaystyle u(\cdot): \{1, 2\} \times C \to C come segue: a \in A_i\ \Rightarrow\ u\bigl((j, a)\bigr) := f_i\bigl((j, a)\bigr).
u(\cdot), per come è stato definito l'ordinamento e poiché \bigl(A_i, f_i \bigr) è una catena, risulta ben definita. Infatti u\bigl(\{1, 2\} \times C\bigr) \subseteq C \subseteq X. Inoltre u(\cdot) è iniettiva, quindi \bigl(C, u(\cdot) \bigr) \in \mathfrak{F}.
È evidente, per costruzione, che \forall\ i\in \mathcal{I}\quad \bigl(A_i, f_i(\cdot)\bigr) \leq \bigl(C, u(\cdot)\bigr), perciocché quest'ultima coppia è un maggiorante della catena. Ne segue, allora, che esiste, per il Lemma di Zorn, un elemento \bigl(B, g(\cdot)\bigl) massimale in \mathfrak{F}.
Se, ora, |B|=|X| si ha la tesi.
Sia, invece, |B|<|X|.
Se |X \setminus B| fosse finita, per la Proposizione 3, si avrebbe |X|=|X \setminus B \cup B|=|B| e questo è assurdo. Quindi |X \setminus B| è infinità, perciò \exists\ \mathbb{M} \subseteq X \setminus B : |\mathbb{M}|=|\mathbb{N}|. Sia definito D := B\ \cup\ \mathbb{M}.
Per la Proposizione 1 esiste una funzione biiettiva i(\cdot): \{1, 2\} \times \mathbb{M} \to \mathbb{M}. Allora è possibile definire la seguente funzione:
    h(\cdot): \{1, 2\} \times D \to D: \begin{cases}
h|_{\{1, 2\} \times B}(\cdot) := g(\cdot)\\
\\
h|_{\{1, 2\} \times \mathbb{M}}(\cdot) := i(\cdot)
\end{cases}\ .
L'applicazione h(\cdot) è iniettiva, quindi \bigl(D, h(\cdot)\bigr) \in \mathfrak{F}; inoltre \bigl(B, g(\cdot)\bigl) \leq \bigl(D, h(\cdot)\bigr), ma ciò contraddice la massimalità di \bigl(B, g(\cdot)\bigl) in \mathfrak{F}.
Infine, dunque, |B|=|X|, perciò esiste una biiezione b(\cdot): B \to X; poiché evidentemente esiste un'applicazione iniettiva l(\cdot): B \to \{1, 2\} \times B se ne deduce, per il Teorema di Bernstein-Schroeder (v. qui, dove vi è anche una bellissima dimostrazione), che |B|=|\{1,2 \} \times B| e quindi la tesi. \square


Corollario 1. Siano X, Y due qualunque insiemi di cardinalità infinita. Allora |X \mathcal{t} Y| = \max\bigl(|X|, |Y|\bigr).

Dim. Si ponga, wlog, |Y|\leq|X|. Come nella Proposizione 1 si può definire una funzione biiettiva g(\cdot): \{1, 2\} \times X \to X \mathcal{t} X: (j, x) \mapsto (x, j). È immediato verificare che esiste una applicazione iniettiva f(\cdot): X \cup Y \to X \mathcal{t} X e quindi |X| \leq |X \cup Y| \leq |X \mathcal{t} X| = |\{1, 2\} \times X|; ma |\{1, 2\} \times X| = |X| e quindi la tesi. \square


Teorema 1. Sia X un qualsiasi insieme di cardinalità infinita (ovvero che non può essere messo in corrispondenza biunivoca con alcun sottoinsieme finito di \mathbb{N}). Allora |X \times X|=|X|. (Questa proposizione è equivalente all'Assioma della Scelta, v. qui, e quindi, in questo caso, al Lemma di Zorn).

Dim. Si definisca la seguente famiglia: \mathfrak{F} := \Bigl\{\bigl(A, f(\cdot)\bigr): A \subseteq X,\ f(\cdot): A \times A \to A,\ \forall\ a, b \in A\ f(a)=f(b) \Rightarrow a = b\Bigr\}.
Poiché ogni insieme infinito contiene almeno un sottoinsieme numerabile, \mathfrak{F} non è vuoto, infatti |\mathbb{N} \times \mathbb{N}|=|\mathbb{N}|.
Si definisce una relazione di ordine (\mathfrak{F}, \leq) in questo modo: \bigl(A, f(\cdot)\bigr) \leq \bigl(B, g(\cdot)\bigr) \text{ se } A \subseteq B \wedge\ g|_{\{1, 2\} \times A}(\cdot)=f(\cdot).
Sia \bigl(A_i, f_i(\cdot)\bigr), con i \in \mathcal{I} famiglia di indici, una catena in \mathfrak{F}, e si definisca C := \bigcup_{i\in\mathcal{I}}A_i e la funzione \displaystyle u(\cdot): C \times C \to C come segue: a_1, a_2 \in A_i\ \Rightarrow\ u\bigl((a_1, a_2)\bigr) := f_i\bigl((a_1, a_2)\bigr).
u(\cdot), per come è stato definito l'ordinamento e poiché \bigl(A_i, f_i \bigr) è una catena, risulta ben definita. Infatti u(C \times C) \subseteq C \subseteq X. Inoltre u(\cdot) è iniettiva, quindi \bigl(C, u(\cdot) \bigr) \in \mathfrak{F}.
È evidente, per costruzione, che \forall\ i\in \mathcal{I}\quad \bigl(A_i, f_i(\cdot)\bigr) \leq \bigl(C, u(\cdot)\bigr), perciocché quest'ultima coppia è un maggiorante della catena. Ne segue, allora, che esiste, per il Lemma di Zorn, un elemento \bigl(B, g(\cdot)\bigl) massimale in \mathfrak{F}.
Se, ora, |B|=|X| si ha la tesi.
Sia, invece, |B|<|X|.
Ovviamente esiste un'applicazione i(\cdot): B \to B \times B iniettiva, quindi, per il Teorema di Bernstein-Schroeder, |B|=|B \times B|. Poiché |X|=|B \cup X\setminus B| = \max (|X\setminus B|, |B|) deve essere |X|=|X\setminus B| per l'ipotesi fatta. Quindi si ha |B|<|X\setminus B| e necessariamente \exists\ C \subset X\setminus B : |C|=|B|.
Ne consegue che |B|=|B \times B|= |B \times C|=|C \times B|=|C \times C|.
Notando che (B \cup C)\times(B \cup C)= (B \times B) \cup (B \times C) \cup (C \times B) \cup (C \times C) si definsce D := (B \times C) \cup (C \times B) \cup (C \times C) e la funzione biiettiva l(\cdot): D \to C, che si sa esistere in quanto |D| = \max \bigl( |B \times C|, |C \times B|,|C \times C| \bigr) = |B \times B| = |B| = |C|.
Si definisca, inoltre, la seguente funzione
    h(\cdot): (B \cup C) \times (C \cup B) \to B \cup C: \begin{cases}
h|_{B\times B}(\cdot) := g(\cdot) \\
\\
h|_{D}(\cdot) := l(\cdot)
\end{cases}\ .
h(\cdot), che è iniettiva, estende chiaramente g(\cdot); per cui \bigl(B \cup C, h(\cdot)\bigr) \in \mathfrak{F} e, soprattutto, \bigl(B, g(\cdot)\bigr) \leq \bigl(B \cup C, h(\cdot)\bigr) e questo è un assurdo, in quanto contraddice la massimalità di \bigl(B, g(\cdot)\bigr). Infine, |B|=|X| e quindi la tesi. \square
Feanor
 
Messaggi: 732
Iscritto il: lun 29 set 2008, 20:58

Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron