Aritmetica e complementi sugli insiemi

Oltre la matematica elementare: teoria, esercizi, e riflessioni sulle varie branche della matematica che si fanno all'università.

Aritmetica e complementi sugli insiemi

Messaggioda hyka » 14/10/2014, 19:30

Piccola serie di esercizi (inizialmente banali, man mano leggermente più difficili) per la vostra gioia.

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\)

Intermezzo
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\)

Tutte le espressioni algebriche più fantasiose che potevano essere espresse sui naturali ora hanno senso anche sugli insiemi :lol:

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\)

Un insieme \(A\) si dice avere un punto fisso se \(\forall f : A \to A (\exists a \in A . f(a) = 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?)

Per ora direi che basta (100 testoni a chi scrive tutte le dimostrazioni, 70 a chi scrive tutte quelle di continuando) :twisted:
Ultima modifica di hyka il 15/10/2014, 19:03, modificato 2 volte in totale.
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Aritmetica e complementi sugli insiemi

Messaggioda hyka » 14/10/2014, 19:44

Double post (se qualche admin ha gulia, che lo cancelli)
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Aritmetica e complementi sugli insiemi

Messaggioda afullo » 15/10/2014, 16:21

Esercizi belli istruttivi direi, grazie per questa lunga lista che può aiutare tanti olimpionici in erba a fare il salto di qualità :D

hyka ha scritto:Double post (se qualche admin ha gulia, che lo cancelli)

Ho dovuto cercare il significato qui, io so' polentone, non puoi pretendere che conosca il dialetto napoletano :mrgreen:
afullo
 
Messaggi: 1388
Iscritto il: 13/03/2013, 22:06

Re: Aritmetica e complementi sugli insiemi

Messaggioda Drago » 15/10/2014, 17:33

Sembrano molto belli, mi pare ci sia solo un typo nei baby steps: scrivi $ A=B\implies A×C=A×B $ quando dovrebbe essere $ A×C=B×C $ :)
Avatar utente
Drago
 
Messaggi: 1055
Iscritto il: 14/03/2013, 15:51

Re: Aritmetica e complementi sugli insiemi

Messaggioda hyka » 15/10/2014, 19:05

afullo ha scritto:Ho dovuto cercare il significato qui, io so' polentone, non puoi pretendere che conosca il dialetto napoletano :mrgreen:


Colpa di un professore :roll:

@Drago, grazie, ho corretto
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03


Torna a Matematica Universitaria

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti