Notazioni
Diamo innanzitutto per scontato la conoscenza di cosa siano i numeri naturali \(\mathbb{N}\), gli insiemi, l'unione, l'intersezione, le tuple, le funzioni, funzioni iniettive, suriettive, biettive, isomorfismi (per evitare malintesi, una funzione \(f : A \to B\) è un isomorfismo se esiste una funzione \(g : B \to A\) tale che \(g \circ f = \text{id}_A \wedge f \circ g = \text{id}_B\), inoltre una funzione è un isomorfismo se e soltanto se è biettiva).
Definiamo il prodotto di due insiemi \(A\), \(B\) come il prodotto cartesiano:
\(A \times B = \{(a, b) . a \in A . b \in B\}\)
e la somma di due insiemi \(A\), \(B\) come (questa particolare costruzione di) la somma disgiunta:
\(A + B = (\{0\} \times A) \cup (\{1\} \times B)\)
Poniamo inoltre
\(I_n = \{m \in \mathbb{N} . 1 \leq m \leq n\}\)
in particolare chiamiamo \(0 = I_0 = \emptyset\) e \(1 = I_1 = \{1\}\)(per il semplice fatto che questi elementi si comporteranno come lo \(0\) e come \(1\) dei naturali sugli insiemi).
Definiamo l'esponenziazione di due insiemi \(A\), \(B\) come l'insieme delle funzioni:
\(B^A = \{f : A \to B\}\)
Infine diciamo che due insiemi \(A\), \(B\) sono uguali, scritto \(A = B\), se esiste un isomorfismo da \(A\) verso \(B\) (ricordiamo che la relazione di isomorfismo è una relazione di equivalenza, quindi ha senso usare l'uguale). Per dimostrare le equivalenze sarà quindi sufficiente mostrare un isomorfismo tra i due insiemi, ad esempio per dimostrare che \(A \times B = B \times A\) basterà esibire la funzione \(\text{swap}_{A, B} : A \times B \to B \times A\) che "inverte" le componenti delle tuple, e dimostrare che la funzione \(\text{swap}_{B, A}\) è la sua funzione inversa.
Baby steps
Per insiemi \(A\), \(B\), \(C\), dimostrare che:
- \(A + B = B + A\)
- \(A = B \rightarrow A + C = B + C\)
- \(A + 0 = A\)
- \((A+B)+C = A + (B+C)\)
- \(A \times B = B \times A\)
- \(A = B \rightarrow A \times C = B \times C\)
- \(A \times 1 = A\)
- \((A \times B) \times C = A \times (B \times C)\)
- \(A \times 0 = 0\)
- \(A \times (B + C) = A \times B + A \times C\)
- \((A + B) \times C = A \times C + B \times C\)
Abbiamo detto che la somma ed il prodotto sono associativi. Dimostrare per induzione sul numero di insiemi che "l'ordine con cui si esegue la somma" è indifferente, e l'analogo per il prodotto.
Dimostrare che la notazione di somma e di prodotto di una famiglia finita di insiemi definita ricorsivamente è equivalente alla definizione di somma e prodotto generalizzato:
\(\displaystyle \sum_{i \in I_n} A_i = \bigcup_{i \in I_n} \{i\} \times A_i\)
\(\displaystyle \prod_{i \in I_n} A_i = \{(a_1, a_2, \ldots, a_n) . a_i \in A_i\}\)
Esponenti
Dato un insieme \(A\) e un numero naturale \(n \in \mathbb{N}\), definiamo \(A^n = \underbrace{A \times A \times \ldots \times A}_\text{n-volte}\).
Dimostrare che \(A^n = A^{I_n}\). D'ora in poi indicheremo \(A^{I_n}\) con \(A^n\) (in particolare ci servirà per mantenere la notazione di \(0\) e \(1\)).
Per ogni \(A\), \(B\), \(C\), dimostrare che:
- \(A = B \rightarrow C^A = C^B\)
- \(A = B \rightarrow A^C = B^C\)
- \(A^0 = 1\)
- \(A \neq 0 \rightarrow 0^A = 0\)
- \(1^A = 1\)
- \(A^1 = A\)
- \((A \times B)^C = A^C \times B^C\)
- \(C^{A + B} = C^A \times C^B\)
- \(C^{A \times B} = (C^A)^B\)
Continuando
Data una funzione \(f : A \to B\) esiste una funzione \(f^X : A^X \to B^X\) definita come \(f^X(g) = f \circ g\).
Analogamente, data \(f : A \to B\) esiste una funzione funzione \(C^f : C^B \to C^A\) definita come \(C^f(g) = g \circ f\).
Dimostrare che:
- \(f: A \to B\) è iniettiva se e soltanto se \(2^f : 2^B \to 2^A\) è suriettiva
- \(f: A \to B\) è suriettiva se e soltanto se \(2^f : 2^B \to 2^A\) è iniettiva
- L'insieme delle parti di \(A\) è isomorfo a \(2^A\). D'ora in poi indicheremo l'insieme delle parti di \(A\) con \(2^A\)
- Se esiste una funzione suriettiva \(f : B \to A^B\) allora \(A\) ha un punto fisso
- (Cantor) Non esiste nessuna funzione suriettiva da \(A\) verso \(2^A\), in particolare \(2^A \neq A\)
- \(\forall n \in \mathbb{N} . \mathbb{N}^n = \mathbb{N}\) (si assuma \(\mathbb{N}^2 = \mathbb{N}\) da questo topic, anche se ciò banalizza il problema)
- \(\mathbb{N}^\mathbb{N} = 2^\mathbb{N}\)
- \(\mathbb{N}^\mathbb{N} \neq \mathbb{N}\) (conta come esercizio?)
