% File: algebraI.tex % Created: Sat Oct 07 10:00 AM 2006 C % Last Change: Sat Oct 07 10:00 AM 2006 C % % % (c) Copyright 2007 Andrea Lo Pumo aka AlpT % % This source code is free software; you can redistribute it and/or % modify it under the terms of the GNU General Public License as published % by the Free Software Foundation; either version 2 of the License, % or (at your option) any later version. % % This source code is distributed in the hope that it will be useful, % but WITHOUT ANY WARRANTY; without even the implied warranty of % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. % Please refer to the GNU Public License for more details. % % You should have received a copy of the GNU Public License along with % this source code; if not, write to: % Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. % \documentclass[a4paper]{article} \usepackage{amath} \title{Algebra I} \author{AlpT (@freaknet.org)} \begin{document} \pagenumbering{roman} \maketitle{} \begin{abstract} Questo testo e' una rielaborazione personale degli appunti presi durante il corso di Algebra I, tenuto dal Prof. Alfio Ragusa presso il dipartimento di Matematica, Catania, A.A. 2006/2007.\\ Saro' ben lieto di correggere ogni eventuale errore che mi comunicherai. Buon lettura. \begin{center} \verb|^_^| \end{center} \end{abstract} \input{gpl} \clearpage \tableofcontents \clearpage \pagenumbering{arabic} \let\oldsection\section \let\oldsubsection\subsection \let\oldsubsubsection\subsubsection \section{Gli insiemi} L'\emph{insieme} e' uno dei concetti piu' generali della matematica. E' talmente generale, che rende possibile ricostruire quasi tutta la matematica moderna a partire dalla teoria degli insiemi. \subsection{Concetto primitivo} \label{sec:primitive} L'insieme e' definito come elemento \emph{primitivo}.\\ Un elemento primitivo e' un concetto che si definisce senza ricorrere a nessun'altra precedente definizione.\\ I concetti primitivi sono necessari per poi poter porre altre definizioni che si basano su essi. \paragraph{} Poiche' il concetto d'insieme e' facilmente comprensibile dalla maggior parte degli esseri umani, i matematici lo hanno scelto come elemento primitivo. Questo, pero', non e' sempre vero, un concetto primitivo non e' universale. Per spiegare il semplice concetto d'insieme a un computer e' necessario istruirlo con migliaia e migliaia di righe di codice. D'altronde, lo stesso vale per un essere umano di pochi anni: e' un compito arduo, se non impossibile chiarire il concetto d'insieme a un bambino appena nato. \paragraph{} In conclusione, sarebbe piu' corretto dire che l'insieme e' un concetto primitivo per gli esseri umani che hanno raggiunto un minimo di allenamento mentale. Poiche', tu lettore, stai leggendo questo testo, sarai anche in grado di comprendere il concetto d'insieme, e di conseguenza quasi tutta la matematica moderna. \subsection{L'elemento} \label{sec:element} Un elemento puo' essere qualsiasi un qualsiasi simbolo che possa essere riconosciuto e distinto da altri simboli. In questo caso ``simbolo'' e' sinonimo di ``informazione''. \subsection{L'insieme} \label{sec:set} Un \emph{insieme} e' formato da una lista non ordinata di elementi di qualsiasi tipo. Per descrivere un insieme, bisogna includere la lista di tutti i suoi elementi all'interno di parentesi graffe. Ad esempio, questo e' l'insieme di alcuni linguaggi di programmazione: \[ \left\{ \textrm{C, Perl, TCL, Awk, Python, Bash, Lisp} \right\} \] Possiamo anche assegnare un nome all'insieme: \[ \mathbb{L}=\left\{ \textrm{C, Perl, TCL, Awk, Python, Bash, Lisp} \right\} \] Che tradotto in parole diventa: ``$\mathbb{L}$ e' l'insieme che contiene i seguenti linguaggi di programmazione: \emph{C, Perl, TCL, Awk, Python, Bash, Lisp}'' Poiche' un insieme puo' contenere qualsiasi tipo di elemento possiamo anche definire l'insieme di tutti i linguaggi di programmazione: \[ \mathbb{L}=\left\{ \textrm{Tutti i linguaggi di programmazione esistenti fino a oggi} \right\} \] \label{sec:cardinalityset} Per indicare il numero degli elementi di un insieme (che viene chiamato cardinalita' dell'insieme), si usano le sbarrette del valore assoluto: \[ |L| = 7 \] Il numero degli elementi di $L$ e' 7. \subsubsection{Insieme vuoto} \label{sec:emptyset} L'insieme vuoto e' quell'insieme che non contiene alcun elemento. \subsubsection{Insieme identico} \label{sec:identityset} L'insieme identico dell'insieme A e' l'insieme A stesso. \subsection{Sottoinsieme} \label{sec:subset} L'insieme B e' un sottoinsieme di A, se tutti gli elementi di B sono contenuti in A. \begin{displaymath} B \subseteq A \quad \Leftrightarrow \quad \forall b \in B \mid b \in A \end{displaymath} \oldsubsubsection{Proprieta'} \begin{enumerate} \item L'insieme vuoto e' sempre un sottoinsieme di qualsiasi insieme. \[\emptyset \subseteq A\] \item Qualsiasi insieme contiene l'insieme identico come sotto insieme. \[A \subseteq A\] \item Se $n$ e' il numero degli elementi dell'insieme A, allora il numero totale di tutti i suoi possibili sottoinsiemi e' pari a $2^n$ \end{enumerate} \subsection{Insiemi uguali} \label{sec:eqset} Due insieme B e A sono uguali se B e' un sottoinsieme di A ed A e' un sottoinsieme di B, \begin{displaymath} B = A \quad \Leftrightarrow \quad B \subseteq A \land A \subseteq B \end{displaymath} \subsubsection{Sottoinsieme proprio e improprio} \label{sec:propersubset} Il sottoinsieme \emph{improprio} di A, e' quell'insieme che contiene tutti gli elementi di A, ovvero, e' uguale ad A stesso. Il sottoinsieme \emph{proprio} di A, e' invece un qualsiasi sottoinsieme che non contiene almeno un elemento di A. I simbolo utilizzato per indicare un sottoinsieme generale (improprio o proprio) e quello per indicare un sottoinsieme proprio sono rispettivamente $\subseteq$ e $\subset$. Per analogia si possono confrontare con i simboli $\leq$ e $<$: se il numero degli elementi di B e' $\leq$ di quelli di A scriveremo $B \subseteq A$, altrimenti $B \subset A$. \subsection{Intersezione} \label{sec:intersectset} L'intersezione di A e B e' quell'insieme che contiene tutti gli elementi che sono sia in A che in B. Nell'algebra booleana, l'intersezione corrisponde all'operazione $\mbox{AND}$. \[ (x \in A \cap B) \Leftrightarrow (x \in A \land x \in B) \] \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{fig/Venn_A_intersect_B} \end{center} \caption{Intersezione di A e B} \label{fig:venn_intersect} \end{figure} \oldsubsubsection{Proprieta'} \begin{enumerate} \item $A \cap B = B \cap A\quad$ (proprieta' commutativa) \item $A \cap A = A$ \item $A \cap \emptyset = \emptyset$ \item $(A \cap B) \cap C = A \cap (B \cap C) \quad$ (proprieta' associativa) \item $B \subseteq A \quad \Leftrightarrow \quad B \cap A = B$ \end{enumerate} \subsection{Insiemi disgiunti} \label{sec:disjointset} Due insieme A e B sono disgiunti se non hanno nessun elemento in comune. \begin{displaymath} \textrm{A, B sono disgiunti} \Leftrightarrow A \cap B = \emptyset \end{displaymath} \subsection{Insiemi coincidenti} \label{sec:jointset} Due insiemi A e B sono coincidenti se hanno tutti gli elementi in comune, ovvero sono insiemi uguali (vedi \ref{sec:eqset}). \begin{displaymath} \textrm{A, B sono coincidenti} \Leftrightarrow A = B \end{displaymath} \subsection{Insieme delle parti} \label{sec:powerset} Si dice \emph{insieme delle parti} (o \emph{insieme potenza}) dell'insieme A, quell'insieme che contiene come elementi, tutti i sottoinsiemi di A. L'insieme delle parti si indica con $\mathcal{P}(A)$. \oldsubsubsection{Proprieta'} \begin{enumerate} \item $B \subseteq A \quad \Leftrightarrow \quad B \in \mathcal{P}(A)$ \item $a \subseteq A \quad \Leftrightarrow \quad \{a\} \subseteq A \quad \Leftrightarrow \quad \{a\} \in \mathcal{P}(A)$ \item $|\mathcal{P}(A)| = 2^{|A|} \quad$ Ovvero, il numero degli elementi di $\mathcal{P}(A)$ e' pari a $2$ elevato al numero degli elementi di $A$. (questa proprieta' vale solo se $\mathcal{P}(A)$ e' finito). \begin{proof} Poniamo $n = |A|$ e $p \in \mathcal{P}(A)$ Rappresentiamo $p$ come un numero a $n$-bit. L'$n$-esimo bit e' uguale a 1 se l'$n$-esimo elemento di $A$ e' presente in $p$, altrimenti e' uguale a 0. Poiche' di numeri a $n$-bit ne esistono $2^n$, il numero di tutti gli $p \in \mathcal{P}(A)$ e' pari a $2^n$. \end{proof} \end{enumerate} \subsection{Insieme di indici} \label{sec:indexset} Consideriamo un insieme $I$ e un insieme $A$. E' possibile indicizzare gli elementi di $A$ utilizzando gli elementi di $I$, cosi', se $i \in I$, $a_i \in A$ e' l'elemento $i$-esimo di $A$. L'insieme $I$ viene chiamato \emph{insieme degli indici}. \\ Ad esempio, indicizziamo l'insieme $\mathbb{L}$ con l'insieme $I=\mathbb{N}$, \label{ex:indexset1} \begin{align*} &I=\mathbb{N}\\ &\mathbb{L}=\left\{ \textrm{C, Perl, TCL, Awk, Python, Bash, Lisp} \right\} \end{align*} e otteniamo: \begin{align*} &l_0=\textrm{C}\\ &l_1=\textrm{Perl}\\ &l_2=\textrm{TCL}\\ &\vdots\\ &l_6=\textrm{Lisp} \end{align*} \subsection{Famiglia} \label{sec:familyset} Una famiglia e' costituita da due insiemi: l'insieme degli indici $I$ e l'insieme $A$. Ad ogni elemento di $A$ e' associato un indice $i \in I$. Una famiglia e' indicata come $\left\{ A_i \right\}_{i \in I}$, dove $I$ e' l'insieme degli indici, e $A_{i}$ e' l'elemento della famiglia associato a $i$. \\ Riprendendo il precedente esempio (\ref{ex:indexset1}), possiamo scrivere: \[ \left\{ L_i \right\}_{i\in \mathbb{N}} \] \subsubsection{Notazioni indicizzate} \label{sec:indexednotation} Gli indici vengono anche usati per abbreviare e semplificare la scrittura di proposizioni matematiche. Ad esempio: per indicare l'intersezione di tutti gli elementi della famiglia $\left\{ A_i \right\}_{i \in I}$ possiamo scrivere: \begin{equation*} A_1 \cap A_2 \cap A_{\dots} \cap A_n = \{ x | x \in A_1, x \in A_2, x \in A_{\dots}, x \in A_{n}\} \end{equation*} Oppure, possiamo scrivere in forma abbreviata: \begin{equation*} \bigcap_{i \in I} A_i = \left\{ x | x \in A_i, \forall i \in I \right\} \end{equation*} \subsection{Unione} \label{sec:unionset} L'unione di $A$ con $B$ viene indicata con $A \cup B$, ed e' definita come: \[ A \cup B = \{ x | x \in A \lor x \in B \} \] \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{fig/Venn_A_union_B} \end{center} \caption{Unione di A e B} \label{fig:venn_union} \end{figure} Nell'algebra booleana, l'unione corrisponde all'operazione logica $\mbox{OR}$. \oldsubsubsection{Proprieta'} \begin{enumerate} \item $A \cup \emptyset = A$ \item $A \cup A = A \quad$ (proprieta' riflessiva) \item $A \cup B = B \cup A \quad$ (proprieta' commutativa) \item $A \cup (B \cup C) = (A \cup B) \cup C \quad$ (proprieta' associativa) \item $B \subseteq A \quad \Leftrightarrow \quad B \cup A = A$ \end{enumerate} \subsection{Unione e intersezione} \label{sec:union_and_intersection} Ecco alcune identita' che fanno uso sia dell'intersezione (\ref{sec:intersectset}) che dell'unione (\ref{sec:unionset}): \begin{enumerate} \item $A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \qquad$ (proprieta' distributiva dell'intersezione rispetto all'unione). \item $A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \qquad$ (proprieta' distributiva dell'unione rispetto all'intersezione). \end{enumerate} \subsection{Differenza} \label{sec:differenceset} La differenza ``$B$ meno $A$'' si indica con $B \setminus A$, e viene definita come: \[ B \setminus A = \{ x | \forall x \in B, x \notin A \} \] \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{fig/B_minus_A} \end{center} \caption{Differenza tra B ed A} \label{fig:venn_B_minus_A} \end{figure} \oldsubsubsection{Proprieta'} \begin{enumerate} \item $A \setminus \emptyset = A$ \item $A \setminus \emptyset = \emptyset$ \item $B \subseteq A \quad \Rightarrow \quad B \setminus A = \emptyset$ \item \textbf{Leggi di De Morgan}: \\ \begin{align*} &A \setminus (B \cup C) \quad \Leftrightarrow \quad (A \setminus B) \cap (A \setminus C)\\ &A \setminus (B \cap C) \quad \Leftrightarrow \quad (A \setminus B) \cup (A \setminus C) \end{align*} \begin{proof} Dimostriamo il primo caso.\\ Per la definizione di differenza: \[ A \setminus (B \cup C) = \{ x | x\in A, x \notin (B \cup C)\} \] Per la definizione di unione: \[ x \notin (B \cup C) \Rightarrow (x \notin B) \land (x \notin C) \qquad \textrm{[1]}\] Dato che $(x \notin B)$ e che $(x\in A)$, sempre per la definizione di differenza possiamo scrivere: \[ (x \notin B, (x\in A) \Rightarrow\; x\in(A \setminus B) \] Lo stesso vale per $A$ e $C$: \[ (x \notin C), (x\in A) \Rightarrow \;x\in(A \setminus C) \] Possiamo quindi riscrivere la [1]: \[ x \notin (B \cup C) \Rightarrow (x \notin B) \land (x \notin C) \Rightarrow x\in (A \setminus B) \land (A \setminus C) \Rightarrow x\in(A \setminus B) \cap (A \setminus C)\] In conclusione: \[ A \setminus (B \cup C) = \{ x | x\in A, x \notin (B \cup C)\} = (A \setminus B) \cap (A \setminus C)\] \end{proof} \item Siano $A,B\(\Omega $, con $A^c$ indichiamo $\Omega \-A$, allora si ha \eal{&A\^B^c=A\-B=A\-(A\^B) } \end{enumerate} \subsection{Differenza simmetrica} \label{sec:symmetric_difference_set} La differenza simmetrica corrisponde all'operazione $XOR$ nell'algebra booleana e si indica con il simbolo $\bigtriangleup$. \[ A \Delta B = \{ x | (x \in A \lor x \in B) \land \overline{(x \in A \land x \in B)} \} = \{x : (x \in A) \mbox{ XOR } (x \in B)\} \] Ovvero, $x$ appartiene o ad $A$ o a $B$, ma mai a entrambi. \begin{figure}[h] \begin{center} \includegraphics{fig/Sym_complement} \end{center} \caption{Differenza simmetrica} \label{fig:sym_complement} \end{figure} \oldsubsubsection{Proprieta'} \begin{enumerate} \item $A \Delta B = B \Delta A\quad$ (proprieta' commutativa) \item $(A \Delta B) \Delta C = A \Delta (B \Delta C)\quad$ (proprieta' associativa) \item $A \Delta A = \emptyset$ \item $A \Delta \emptyset = A$ \item $A \Delta B = (A \setminus B) \cup (B \setminus A)\,$ \item $A \Delta B = (A \cup B) \setminus (A \cap B)$ \item $A \cap (B \Delta C) = (A \cap B) \Delta (A \cap C)$ (proprieta' distributiva dell'intersezione sulla differenza simmetrica) \end{enumerate} \subsection{Unione disgiunta (o somma disgiunta)} \label{sec:disjoint_union_set} \label{sec:disjoint_sum_set} Dati due insiemi A e B, la loro somma disgiunta equivale all'insieme delle coppie formate da un simbolo che denota l'appartenenza ad A oppure a B e l'elemento dell'insieme. L'unione disgiunta si indica con il simbolo $\oplus$. Nota: la scrittura $(a,b)$ indica una coppia ordinata di due elementi $a$ e $b$. \[ A \oplus B = \{ (0,a) | \forall a \in A \} \cup \{ (1,b) | \forall b \in B \} \] O usando il prodotto cartesiano (vedi \ref{sec:product_set}) \[ A \oplus B = ( A \times \{0\}) \cup (B \times \{1\}) \] \subsection{Partizione di A} \label{sec:partition_rel} Una partizione di un insieme $X$ e' un insieme $P$ di sottoinsiemi di $X$ tale che \eal{&0.\;\;a\in P \> a\( X\\ &1.\;\;a,b\in P:\;a \neq b\;\;\>a\cap b \neq \emptyset\\ &2.\;\;\bigcup_{a\in P} a = X} ovvero, due elementi distinti di $P$ sono due sottoinsiemi disgiunti di $X$, e l'unione di tutti gli elementi di $P$ e' proprio $X$.\\ \subsection{Prodotto cartesiano} \label{sec:product_set} Il prodotto cartesiano dei due insiemi A e B si definisce come: \[ A \times B = \{ (a,b) | a \in A, b \in B \} \] Dove, $(a,b)$ indica una coppia ordinata di due elementi $a$ e $b$. \\ Il piano cartesiano e' un prodotto cartesiano $R \times R$: \[ \mathbb{R}^2 = \mathbb{R} \times \mathbb{R} = \{ (x,y) | \forall x,y \in \mathbb{R} \} \] % % Funzioni % \section{Funzioni} \subsection{Funzione (applicazione)} \def\*{{\times}} \label{sec:function} \label{sec:map} \[ f: X \rightarrow Y \] La funzione $f$ e' un sottoinsieme di $X\* Y$, tale che \eal{&f\( X\*Y\\ &\forall x\in X\;\;\exists!\;y\in Y:\;(x,y)\in f } Ovvero, la funzione $f: X \rightarrow Y$ e' un sottoinsieme del prodotto cartesiano $X\times Y$ tale che per ogni $x\in X$ esiste uno ed un solo elemento $y \in Y$, tale che $(x,y)\in f$.\\ In altre parole, possiamo pensare $f$ come una legge che associa associa ad ogni elemento di $X$, uno e un solo elemento di $Y$. \subsubsection{Dominio e Codominio} \label{sec:dominio} \label{sec:codominio} \label{sec:domain} \label{sec:codomain} L'insieme $X$ viene chiamato \emph{dominio} della funzione $f$, mentre l'insieme $Y$ \emph{codominio}. \subsubsection{Immagine e Controimmagine} \label{sec:immagine} \label{sec:controimmagine} \label{sec:image} \label{sec:preimage} L'immagine della funzione $f$ e' l'insieme: \[ Im(f) = f(X) = \Im f = \{y \in Y : \exists x \in X : f(x)=y\} \] Ovvero, e' quell'sottoinsieme del codominio ai cui elementi corrisponde sempre almeno un elemento del dominio. L'immagine di f si indica con $Im(f), f(X), \Im f$.\\ \begin{figure}[t] \begin{center} \includegraphics[scale=0.3]{fig/Funcoes_x2} \end{center} \caption{L'immagine della funzione e' quella parte tratteggiata che si trova all'interno del'insieme CD (codominio)} \label{fig:immagine_funzione} \end{figure} La controimmagine della funzione $f$ e' l'insieme: \[ f^{-1}(X) = \{x \in X: f(x) \in Y \} \] Ovvero, e' quel sottinsieme del dominio, i cui elementi hanno tutti un corrispondente nel codominio. \newline L'immagine di un insieme $A\subseteq X$ si indica con $f(A)$ ed e': \[ f(A)= \{ f(a)\;|\;a\in A\} \] La controimmagine di un insieme $B\subseteq Y$ e': \[ f^{-1}(B)=\{ x\in X\;|\;f(x)\in B\} \] \oldsubsubsection{Proprieta'} \label{propimmagineecontroimmagine} \begin{enumerate} \item $f(A\cup B)=f(A)\cup f(B)$ \item $f(A\cap B)\subseteq f(A)\cap f(B)$\\ Se e' iniettiva vale l'uguaglianza. \item $f(f^{-1}(V))\subseteq V$ \begin{prova} \pf \begin{align*} &z\in f(f^{-1}(V))= f(\{ x\in X\;|\;f(x)\in V\}\})= \{f(x)\;|\;x\in X,\;f(x)\in V\}= \{f(x)\in V\;|x\in X\}\\ &\;\Rightarrow\; z=f(x)\in V \end{align*} \end{prova} Se e' surriettiva vale l'uguaglianza. \item $V\( f^{-1}(f(V))$ \begin{prova} \pf \eal{&v\in V \> f(v)\in f(V) \> v\in f^{-1}(f(V)) } \end{prova} Se e' iniettiva vale l'uguaglianza. \begin{prova} \pf \eal{&v\in f^{-1}(f(V)) \= f(v) \in f(V) \= f(v)=f(\ubrace{\ove v}{\in V}) \ubrace{\>}{f \T{ iniettiva } } v=\ove v\in V } \end{prova} \item $f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$ \begin{prova} \pf \begin{align*} &z\in f^{-1}(A\cap B)\;\Leftrightarrow \;f(z)\in A\cap B\;\Leftrightarrow \;f(z)\in A\;\land \;f(z)\in B\;\Leftrightarrow \;z\in f^{-1}(A)\;\land \;z\in f^{-1}(B) \end{align*} \end{prova} \item $f^{-1}(A\cup B)=f^{-1}(A)\cup f^{-1}(B)$ \item \label{propfunzAeqBfiniettiva} Data $f:A\longrightarrow B$ iniettiva, se $|A|=|B|$, e $A,B$ sono finiti, allora $f$ e' anche surriettiva. \begin{prova} \pf Supponiamo per assurdo che $\Im f \neq B$, cioe' che $\Im f \subset B$. Poiche' stiamo lavorando su insiemi finiti, $|\Im f|< |B|$. Allora, \eal{&|\Im f| < |B|=|A| } ma questo e' assurdo, perche' $f$ e' iniettiva. Infatti, essendo $f$ iniettiva, \eal{\forall b\in \Im f\;\;\exists ! a\in A:\;\;f(a)=b} e d'altronde per definizione di funzione, \eal{&\forall a\in A \exists!b\in \Im f:\;f(a)=b} quindi $|\Im f|=|A|$. \end{prova} \end{enumerate} \subsection{Unione di funzioni} \begin{prop} Siano date due funzioni $f:A\longrightarrow B,\;\;g:A'\longrightarrow B'$. Si ha che \eal{&f(x)=g(x)\;\;\forall x\in A\^ A' \> h=f\cup g \T{ e' una funzione. } } E piu' precisamente, la legge di $h$ e' \eal{&h(x) = \sist{f(x) & x\in A\\ g(x)&x\in A'}\\ &h: A\cup A' \longrightarrow B\cup B' } ovvero, $h(x)=f(x)$ se $x\in A$, altrimenti se $x\in A'$ si ha $h(x)=g(x)$. \end{prop} \begin{proof} Per definizione, $f\( A\times B,\;\;g\( A'\times B'$. Quindi, ha senso considerare la loro unione: \eal{&h=f\cup g \( A\times B \cup A'\times B' \( A\cup A'\times B\cup B'}. Inoltre, poiche' $f(x)=g(x)\;\;\forall x\in A\^A'$, e per l'unicita' di $f(x)$ e $g(x)$, si ha che \eal{&\forall x\in A\cup A'\;\;\exists ! y\in B\cup B':\;\;(x,y)\in h } quindi $h$ e' una funzione a tutti gli effetti, che puo' anche essere descritta dalla seguente legge: \eal{&h(x) = \sist{f(x) & x\in A\\ g(x)&x\in A'} } \end{proof} \subsection{Funzione surriettiva} \label{sec:surjective} In una funzione surriettiva il codominio coincide con la sua immagine. Formalmente possiamo scrivere: \[ f: X \rightarrow Y \textrm{e' surriettiva} \quad \Leftrightarrow \quad \forall y \in Y, \exists x \in X | f(x) = y \] Una funzione surriettiva da $A$ in $B$ si indica con: \[ f: A \mapsto B \] Per dimostrare che una funzione e' surriettiva basta provare che $\forall y \in Y, \exists x \in X | f(x) = y$ \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{fig/Non-injective_and_surjective} \end{center} \caption{Funzione surriettiva e non iniettiva} \label{fig:Non-injective_and_surjective} \end{figure} \subsection{Funzione iniettiva} \label{sec:injective} In una funzione iniettiva, a un elemento dell'immagine corrisponde uno e un solo elemento del dominio. Formalmente possiamo scrivere: \[ f: X \rightarrow Y \textrm{e' iniettiva}\quad \Leftrightarrow \quad \forall x_1, x_2 \in X, x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2) \] oppure \[ f: X \rightarrow Y \textrm{e' iniettiva}\quad \Leftrightarrow \quad \forall x_1, x_2 \in X,f(x_1)=f(x_2) \Rightarrow x_1=x_2 \] Una funzione iniettiva da $A$ in $B$ si indica con: \[ f: A \hookrightarrow B \] Per dimostrare che una funzione e' iniettiva basta provare $f(x)=f(y) \Rightarrow x=y$ \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{fig/Injective_and_non-surjective} \end{center} \caption{Funzione iniettiva e non surriettiva} \label{fig:Injective_and_non-surjective} \end{figure} \subsection{Funzione biettiva} \label{sec:bijective} Una funzione e' biettiva quando e' sia inniettiva che surriettiva. Una funzione biettiva da $A$ in $B$ si indica con: \[ f: A \leftrightarrow B \] \subsection{Composizione di funzioni} \label{sec:func_composition} Date due funzioni $f: X \rightarrow Y$ e $g: Y \rightarrow Z$, possiamo \emph{comporle} in un unica funzione $g \circ f: X \rightarrow Z$, ponendo $(g \circ f(x)) = g(f(x)) \forall x \in X$. \oldsubsubsection{Proprieta'} \begin{enumerate} \item La composizione di funzioni non gode della proprieta' commutativa, infatti, quasi sempre e' vero che $(g \circ f) \neq f \circ g$. \item $g \circ (f \circ h) = (g \circ f) \circ h \quad$ (proprieta' associativa) \item Se $f$ e $g$ sono iniettive, la loro composizione e' iniettiva. \item Se $f$ e $g$ sono surriettive, la loro composizione e' surriettiva. \item Se $f$ e $g$ sono biettive, la loro composizione e' biettiva. \item Se $f \circ g$ e' surriettiva, $f$ e' sicuramente surriettiva, ma $g$ puo' non esserlo. \item Se $f \circ g$ e' iniettiva, $g$ e' sicuramente iniettiva, ma $f$ puo' non esserlo. \item Se $f \circ g$ e' biettiva, possiamo dedurre che $g$ e' iniettiva e $f$ e' surriettiva. \end{enumerate} \begin{figure}[h] \begin{center} \includegraphics{fig/Compfun} \end{center} \caption{Composizione di due funzioni} \label{fig:func_composition} \end{figure} \subsection{Funzione inversa} \label{sec:inverse_func} La funzione inversa della funzione $f$, e' indicata con $f^{-1}$, e corrisponde a quella funzione che associa a ogni elemento del codominio di $f$ l'elemento corrispondente del dominio. La funzione inversa esiste se e solo se $f$ e' biettiva. \[ f(f^{-1}(y))=y, \quad \forall y \in Y \] \[ f^{-1}(f(x))=x, \quad \forall x \in X \] \oldsubsubsection{Proprieta'} \begin{enumerate} \item $(f \circ g)^{-1} = g^{-1} \circ f^{-1}$ \item $f^{-1} \circ f: X \rightarrow X \quad$. Identita' assoluta in X, che si indica con: $f^{-1} \circ f=i_X$ \item $f \circ f^{-1}: Y \rightarrow Y \quad$. Identita' assoluta in Y, che si indica con: $f \circ f^{-1}=i_Y$. \item Data la funzione $f: A\rightarrow B$ \[ \exists g:B\rightarrow A \T{ tale che } f\circ g = i_B\;\Leftrightarrow \; f\equiv\textrm{surriettiva}\] \begin{prova} \step{}{Dim $\Rightarrow $} \begin{prova} Sia $b\in B$, vogliamo dimostrare che $\exists a\in A:\;f(a)=b$.\\ Sia allora $a=g(b)$, \eal{ &f(a)=f(g(b))=(f\circ g)(b)=i_B(b)=b } \end{prova} \step{}{Dim $\Leftarrow $} \begin{prova} Sia $b\in B$. Poiche' $f$ e' surriettiva, $\exists a\in A:\;f(a)=b$ allora poniamo $g(b):=a$. Abbiamo cosi' creato la funzione $g$, e inoltre: \[ f(g(b))=b\;\;\forall b\in B \] \end{prova} \qed \end{prova} Se, invece, $g\circ f = i_A$, allora: \[ \exists g:B\rightarrow A \T{ tale che } g\circ f = i_A\;\Leftrightarrow \;f\equiv\textrm{iniettiva} \] Se sono entrambi vere, allora $f$ e' biettiva. \end{enumerate} \subsection{Insieme di tutte le applicazioni A$\rightarrow$B} \label{sec:B^A_func} Consideriamo un dominio $A$ e un codominio $B$. Indichiamo con $B^{A}$ l'insieme di tutte le funzioni $A \rightarrow B$. \[ B^A = \{ \mbox{ insieme di tutte le funzioni }\, A \rightarrow B \} \] possiamo anche scrivere: \[ B^A = hom(A,B) \] \subsubsection{Numero di funzioni} Se $A,B$ sono finiti, possiamo contare esattamente quante funzioni esistono: sia $A=\pgra{a_1,a_2,\dots,a_m}, B=\pgra{b_1,b_2,\dots,b_n}$, \begin{enumerate} \item Il numero di funzioni iniettive e': \eal{&\binom{n}{m}m! = \frac{n!}{(n-m)!} } che e' il numero di disposizioni semplici di $n$ oggetti in classi di $m$ oggetti.\\ Si deve anche avere che $m\le n$, altrimenti non ci sarebbero funzioni iniettive. \begin{prova} \pf Poiche' le funzioni sono iniettive, ogni $f$ assegna a un a elementi distinti di $A$ elementi distinti di $B$.\\ Quindi la $m$-upla $({a_1,a_2,\dots,a_m})$, che contiene tutti gli elementi (distinti) di $A$ viene associata a una $m$-upla di elementi distinti $B$.\\ % \eal{ % &({a_1,a_2,\dots,a_m}) \longrightarrow (b_1,b_2,\dots,b_m)\\ % &({a_1,a_2,\dots,a_m}) \longrightarrow (b_2,b_3,\dots,b_{m+1})\\ % &\vdots % &({a_1,a_2,\dots,a_m}) \longrightarrow (b_6,b_3,\dots,b_{m+1})\\ % } Tutte le possibili $m$-uple di elementi distinti $B$ sono in numero \eal{&\binom{n}{m}} che e' il numero di combinazioni semplici di $n$ oggetti in classi di $m$ oggetti.\\ Fissiamo una associazione $f$ tra queste che abbiamo gia' considerato: \eal{({a_1,a_2,\dots,a_m})\longrightarrow (f(a_1),f(a_2),\dots,f(a_m))} e' chiaro che da questa associazione, possiamo creare quelle del tipo $\alpha \longrightarrow (f(a_1),f(a_2),\dots,f(a_m))$, dove $\alpha$ e' una qualsiasi $m$-upla che e' una permutazione di $({a_1,a_2,\dots,a_m})$. Tutte le possibili permutazioni di $m$ oggetti sono in numero $m!$.\\ Quindi per ogni associazione di prima, abbiamo altre $m!$ associazioni.\\ Il totale e' percio': \eal{&\binom{n}{m}m! } \end{prova} \item Il numero di funzioni biettive e' $n!$. Dove $m=n$. \begin{prova} \pf Se per assurdo $mn$, allora non si avrebbero funzioni iniettive. Allora $m=n$.\\ Basta utilizzare la formula del numero di funzioni iniettive: \eal{&\binom{n}{m}m ! = \binom{n}{n}n! = \frac{n!}{n!(n-n)!}n! = n! } \end{prova} \item Il numero di funzioni surriettive $A\longrightarrow B$ e': \eal{&\sum_{k=0}^{n}(-1)^k\binom{n}{n-k}(n-k)^m} \end{enumerate} \subsection{Funzione caratteristica} \label{sec:characteristic_func} La funzione caratteristica, applicata a un insieme $B$, associa $1$ ad ogni elemento del dominio che e' contenuto in $B$, e a tutti gli altri elementi associa $0$. \[ \varphi_{B} (x) = \begin{cases} 1, & x \in B; \\ 0, & x \not \in B. \end{cases} \] \subsection{Operazione binaria interna} \label{sec:binary_op} Un'operazione binaria interna su $A$ e' un'applicazione: \[ S:A\times A \rightarrow A \] Ovvero $s((a,b)) \in A, \quad \forall (a,b) \in A\times A$. % % Relazioni % \section{Relazioni} \label{sec:relation} \subsection{Relazione binaria} \label{sec:binary_rel} Una \emph{relazione binaria} su $A$ e $B$ e' un qualsiasi sottoinsieme di $A \times B$. Per indicare che la coppia $(x,y)$ appartiene alla relazione, e che quindi $x$ e $y$ sono in relazione, si puo' usare una delle seguenti scritture: \begin{align*} &(x,y) \in R\\ &x \stackrel{R}{\sim} y\\ &x \stackrel{R}{\equiv} y \end{align*} \subsubsection{Esempio} \begin{align*} &R \subseteq N \times N \\ &R = \{ x | x \mbox{ divide } y \quad (y \mbox{ e' multiplo di } x) \}\\ &(5,10) \in R\\ &(5,7) \notin R \end{align*} \subsection{Relazione binaria interna} \label{sec:internal_binary_rel} Una relazione su A e' interna quando \[ R \subseteq A \times A \] \subsection{Relazione binaria diagonale} \label{sec:diagonal_binary_rel} Una relazione binaria diagonale e' definita come: \begin{align*} &R \subseteq A \times A\\ &R = {\Delta}_{A} = \{ (a,a) \forall a \in A \} \end{align*} \subsection{Relazione binaria inversa} \label{sec:inverse_binary_rel} La relazione binaria inversa di una relazione $R$ e' semplicemente la relazione $R$ con le coppie invertite: \[ R^{-1} = \{ (x,y) | (y,z) \in R \} \] \subsubsection{Esempio} \[ (1,0) \in R \quad \Leftrightarrow \quad (0,1) \in R^{-1} \] \subsection{Composizione tra relazioni binarie interne} \label{sec:composition_binary_rel} Possiamo anche comporre due o piu' relazioni: \begin{align*} &R,S \subset A \times A \\ &R \circ S = \{ (x,y) | \exists z \in A | (x,z) \in R \land (z,y) \in S \} \end{align*} \subsubsection{Esempio} \begin{align*} &R,S \subset A \times A, \quad A = \mathbb{N} \\ &R = \{ (5,7), (3,2), (2,1), (10,20) \} \\ &S = \{ (20,1), (2,4), (5,7) \} \\ &R \circ S = \{ (3,4), (10,1) \} \\ &S \circ R = \emptyset \end{align*} \subsection{Relazione binaria interna riflessiva} \label{sec:riflessive_binary_rel} $R \subseteq A \times A$ e' riflessiva se $\forall a \in A \quad \Rightarrow \quad a \stackrel{R}{\sim} a$, ovvero, quando ogni elemento $a \in A$ e' relazione con se stesso. Possiamo anche esprimere lo stesso concetto usando la relazione diagonale (vedi \ref{sec:diagonal_binary_rel}): \[ \Delta_{A} \in R \] \subsection{Relazione binaria interna simmetrica} \label{sec:sym_binary_rel} $R \subseteq A \times A$ e' simmetrica se $a \stackrel{R}{\sim} b$ e $b \stackrel{R}{\sim} a$, ovvero $(a,b) \in R$ e $(b,a) \in R$. Possiamo anche dire la stessa cosa scrivendo: \[ R = R^{-1} \] \subsection{Relazione binaria interna antisimmetrica} \label{sec:asym_binary_rel} $R \subseteq A \times A$ e' antisimmetrica se \[ a \stackrel{R}{\sim} b,\quad b \stackrel{R}{\sim} a \quad \Rightarrow a = b \] Ovvero, quando possiamo dedurre che $a$ sia uguale a $b$ dal fatto che $a$ e $b$ siano in relazione simmetricamente. \subsubsection{Esempio} \begin{align*} &x \stackrel{R}{\sim} y \quad \mbox{se} \quad y=mx,\quad \forall m\in R\\ &y=mx, \qquad x=ny\\ &x=nmx \qquad \Rightarrow \quad mn=1 \quad \Rightarrow x=x \end{align*} \subsection{Relazione binaria interna transitiva} \label{sec:trans_binary_rel} $R \subseteq A \times A$ e' transitiva se \[ a \stackrel{R}{\sim} \underline{b},\quad \underline{b} \stackrel{R}{\sim} c \qquad \Rightarrow \qquad \stackrel{R}{\sim} c \] Possiamo anche definirla come quella relazione per cui vale \[ R \circ R \subseteq R \] \subsubsection{Esempio} \begin{align*} &x \stackrel{R}{\sim} y \quad \mbox{se} \quad y=mx,\quad \forall m\in R\\ &y=mx, \qquad z=ny\\ &z=nmx \qquad \Rightarrow \quad z \stackrel{R}{\sim} x \end{align*} Nell'ultima parte abbiamo visto che poiche' $z=nmx$, allora $z$ e' in relazione con $x$. \section{Relazioni di equivalenza} \label{sec:rel_equ_ord} Le relazioni che godono della proprieta' riflessiva (\ref{sec:riflessive_binary_rel}), simmetrica (\ref{sec:sym_binary_rel}) e transitiva (\ref{sec:trans_binary_rel}), si chiamano \emph{relazioni di equivalenza}. \subsection{Classe d'equivalenza} \label{sec:class_equ} Consideriamo un insieme $A$ e sia $R\( A\times A$ una relazione d'equivalenza su $A$.\\ La classe d'equivalenza dell'elemento $a\in A$ e' definita come: \[ [a] = \{ x \in A | x \stackrel{R}{\sim} a \} \] Ovvero e' quel sottoinsieme di $A$, che contiene tutti gli elementi che sono in relazione con $a$.\\ \label{sec:quotient_set_rel} Definiamo l'insieme quoziente di $A$ su $R$ come: \eal{&A/_R = \pgra{[a]_R\;|\;a\in A}} ovvero, l'insieme di tutte le classi d'equivalenza indotte da $R$. \oldsubsubsection{Proprieta'} \begin{enumerate} \item Certamente possiamo dire che $[a] \neq \emptyset$, poiche' in $[a]$ esiste almeno $a$ che e' in relazione con se stesso ($a \stackrel{R}{\sim} a$) per la proprieta' riflessiva della relazione d'equivalenza. \item Due classi d'equivalenza distinte tra loro sono disgiunte: \begin{align*} &[a] \neq [b] \Rightarrow [a]\cap [b] =\emptyset \end{align*} \begin{proof} Supponiamo per assurdo che \[ [a] \cap [b] \neq \emptyset \] da questo segue che: \eal{&\exists c\in[a],[b] \= c\sim a,\;c\sim b \= a\sim c,c \sim b \> a\sim b\\ &a\sim b \> [a]=[b]} assurdo. \end{proof} \item ${\bigcup}_{a\in A}[a] = A\qquad$ (L'unione di tutte le classi di equivalenza che appartengono ad $A$ formano lo stesso insieme $A$. \begin{prova} \pf \step{}{Dim $\($} \begin{prova} \eal{&b\in {\bigcup}_{a\in A}[a] \> \exists a\in A:\;b\in [a] \( A \> b\in A } \end{prova} \step{}{Dim $\)$} \begin{prova} \eal{&b\in A \> b\in [b]\({\bigcup}_{a\in A}[a] } \end{prova} \qed \end{prova} \item Grazie alle precedenti tre proprieta' possiamo dire che $A/_R$ e' una partizione di $A$. (vedi \ref{sec:partition_rel})\\ \item La partizione $P$ di $A$ induce la seguente relazione di equivalenza: \eal{&x\sim y \= \exists p \in P:\;x,y\in p} si vede facilmente che e' una relazione di equivalenza. \begin{prova} \pf \step{}{$x\sim x$} \begin{prova} \eal{&x\sim x \= \exists p\in P:x \in p} e questo e' vero perche' \eal{&x\in A=\bigcup_{p\in P} p} \end{prova} \step{}{$x\sim y\> y\sim x$} \begin{prova} \eal{&x\sim y \= \exists p \in P:\;x,y\in p \= y\sim x} \end{prova} \step{}{$x\sim y,\;y\sim z\> x\sim z$} \begin{prova} \eal{&x\sim y \= \exists p \in P:\;x,y\in p\\ &y\sim z \= \exists p' \in P:\in y,z'\in p'\\ &y\in p,\;y\in p' \> p\^p' \neq \emptyset} ma poiche' gli elemti di $X$ sono a due a due disgiunti, segue che $p=p'$ e quindi \eal{&x,y,z\in p \> x\sim z} \end{prova} \end{prova} \end{enumerate} % % Relazione di ordine % \section{Relazioni di ordine} \label{sec:rel_ord} Le relazioni che godono della proprieta' riflessiva (\ref{sec:riflessive_binary_rel}), antisimmetrica (\ref{sec:asym_binary_rel}) e transitiva (\ref{sec:trans_binary_rel}), si chiamano \emph{relazioni di ordine}. Per dire che $a$ e' in relazione d'ordine con $b$, si scrive: $a \le b$. Nota che la relazione d'ordine $a \le b$ puo' anche indicare una relazione diversa da quella dell'usuale minore-uguale. \subsubsection*{Esempio} Diremo che $x \stackrel{R}{\sim} y$ se esiste un numero $z \in \mathbb{R}^{+}$ tale che $x+z=y$. In altre parole stiamo definiendo la relazione di minore-uguale ( $\le$ ). Dimostriamo che gode delle tre proprieta': \begin{description} \item[Riflessiva] Deve essere che $x \le x$, infatti: \[ x+0=x \] \item[Antisimmetrica] Dobbiamo verificare che $x\le y, \quad y\le x\quad \Leftrightarrow \quad x=y$: \begin{align*} &z_1, z_2 \in \mathbb{R}^{+}\\ &x+z_1 = y\\ &y+z_2 = x \end{align*} \[ x+z_1 = x-z_2\quad \Rightarrow \quad z_2 = z_1 = 0 \] Sostituendo $z_2$ e $z_1$, nelle prime equazioni otteniamo: $x=y$ e $y=x$. \item[Transitiva] Verifichiamo che $x\le y, y\le z \Rightarrow x\le z$: \begin{align*} &x+\alpha=y\\ &y+\beta=z\\ &x+\alpha=z-\beta\\ &x+(\alpha+\beta)=z \quad \Rightarrow \quad x\le z \end{align*} \end{description} \subsection{Insieme parzialmente ordinato} \label{sec:poset} Per indicare che su un insieme $A$ abbiamo fissato una relazione d'ordine $\le$, si scrive $(A, \le)$. Se sull'insieme $A$ e' stata fissata un relazione d'ordine, allora, e' un insieme \textbf{parzialmente ordinato}. In inglese si dice \emph{Partially ordered Set} (\textbf{poset}). \subsection{Insieme totalemente ordinato} \label{sec:total_poset} Un poset in cui due elementi sono sempre confrontabili ($a \le b$, oppure $b \le a$) si dice insieme totalmente ordinato (TOTET).\\ Un totet si dice anche \emph{catena}. \subsubsection{Esempio} Associamo in $R$ l'usuale rel. d'ordine minore-uguale: \[ (R, \le) \] Notiamo che se \[ x,y \in R \], allora o accade che: \[ x \le y \] oppure \[ y \le x \]. Quindi $(R, \le)$ e' un insieme totalemente ordinato. \subsection{Minimo} \label{sec:Minimo} Dato un poset $(A,\le)$, un elemento $m \in A$ si dice minimo se: \[ m \le x, \quad \forall x \in A \] \oldsubsubsection{Proprieta'} Se il minimo esiste, allora e' unico \begin{proof} Supponiamo per assurdo che esistano due minimi $m_1, m_2$, allora per la definizione di minimo deve accadere che: \[ m_1 \le m_2 \] e \[ m_2 \le m_1 \] Ma per la proprieta' antisimmetrica, otteniamo che \[ m_1 = m_2 \] \end{proof} \subsection{Insieme ben ordinato} \label{sec:well_ordered_set} Se ogni sottoinsieme di $A \neq \0$ possiede un minimo, allora $A$ si dira' \emph{insieme ben ordinato}. Se $A$ e' ben ordinato, segue che $A$ e' anche totalmente ordinato. (ma non sempre il viceversa). \begin{proof} Supponiamo che $A$ sia un insieme ben ordinato, e cnsideriamo il sottoinsieme \[\left\{ a,b \right\} \subseteq A, \quad \forall a,b \in A \]. Allora, dato che per definizione questo ogni sottoinsieme di $A$ deve avere un minimo, sara' che o $a \le b$ oppure $b \le a$. Si puo' ripetere questo ragionamento per ogni sottoinsieme di $A$, quindi $A$ e' un insieme totalmente ordinato. \end{proof} \subsection{Massimo} \label{sec:Massimo} Dato un poset $(A,\le)$, un elemento $M \in A$ si dice massimo se: \[ M \ge x, \quad \forall x \in A \] Ovvero: \[ x \le M, \quad \forall x \in A \] \oldsubsubsection{Proprieta'} Se il massimo esiste, allora e' unico. \subsection{Minimale} Un elemento $a \in A$ di un poset $(A, \le)$ si dice \textbf{minimale} se $\forall x\in A$ risulta \[ x \le a \, \Leftrightarrow x=a \] Ovvero, oltra ad $a$, elementi ``piu' piccoli'' non ce ne sono. Od anche: se $x$ e' l'unico elemento di $A$ tale che $x\le a$, allora $x$ e' $a$ stesso. \oldsubsubsection{Proprieta'} Il minimo di un poset, e' l'unico minimale del poset stesso. \subsubsection{Esempio} \[ A=\left\{ 5,6,10,11,12,49 \right\} \] Definiamo il seguente poset: \[ (A, /) \] dove $/$ e' la relazione di divisibilita' ($a \sim b$ se $\exists n\in \mathbb{N}^{*} | an=b$). Nel poset definito i minimali sono: $5,6,11,49$. Infatti, considerando il $5$, la relazione $x / 5$ vale solo per $5 / 5$, quindi $5$ e' un elemento minimale. \subsection{Massimale} Un elemento $a \in A$ di un poset $(A, \le)$ si dice \textbf{massimale} se $\forall x \in A$ risulta: \[ a \le x \, \Leftrightarrow x=a \] Ovvero, oltra ad $a$, elementi ``piu' grandi'' non ce ne sono. Od anche: se $x$ e' l'unico elemento di $A$ tale che $a\le x$, allora $x$ e' $a$ stesso. \oldsubsubsection{Proprieta'} Il massimo di un poset, e' l'unico massimale del poset stesso. \subsubsection{Esempio} \[ A=\left\{ 5,6,10,11,12,49 \right\} \] Definiamo il seguente poset: \[ (A, /) \] Nel poset definito i massimali sono: $10,11,12,49$. Infatti, considerando il $10$, la relazione $10 / x$ vale solo per $10 / 10$, quindi $10$ e' un elemento massimale. \subsection{Minorante} Consideriamo un insieme $A$ e un suo sottoinsieme $B \subseteq A$. Fissiamo in $A$ una relazione d'ordine: \[ (A, \le) \] In $B$, possiamo fissare la stessa rel. d'ordine \[ (B, \le) \] \\ Un elemento $l \in A$ si dice \textbf{minorante} di $B$ se : \[ l \le b, \quad \forall b \in B \] \subsubsection{Esempio} \[ A = (\mathbb{N}^{*}, /) \] \[ B = \left\{ 20, 24,28,36 \right\} \] I minoranti di $B$ sono: $1,2,4$. \subsection{Maggiorante} Consideriamo un insieme $A$ e un suo sottoinsieme $B \subseteq A$. Fissiamo in $A$ una relazione d'ordine: \[ (A, \le) \] In $B$, possiamo fissare la stessa rel. d'ordine \[ (B, \le) \] \\ Un elemento $L \in A$ si dice \textbf{maggiorante} di $B$ se : \[ b \le L, \quad \forall b \in B \] \subsubsection{Esempio} \[ A = (\mathbb{N}^{*}, /) \] \[ B = \left\{ 20,24,28,36 \right\} \] I maggioranti di $B$ sono: $2520,2520*2,2520*3,\dots$. Ovvero tutti i multipli del minimo comune multiplo dei numeri in $B$. \subsection{Estremo inferiore} Consideriamo un insieme $A$ e un suo sottoinsieme $B \subseteq A$. Fissiamo in $A$ una relazione d'ordine: \[ (A, \le) \] In $B$, possiamo fissare la stessa rel. d'ordine \[ (B, \le) \] Chiamiamo \emph{Min} l'insieme di tutti i minoranti di $B$ in $A$. Sappiamo che $\mbox{Min} \in A$. \\ Si dice \textbf{estremo inferiore} di $B$ in $A$, il massimo dei suoi minoranti e si indica con $\inf B$ \subsubsection{Esempio} \[ A = (\mathbb{N}^{*}, /) \] \[ B = \left\{ 20,24,28,36 \right\} \] I minoranti di $B$ sono: $1,2,4$. L'estremo inferiore di B in A e' 4 (ma non perche' 4 e' maggiore di 2 e di 1, ma perche' 1 divide 4 e 2 divide 4 e quindi 4, secondo la definizione e' il massimo dell'insieme $\{1,2,4\}$). \subsection{Estremo superiore} Si dice \textbf{estremo inferiore} di $B$ in $A$, il minimo dei suoi maggioranti e si indica con $\sup B$. \subsection{POSET completo} $(A,\le )$ e' un POSET completo $\=$ per ogni sottoinsieme $\0 \neq B\(A$ si ha $\exists \inf B,\;\exists \sup B$. \section{L'insieme $\mathbb{N}$} \label{sec:N} \subsection{Assiomatizzazione di Peano} \label{sec:peano} \def\nz{{\mathbf{0}}} \begin{defn} Consideriamo un insieme $N$ che goda delle seguenti proprieta': \begin{enumerate} \item Esiste la seguente applicazione iniettiva: \[ s: N \rightarrow N \] Chiameremo l'immagine dell'elemento $n$ il successivo di $n$: $s(n)$ = \emph{successivo di n}. \item L'insieme $N \setminus Im(s)$ contiene un solo elemento. ($Im(s)$ e' l'immagine di $s$). Chiameremo quest'unico elemento $zero$ e lo indicheremo con $\nz$.\\ In altre parole, lo zero e' l'unico elemento che non e' il successivo di nessun altro elemento. \item \textbf{Principio (o assioma) di induzione}.\\ Per ogni sottoinsieme $U \subseteq N$ per cui valgono le seguenti proposizioni \begin{enumerate} \item $\nz \in U$ \item $u \in U \> s(u) \in U$ \end{enumerate} si ha che $U=N$ \end{enumerate} Un insieme $N$, con le suddette proprieta' si dira' ``insieme dei numeri naturali''. Nota: il principio di induzione e' un assioma perche' $N$ e' \emph{infinito}. Se $N$ fosse stato finito, allora non avremmo avuto alcun bisogno del principio di induzione. \end{defn} \begin{exemp} Non esiste un solo insieme di numeri naturali. Infatti, \begin{enumerate} \item L'insieme $\pgra{0,1,2,3,4,\dots}$ e' un insieme di numeri naturali. La funzione $s()$ e' quella standard: \eal{&1\mapsto 2 \mapsto 3 \mapsto \dots} E lo zero e' $\nz=0$. \item Anche l'insieme $\pgra{2,4,6,8,\dots}$ e' un insieme di numeri naturali. La funzione $s()$ e' \eal{&0,\mapsto 2\mapsto 4 \mapsto 6\mapsto } Lo zero e' $\nz=2$ \item Anche i seguenti insiemi sono insiemi naturali: \eal{&\pgra{5,6,7,\dots}\\ &\pgra{5,10,15,20,\dots} } \end{enumerate} \end{exemp} \begin{defn} Definiamo il seguente insieme: \eal{&\mathbb{N}=\pgra{0,1,2,3,\dots}} Come abbiamo visto prima $\mathbb{N}$ e' un insieme di numeri naturali. Da ora in poi, ``l'insieme dei numeri naturali'' sara' $\mathbb{N}$.\\ Nota: $0,1,2,\dots$ sono solo dei simboli. \end{defn} \subsection{Dimostrazione per induzione} \label{dimperinduzione} \begin{prop} Sia $N$ un qualsiasi insieme di numeri naturali, sia $\nz$ lo zero e $s()$ la funzione successivo, allora \eal{&\sist{P(\nz)\\ P(n) \> P(s(n))}\> P(n)\;\;\forall n\in N} In altre parole, per provare che una proposizione $P(n)$ e' vera $\forall n\in N$, si puo' procedere cosi': \begin{enumerate} \item Si dimostra $P(\nz)$ \item Si dimostra $P(n) \> P(s(n))$ \end{enumerate} ovvero \begin{enumerate} \item Dimostro che $P(\nz)$ e' vera \item Suppongo vera $P(n)$ \item Dimostro che $P(s(n))$ e' vera \item A questo punto possiamo affermare che $U = N$ \end{enumerate} \end{prop} \begin{proof} Consideriamo l'insieme \eal{&U=\pgra{n\;|\;P(n)\T{ e' vera}}} Per ipotesi: \eal{&P(\nz)\T{ vera } \> \nz\in U\\ &\pton{P(n) \> P(s(n)) }\=\pton{n\in U \> s(n)\in U}\\ &\sist{\nz\in U\\ n\in U \> s(n)\in U} \ubrace{\>}{\T{assioma di induzione}} U=N\\ &U=N \= \forall n\in N \;\;P(n)\T{ e' vera} } \end{proof} \begin{exemp} Sia $N=\mathbb{N}$, ovvero $N=\pgra{1,2,3,\dots}$. Dimostriamo che la somma dei primi $n$ numeri dispari e' pari a $n^2$. (Nota\footnote{in effetti, non abbiamo ancora definito la somma di numeri naturali, ne' i numeri pari o dispari. Per semplicita', in questo esempio, usiamo i concetti usuali.}) \end{exemp} \begin{proof} Ecco la prova. \begin{enumerate} \item Verifichiamo direttamente $P(1)$ e $P(2)$: \[ 1 = 1^2 \] \[ 1+3 = 2^2 \] \item Suppiamo che la seguente identita' sia vera: \[ 1+3+\cdots+(2n-1) = n^2 \] \item Dimostriamo che quest'ultima identita' e' vera anche per $n+1$: \begin{align*} &\underbrace{1+3+\cdots+(2n-1)}_{n^2}+(2(n+1)-1) = (n+1)^2\\ &n^2+(2(n+1)-1) = n^2+2n+1\\ &n^2+2n+1 = n^2+2n+1\\ &0 = 0 \end{align*} q.e.d \end{enumerate} \end{proof} \subsection{Principii di induzione} \begin{prop} Sia $N$ un insieme di numeri naturali, $\nz$ lo zero e $s()$ la funzione successivo. Allora, le seguenti proposizioni sono equivalenti: \eal{&1.\;\;\T{Induzione: }\forall U\( N\\ &\qq \sist{\nz\in U\\ n\in U\> s(n) \in U } \> U=N\\ &2.\;\;\T{Induzione forte: } \forall U\( N \\ &\qq \sist{\nz\in U\\ \pgra{k\in N\;|\;\nz\le k< n }\( U \> n\in U} \> U=N\\ &3.\;\;\T{Buon ordinamento di N:} \\ &\qq N\T{ e' un insieme ben ordinato secondo la relazione $\le $ (vedi \see{sec:well_ordered_set}) } } La relazione d'ordine $(N,\le)$ e' quella usuale: \eal{&a\le b\= \exists c\in N:\;a+n=b} L'operazione $+$ e' definita in \see{addizioneinN} \end{prop} \begin{proof} Bastera' dimostrare $2.\;\>\;1.\;\>\;3.\;\>2$ \step{}{Dim $2.\>1.$} \begin{prova} Sia $U\(N$. Dobbiamo dimostrare l'implicazione \eal{& \sist{\nz\in U\\ n\in U\> s(n) \in U } \> U=N} Supponiamo che la premessa sia vera: \eal{&\sist{\nz\in U\\ n\in U\> s(n) \in U }\;\;\;\;(1) } e dimostriamo $U=N$ sfruttando la $2.$\\ Supponiamo che \eal{&\pgra{k\in N\;|\;\nz\le k< s(n) }\( U } allora, \eal{&n\in N \> \nz\le n n \in \pgra{k\in N\;|\;\nz\le k< s(n) }\( U\> n\in U \ubrace{\>}{(1)} s(n)\in U } Cosi' facendo abbiamo dimostrato l'implicazione: \eal{&\pgra{k\in N\;|\;\nz\le k< s(n) }\( U \> s(n)\in U \;\;(*)} Allora, anche la seguente implicazione e' vera: \eal{&\pgra{k\in N\;|\;\nz\le k< m }\( U \> m\in U \;\;(2) } infatti, se $m=\nz$, \eal{&\pgra{k\in N \;|\;\nz\le k<\nz}=\0 \( U \> \nz\in U\\ &\0 \( U \> \nz\in U\qq \T{ [che e' vera per la }(1)]} se invece $m \neq \nz$, \eal{&m \neq \nz \ubrace{\>}{\T{II assioma di Peano} } m\in \Im s \= \exists n:\;m=s(n)\\ &\T{E quindi la $(*)$ si riscrive come: }\\ &\pgra{k\in N\;|\;\nz\le k< s(n) }\( U \> s(n)\in U } ovvero la $(2)$.\\ Adesso entra in gioco la $2.$: \eal{&(1)\> \nz\in U\\ &\sist{\nz\in U\\ (2)} \ubrace{\>}{2.} U=N } che era cio' che volevamo dimostrare. \end{prova} \step{}{Dim. $1.\>3.$} \begin{prova} Sia $U\( N,\;U \neq \0$. Dobbiamo dimostrare che $U$ ha il minimo.\\ \begin{prova} Sia \eal{&T=\pgra{t\in N\;|\;t\le u\;\;\forall u\in U}\;\;\T{ l'insieme dei minoranti di U}\\ &\nz \le n\;\;\forall n\in N \> \nz \in T \> T \neq \0} \case{Supponiamo vera l'implicazione $t\in T \> s(t)\in T$} \begin{prova} Se $t\in T \> s(t)\in T$, si ha \eal{&\sist{\nz \in T\\ t\in T \> s(t) \in T } \ubrace{\>}{1.} T=N \> U\( T \> \exists \min U } \end{prova} \case{Supponiamo falsa l'implicazione $t\in T \> s(t)\in T$} \begin{prova} Ovvero $\exists t\in T:\;s(t)\notin T$. \eal{&t\in T \> t\le u\;\;\forall u\in U\;\;(1) } \case{$\exists u\in U:\;t=u$} \begin{prova} In questo caso, $t=\min U$ e non abbiamo piu' nulla da dimostrare. \end{prova} \case{$t \neq u\;\;\forall u\in U$} \begin{prova} In questo caso, la $(1)$ diventa \eal{&t s(t)\in T} assurdo. \end{prova} \end{prova} \end{prova} \end{prova} \step{}{Dim $3.\>2.$} \begin{prova} Sia $U\(N$. Dobbiamo dimostrare la seguente implicazione: \eal{& \sist{\nz\in U\\ \pgra{k\in N\;|\;\nz\le k< n }\( U \> n\in U} \> U=N } Supponiamo vera la premessa: \eal{&\sist{\nz\in U\\ \pgra{k\in N\;|\;\nz\le k< n }\( U \> n\in U} \;\;(1) } e dimostriamo $U=N$.\\ Supponiamo per assurdo che $U \neq N$. Sia $V=N\-U$ \eal{&U \neq N \> V \neq \0 \ubrace{\>}{3.}\exists m=\min V } Consideriamo l'insieme $K=\pgra{k\in N\;|\;\nz \le k< m}$ \eal{ &k\in K \> k k\notin V=N\-U \ubrace{\>}{k\in N} k\in U\\ &\forall k\in K\;\;k\in U \> K \( U \ubrace{\>}{(1)} m\in U\\ &m=\min V \> m\in V\\ &m\in U,\;m\in V=N\-U } assurdo. \end{prova} \end{proof} \begin{prop} Alcune precisazioni sul principio di induzione forte.\\ Sia $N$ un qualsiasi insieme di numeri naturali, sia $\nz$ lo zero e $s()$ la funzione successivo.\\ Analogamente a come abbiamo fatto in \see{dimperinduzione}, possiamo sfruttare l'Induzione forte per dimostrare $P(n)\;\;\forall n\in N$. Infatti, si ha: \eal{&\sist{P(\nz)\\ \pton{P(k)\;\;\;\forall k:\;\nz\le k P(n)}\> P(n)\;\;\forall n\in N} Il metodo e' quindi: \begin{enumerate} \item Dimostro che $P(\nz)$ e' vera \item Suppongo vera $P(k)$ per tutte le $k$ che sono $\nz\le k c/_{ma}} ovvero $c$ divide anche i multipli di \item \eal{& c/_x,\;c/_y \> c/_{(x+y)}} \begin{proof} \begin{align*} &x=cq_1+r_1\\ &y=cq_2+r_2\\ &x+y=cq_1+r_1+cq_2+r_2\\ &x+y=c(q_1+q_2)+(r_1+r_2) \quad \Rightarrow \quad c/_{(x+y)} \end{align*} \end{proof} \item \eal{& \sist{x=y+z\\c/_x,\;c/_y} \> c/_z} \begin{proof} \begin{align*} &x=cq_1, \quad y=cq_2\\ &x=y+z \quad \Rightarrow \quad cq_1=cq_2+z\\ &c(q_1-q_2)=z \quad \Rightarrow \quad c/_z \end{align*} \end{proof} \item \label{propdivaeqbc} Questa proprieta' utilizza concetti che vedremo piu' avanti: \eal{&\sist{a=bc\\ d\div a,\;d\ndiv b\\ (d,b)=1} \> d\div c } \begin{proof} Per Bezout (vedi \see{iddibezout}) abbiamo \eal{&(d,b)=1\=1=\lambda d + \mu b \\ &c= \lambda dc + \mu bc\\ &\sist{d \div \mu bc = \mu a\\ d\div \lambda dc} \> d\div ( \lambda dc + \mu bc)=c } \end{proof} \end{enumerate} \subsection{Massimo Comune Divisore} Il MCD e' definito il questo modo: \[ a,b,d,d' \in \mathbb{N} \] \[ d=MCD(a,b) \quad \Leftarrow \quad d/_a \land d/_b \land \left( ( d'/_a \land d'/_b) \Rightarrow d'/_d \right) \] Ovvero, $d$ e' un MCD di $a$ e $b$ se divide sia $a$ sia $b$ e se e' diviso da qualsiasi altro divisore comune ad $a$ e a $b$. \oldsubsubsection{Proprieta'} Il MCD esiste sempre ed e' unico. \begin{proof} Dobbiamo dimostrare che se $d_1$ e $d_2$ sono $MCD(a,b)$, allora $d_1 = d_2$.\\ $d_1$ e' $MCD(a,b)$ e quindi per definizione $d_2/d_1$.\\ $d_2$ e' $MCD(a,b)$ e quindi per definizione $d_1/d_2$. Allora per la proprieta' asym segue che: $d_2=d_1$ \end{proof} \subsection{Algoritmo di divisione in $\mathbb{N}$} \label{sec:divisione_algo} Data una coppia $(a,b)\in \mathbb{N}^2, \; b\neq 0$, allora esistono e sono unici due \[q,r\in \mathbb{N} \; | \; a=bq+r\] \begin{proof} Definiamo l'insieme T: \[ T = \left\{ x \in N | \; xb > a \right\} \] Sicuramente $T \neq \emptyset$ perche' contiene almeno $a+1$. Inoltre, $T \subset \mathbb{N}$, quindi dato che $\mathbb{N}$ e' ben ordinato, sappiamo che $T$ avra' un minimo \[q'=\min T \neq 0\]. Quindi $q'$ e' almeno il successivo di qualche numero $q$: \[q'=q+1\] Ma $q \notin T$ perche' $q'$ e' il minimo di $T$, allora: \[ qb \le a \Rightarrow \exists r | qb+r=a \] E questo conclude la prima parte della dimostrazione. Ora dimostriamo che $ra\\ &a |B|\quad \Leftrightarrow \quad \exists \;\;\varphi: A\mapsto B, \;\; \nexists \psi: A \leftrightarrow B\\ \end{align*} \oldsubsubsection{Proprieta'} \begin{enumerate} \item $|A| < |P(A)| \quad \forall A$.\\ Questo e' il teorema di Cantor. \begin{proof} Basta dimostrare che \[\exists \;\;\varphi: A\hookrightarrow P(A), \;\; \nexists \psi: A \mapsto P(A)\] La prima parte e' semplice, perche' dobbiamo trovare almeno una $\varphi$ iniettiva. Scegliamo allora una funzione $f(a)$ che ritorna un insieme che contiene $a$: \[ f(a)=\{a\} \] Dimostriamo che e' iniettiva: \begin{align*} &x,y\in A\\ &f(x)=f(y)\quad\Rightarrow\quad\{x\}=\{y\}\quad \Rightarrow \quad x=y \end{align*} E dato che $\{x\},\{y\} \in P(A)$, possiamo concludere che: \[ |A| \le P(A) \] Per la seconda parte ragioniamo per assurdo: supponiamo che esiste una funzione surriettiva $\psi: A \mapsto P(A) $. Prendiamo l'insieme $B$ che contiene tutti gli elementi che sono in $A$ ma non nella loro immagine di $\psi$: \begin{align*} &B=\left\{ x\in A| x\notin \psi(x) \right\} \subseteq A\\ &B\subseteq A \Rightarrow B \in P(A) \end{align*} Per l'ipotesi della surriettivita' di $\psi$ possiamo scrivere: \[ \exists y\in A | \psi(y)=B \] Ora possono verificarsi due casi: 1) $y\in B$ 2) $y\notin B$. Analizziamoli: \begin{description} \item [y$\in$ B] Per la definizione di $B$, allora accade che $y\notin \psi(y)$, ma $\psi(y)=B$. E questo e' assurdo, perche' $y$ non puo' contemporaneamente appartenere e non appartenere a $B$. \item [y$\notin$ B] Per la definizione di $B$: $y \in \psi(y)=B$. Il che' e' assurdo. \end{description} Dato che abbiamo trovato un assurdo in entrambi i casi, vuol dire che la nostra ipotesi e' assurda, ovvero $\psi$ non e' surriettiva. \end{proof} \item $|P(A)| = |{\underline{2}}^{A}|$ Dove ${\underline{2}}^{A}$ e' l'insieme di tutte le applicazioni che vanno da $A$ a $\underline{2}$. \begin{proof} Dobbiamo dimostrare che $P(A)$ e ${\underline{2}}^{A}$ sono equipotenti, ovvero che esiste un'applicazione biettiva tra di loro.\\ Intanto diamo un po' di definizioni. \[ \varphi_{B} (x) = \begin{cases} 1, & x \in B; \\ 0, & x \not \in B. \end{cases} \] $\varphi_{B}$ e' la funzione caratteristica.\\ Definiamo $A_f$: \begin{align*} &f \in {\underline{2}}^{A}\\ &A_f=\left\{ a\in A | f(a)=1 \right\}\\ &A_f \subseteq A\quad \Rightarrow \quad A_f \in P(A) \end{align*} Ora scegliamoci due funzioni opportune: \begin{align*} &\varphi: P(A) \rightarrow {\underline{2}}^{A}, \quad \forall B\in P(A)\;\; \varphi(B)=\varphi_{B}\\ &\psi: {\underline{2}}^{A} \rightarrow P(A), \quad \forall f\in {\underline{2}}^{A}\;\; \psi(f)=A_f \in P(A) \end{align*} Se riuscissimo a dimostrare che \begin{align} &\varphi\circ\psi=1_{ {\underline{2}}^{A} } \label{eq:A}\\ &\psi\circ\varphi=1_{ P(A) } \label{eq:B} \end{align} vorrebbe dire che $\psi$ e' biettiva, e quindi avremmo finito.\\ Cominciamo con la \eqref{eq:A}. Dobbiamo verificare che: \[ \forall f \in {\underline{2}}^{A}, \quad \varphi\circ\psi(f)=f \qquad \Rightarrow \qquad [\varphi\circ\psi(f)](a)=f(a), \quad \forall a \in A \] Procediamo per sostituzione: \[ [\varphi(A_f)](a) = \varphi_{A_f}(a) = \begin{cases} 1&a\in A_f\\ 0&a\notin A_f \end{cases} \] Notiamo che se $a\in A_f$ allora $f(a)=1$ (per la stessa definizione di $A_f$), ovvero, in questo caso $f(a)=\varphi_{A_f}(a)$.\\ Se $a\notin A_f$ allora $f(a)=0$, quindi, anche in questo caso $f(a)=\varphi_{A_f}(a)$.\\ Dato che in entrambi i casi $f(a)$ coincide con la composizione, possiamo concludere che $[\varphi\circ\psi(f)](a)=f(a)$ e quindi che $\varphi\circ\psi=1_{ {\underline{2}}^{A} }$.\\ Ok, adesso abbiamo finito la prima parte della dimostrazione, ci resta da verificare che \[ \psi\circ\varphi=1_{ P(A) }\quad\Rightarrow \quad \forall B\in P(A),\;\; \psi\circ\varphi(B)=B \] Sostituiamo: \[ \psi\circ\varphi(B)=\psi(\varphi_B)=A_{ {\varphi}_B} \] Ma $A_{\varphi_B}$ e' l'insieme che contiene tutti gli elementi $a \in A$ tale che $\varphi_{B}(a)=1$, ovvero contiene tutti gli elementi che stanno in $A$ e in $B$. Ma dato che $B \in P(A)$, $B$ e' un sottoinsieme di $A$, quindi ``tutti gli elementi che stanno in $A$ e in $B$'' formano l'insieme $B$ stesso. In poche parole: \[ A_{\varphi_B}=B \] Che e' quello che volevamo dimostrare.\\ Fine dimostrazione \verb|^_^| \end{proof} \end{enumerate} \subsection{Diagonalizzazione di Cantor} \label{diagonalizzcantor} \begin{prop} Vale il seguente teorema: \eal{&|\mathbb{N}|=|\mathbb{N}\*\mathbb{N}|} che si puo' facilmente estendere per induzione: \eal{&|\mathbb{N}|=|\mathbb{N}^n|\;\;\;\forall n\in \mathbb{N} } Queste formule definiscono una relazione biettiva tra $\mathbb{N}$ e $\mathbb{N}\*\mathbb{N}$: \begin{align*} &f: \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N} & n=f(a,b)=\binom{a+b+1}{2}+a \end{align*} Per l'inverso conosciamo $n$ e vogliamo calcolare $a$ e $b$: \begin{align*} &T=\left\{ x\;| \;\;\binom{x}{2} \le n \right\}\\ &d=\max T\\ &g: \mathbb{N} \longrightarrow \mathbb{N} \times \mathbb{N}\\ &a=n-\binom{d}{2}\\ &b=d-a-1 \end{align*} Piu' in generale, vale il seguente risultato: considerato l'insieme \eal{&A=\pgra{A_1,A_2,\dots} } si ha \eal{&|A|=|A_i|=|\mathbb{N}|\;\;\forall A_i\in A \> \Big|\bigcup_{A_i\in A}A_i \Big| = |\mathbb{N}| } ovvero, l'unione di un numero finito o infinitamente numerabile di insiemi numerabili, e' ancora un insieme numerabile.\\ Ad esempio, \eal{&\mathbb{Z}=\mathbb{N}\U \pgra{-1,-2,\dots} } quindi $\mathbb{Z}$ e' numerabile. \end{prop} \begin{prop} $|\mathbb{R}|=|\mathbb{R}^n|$ \end{prop} \begin{prova} \pf \def\*{{\times}} \step{}{Dimostriamo che $|[0,1]|=|[0,1]\*[0,1]|$} \begin{prova} Rappresentiamo ogni numero reale $\alpha\in [0,1]$ come \eal{&\alpha=0,d_1d_2d_3\dots,\;\;\;d_i\in {0,1,\dots,9}} I numeri razionali non periodici, li rappresentiamo con infiniti $9$ al posto dello zero finale, ad esempio: \eal{&0.5=0.50=0.59999\dots} Consideriamo $(a,b)\in [0,1]\*[0,1]$, \eal{&a=0.a_1a_2\dots\\ &b=0.b_1b_2\dots } Raggruppiamo le cifre decimali di $a$ con la seguente legge: partendo da un $a_i$, consideriamo $a_{i+1},a_{i+2},\dots$ fino a quando non giungiamo a $a_{i+j} \neq 0$. Il gruppo creato e' $A_1=a_{i}a_{i+1}\dots a_{i+j}$. Il prossimo gruppo verra' creato a partire da $a_{i+j+1}$, e cosi' via\dots.\\ Procediamo allo stesso modo per $b$.\\ Creiamo il seguente numero reale $c\in [0,1]$: \eal{&a=0.A_1A_2\dots\\ &b=0.B_1B_2\dots\\ &c=0.A_1B_1A_2B_2\dots} Ad esempio, \eal{&a=0.12034100100089\dots=0.\;\;1\;2\;03\;4\;1\;001\;0008\;9\dots\\ &b=0.0330041301\dots=0.\;\;03\;3\;004\;1\;3\;01\;\dots\\ &c=0.\;1\;03\;2\;3\;03\;004\;4\;1\;\dots} Abbiamo cosi' definito una legge $f:[0,1]\*[0,1]\longrightarrow [0,1]$.\\ $f$ e' invertibile, e quindi biettiva, infatti, dato \eal{&f(a,b)=c=0.c_1c_2\dots} possiamo scomporre le cifre decimali di $c$ usando la stessa legge di prima. Otteniamo cosi' $C_1,C_2,\dots$. Quindi \eal{&f^{-1}(c)=(a,b)\\ &\T{ con }\\ &\qq a=0.C_1C_3C_5\dots\\ &\qq b=0.C_2C_4C_6\dots} E' chiaro che \eal{&f\circ f^{-1}(c)=c\\ &f^{-1}\circ f(a,b)=(a,b)} \end{prova} \qedstep \begin{prova} In topologia.pdf (1.19 Omeomorfismo) abbiamo visto che due intervalli qualsiasi di $\mathbb{R}$ sono omeomorfi, e quindi equipotenti. In particolare allora $|[0,1]|=|\mathbb{R}|$ \end{prova} \qed \end{prova} \subsection{Potenza del continuo} Un insieme A ha la potenza del continuo se: \[ |A| = |P(\mathbb{N})| \] Sappiamo che $|\mathbb{R}|=|P(\mathbb{N})|$, quindi si puo' anche dire che $A$ ha la potenza del continuo se $|A|=|\mathbb{R}|$. \subsection{Ipotesi del continuo} L'ipotesi del continuo afferma che dato un insieme $A$: \[ |\mathbb{N}| \le |A| \le |P(\mathbb{N})| \;\;\Leftrightarrow \;\; |A|=|N| \lor |A|=|P(\mathbb{N})| \] Cioe', se $|\mathbb{N}| < |A| \le |P(\mathbb{N})|$, allora $|A|=|P(\mathbb{N})|$ \section{L'insieme $\mathbb{Z}$} Definiamo in $\mathbb{N} \times \mathbb{N}$ la seguente relazione, che si rileva essere una relazione d'equivalenza: \[ (a,b) \sim (c,d) \;\; \Leftrightarrow \;\; a+d=b+c \] Si puo' facilmente verificare che gode delle tre proprieta' (rifl., simm., trans.). Adesso prendiamo \[ {\mathbb{N} \times \mathbb{N}}/_\sim = \left\{ \textrm{insieme di tutte le classi d'equivalenza } \right\} = \mathbb{Z} \] $\mathbb{Z}$ non e' nient'altro che questo insieme. Un suo elemento qualsiasi e' quindi la classe d'equivalenza $[(a,b)]$\\ Per questo motivo, insiemisticamente parlando, la scrittura $\mathbb{N} \subset Z$ e' errata. Ora ridefiniamo tutte le operazioni abituali. \subsection{Addizione} \[ [(a,b)]+[(c,d)]=[(a+c), (b+d)] \] In realta', $[(a,b)]$ e' una classe di equivalenza, e quindi esiste anche $(a',b') \sim (a,b) \; \Rightarrow \; [(a',b')]=[(a,b)]$ che rientra nella stessa classe.\\ Allora, la seguente equivalenza e' vera? \[[(a,b)]+[(c,d)]=[(a',b')]+[(c,d)]=[(a+c), (b+d)]=[(a'+c), (b'+d)]\] Verifichiamolo: \begin{align} &(a',b') \sim (a,b) \; \Rightarrow \; a'+b=b'+a\\ &\left( (a+c), (b+d) \right) \sim ( (a'+c), (b'+d) ) \; \Rightarrow \; (a+c)+(b'+d) = (b+d)+(a'+c)\\ &a+b'+c+d=a'+b+c+d\;\; \Rightarrow \;\; a+b'=a'+b\\ &0=0\quad \textrm{per la (1)} \end{align} \oldsubsubsection{Proprieta'} L'addizione in $\mathbb{Z}$ gode di queste proprieta': \begin{enumerate} \item Associativa \item Commutativa \item $0$ e' l'elemento neutro \item Legge di cancellazione: $a+c=b+c\; \Rightarrow ;\ a=b$ \end{enumerate} \subsection{Moltiplicazione} \[ [(a,b)][(c,d)]=[(ac+bd),(ad+bc)] \] \oldsubsubsection{Proprieta'} La moltiplicazione in $\mathbb{Z}$ gode di queste proprieta': \begin{enumerate} \item Associativa \item Commutativa \item Distributiva rispetto alla somma \item $[1,0]=+1$ e' l'elemento unita' \item Esiste l'opposto (che non esisteva in $\mathbb{N}$: $\forall a \in \mathbb{Z}\; \exists a': \; a+a'=a'+a=0$ \end{enumerate} \subsection{Simbolismo} Adesso ritorniamo all'usuale rappresentazione dei numeri interi relativi: \[ [a,b] = \begin{cases} a > b&\exists n: a=b+n \quad [a,b]\rightarrow +n\\ a < b&\exists n: b=a+n \quad [a,b]\rightarrow -n\\ a=b & \quad [a,b]=0 \end{cases} \] ($[a,b]\rightarrow +n$ significa che a $[a,b]$ associamo $+n$, ad esempio $[7,3] \rightarrow +4$)\\ Siamo sicuri che $[a,b]\rightarrow +n$ per ogni coppia in $[a,b]$? \begin{proof} Verifichiamolo per $a > b$.\\ \begin{align*} &(a',b') \sim (a,b)\\ &a'+b=b'+a\\ &a>b \; \Rightarrow \; a=b+n\\ &a'+b=b'+b+n\;\Rightarrow \; a'=b'+n \; \Rightarrow \; a' > b' \end{align*} \end{proof} \subsection{$\mathbb{N}$ immerso in $\mathbb{Z}$} Consideriamo una funzione iniettiva: \[ f: \mathbb{N} \hookrightarrow \mathbb{Z} \] Se gode di queste proprieta', si dice che e' un'\emph{immersione}: \begin{enumerate} \item $f(m+n)=f(m)+f(n)$ \item $f(mn)=f(m)f(n)$ \end{enumerate} In poche parole $f()$ eredita le operazioni di $N$. Poiche' questo e' vero per $\forall m,n \in \mathbb{N}$, possiamo dire che $\mathbb{N}$ e' immerso in $\mathbb{Z}$ e scriveremo $N \subset Z$. \begin{proof} Proviamo che $f(n)=[n,0]=+n$ e' un'immersione.\\ \begin{enumerate} \item E' inniettiva?\\ \begin{align*} &f(m)=f(n)\;\Rightarrow m=n\\ &[m,0]=[n,0]\\ &(m,0)\sim (n,0)\\ &m+0=n+0\\ &m=n \end{align*} \item Eredita l'addizione?\\ \begin{align*} &f(m+n)=f(m)+f(n)\\ &[m+n,0]=[m,0]+[n,0]=[m+n,0] \end{align*} \item Eredita la moltiplicazione?\\ \begin{align*} &f(mn)=f(m)f(n)\\ &[mn,0]=[m,0][n,0]=[mn+0\cdot 0, m0+0n]=[mn,0] \end{align*} \end{enumerate} \end{proof} \subsection{$\mathbb{Z}$ e' un totet} $\mathbb{Z}$ non e' piu' ben ordinato, infatti, non ha piu' un minimo, pero' rimane sempre totalmente ordinato.\\ Inoltre, $(\mathbb{Z},+,\cdot)$ e' un dominio d'integrita' e $(\mathbb{Z},+,\cdot, \le)$ e' un dominio ordinato. Con questo intendiamo che la relazione d'ordine $\le $ rimane compatibile con le operazioni di somma e prodotto: \begin{enumerate} \item se $a\le b\;\;\Rightarrow \;\;a+c\le b+c$ \item se $a\le b, \;c\ge 0\;\;\Rightarrow \;\;ac\le bc$ \end{enumerate} \subsection{Teoria della divisibilita' in $\mathbb{Z}$} \[ a/_b \;\;\Leftrightarrow \;\; az=b,\;\;\;a,b,z\in \mathbb{Z} \] \oldsubsubsection{Proprieta'} \begin{enumerate} \item Se $m,n\in \mathbb{Z}$, $mn=1 \;\;\Rightarrow \;\; m=n=\pm1$ \item Se $a/_b \;\land \; b/_a\;\;\Rightarrow \;\; b=\pm a$ \end{enumerate} \subsection{Numeri irriducibili e primi} Un numero $z \in \mathbb{Z}$ e' irriducibile se i suoi unici divisori sono $\pm1, \;\pm z$, ovvero \[ z=bc \;\Rightarrow \; b\equiv \textrm{ invertibile} \lor c\equiv \textrm{ invertibile} \] Nota: gli unici invertibili in $\mathbb{Z}$ sono $\pm 1$.\\ Un numero $p \in \mathbb{Z}$ e' primo se e' vera la seguenete implicazione: \[ p/_{ab} \;\;\Rightarrow \;\; p/_a \;\lor\;p/_b \] Un numero $p \neq 0$ e' primo se e solo se e' irriducibile: \[ \textrm{primo} \Leftrightarrow \textrm{irriducibile} \] \begin{proof} Dimostriamo il verso $\Rightarrow$.\\ Per ipotesi $p=ab$ e' primo, quindi $p/_a\lor p/_b$\\ Se $p/_a$, allora: \begin{align*} &a=\lambda p\\ &p=ab \;\Rightarrow \; p=\lambda pb \ubrace{\>}{p \neq 0} 1=\lambda b \\ &b=\pm 1 \end{align*} Se invece $p/_b$ allora: \begin{align*} &b=\mu p\\ &p=ab \;\Rightarrow \; p=a\mu p \ubrace{\>}{p \neq 0} 1=a\mu\\ &a=\pm 1 \end{align*} \end{proof} \begin{proof} Dimostriamo l'altro verso $\Leftarrow$\\ Ipotesi: $p$ e' irriducibile.\\ Supponiamo che $p$ sia effettivamente primo, allora scriviamo che: \[ p/_{ab} \] e supponiamo anche che $p$ non divida $a$. Se allora riusciamo a dimostrare che divide $b$, abbiamo finito. Dato che $p$ non divide $a$: $MCD(a,p)=1$. Applichiamo l'identita' di Bezout: \[ 1=ma+np \] Moltiplichiamo la precedente per $b$: \[ b=bma+bnp=(bm)a + (pn)b \] Poiche' per Hp $p/_{ab}$ allora $p/_{(ab)m}$, e poiche' $p/_{pnb}$, allora $p$ divide la loro somma e quindi \[p/_{b}\] \end{proof} \subsection{MCD in $\mathbb{Z}$} Il MCD in $\mathbb{Z}$ e' definito allo stesso modo di come e' stato prima definito in $\mathbb{N}$: \[ d=MCD(a,b)\;\Leftrightarrow\; d/_a,\;d/_b,\; \exists d' | d'/_a, d'/_b \Rightarrow {d'}/_d \] \subsection{Minimo Comume Multiplo} Il $mcm(a.b)$ e' semplicemente il contrario del MCD: \[ m=mcm(a,b)\;\Leftrightarrow\;a/_m,\;b/_m,\;\exists m'|a/_{m'}, b/_{m'} \Rightarrow m/m' \] \oldsubsubsection{Proprieta'} \label{mcmMCD123} \begin{enumerate} \item Possiamo calcolare il MCD e il mcm in questo modo: \begin{align*} &a=q_1^{m_1}q_2^{m_2}\cdots q_s^{m_s},\;\;m_i\ge 0\\ &b=q_1^{t_1}q_2^{t_2}\cdots q_s^{t_s},\;\;t_i\ge 0\\ &\alpha_i=min(m_i,t_i)\\ &\beta_i=max(m_i,t_i)\\ &MCD(a,b)=q_1^{\alpha_1}q_2^{\alpha_2}\cdots q_s^{\alpha_s}\\ &mcm(a,b)=q_1^{\beta_1}q_2^{\beta_2}\cdots q_s^{\beta_s} \end{align*} \begin{proof} Sia $m=q_1^{\beta_1}q_2^{\beta_2}\cdots q_s^{\beta_s}$. Poiche' \eal{&\beta_i = \max(m_i,t_i) \ge m_i,t_i } e' chiaro che $m$ e' un multiplo sia di $a$ che di $b$.\\ Supponiamo che $m'$ sia un multiplo di $a$ e di $b$, allora \eal{&m'=kab=kq_1^{m_1+t_1}q_{2}^{m_2+t_2}+\cdots+ q_s^{m_s+t_s} } Si ha anche che \eal{&\beta_i = m_i \| \beta_i = t_i \> \beta_i \le m_i+t_i } e quindi e' chiaro che $m\div m'$.\\ Percio' $m=mcm(a,b)$.\\ In modo analogo si procede per il $MCD$. \end{proof} \item \[mcm(a,b)\cdot MCD(a,b)=ab\] \begin{proof} Procedendo come nella prop. precedente, decomponiamo $ab$: \eal{&ab=(q_1^{m_1}q_2^{m_2}\cdots q_s^{m_s}) (q_1^{t_1}q_2^{t_2}\cdots q_s^{t_s}) = q_1^{m_1+t_1}q_{2}^{m_2+t_2}+\cdots+ q_s^{m_s+t_s} } Per la prop. precedente abbiamo \eal{& mcm(a,b)MCD(a,b)= (q_1^{\alpha_1}q_2^{\alpha_2}\cdots q_s^{\alpha_s}) (q_1^{\beta_1}q_2^{\beta_2}\cdots q_s^{\beta_s}) = q_1^{\alpha_1+\beta_1}q_{2}^{\alpha_2+\beta_2}+\cdots+q_s^{\alpha_s+\beta_s} } Ma poiche' \eal{&\alpha_i+\beta_i= \min(m_i,t_i) +\max(m_i,t_i) = m_i+t_i } si ha la tesi. \end{proof} \item \eal{&mcm(a,b) = ab \= MCD(a,b)=1} \begin{proof} Immediata conseguenza della prec. prop. \end{proof} \item \eal{&a\div n,\;\;b\div n \= mcm(a,b)\div n} \begin{proof} \BEGINpnecessaria Semplice conseguenza della $1.$ \END \BEGINsufficiente \eal{&\T{per definizione }mcm(a,b)=\lambda a = \mu b\NN mcm(a,b)\div n\NN \qq \> a,b\div n } \END \end{proof} \end{enumerate} \subsection{Algoritmo di divisione in $\mathbb{Z}$} Non e' altro che l'estensione di quello in $\mathbb{N}$: \[ \forall a,b\in Z, \; \exists! q,r\in Z|\; a=qb+r,\;\;0\le r < |b| \] \begin{proof} Proviamolo. \begin{enumerate} \item In questo primo caso poniamo $a \ge 0$ e procediamo per induzione su $a$.\\ Base: $a=0 \Rightarrow (a=0)=0+0$\\ Hp: $a=qb+r,\;\;0\le r < |b|$\\ Dim: Aggiungiamo $1$ ad ambo i membri di $a=qb+r$: \begin{align*} &a+1=qb+(r+1)=qb+r',\;\;r'=r+1 \end{align*} Se dimostriamo che $0\le r' < |b|$ abbiamo finito.\\ Sicuramente $r' \ge 0$ perche' e' $r\ge 0$ per l'ipotesi induttiva.\\ E' anche vero che $(r'=r+1) \le |b|$ perche' per Hp $r < |b|$. Allora si possono verificare due casi: \begin{enumerate} \item $r' < |b|$. E qui abbiamo finito. \item $r' = |b|$. Allora: \begin{align*} &a+1=qb+|b|\\ &a+1=qb+|b|=b(q\pm 1)+0 \end{align*} Questo significa che siamo riusciti a dividere $a+1$ per $b$ e che il suo resto e' $0 < |b|$. Fine. \end{enumerate} \end{enumerate} \end{proof} \subsection{Identita' di Bezout} \begin{prop} \label{iddibezout} \[ d=MCD(a,b) \;\;\Rightarrow\;\;\exists \lambda,\mu\in \mathbb{Z}: d=\lambda a+\mu b \] Per calcolare $\lambda$ e $\mu$ si utilizza l'agoritmo Euclideo ( \vedi{algoeuclidemcd}): \begin{align*} &a=bq_1+r_1\\ &b=r_1q_2+r_2\\ &r_1=r_2q_3+r_3\\ &r_2=r_3q_4+r_4\\ &\quad\vdots\\ &r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}\\ &r_{n-2}=r_{n-1}q_{n}+r_{n}\\ &r_{n-1}=r_{n}q_{n+1}+0\NN d=r_n \end{align*} Si parte dalla prima equazione e si procede per sostituzioni successive: \eal{&r_1= -q_1b+a = \lambda_0b+\mu_0a\NN r_2=b-r_1q_2=b-(\lambda_0b+\mu_0a)q_2 = (1-\lambda_0)b-q_2\mu_0a=\lambda_1b+\mu_1a\NN r_3= r_1 - r_2q_3=\pton{\lambda_0b+\mu_0a}-\pton{\lambda_1 b+\mu_1a}q_3 = \lambda_2b+\mu_2a \NN \vdots\NN r_n=r_{n-2}-r_{n-1}q_{n}= \pton{\lambda_{n-3}b+\mu_{n-3}a}-\pton{\lambda_{n-2} b+\mu_{n-2}a}q_3 = \lambda_{n-1}b+\mu_{n-1}a\NN d=r_n= \lambda_{n-1}b+\mu_{n-1}a } \end{prop} \subsection{Teorema fondamentale dell'aritmetica} $\forall n\in Z^{*}$, non invertibile, si puo' esprimere in maniera ``unica'' come prodotto di numeri primi. Questa ``unicita\''' vale a meno dell'ordine e del segno. \begin{proof} Poiche' l'unicita' e' a meno del segno e che $n\neq 1$, supponiamo che $n > 1$ e procediamo per induzione su $n$:\\ base: $n=2$. Questo e' vero perche' $2$ e' primo.\\ Hp: se $m q_1 \div p_1p_2\cdots p_s\\ &\T{Sia } p=p_2\cdots p_s\\ &q_1\T{ primo } \> {q_1 \neq p}} Se per assurdo $(q_1, p) \neq 1$, allora \eal{&(q_1,p) \neq 1 \> \exists d \neq 1:\;\;d\div q_1 \land d \div p \\ &d\div q_1 \ubrace{\=}{q_1\T{ e' primo }} d=1 \lor d=q_1 \ubrace{\>}{d \neq 1} d=q_1\\ &d\div p \= q_1 \div p=p_2\cdots p_s \ubrace{\>}{q_1 \T{ e' primo }} q_1 \div p_k,\;\;2\le k\le s \ubrace{\>}{q_1 \T{ e' primo}} q_1 = p_k } assurdo, contro la nostra supposizione iniziale. Quindi $(q_1, p)=1$. \eal{ &\sist{n=p_1p\\ q_1\div n,\;\;q_1 \ndiv p\\ (q_1,p) =1 } \ubrace{\>}{\T{prop. divisibilita' }\see{propdivaeqbc}} q_1\div p_1 \\ &\sist{q_1\T{ primo },\;q_1 \neq 1\\ q_1\div p_1 } \> q_1 = p_1 } E questo e' assurdo.\\ Allora, concludiamo che \eal{&\exists i:\;\;q_1 = p_i} E analogamente per qualsiasi altro $q_j$.\\ Quindi $q_1=p_i$. Per semplicita', a meno di riordinare i fattori, poniamo $i=1$.\\ Quindi riscriviamo l'equazione di partenza, semplificando $q_1$ e $p_1$ da entrambi i membri: \[ q_2\cdots q_r=p_2\cdots p_s \] Ora possiamo ripetere questa stessa procedura $r$ volte, fino a quando arriviamo a: \[ 1=p_{r+1}\cdots p_s \] Ma questo e' assurdo perche' il prodotto di numeri primi, di certo, non e' uguale a $1$, quindi, se questo e' assurdo, e' assurda l'ipotesi che $rs$ e arriveremmo anche qui a un assurdo, allora $r=s$. Da quanto abbiamo dimostrato prima $n$ si puo' fattorizzare in fattori primi, ma se ogni sua fattorizzazione ha esattamente $r$ fattori, allora tutte queste sono equivalenti. In poche parole, esiste una sola fattorizzazione di $n$. \end{proof} \section{Aritmetica modulare} Sappiamo che possiamo scrivere ogni numero $x \in \mathbb{Z}$ come $x=mn+y$, allora possiamo inventarci questa relazione: \[ x \sim y \;\Leftrightarrow \; x-y=nm \] e diciamo che $x$ e' congruo a $y$ modulo $n$. In altre parole $x\sim y$ se $x-y$ e' un multiplo di $n$, ovvero se $x$ diviso $n$ e $y$ diviso $n$ hanno lo stesso resto.\\ Questa relazione e' una relazione d'equivalenza. Possiamo costruire allora le classi di equivalenza: \[ [a]_n=\overline{a}=\{x \in \mathbb{Z} | \; x \sim a\} = \{x \in \mathbb{Z} | \; x-a=mn \} \] Creiamo l'insieme quoziente $\mathbb{Z}/_{\sim}$, ovvero: \[ \mathbb{Z}_n=\mathbb{Z}/_{\sim}=\{\textrm{classi di equivalenza}\} \] $[a]_n$ sono tutti quei numeri che divisi per $n$ hanno lo stesso resto di $a$ diviso $n$. Poiche' sappiamo per l'algoritmo di divisione in $\mathbb{Z}$ che il resto e' sempre $0\le r < n$, allora ci saranno esattamente $n-1$ classi d'equivalenza, ovvero: \[ \mathbb{Z}_n = \{ [1], [2], \dots, [n-1] \} \] Il numero di elementi di $\mathbb{Z}_n$ e' uguale a $n$. A questo punto definiamo le solite operazioni su $\mathbb{Z}_n$. \subsection{Somma} \[ [a]+[b]=[a+b] \] Dobbiamo pero' verificare che questo discorso sia realmente valido, cioe' se io prendo $[a']=[a]$ e $[b']=[b]$ deve risultare $[a'+b']=[a+b]$ \begin{proof} Hp: $[a']=[a]$ e $[b']=[b]$\\ Ts: $[a'+b']=[a+b]$\\ \begin{align*} &a'-a=\lambda n \;\Rightarrow \; a'=\lambda n + a\\ &b'-b=\mu n \;\Rightarrow ; b'=\mu n +b\\ &(a'+b')-(a+b)=\lambda n + a + \mu n + b - a - b = (\lambda + \mu )n\\ &(a'+b')-(a+b)=(\lambda + \mu)n \; \Rightarrow \; (a'+b') \sim (a+b) \; \Rightarrow \; [a'+b']=[a+b] \end{align*} \end{proof} \subsubsection{Prodotto} \[ [a][b]=[ab] \] Ora verifichiamo che sia una definzione ben posta, cosi' come abbiamo fatto prima. \begin{proof} Hp: $[a']=[a], \;\;[b']=[b]$\\ Ts: $[a'b']=[ab]$\\ \begin{align*} &a'-a=\lambda n \;\Rightarrow \; a'=\lambda n + a\\ &b'-b=\mu n \;\Rightarrow ; b'=\mu n +b\\ &a'b'-ab=(\lambda n + a)(\mu n +b)-ab=\lambda\mu n^2+\lambda bn+a\mu n+ab-ab=n(\lambda\mu n + \lambda b + \mu a)\\ &a'b'-ab=n(\lambda\mu n + \lambda b + \mu a) \; \Rightarrow \; a'b' \sim ab\;\Rightarrow \; [a'b']=[ab] \end{align*} \end{proof} \oldsubsection{Proprieta'} La moltiplicazione e il prodotto formano un anello commutativo abeliano, ovvero godono delle seguenti otto proprieta': \begin{enumerate} \item $[a]+([b]+[c])=([a]+[b])+[c] \quad$ (associativa) \item $[a]+[b]=[b]+[a] \quad$ (commutativa) \item $[0]+[a]=[a]+[0]=[a] \quad$ (elem. neutro dell'addizione) \item $\exists\; [a'] \in \mathbb{Z}_n \;| \;[a]+[a']=[0] \quad $ (elem. opposto)\\ Inoltre $[a']=[n-a]=[-a]$ \item $[a]([b][c])=([a][b])[c] \quad$ (associativa) \item $[a][b]=[b][a] \quad$ (commutativa) \item $[a]([b]+[c])=[a][b]+[a][c] \quad$ (distributiva) \item $[1][a]=[a][1]=1 \quad$ (elem. neutro del prodotto) \end{enumerate} \subsection{Elementi invertibili} \begin{prop} \label{elementiinvertibiliinZn} In $\mathbb{Z}_n$ accade che $[a]_n$ e' invertibile se: \[ [a]_n \equiv \textrm{invertibile} \;\;\Leftrightarrow\;\; MCD(a,n)=1 \] Ovvero, se $a,n$ sono coprimi (primi fra loro, non hanno primi in comune).\\ Ricordiamoci che un elem. $[a]$ e' invertibile se $\exists\; [a'] \;|\; [a][a']=[1]$. \end{prop} \begin{proof} Dimostriamo $\Rightarrow $.\\ Hp: $[a]_n \equiv \textrm{invertibile}$\\ Ts: $MCD(a,n)=1$\\ Per definizione $\exists\; [a'] \;|\; [a][a']=[1]$. Ovvero, \begin{align*} &[aa']=[1]\; \Rightarrow \; aa'-1=\lambda n\\ &aa'-\lambda n=1 \end{align*} Adesso supponiamo che $d$ sia un divisore comune di $a$ e $n$, allora $d$ divide $aa'$, $d/_{aa'}$ e divide $\lambda n$. Ma allora a maggior ragione divide la loro differenza. Ma $aa'-\lambda n=1$, quindi $d$ divide $1$. Questo significa che necessariamente $d=1$. \end{proof} \begin{proof} Adesso dimostriamo $\Leftarrow $.\\ Hp: $MCD(a,n)=1$\\ Ts: $[a]_n \equiv \textrm{invertibile}$\\ Per Bezout possiamo scrivere: \[ 1=\lambda a + \mu n\] Ma allora: \[ [1]=[\lambda a] + [\mu n] = [\lambda a] + [0] = [\lambda a] = [\lambda][a] \] Cioe', \[ [1]=[a][\lambda] \] \end{proof} Una conseguenza di questo fatto e' che la legge dell'annullamente del prodotto vale solo in $\mathbb{Z}_p$ dove $p$ e' un numero primo. Ad esempio se in $\mathbb{Z}_{10}, \;\; [5][4]=[0]$. \subsubsection{Insieme degli invertibili} \label{sec:invertible_set} \[ U_n=\{\textrm{gli invertibili distinti di } \mathbb{Z}_n\} \] \subsection{Equazione modulare} \begin{prop}\label{equmodulareunica} \def\Z{{\mathbb{Z}}} Se $\MCD(a,n)=1$, allora l'equazione \[ ax=b\;\;(\Z_n) \] ammette una e una sola soluzione in $\Z_n$ \end{prop} \begin{proof} \def\Z{{\mathbb{Z}}} \eal{&(a,n)=1 \ubrace{\=}{\see{elementiinvertibiliinZn}} a\T{ e' invertibile in }\Z_n \= \exists \inv a \T{ in }\Z_n\\ &ax=b\;\;(\Z_n) \> \inv a a x = \inv a b \= x=\inv a b\;\;(\Z_n) } Vogliamo dimostrare che e' unica. Supponiamo per assurdo che esistano due soluzioni: \begin{align*} &\sist{ax_1=b\;\;(\Z_n)\\ ax_2=b\;\;(\Z_n)} \> ax_1=ax_2 \;\;(\Z_n) \> \inv a a x_1 =\inv a a x_2 \;\;(\Z_n) \= x_1 =x_2 \end{align*} \end{proof} \begin{prop} \def\Z{{\mathbb{Z}}} \eal{&ax=b\;\;(\Z_n)\T{ ammette soluzioni } \= (a,n)\div b } dove $(a,n)=\MCD(a,n)$ \end{prop} \begin{proof} \def\Z{{\mathbb{Z}}} \eal{&ax=b \;\;(\Z_n)\= ax-b=\mu n \ubrace{\=}{y=-\mu} ax + ny=b } Quest'ultima e' una equazione diofantea. Per quanto visto in \see{equazionidiofantea}, ammette soluzioni in $x,y$ se e solo se $(a,n)\div b$. \end{proof} \begin{prop} \label{soluzioneequmodulare} \def\Z{{\mathbb{Z}}} Sia $d=MCD(a,n)$. Se $d\div b$, allora l'equazione \eal{&ax=b\;\;(\Z_n) } ammette $d$ soluzioni distinte in $\Z_n$.\\ Data la soluzione $x_0$, tutte e sole le soluzioni sono: \[ x_i=x_0+\frac{n}{d}i\;\;i\in \mathbb{Z} %\;\;(\Z_n) \] Quelle distinte in $\Z_n$ si ottengono per $i=0,\dots,d-1$.\\ L'algoritmo per calcolarle e': \begin{enumerate} \item Per Bezout possiamo scrivere: \[ d=\lambda a + \mu n \] \item Quest'ultima e' un'equazione diofanteea che possiamo risolvere in diversi modi (vedi \ref{sec:eq_diof_sol}). Troviamo quindi $\lambda$ e $\mu$. \item Tutte le soluzioni saranno: \[ \begin{cases} x_0=\lambda \frac{b}{d} \;\;\mod n\\ x_i=x_0 + i\frac{n}{d}\;\;\mod n \end{cases} \] \item Le soluzioni distinte sono solo $d$, e cioe' $x_i$ per $ \;\;i=0,\dots,d-1$ \end{enumerate} \end{prop} \subsection{Sistemi lineari di congruenze} \subsubsection{Teorema cinese del resto} \def\Z{{\mathbb{Z}}} \begin{prop} Sia $(m_i,m_j)=1\;\;\forall i\neq j$ e sia dato il sistema \[ \begin{cases} a_1x=b_1\;\; (\mathbb{Z}_{m_1})\\ \vdots\\ a_nx=b_n\;\; (\mathbb{Z}_{m_t}) \end{cases}\;\;(1) \] tale che ogni equazione ammetta soluzione. Allora il sistema $(1)$ e' equivalente al sistema del tipo \[ \begin{cases} x=c_1\;\; (\mathbb{Z}_{m_1'})\\ \vdots\\ x=c_n\;\; (\mathbb{Z}_{m_t'}) \end{cases} \] dove $(m_i',m_j')=1\;\;\forall i\neq j$. \end{prop} \begin{proof} Ogni singola equazione del sistema e' risolvibile e quindi $d_i=(a_i,m_i)\div b_i$ (\vedi{soluzioneequmodulare}).\\ Dividendo ogni equazione per $d_i$, ci riconduciamo al sistema equivalente \eal{& \begin{cases} a_1'x=b_1'\;\; (\mathbb{Z}_{m_1'})\\ \vdots\\ a_n'x=b_n'\;\; (\mathbb{Z}_{m_t'}) \end{cases} } dove $a_i'=\frac{a_i}{d_i},\;b_i'=\frac{b_i}{d_i},\;m_i'=\frac{m_i}{d_i}$.\\ Continua a valere la condizione $(m_i',m_j')=1\;\;\forall i\neq j$. Inoltre, \eal{& \sist{d_i=(a_i,m_i)\\ a_i'=\frac{a_i}{d_i}\\ m_i'=\frac{m_i}{d_i} } \> (a_n',m_t')=1 } Quindi per la prop \see{equmodulareunica}, ogni equazione $i$ ammette un'unica soluzione in $\Z_{m_{i}'}$.\\ Risolvendo ogni singola equazione abbiamo il sistema: \[ \begin{cases} x=c_1\;\; (\mathbb{Z}_{m_1'})\\ \vdots\\ x=c_n\;\; (\mathbb{Z}_{m_t'}) \end{cases} \] \end{proof} \begin{thm}\label{thmcinesedelresto} \def\Z{{\mathbb{Z}}} Se $\MCD(m_i,m_j)=1\;\;\forall i\neq j$, allora il sistema \eal{& \begin{cases} x=c_1\;\; (\mathbb{Z}_{m_1})\\ \vdots\\ x=c_n\;\; (\mathbb{Z}_{m_t}) \end{cases} } ammette soluzioni. Non vale il viceversa.\\ Inoltre, tutte le soluzioni sono uguali in $\Z_R$, dove $R=m_1m_2\cdots m_t$.\\ Il metodo risolutivo e' esposto nella dimostrazione. \end{thm} \begin{proof} \def\Z{{\mathbb{Z}}} Poniamo \begin{align*} &R=m_1m_2\dots m_t = \mcm(m1,\dots,m_t)\\ &R_i=\frac{R}{m_i}=m_1\cdots m_{j-1}m_{j+1}\cdots m_t\\ \end{align*} Consideriamo l'equ: \[ R_ix_i=c_i\;\;(\mathbb{Z}_{m_i}) \] Questa equazione ha un unica soluzione (\vedi{equmodulareunica}), proprio perche' $R_i$ non contiene $m_i$, tutti gli $m_i$ sono coprimi e quindi $MCD(R_i,m_i)=1$.\\ La soluzione del sistema e': \[ x=x_1R_1+\dots+x_tR_t \] Per provare che questo e' vero consideriamo $[x]_{m_1}$, cioe': \[ x=x_1R_1+\dots+x_tR_t\;\;(\mathbb{Z}_{m_1}) \] Poiche' in $\mathbb{Z}_{m_1}$ tutti i $R_2,\dots,R_t$ sono 0, perche' multipli di $m_1$, si ha: \[ x=x_1R_1=c_1 \;\;(\mathbb{Z}_{m_1}) \] Lo stesso vale per tutte le altre equazioni: \[ x=c_i\;\;(\mathbb{Z}_{m_i}) \] questo vuol dire che ogni equazione del sistema originale e' soddisfatta.\\ Sia adesso $x$ una qualsiasi soluzione del sistema. Allora, tutte e sole le soluzioni del sistema sono: \[ x+\lambda R,\;\;\;\lambda\in \mathbb{Z} \] Infatti, in ogni $\mathbb{Z}_{m_i}$ succede che $R=0$ e quindi \[ x+\lambda R = x = c_i \;\;(\mathbb{Z}_{m_i}) \] Viceversa, se $y$ e' una soluzione del sistema allora \eal{&x=c_i=y\;\;(\mathbb{Z}_{m_i}) \;\;\forall i \= x- y = 0\;\;(\Z_{m_i})\;\;\forall i \=\\ & \= m_i\div x- y\;\;\forall i \ubrace{\>}{(m_i,m_j)=1\;\;\forall i \neq j} m_1m_2\cdots m_t \div x-y \= x-y=0 \;\;(\Z_{R}) \= y=x\;\;(\Z_{R}) } e quindi \eal{&y=x+\lambda R } \end{proof} \subsubsection{Applicazione del teorema cinese del resto} Il teorema cinese del resto puo' essere usato per dimostrare che la seguente funzione e' surriettiva, se e solo se $MCD(m,n)=1$: \[ f:\mathbb{Z} \longrightarrow \mathbb{Z}_m\times \mathbb{Z}_n \] \begin{proof} Dobbiamo dimostrare che: \[ \forall (\alpha, \beta) \in \mathbb{Z}_m\times\mathbb{Z}_n\;\;\exists x\in \mathbb{Z}: \;f(x)=(\alpha, \beta) \] Ovvero: \[ \begin{cases} x=\alpha\;\;(\mathbb{Z}_m)\\ x=\beta\;\;(\mathbb{Z}_n) \end{cases} \] Dato che $MCD(m,n)=1$, il teorema cinese del resto afferma che questo sistema ammette soluzioni. \end{proof} \subsubsection{Metodo di sostituzione} Un secondo metodo per risolvere i sistemi modulari consiste in: \begin{enumerate} \item prendere due equazioni del sistema \item convertirle in $\mathbb{Z}$ applicando la definizione di congruenza. Es: $y=5\;\;(\mathbb{Z}_7) \;\;\Rightarrow \;\;y=5+7\lambda$. \item eguagliare le due equazioni, ottenendo una equazione diofantea \item risolvere l'equazione diofantea ottenendo le due incognite $\lambda, \mu$ \item sostituendo una incognita in una delle due equazioni otteniamo un numero $n$. Ad esempio, se abbiamo trovato che $\lambda=9$, allora $n=5+7\cdot9$. \item Creiamo l'equazione: \[ y=n+h\cdot mcm(m_1,m_2) \] dove $h\in \mathbb{Z}$ e' un parametro variabile, e $m_1, m_2$ sono i moduli rispettivi delle nostre due equazioni precedenti. Tutte queste $y$, al variare di $h$ sono soluzione del sistema formato dalle due equazioni modulari. \item Se il sistema modulare era formato solo da due equazioni, abbiamo finito, altrimenti creiamo un sistema che comprende quest'ultima equazione e un'altra scelta dal sistema originale. \item Ora riandiamo al passo 2, e reiteriamo tutto questo procedimento fino a quando non possiamo piu' scegliere nuove equazioni dal sistema originale. \end{enumerate} % \item $\exists [a'] \in \mathbb{Z}_n | [a][a']=[1] \quad $ (elem. % inverso) \subsection{Altri sistemi di congruenze} \def\Z{{\mathbb{Z}}} \def\NN{\\& } % newline inside \eal{} \def\N{{\mathbb{N}}} \begin{prop}\label{propmodulodelmodulosedivisibile} \eal{&\sist{z'=z\;\;\Z_m\\n\div m} \> z'=z\;\;\Z_n } \end{prop} \begin{proof} \eal{& n\div m \> m=0\;\;\Z_n\;\;(1)\NN z'=z\;\;\Z_m \= \exists \mu:\;z'=z+\mu m \ubrace{\>}{(1)} z'=z+0\;\;\Z_n } \end{proof} \begin{exemp} \eal{&710923=7\;\;\Z_{12}\NN 7=1\;\;\Z_{3} } Utilizzando la prop \see{propmodulodelmodulosedivisibile} possiamo dire: \eal{&710923=1\;\;\Z_3} \end{exemp} \begin{prop}\label{sistemcongrm1divm2divmn} Possiamo sfruttare le idee della prop \see{propmodulodelmodulosedivisibile} per risolvere sistemi del tipo: \eal{&\sist{f_1(x)=0\;\;\Z_{m_1}\\ f_2(x)=0\;\;\Z_{m_2}\\ \vdots\\ f_n(x)=0\;\;\Z_{m_n}\\ }\NN f_i:\Z_{m_i}\longrightarrow \Z_{m_i}\;\;\forall i=1,\dots,n\NN m_i\div m_{i+1}\;\;\forall i =1,\dots,n-1 } Nota\footnote{$f_i$ e' una funzione definita su $\Z_{m_i}$ nel senso che: \eal{&x=y\;\;\Z_{m_i} \> f_i(x)=f_i(y)\NN x\in \Z \> f(x)=f([x]_{m_i})} Una tale $f_i$ potrebbe essere un polinomio, in quanto le operazioni $\cdot,+$ rispettano la congruenza. } Sia \eal{&X_1=\pgra{0\le x< m_1\;|\;\;f_1(x)=0\;\;\Z_{m_1}}\NN X_2=\pgra{x+\lambda m_1\;|\;0\le x+\lambda m_1 f_i(x)=0\;\;\Z_{m_i}\;\;\forall i=1,\dots,n\;\;(1') } Se $n=1$ allora $x\in X_n=X_1$, e quindi, per definizione di $X_1$, soddisfa l'unica equazione $f_1$.\\ Supponiamo $x\in X_{n+1}$, allora \eal{&x\in X_{n+1 } \> \exists \lambda:\;\;x=z+\lambda m_{n},\;z\in X_n,\;f_{n+1}(x)=0\;\;(1)\NN z\in X_{n} \ubrace{\>}{\T{Hp induttiva}} z\T{ soddisfa il sistema delle equazioni }f_1,\dots,f_n \= f_i(z)=0\;\Z_{m_i}\;\;\forall i=1,\dots,n\;\;(2)\NN m_i\div m_n \> z+\lambda m_{n}= z \;\;\Z_{m_i} \ubrace{\>}{(2),\;f_i\T{ definita su }\Z_{m_i}} f(x)=f(z+\lambda m_n) = f_i(z)=0\;\Z_{m_i}\;\;\forall i=1,\dots,n\;\;(3)\NN (1),(3)\> x\T{ soddisfa tutte le }n+1 \T{ equazioni} } Con la $(1')$ possiamo cosi' concludere che: \eal{&\exists x\in X_n, \lambda\in\Z \ubrace{\>}{m_i\div m_n} \> x+\lambda m_n = x \;\;\Z_{m_i}\;\;\forall i\le n \ubrace{\>}{f_i \T{ definita su }\Z_{m_i}} f_i(x+\lambda m_n)=f_i(x) \ubrace{=}{(1')} 0\;\;\forall i=1,\dots,n } Quindi $x+\lambda m_n$ e' una soluzione del sistema. \end{prova} \step{}{Dim $\($} \begin{prova} Viceversa, supponiamo che $y$ sia una soluzione del sistema e dimostriamo che $\exists x\in X_n,\;\exists \lambda\in \Z:\;\;y=x+\lambda m_n$. Procediamo per induzione su $n$.\\ Per $n=1$, \eal{&y\T{ soluzione } \> f_1(y)=0\;\;\Z_{m_1}\NN \T{Sia } \ove y= \min\pgra{ y'\in \N\;|\;y'=y\;\;\Z_{m_1}}\NN 0\le \ove y < m_1,\;\; y=\ove y +\mu m_1\NN 0=f_1(y) =f_1(\ove y+\mu m_1) \ubrace{=}{f_{1}\T{ definita su }\Z_{m_{1}}} f_1(\ove y) \NN \qq \> \ove y \in X_1\NN \T{Quindi ponendo } x=\ove y, \;\lambda = \mu\T{ abbiamo la tesi} } Caso $n+1$, \eal{&y\T{ soluzione } di f_1,\dots,f_{n+1} \> y\T{ soluzione di } f_1,\dots,f_n \ubrace{\>}{\T{Hp indutt.}} y=x+\lambda m_n,\T{ con }x\in X_n\;\;\NN \T{Sia } \ove y = \min\pgra{ y'\in \N\;|\;y'=y\;\;\Z_{m_{n+1}}}\;\;(1)\NN (1) \> 0\le \ove y < m_{n+1} (1.1)\NN (1)\> x+\lambda m_n= y = \ove y + \mu m_{n+1} \ubrace{\>}{m_n\div m_{n+1}} \ove y= x+ (\lambda+\mu^*)m_n,\;\;x\in X_n\;\;(1.2)\NN (1) \ubrace{\>}{f_{n+1}\T{ def. su }\Z_{m_{n+1}}} f_{n+1}(\ove y)=f_{n+1}(y) \ubrace{=}{y\T{ soluzione}} 0 \;\;Z_{m_{n+1}}(1.3)\NN (1.1), \;(1.2),\;(1.3) \> \ove y \in X_{n+1}\NN \sist{ \ove y \in X_{n+1}\\y = \ove y + \mu m_{n+1} } \T{ che e' la tesi} } \end{prova} \end{proof} \section{Equazioni diofantee} \begin{prop} \label{equazionidiofantea} \[ ax+by=c,\;\;\;a,x,b,y,c\in \mathbb{Z} \] e' una equazione diofantea. \\ Una equazione diofantea ha soluzioni (infinite) se e solo se: \[ MCD(a,b)/_c \] \end{prop} \begin{proof} Dimostriamo $\Rightarrow$.\\ Supponiamo che $(\alpha, \beta)$ e' una soluzione. \begin{align*} &a\alpha+b\beta = c\\ &d=MCD(a,b)\\ &a=md,\;\;b=nd\\ &md\alpha + nd\beta=c \;\;\Rightarrow \;\;d/_c \end{align*} Dimostriamo $\Leftarrow $.\\ \begin{align*} &d=ma+nb,\;\;d/_c\\ &dh=c\\ &dh=mha+nhb\\ &c=(mh)a+(nh)b \end{align*} $(mh)$ e $(nh)$ sono le soluzioni. \end{proof} \begin{proof} Adesso dimostriamo che ha infinite soluzioni. \begin{align*} &ax_0+by_0=c\\ &a(x_0+\lambda b)+b(y_0 + \lambda a)=c\\ &ax_0+a\lambda b+by_0-a\lambda b=ax_0+by_0=c \end{align*} \end{proof} Tutte le soluzioni di un equazione diofantea lineare sono del tipo: \[ (x_0 + \lambda\frac{b}{d}, y_0-\lambda\frac{a}{d}) \] dove $(x_0, y_0)$ e' una soluzione qualsiasi, $d=MCD(a,b)$ e $\lambda \in \mathbb{Z}$. \begin{proof} Dimostriamo che tutte le soluzioni sono di quel tipo.\\ Consideriamo un'altra soluzione $(x_1,y_1)$: \begin{align*} &ax_0+by_0=c\\ &ax_1+by_1=c\\ &ax_0+by_0=ax_1+by_1\\ &a(x_0-x_1)=b(y_1-y_0)\\ &\frac{a}{d}(x_0-x_1)=\frac{b}{d}(y_1-y_0)\\ &MCD(\frac{a}{d}, \frac{b}{d})=1 \end{align*} Scegliamo un primo $p$ tale che divida $\frac{a}{d}$. $p$ non dividera' $\frac{b}{d}$ perche' e' coprimo con $\frac{a}{d}$.\\ \begin{align*} &p/_\frac{a}{d} \;\Rightarrow \; p/_{\frac{a}{d}(x_0-x_1)}\\ &{\frac{a}{d}(x_0-x_1)}={\frac{b}{d}(y_1-y_0)}\;\Rightarrow \;p/_{\frac{b}{d}(y_1-y_0)} \end{align*} Ma $p$ non divide $\frac{b}{d}$, quindi deve per forza dividere $(y_1-y_0)$. Poiche' $\frac{a}{d}$ divide il secondo membro, e poiche' il suo divisore $p$ non divide $\frac{b}{d}$, allora dividera' solo $(y_1-y_0)$ Ovvero: \[ y_1-y_0=\mu \frac{a}{d} \] Ripetendo lo stesso discorso otteniamo: \[ x_0-x_1=\lambda \frac{b}{d} \] Sostituiamo cio' che abbiamo ottenuto in $a(x_0-x_1)=b(y_1-y_0)$: \begin{align*} &a\lambda \frac{b}{d}=b\mu \frac{a}{d}\\ &\lambda=\mu\\ &x_0-x_1=\lambda \frac{b}{d}\\ &y_1-y_0=\lambda \frac{a}{d} \end{align*} Cioe': \[ \begin{cases} x_1=x_0+\lambda \frac{b}{d}\\ y_1=y_0+\lambda \frac{a}{d} \end{cases} \] \end{proof} \subsubsection{Risoluzione} \label{sec:eq_diof_sol} Un primo metodo per risolve una diofantea e' quello di usare l'identita' di Bezout. Sappiamo che la soluzione esiste se \[ (d=MCD(a,b))/_c \;\;\Rightarrow \;\;c=hd \] Per Bezout: \[ d=ma+nb\;\Rightarrow \;hd=(mh)a+(nh)b\;\Rightarrow \;c=(mh)a+(nh)b \] Per trovare $m$ e $n$ si adotta l'algoritmo euclideo. \\ Un secondo metodo sfrutta l'aritmetica modulare: \begin{align*} &18n+35m=1000\\ &[18n+35m]=[1000]\;\; (\mathbb{Z}_{18})\\ &[18n]+[35m]=[1000]\;\; (\mathbb{Z}_{18})\\ &[17m]=[10]\;\; (\mathbb{Z}_{18})\\ &[-1m]=[10]\;\;(\mathbb{Z}_{18}) &[m]=[-10]=[8]\;\;(\mathbb{Z}_{18})\\ &m-8=\lambda 18\\ &m=8+\lambda18 \end{align*} Usiamo lo stesso sistema in $\mathbb{Z}_{35}$ e otteniamo: \[ n=5+\mu 35 \] Sostituiamo nell'equ originale: \begin{align*} &18(5+\mu 35)+35(8+\lambda18)=1000\\ &18\cdot35(\mu+\lambda)=630\\ &\mu+\lambda=1\\ &\lambda=1-\mu \end{align*} Adesso abbiamo legato $\mu$ a $\lambda$, e abbiamo tutte le soluzioni, cioe': \[ \begin{cases} n=5+35\mu\\ m=26-18\mu \end{cases} \] \section{I numeri primi} \subsection{La funzione di Eulero} \def\f{{\varphi}} \begin{defn} \label{funzionedieulero} Ecco la funzione di Eulero: \[ \varphi(n)=|U_n| \] Dove $U_n$ era stato definito in \see{sec:invertible_set}. In altre parole, $\phi(n)$ e' il numero di tutti i coprimi a $n$, minori di $n$. \end{defn} \def\Z{{\mathbb{Z}}} \begin{prop}\label{euleromoltiplicativo} Dati $m,n \in \mathbb{N}$ si ha \eal{&(m,n) =1 \> \f(mn)=\f(m)\f(n) } \end{prop} \begin{proof} $\mathbb{Z}_{mn}$ e $\mathbb{Z}_m\times\mathbb{Z}_n$ sono due insiemi che si possono legare da una applicazione biettiva, cioe': \eal{& f:\mathbb{Z}_{mn} \leftrightarrow \mathbb{Z}_m\times\mathbb{Z}_n\\ &[z]_{mn}\mapsto ([z]_m,[z]_n) } \begin{enumerate} \item Suriettivita':\\ \[ \forall (\alpha, \beta) \in \mathbb{Z}_m\times\mathbb{Z}_n\;\;\exists x\in \mathbb{Z}_{mn}: \;f(x)=(\alpha, \beta) \] Ovvero: \[ \begin{cases} x=\alpha\;\;(\mathbb{Z}_m)\\ x=\beta\;\;(\mathbb{Z}_n) \end{cases} \] Dato che $MCD(m,n)=1$, il teorema cinese del resto afferma che questo sistema ammette soluzioni (\vedi{thmcinesedelresto}). \item Iniettivita':\\ Presi $x,y\in \Z_{mn}$, dobbiamo dimostrare che $f(x)=f(y) \;\Rightarrow \;x=y$. \begin{align*} &f(x)=([x]_m,[x]_n)=f(y)=([y]_m,[y]_n)\;\Rightarrow \sist{x=y\;\;\Z_m\\ x=y\;\;\Z_n }\;\;(1) \end{align*} Consideriamo il sistema \eal{&\sist{\xi = y\;\;\Z_m\\ \xi = y\;\;\Z_n }\;\;(2) } Due soluzioni di $(2)$ sono $\xi=y$ e $\xi=x$ (per la $(1)$).\\ Sempre per il teorema cinese del resto tali soluzioni sono uguali in $\Z_{mn}$, e quindi \eal{&x=y\;\;\Z_{mn}} \end{enumerate} Sia data la seguente funzione \eal{&g:U_{mn}\longrightarrow U_m\*U_n\\ &g(x)=f(x) } Dimostriamo intanto che e' ben posta, ovvero che $g(x)\in U_m\*U_n\;\;\forall x\in U_{mn}$. \eal{&x\in U_{mn}\= x\T{ e' invertibile in } \Z_{mn}\ubrace{\=}{\see{elementiinvertibiliinZn}} (x,mn)=1\\ &g(x)=([x]_m,[x]_n)\in U_m\*U_n \=\sist{(x,m)=1\\ (x,n)=1} } se per assurdo $(x,m)=d \neq 1$, allora anche $(x,mn) \neq 1$, assurdo. Analogamente deve essere $(x,n)=1$. Quindi, $g$ e' ben posta.\\ Dimostriamo che $g$ e' biettiva. \begin{enumerate} \item Suriettivita': Sappiamo gia' che $f$ e' surriettiva, quindi \eal{&f\T{ surriettiva } \> \forall (a,b)\in U_m\*U_n\( \Z_m\*\Z_n\;\;\exists x \in \Z_{mn}:\;\;f(x)=(a,b)\= \sist{x=a\;\;\Z_m\\ x=b\;\;\Z_n } } Resta da dimostrare che $x\in U_{mn}$. \eal{&x\in U_{mn} \= x\T{ e' invertibile in } \Z_{mn} \ubrace{\=}{\see{elementiinvertibiliinZn}} (x,mn)=1\\ } Quindi basta dimostrare che $(x,mn)=1$. Supponiamo per assurdo che $\exists p\T{ primo: }p\div x,\;p\div mn$ \eal{ &a\in U_m\= (a,m)=1 \ubrace{\=}{x=a\;\;\Z_m}(x,m)=1 \\ &b\in U_n \= (b,n)=1 \ubrace{\=}{x=b\;\;\Z_n}(x,n)=1 \\ &\sist{p\div mn\\ p\T{ primo }} \> p\div m \| p\div n \ubrace{\>}{p\div x} \> (x,m) \neq 1 \| (x,n) \neq 1 } in ogni caso arriviamo ad un assurdo. \item Iniettivita':\\ essendo $f$ iniettiva, anche $g$ lo e'. \end{enumerate} In conclusione: \eal{&\sist{U_{mn} \leftrightarrow U_m\*U_n\\ U_{mn},\;U_m,\;U_n\T{ insiemi finiti} } \> |U_{mn}| = |U_m\*U_n| = |U_m| |U_n| \= \f(mn)=\f(m)\f(n) } che e' la tesi. \end{proof} \begin{prop}\label{formulafunzioneeulero} Sia $n\in \mathbb{N}$, allora \[ \varphi(n={p_1}^{m_1}{p_2}^{m_2}\dots {p_t}^{m_t})=n\left(1-{1 \over p_1}\right)\left(1-{1 \over p_2}\right)\dots\left(1-{1 \over p_t}\right) \] Dove ${p_1}^{m_1}{p_2}^{m_2}\dots {p_t}^{m_t}$, con $m_i>0$, e' la fattorizzazione di $n$. \end{prop} \begin{proof} Per la prop \see{euleromoltiplicativo} possiamo scrivere: \[ \varphi(n={p_1}^{m_1}{p_2}^{m_2}\dots {p_t}^{m_t})= \varphi({p_1}^{m_1})\varphi({p_2}^{m_2})\dots \varphi({p_t}^{m_t}) \] Adesso consideriamo un primo $p$ e un numero $m$ tale che: \[ m4$. \end{enumerate} \subsection{Teorema di Wilson} \[ p\equiv \textrm{primo} \;\;\Leftrightarrow \;\;(p-1)! = -1 \;\;(\mathbb{Z}_p)\;\;\Leftrightarrow \;\;(p-1)! = p-1 \;\;(\mathbb{Z}_p) \] \begin{proof} Dimostriamo $\Leftarrow $.\\ L'ipotesi, tradotta in $\mathbb{Z}$ e': \[ (p-1)!+1=\lambda p \] Supponiamo per assurdo che $p$ non e' primo, allora: \[ \exists 12\})\] $\mathbb{R}$ e' un campo ed e' anche un \emph{campo ordinato}, ovvero e' un insieme totalmente ordinato (TOTET) e valgono queste due proprieta': \begin{align*} &a\le b \> a+c\le b+c\\ &a\le b,\;c\ge 0 \> ac\le bc \end{align*} Per tutti i campi ordinati valgono queste due proprieta': \[ a\in K^{*} \Rightarrow a^2>0 \] \[ a>0 \;\Rightarrow \; -a<0 \] \section{L'insieme $\mathbb{C}$} \[ \mathbb{C}=\mathbb{R}\times \mathbb{R} \] Ecco fatto.\\ $\mathbb{C}$ e' un campo, ma non e' ordinato. \begin{proof} Dimostriamo che $\mathbb{C}$ non e' un campo ordinato.\\ Per assurdo supponiamo che esista una relazione d'ordine che trasforma $\mathbb{C}$ in un campo ordinato.\\ Allora per le proprieta' dei campi ordinati accade che: \begin{align*} &\forall z \in \mathbb{C}^{*}\;\;z^2>0\\ &z=(1,0)=1, \;\; 1=1^2>0 \;\Rightarrow\; -1<0\\ &i^2>0\;\;\Rightarrow \;\;-1>0 \end{align*} Le ultime due relazioni a destra sono in contrasto, quindi siamo arrivati a un assurdo. \end{proof} \subsection{Inverso} L'inverso di $(a,b)$ si calcola ponendo $(a,b)(x,y)=1$. Svolgendo quest'ultimo sistema lineare, otteniamo: \[ (x,y)=\left( \frac{a}{a^2+b^2} , -\frac{b}{a^2+b^2} \right) \] \subsection{Radici n-esime dell'unita'} Le radici ennesime complesse dell'unita' sono tutte quelle $x$ che $x^n=1$.\\ Chiameremo $U_n$ l'insieme di tutte queste radici.\\ Le radici ennesime dell'unita' godono di queste proprieta'.\\ Sia $u_{j_1}, u_{j_2}\in U_n$\\ \begin{enumerate} \item $u_{j_1} + u_{j_2} = u_{(j_1+j_2\mod n)}$ \item $u_{j_1}u_{j_2} = u_{(j_1j_2 \mod n)}$ \end{enumerate} \section{Polinomi} \subsection{Funzione polinomiale} Sia $K$ un campo. Una funzione $f:K\longrightarrow K$ si dice polinomiale se appartiente all'insieme di tutte le funzioni polinomiali, ovvero: \[ \I_k=\left\{ f:K\longrightarrow K|\;\exists d\in\mathbb{N}:\;\;a_0,\dots,a_d\in K| \;f(x)=a_0+a_1x+a_2x^2+\dots+a_dx^d,\;\;\forall x \in K\right\} \] Su $\I_k$ possiamo definire le operazioni di somma e prodotto. \subsection{Somma} \[ (f+g)(x)=f(x)+g(x) \] Ovvero, \[ f(x)=\sum_{i=0}^da_ix^i \] \[ g(x)=\sum_{i=0}^{d'} b_ix^i \] \[ (f+g)(x)=\sum_{i=0}^{\max(d,d')}(a_i+b_i)x^i \] \subsection{Prodotto} \[ (f\cdot g)(x)=f(x)g(x) \] Ovvero, \[ f(x)=\sum_{i=0}^da_ix^i\;\;\;\T{ con } a_i =0 \;\;\forall i > d \] \[ g(x)=\sum_{i=0}^{d'} b_ix^i\;\;\;\T{con }b_i =0 \;\;\forall i>d' \] \[ c_t=\sum_{i=0}^{t} a_ib_{t-i} \] \[ (f\cdot g)(x)=\sum_{i=0}^{d+d'}c_ix^i \] \par Con queste operazioni, $(\I_k,+,\cdot)$ e' un gruppo abeliano (+ ass, + comm, + elem. neutro, + opposto), e' un anello commutativo ($\cdot$ ass., $\cdot$ comm, $\cdot$ distr rispetto a $+$), e' un anello unitario (esiste l'elem. unita'), e poiche' esiste la legge dell'annullamento del prodtto e' un dominio di integrita'. \subsection{Polinomio} Consideriamo un campo $K$. \[ S_k=\left\{ s:\mathbb{N}\longrightarrow K \right\} \] $S_k$ e' l'insieme di tutte le funzioni che vanno da $\mathbb{N}$ a $K$, ovvero di tutte le successioni in $K$. Consideriamo ora un suo sottoinsieme $P_k \subset S_k$: \[ P_k=\left\{ s:N\longrightarrow K| \;\exists d\in \mathbb{N}:\;\;\forall m > d,\;\;s(m)=0 \right\} \] Ovvero, $P_k$ e' l'insieme delle successioni definitivamente nulle, cioe' di quelle successioni che a partire da un certo punto sono sempre $0$. \[ s=(s_0,s_1,\dots, s_d,0,0,0,\dots) \] Un polinomio a coefficienti in $K$ e' un elemento che appartiene a $P_k$.\\ Anche sui polinomi possiamo definire la somma e il prodotto: esattamente come abbiamo fatto prima. $(P_k,+,\cdot)$ e' un dominio di integrita', perche' gode delle nove proprieta'.\\ Ma cosa c'entra tutto questo con i polinomi usuali? Questa e' la risposta:\\ poniamo $a:=(a,0,0,0,\dots),\;\;\forall a \in K$ e diamo anche queste definizioni: \begin{align*} &x:=(0,1,0,0,0,\dots)\\ &x^2=x\cdot x =(0,1,0,0,0,\dots)(0,1,0,0,0,\dots)=(0,0,1,0,0,0,\dots)\\ &x^n=(0,\dots,\underbrace{1}_{\textrm{n+1 pos.}},0,\dots) \end{align*} Allora una qualsiasi successione $s \in P_k$, si puo' scrivere come: \begin{align*}s=&(a_0,a_1,\dots, a_d,0,0,0,\dots) \\=&(a_0,0,\dots)+(a_1,0,\dots)(0,1,0,\dots)+(a_2,0,\dots)(0,0,1,\dots)+&\\ &+\dots+(a_d,0,\dots)(0,0,\dots,\underbrace{1}_{\textrm{d+1 pos.}},0,\dots)\\ =&a_0+a_1x+a_2x^2+\dots+a_dx^d \end{align*} $P_k=K[x]$ e' l'anello dei polinomi a coefficienti in $K$ sulla indeterminata $x$.\\ Ovviamente i polinomi sono legati alle funzioni polinomiali, possiamo infatti far corrispondere a un polinomio $f(x)=a_0+a_1x+a_2x^2+\dots+a_dx^d$, la funzione polinomiale $f(\alpha)=a_0+a_1\alpha+a_2\alpha^2+\dots+a_d\alpha^d,\;\;\alpha\in K$. Consideriamo allora la funzione \[ \varphi: K[x] \longrightarrow \I_k,\;\;\;\varphi(f(x) ) = \textrm{funzione polinomialie definita da f(x)} \] che associa a ogni polinomio la sua funzione polinomiale corrispondente. Questa funzione e' sicuramente suriettiva, infatti, a ogni funzione polinomiale corrisponde il polinomio che ha gli stessi coefficienti. $\varphi$ non e' pero' sempre iniettiva, anzi, nei campi finiti non lo e' il piu' delle volte. Ad esempio, considerando in $\mathbb{Z}_3$: \begin{align*} &f(x)=x^3+x^2+x+1\quad g(x)=x^2+2x+1\\ &f(0)=0\quad g(0)=0\\ &f(1)=1\quad g(1)=1\\ &f(0)=0\quad g(0)=0 \end{align*} I polinomi $f(x), g(x)$ sono diversi tra loro, ma le funzioni polinomiali che gli corrispondono in $\mathbb{Z}_3$ sono uguali.\\ Se invece $K$ e' infinito, $\varphi$ e' anche iniettiva. \begin{proof} Proviamo l'iniettivita' di $\varphi$ in $K$, campo infinito $|K|=\infty$.\\ Dire che e' iniettiva equivale a: \[ \varphi(f(x))=\varphi(g(x) )\;\Rightarrow \; f(x)=g(x) \] Supponiamo per assurdo che $f(x)\neq g(x)$.\\ Scegliamo questa funzione: \[ F(x)=f(x)-g(x)\neq 0 \] Dire $\varphi(f(x))=\varphi(g(x) )$ equivale ad affermare che: \[ \forall \alpha\in K,\;\;\varphi(f(x))(\alpha)=\varphi(g(x))(\alpha)\=f(\alpha)=g(\alpha)\;\forall\alpha\in K \] Allora tutte le $\alpha$ sono radici di $F(x)$, ma questo e' in assurdo con il corollario del teorema di ruffini (\vedi{cor_ruff}), perche' vorrebbe dire che possiede infinite radici, invece, ruffini dice che ce ne sono al piu' $\deg F(x)$. Percio' $F(x)$ e' il polinomio nullo e quindi $f(x)=g(x)$ come polinomi. \end{proof} \subsection{Grado di un polinomio} Il grado di un polinomio \[ f(x)=a_0+a_1x+a_2x^2+\dots+a_dx^d \] e' il massimo $i \in \mathbb{N} \;|\; a_i\neq 0$ e si indica con $\deg f(x)$. Ad esempio, \[ \deg( 3^7+9x^2+0\cdot x^{19}-4x^3) = 3 \] Nota da questa definizione segue che il polinomio nullo non ha grado. \oldsubsubsection{Proprieta'} Dato $\deg f(x)=m, \;\deg g(x)=n$, con $f(x),g(x)\neq 0$, allora \begin{enumerate} \item $\deg f(x)+g(x)\le \max(m,n)$ \item $\deg f(x)g(x)=m+n$ \end{enumerate} \subsection{Polinomi invertibili} Gli unici polinomi invertibili sono i polinomi costanti non nulli, cioe' che hanno grado 0, ovvero tutti gli elementi che appartengono al campo $K$. \begin{proof} Se per assurdo un polinomio $f(x)$ con grado $m\ge 1$ fosse invertibile, allora esisterebbe $g(x) $ t.c. $f(x)g(x)=1$, ma questo e' impossibile perche' $\deg f(x)g(x)\ge 1$ \end{proof} Quindi in $\mathbb{R}[x]$ esistono infiniti invertibili, mentre in $\mathbb{Z}_p$ ne esistono $p-1$ ($p$ primo). \subsection{Algoritmo di divisione in $K[x]$} \label{divisionealgopolin} Cosi' come abbiamo fatto nei campi numerici, possiamo stabilire una relazione di divisione anche in $K[x]$, cioe', dati $f(x), g(x) \in K[x]$\[ f(x)/_{g(x)} \;\Leftrightarrow \; \exists h(x): \; g(x)=h(x) f(x) \] A questo punto possiamo dedurre molte delle proprieta' che avevamo visto in $\mathbb{Z}$. Ad esempio, possiamo ricavare l'algoritmo di divisione: \[ \forall f(x),g(x)\neq 0\in K[x] \; \exists! \;q(x), r(x) \in K[x] |\; f(x)=q(x)g(x)+r(x) \] e inoltre \[ r(x) = 0 \;\lor\; \deg r(x) < \deg g(x) \] \begin{proof} (non dimostriamo l'unicita').\\ Prendiamo i due polinomi: $f(x)=a_0+a_1x+\dots+a_mx^m$, e $g(x)=b_0+b_1x+\dots+b_nx^n$ e $m=\deg f(x), \;n=\deg g(x)$.\\ Se $f(x)$ e' il polinomio nullo, allora: $f(x)=0\cdot g(x)+0$. Se $mf(x)\T{ riducibile} \| q(x)=c\in F \ubrace{\>}{f(x)\T{ irriducibile}} q(x)=c\> f(x)=c(x-\a)\T{ ha $1$ } radice} Supponiamo allora che $f(x)$ sia riducibile.\\ Lavoriamo per induzione.\\ Base: $n=0$, il polinomio di grado $0$ ha $0$ radici.\\ Hp: tutti i polinomi di grado $n-1$ hanno al piu' $n-1$ radici.\\ Ts: Per Ruffini, il polinomio $f(x)$ con grado $n$, e' $f(x)=(x-\alpha)q(x)$. Poiche' $f(x)$ e' riducibile, si ha $\deg q(x)=n-1$, quindi per l'Hp induttiva, $q(x)$ ha al piu' $n-1$ radici. E in definitiva, essendo $\alpha$ una radice di $f(x)$, concludiamo che $f(x)$ ha al piu' $n$ radici. \end{proof} \subsection{Molteplicita'} Una radice $\alpha$ di $f(x)$ ha molteplicita' $m$ se: \[ f(x)=(x-\alpha)^mh(x) \] dove $h(x)\neq 0$.\\ Possiamo esprimere il corollario di ruffini dicendo che la somma delle molteplicita' delle radici di un $f(x)$ e' al piu' $\deg f(x)$. \subsection{Irriducibilita' di un polinomio in $\mathbb{C}[x]$} Un polinomio in $\mathbb{C}[x]$ e' irriducibile $\Leftrightarrow $ ha grado $1$. Ovvero, tutti i polinomi con grado $>1$ sono riducibili.\\ A questo risultato si arriva attraverso il teorema fondamentale dell'Algebra che dice che tutti i polinomi in $\mathbb{C}[x]$ di grado $\ge 1$ hanno almeno una radice.\\ Inoltre, sempre dal TFA possiamo affermare che $f(x) \in \mathbb{C}[x]$ ha esattamente $\deg f(x)$ radici. \begin{proof} Proviamo questo a partire dal TFA e usando l'induzione.\\ Base: per $n=1$, e' ovviamente vero.\\ Hp: tutti i polinomi di grado $m 2 \;\lor \; \left(\deg f(x) = 2 \;\land \;\Delta \ge 0\right)\] \begin{proof} Dimostriamo $\Leftarrow $.\\ Se e' di grado $1$ e' ovviamente irriducibile.\\ Se e' di grado $2$ e $\Delta < 0$, allora non ha radici in $\mathbb{R}$, quindi non puo' essere ridotto. \end{proof} \begin{proof} Sia $f(x)$ il nostro polinomio di grado $n$.\\ Dimostriamo $\Rightarrow $, facendo vedere che per \[n > 2 \;\lor \; \left(n = 2 \;\land \;\Delta \ge 0\right)\] e' riducibile. Se $n = 2 \;\land \;\Delta \ge 0$, allora $f(x)$ ha radici in $\mathbb{R}$ e quindi per il corollario di ruffini, puo' essere ridotto.\\ Adesso andiamo in $n> 2$. \\ Distinguiamo due casi: \begin{enumerate} \item Se $n$ e' dispari, e' della forma $n=2m+1,\;\;m\ge 1$. Per quando abbiamo visto prima, ogni radice complessa in $f(x)$ e' in coppia con il suo coniugato, quindi nel peggiori dei casi ci sarebbero $m$ coppie di radici complesse.\\ L'ultima radice rimanente $\alpha_m$ deve essere necessariamente reale perche' dato che non esistono piu' altre radici deve essere uguale alla sua coniugata (che e' sempre ammessa da $f(x)$, cioe': \[\alpha_m = \overline{\alpha_m}\] Ovvero: \[ (a,b)=(a,-b)\;\;\Rightarrow \;\;b=0 \] e quindi $\alpha_m \in \mathbb{R}$. \item Se $n$ e' pari allora distinguiamo due ulteriori casi: \begin{enumerate} \item $f(x)$ ammette delle radici in $\mathbb{R}$. In questo caso abbiamo finito, dato che per il corollario di ruffini e' riducibile. \item $f(x)$ ha solo radici complesse, cioe': \[ f(x)=(x-\alpha_1)(x-\overline{\alpha_1})\dots(x-\alpha_n)(x-\overline{\alpha_n}) \] Analizziamo $(x-\alpha_1)(x-\overline{\alpha_1})$: \begin{align*} (x-\alpha_1)(x-\overline{\alpha_1})=&\\ =&x^2-(\alpha_1+\overline{\alpha_1})x+\alpha_1\overline{\alpha_1} \end{align*} Ma poiche' $\alpha_1+\overline{\alpha_1} \in \mathbb{R}$ e $\alpha_1\overline{\alpha_1} \in \mathbb{R}$, allora \[ x^2-(\alpha_1+\overline{\alpha_1})x+\alpha_1\overline{\alpha_1} \in \mathbb{R}[x] \] Possiamo ripetere questo per tutti gli altri blocchi di coppie di radici complesse, ottenendo: \[ f(x)=\left(x^2-(\alpha_1+\overline{\alpha_1})x+\alpha_1\overline{\alpha_1}\right)\dots \left(x^2-(\alpha_n+\overline{\alpha_n})x+\alpha_n\overline{\alpha_n}\right) \] \end{enumerate} \end{enumerate} \end{proof} \subsection{Irriducibilita' di un polinomio in $\mathbb{Q}$} Dato $f(x) \in \mathbb{Q}[x]$, cioe': \[ f(x)=\frac{a_0}{b_0}+\frac{a_1}{b_1}x+\dots+\frac{a_n}{b_n}x^n \] possiamo ricondurlo come prodotto di un polinomio con i coefficienti in $\mathbb{Z}$ per una costante, cioe': \[ f(x)=\frac{1}{m}\left(a_0'+a_1'x+\dots+a_n'x^n\right) \] Dove $m$ e' il mcm tra $b_0, \dots, b_n$ e \[a_i'=a_i\frac{m}{b_i}\]. Le radici di $f(x)$ si ottengono con questo procedimento: \begin{align*} &D_0=\left\{\textrm{divisori di $a_0'$} \right\}\\ &D_n=\left\{\textrm{divisori di $a_n'$} \right\}\\ &S=\left\{ \frac{\alpha}{\beta} \;\Big| \;\alpha \in D_0,\;\beta \in D_n \right\}\\ &R=\left\{ \textrm{ Radici razionali di $f(x)$ } \right\}\\ &R \subseteq S \end{align*} Se si trovano le radici del polinomio, allora per ruffini si puo' ridurre, pero' se non si trovano non c'e' alcun modo per sapere se si puo' ridurre o no. \begin{proof} Dimostriamo che le radici razionali di $f(x)= a_0+a_1x+\dots+a_nx^n\in \mathbb{Z}[x]$ sono contenute nell'insieme $S$, ovvero, dati $r,s \in \mathbb{Z}:\;MCD(r,s)=1$, \[ f\left(\frac{r}{s}\right)=0 \;\Rightarrow \; r/_{a_0}, s/_{a_n} \] quindi, per Hp: \begin{align*} &a_0+a_1{\frac{r}{s} }+\dots+a_n{\left(\frac{r}{s} \right)}^n=0\\ &a_0s^n+a_1s^{n-1}r+\dots+a_nr^n=0\\ &a_nr^n=-s(a_0s^{n-1}+a_1s^{d-2}+\dots+a_{n-1}) \end{align*} Prendiamo un primo $p:\; p/_s$, ovvero un divisore di $s$. $p$ divide il secondo membro e quindi divide anche il primo, cioe' $p/_{a_nr^n}$, poiche' $MCD(r,s)=1$ deduciamo che $p$, divisore di $s$, deve necessariamente dividere $a_n$. Poiche' possiamo ripetere lo stesso ragionamento per tutti i divisori di $s$ deduciamo che $s/_{a_n}$. Analogamente si vede che $r/_{a_0}$ \end{proof} \subsection{Polinomio primitivo} \begin{defn} \label{defpolprimitivo} Dato $f(x)= a_0+a_1x+\dots+a_nx^n \in \mathbb{Z}[x]$, il contenuto di $f(x)$ e' \[ c(f)=MCD(a_0, \dots, a_n) \] Se $c(f)=1$, allora si dice che $f(x)$ e' un polinomio primitivo. Dato un polinomio non primitivo $f(x)$, lo possiamo esprimere come: \label{pol_prim} \[ f(x)=c(f)f'(x) \] basta mettere in evidenza il MCD dei coefficienti di $f(x)$ e ottenere quindi $f'(x)$. $f'(x)$ sara' primitivo. \end{defn} \subsection{Lemma di Gauss} \label{lemma_del_gaussino} \[f(x), g(x) \in \mathbb{Z}[x], \;c(f)=1, \;c(g)=1\;\Rightarrow \;c\left( f(x)g(x) \right)= 1 \] \begin{proof} Dimostriamolo per assurdo.\\ Dati: \[ f(x)=a_0+a_1x+\dots+a_ix^i \] \[ g(x)=b_0+b_1x+\dots+b_jx^j \] \[ f(x)g(x)=c_0+c_1x+\dots+c_{i+j}x^{i+j} \] \[ d=MCD(c_0,c_1,\dots,c_{i+j})\neq 1 \] Sia $p$ primo tale che $p/_{d}$, allora $p/_{c_i}\;\forall i$. Poiche' $c(f)=1$, ci sara' una $a_i$ che non e' divisa da $p$, analogamente ci sara' una $b_j$ che non e' divisa da $p$, allora dato che \[ c_{i+j}=\left(a_0b_{i+j}+a_1b_{i+j-1}+\dots\right)+a_{i}b_j+\left(\dots+a_{i+j}b_j\right) \] e che $p/_{c_{i+j} }$ e che $p$ divide la prima parentesi e la seconda allora $p$ deve dividere anche $a_{i}b_j$. Poiche' $p$ e' primo, possono accadere due casi: \[ p/_{a_i} \;\lor \; p/_{b_j} \] ma tutte e due casi sono assurdi. \end{proof} \subsection{Corollario del lemma di Gauss} \label{corlemgauss} \[ c(f\cdot g) = c(f)c(g) \] \begin{proof} Possiamo scrivere i due polinomi come abbiamo visto in \ref{pol_prim}: \begin{align*} &f(x)=c(f)f'(x)\\ &g(x)=c(g)g'(x) \end{align*} Moltiplichiamo membro a mebro e otteniamo: \[f(x)g(x)=c(f)c(g)f'(x)g'(x)\] Inoltre, \[ c(c(f)c(g)f'(x)g'(x) )= c(f)c(g)\cdot 1 \] ($c(f'(x)g'(x) )=1$ perche' $f'$ e $g'$ sono primitivi). allora ecco la tesi: \[ c(f(x)g(x ) )=c(c(f)c(g)f'(x)g'(x) )=c(f)c(g) \] \end{proof} \subsection{Irriducibilita' in $\mathbb{Z}[x]$ e $\mathbb{Q}[x]$} \begin{prop} \label{irriducinZestirriducinQ} Se $f(x)\in \mathbb{Z}[x]$ e' primitivo allora: \[ f \textrm{ irriducibile in } \mathbb{Z}[x] \;\Leftrightarrow \; \textrm{ irriducibile in } \mathbb{Q}[x] \] \end{prop} \begin{proof} Dim $\Rightarrow $.\\ Per asssurdo supponiamo che $f(x)\in \mathbb{Q}[x]$ sia riducibile, ovvero: \[ f(x)=h(x)g(x),\;\;h(x), g(x) \in \mathbb{Q}[x] \] \[ \deg h(x) , \deg g(x) > 0 \] Riesprimiamo in $\mathbb{Z}$ $h$ e $g$: \begin{align*} &h(x)=\frac{a}{b}h'(x),\;\;h'(x)\in \mathbb{Z}[x], \;\textrm{primitivo}\\ &g(x)=\frac{c}{d}g'(x),\;\;g'(x)\in \mathbb{Z}[x], \;\textrm{primitivo} \end{align*} sostituiamo: \[ f(x)=\frac{a}{b}h'(x)\frac{c}{d}g'(x) \] normalizziamo: \[ bdf(x)=ach'(x)g'(x) \] prendiamo il contenuto del primo e del secondo membro: \begin{align*} &c(bdf(x) )=bd\;\;\textrm{perche' f(x), per Hp e' primitivo, bd e' una costante}\\ &c(ach'(x)g'(x) )=ac\;\textrm{i polin $h', g'$ sono primitivi}\\ &bd=ac\;\Rightarrow \;bdf(x)=bdh'(x)g'(x)\;\Rightarrow \;f(x)=h'(x)g'(x)\in \mathbb{Z}[x] \end{align*} ma $f(x)=h'(x)g'(x)$ e' assurdo perche' abbiamo supposto che fosse irriducibile in $\mathbb{Z}[x]$ \end{proof} \begin{proof} Dim $\Leftarrow $.\\ Supponiamo per assurdo che $f$ e' riducibile in $\mathbb{Z}[x]$, quindi: \[ f(x)=h(x)g(x)\;\;h(x),g(x) \in \mathbb{Z}[x] \] \[ h(x)\neq \pm 1\;\;g(x)\neq \pm 1 \] Inoltre $\deg h(x), \deg g(x)$ devono essere necessariamente $>0$, infatti, se fosse $\deg h(x)=0\;\Rightarrow \;h(x)=h\neq \pm1\in\mathbb{Z}$ il che' implicherebbe che $f(x)$ non e' primitivo, contro ipotesi. Quindi: \[ \deg h(x), \deg g(x)>0 \] Poiche' possiamo pensare $g(x),h(x)$ come polinomi di $\mathbb{Q}[x]$,cioe': \[ g(x), h(x)\in \mathbb{Z}[x]\subset \mathbb{Q}[x] \] segue che: $f(x)$ e' riducibile in $\mathbb{Q}[x]$, e questo e' assurdo, contro l'Hp iniziale. \end{proof} \subsection{Teorema di Gauss} \label{ThmGaussdimoZ} Per qualunque dominio $D$ che sia UFD (dominio a fattorizzazione unica), vale che $D[x]$ e' UFD. \begin{proof} Dimostreremo il teorema solo per $\mathbb{Z}[x]$.\\ Dato $f(x)\in\mathbb{Z}[x]$, possiamo esprimerlo come \[ f(x)=c(f)f'(x) \] $c(f) \in \mathbb{Z}$ e' un numero intero, quindi si puo' fattorizzare. Resta quindi da fattorizzare $f'(x)$, polinomio primitivo.\\ Sappiamo che in $\mathbb{Q}[x]$ e' fattorizzabile, quindi: \[ f'(x)=q_1(x)\dots q_t(x),\;\;q_i(x)\in \mathbb{Q}[x] \] Mettiamo in evidenza al solito modo il MCD dei coeeficienti di $q_i$: \[ f'(x)=\frac{a_1}{b_1}q_1'(x)\dots \frac{a_t}{b_t}q_t'(x),\;\;q_i'(x)\in \mathbb{Z}[x] \] dove $b_i$ e' il mcm dei denominatori dei coefficienti di $q_i(x)$, e $a_i$ e' il contenuto di $\frac{b_i}{b_i}q_i(x)$.\\ Normalizziamo: \[ b_1\cdots b_tf'(x)=a_1\cdots a_t q_1'(x)\dots q_t'(x) \] tenendo a mente che $f'(x), q_i'(x)$ sono primitivi, prendendo i contenuti di ambo i membri otteniamo: \[ b_1\cdots b_t = a_1 \cdots a_t \] e quindi \[ f'(x)=q_1'(x)\dots q_t'(x) \] ed ecco che abbiamo fattorizzato $f'(x)$ in $\mathbb{Z}[x]$. \end{proof} \subsection{Criterio di Eisenstein} \label{Eisenstein} Sia \[f(x)=a_0+a_1x+\dots+a_dx^d\;\in\mathbb{Z}[x]\] e sia primitivo, allora \[ \begin{cases} f \equiv \textrm{ primitivo}\\ \exists p, \textrm{primo}: \; p/_{a_i},\;i=0,\dots,d-1\\ p^2\nmid_{a_0} \end{cases} \;\Rightarrow \; f(x)\equiv\textrm{irriducibile in }\mathbb{Z}[x], \mathbb{Q}[x] \] \begin{proof} Supponiamo che per assurdo $f(x)$ sia riducibile, ovvero che: \[ f(x)=g(x)h(x) \] \[ g(x)=b_0+b_1x+\dots+b_rx^r,\;\;h(x)=c_0+c_1x+\dots+c_sx^s \] \[ 0 D \T{ dominio }} \end{prop} \begin{proof} Se $a\neq 0, \;\;ab=0$, allora, poiche' siamo in un corpo $\exists a^{-1}$ e quindi: \[ a^{-1}ab=a^{-1}0\;\Rightarrow \;b=0 \] \end{proof} Un teorema afferma che ogni corpo finito e' un campo. \subsection{I quaternioni} I quaternioni sono un corpo infinito non commutativo, ovvero non sono un campo. I quaternioni sono stati inventati come generalizzazioni dei numeri complessi e sono descritti dal seguente insieme di matrici $2\times 2$: \[ \mathbb{Q}_R = \left\{ \begin{pmatrix} \alpha &\beta\\ -\overline{\beta} & \overline{\alpha} \end{pmatrix} \Big| \;\alpha,\beta \in \mathbb{C} \right\} \] Per verificare che i quaternioni sono un campo, dobbiamo controllare prima di tutto che le operazioni tra due elementi sono delle operazioni interne: \[ \begin{pmatrix} \alpha &\beta\\ -\overline{\beta} & \overline{\alpha} \end{pmatrix} + \begin{pmatrix} \gamma & \delta\\ -\overline{\delta} & \overline{\gamma} \end{pmatrix} = \begin{pmatrix} \alpha+\gamma&\beta+\delta\\ -\overline{\beta}-\overline{\delta} &\overline{\alpha}+\overline{\gamma} \end{pmatrix} = \begin{pmatrix} \alpha+\gamma&\beta+\delta\\ -\overline{\beta + \delta} &\overline{\alpha+ \gamma} \end{pmatrix} \] \[ \begin{pmatrix} \alpha &\beta\\ -\overline{\beta} & \overline{\alpha} \end{pmatrix} \begin{pmatrix} \gamma & \delta\\ -\overline{\delta} & \overline{\gamma} \end{pmatrix} = \begin{pmatrix} \alpha\gamma-\beta\overline{\delta}& \alpha\delta+\beta\overline{\gamma}\\ -\overline{\beta}\gamma-\overline{\alpha}\overline{\delta} & -\overline{\beta}\delta+\overline{\alpha} \overline{\gamma} \end{pmatrix}= \begin{pmatrix} \alpha\gamma-\beta\overline{\delta}& \alpha\delta+\beta\overline{\gamma}\\ -(\overline{\alpha\delta+\beta\overline{\gamma}}) & \overline{\alpha\gamma-\beta\overline{\delta}} \end{pmatrix} \] Le 8 proprieta' si verificano facilmente, anche perche', valendo nell'anello delle matrici quadrate $2\times2$ valgono anche qui. Verifichiamo quindi che tutti gli elementi diversi dall'elemento nullo sono invertibili. Poiche' una matrice e' invertibile sse il suo det e' diverso da zero, controlliamo \[ \begin{vmatrix} \alpha &\beta\\ -\overline{\beta} & \overline{\alpha} \end{vmatrix}= \alpha\overline{\alpha}+\beta\overline{\beta} \neq 0 \] Poiche' $(a+ib)(a-ib)=a^2+b^2$, allora \[ \alpha\overline{\alpha}+\beta\overline{\beta}=a^2+b^2+c^2+d^2 \] che e' $=0$ solo per $a=b=c=d=0$.\\ Per dimostrare che questo corpo non e' commutativo basta portare un esempio: \[ \begin{pmatrix} 0&1\\-1&0 \end{pmatrix}\begin{pmatrix} i&0\\0&-i \end{pmatrix}=\begin{pmatrix} 0&-i\\-i&0 \end{pmatrix}\;\neq \; \begin{pmatrix} i&0\\0&-i \end{pmatrix}\begin{pmatrix} 0&1\\-1&0 \end{pmatrix}=\begin{pmatrix} 0&i\\ i&0 \end{pmatrix} \] I quaternioni possono essere scritti in forma algebrica ponendo: \[ \begin{pmatrix} 1&0\\0&1 \end{pmatrix}=1\quad\begin{pmatrix} 0&1\\-1&0 \end{pmatrix}=j\quad\begin{pmatrix} i&0\\0&-i \end{pmatrix}=i\quad \begin{pmatrix} 0&i\\ i&0 \end{pmatrix}=k \] e quindi avendo $\alpha=a+ib,\;\;\beta=c+id$: \[ \mathbb{Q}_R=\left\{a+ib+jc+kd|\;a,b,c,d\in \mathbb{R}\right\} \] \subsection{Domini finiti} Ogni dominio finito e' un campo.\\ Ovvero in ogni anello commutativo finito in cui vale la legge dell'annullamento del prodotto e' un campo, cioe' tutti gli elementi diversi da 0 ammettono l'inverso. Formalmente: \[ D\equiv\textrm{ dominio},\;|D|=n\in\mathbb{N}\;\Rightarrow \; D\equiv\textrm{ campo} \] \begin{proof} Prima di tutto dobbiamo mostrare che $D$ possiede l'elemento unita' del prodotto.\\ Se $D$ e' finito e ha $n$ elementi possiamo scrivere: \[ D=\{ a_1, \dots, a_n \} \] Prendiamo un qualsiasi $a\neq 0\in D$ e consideriamo questo suo sottoinsieme: \[ C=\{ aa_1, \dots, aa_n \} \] (abbiamo moltiplicato tutti gli elementi di $D$ per $a$).\\ Due elementi di $C$ non coincidono mai, infatti, per assurdo: \begin{align*} &a_i\neq a_j\;\;i\neq j\\ &aa_i=aa_j\\ &a(a_i-a_j)=0\;\Rightarrow \;a_i=a_j \end{align*} Quindi $|C|=n$ e quindi $C=D$. Allora, dato che $a \in D$, possiamo scrivere: \[ a = aa_u \] Quindi $a_u$ e' un elemento unitario. Dobbiamo dimostrare pero' che e' unitario anche per tutti gli altri elementi di $D$, cioe' \begin{align*} &\forall b\in D\;\Rightarrow \;b\in C\;\Rightarrow \;b=aa_k\\ &ba_u=aa_ka_u\\ &ba_u=aa_ua_k=aa_k=b\;\Rightarrow \;ba_u=b \end{align*} Ok, poniamo $1:=a_u$ e adesso mostriamo che tutti gli elementi di $D$ diversi da zero sono invertibili, infatti, \begin{align*} &1 \in D\;\Rightarrow \; 1 \in C\;\Rightarrow \; 1=aa_t\\ &1=aa_t\;\Rightarrow \;a^{-1}=a_t \end{align*} In questo caso, abbiamo visto che $a$ ha l'inverso, ma inizialmente, $a$ e' stato scelto come un elemento qualsiasi di $D$, quindi ogni elemento di $D$ ha l'inverso. \end{proof} \subsection{Sottoanello} Un sottoanello $(S,+,\cdot)$ di $(A,+,\cdot)$ e' un sottoinsieme $S\subseteq A$ che mantiene le stesse operazioni di $A$ su se stesso. \\ Per verificare che $S$ sia un sottoanello basta controllare le seguenti tre proprieta', tutte le altre sono poi conseguenza del fatto che $S$ e' un sottoinsieme di $A$: \begin{enumerate} \item Dobbiamo verificare che le operazioni sono interne a $S$, cioe', $\forall x,y\in S$, \[ x+y\in S\;\;\land \;\; xy\in S \] \item Deve esistere lo zero in $S$: \[\exists 0 \in S\] \item e l'opposto di ogni elemento di $S$: \[\forall s \in S\;\;\exists -s \in S\] \end{enumerate} \begin{prop} \label{caratt2sottoanello} Dato $S\subseteq A$, si ha \eal{& S\T{ sottoanello di }A \= \forall x,y\in S\;\sist{ x-y\in S\\ xy\in S } } \end{prop} \begin{proof} infatti, \begin{align*} &x-x \in S\;\Rightarrow \;0\in S\\ &x-(-y) \in S \; \Rightarrow \; x+y \in S\\ &0-y\in S \;\Rightarrow \; \exists -y \in S \end{align*} \end{proof} \subsection{Omomorfismo} Consideriamo ora particolari applicazioni tra anelli.\\ Dati due anelli $(A,+,\cdot)$, $(A',+,\cdot)$ (con le loro rispettive operazioni che possono anche essere diverse), una applicazione \[ f:A\longrightarrow A' \] e' un \emph{omomorfismo}, se \[ f\equiv \textrm{ omomorfismo}\;\Leftrightarrow \;\forall x,y\in A\;\begin{cases} f(x+y)=f(x)+f(y)\\ f(xy)=f(x)f(y) \end{cases} \] L'\emph{omomorfismo nullo} e' $f(a)=0\;\forall a\in A$.\\ Se l'applicazione $f$ e' iniettiva, allora si dice che $f$ e' una \emph{immersione}.\\ Se l'applicazione $f$ e' surriettiva, allora si dice che $f$ e' una \emph{surriezione}.\\ Se l'applicazione $f$ e' biettiva, allora si dice che $f$ e' un \emph{isomorfismo}.\\ \oldsubsubsection{Proprieta'} \begin{enumerate} \item $f(0)=0' \in A'$ \begin{proof} \begin{align*} &f(0)=f(0+0)=f(0)+f(0)\\ &f(0)=f(0)+f(0)\\ &f(0)-f(0)=f(0)+f(0)-f(0)\\ &f(0)=0' \end{align*} \end{proof} \item $f(-a)=-f(a)$ \begin{proof} \begin{align*} &f(-a)=-f(a)\\ &f(-a)+f(a)=0'\\ &f(-a+a)=f(0)=0' \end{align*} \end{proof} \end{enumerate} \begin{prop} \label{propunitapreservatadaf} Dato $f:A\longrightarrow A'$ omomorfismo. In generale la proprieta' $f(1_A)=1_A'$ non vale, si hanno pero' questi due risultati: \eal{&1.\;\;A,A'\T{ domini unitari, }\Im f \neq \pgra{0} \> f(1_A)=1_{A'}\\ &2.\;\;f\T{ surriettiva } \> f(1_A)=1_{A'} } \end{prop} \begin{proof} \step{}{Dim. $1.$} \begin{prova} \begin{align*} &f(1)=f(1\cdot1)=f(1)f(1)\\ &f(1)-f(1)f(1)=0\\ &f(1)(1-f(1))=0\;\Rightarrow \;f(1)=1 \end{align*} Nota che $f(1)\neq 0$, infatti, se per assurdo lo fosse: \begin{align*} &f(1)=0\;\Rightarrow \;f(a)=f(a\cdot1)=f(a)f(1)=0\;\Rightarrow \;f(a)=0\;\forall a \in A \end{align*} e questo e' assurdo contro l'Hp che $f$ e' un omomorfismo non nullo. \end{prova} \step{}{Dim. $2.$} \begin{prova} $f(1)=u'\in A'$, poiche' $f$ e' surriettiva, allora $a'\in A',\;a'=f(a)$ per qualche $a\in A$, quindi \begin{align*} &a'u'=f(a)f(1)=f(a)=a'\\ &a'u'=a' \end{align*} Percio' $f(1)=u'$ e' l'unita' di $A'$. \end{prova} \end{proof} \begin{prop} \label{propinvdifdia} Dato $f:A\longrightarrow A'$ omomorfismo, e preso $a\in A$, si ha \eal{&f(1_A)=1_{A'},\;\;\exists \inv a \> \inv{f(a)}=f(\inv a)} \end{prop} \begin{proof} \eal{&f(a)f(\inv a) \ubrace{=}{f\T{ omomorfismo}} f(a\inv a) = f(1_A) \ubrace{=}{Hp} 1_{A'} \\ &f(\inv a)f(a)=f(1) = 1_{A'}} Quindi $f(\inv a)$ e' l'inverso di $f(a)$, ovvero \eal{& \inv{f(a)}=f(\inv a) } \end{proof} \begin{prop} Sia $f:K\longrightarrow A'$ un omomorfismo, dove $K$ e' un campo, e $A'$ un anello, allora \eal{&\Im f \neq \pgra{0} \> f\T{ iniettiva } } \end{prop} \begin{proof} Vedi \see{fomodacampoadanelloestiniettiva}. \end{proof} \subsection{Immagine e nucleo} Dato l'omomorfismo $f:A\longrightarrow A'$, \[ \textrm{Immagine di f}:=\Im f:= \{a' \in A'| \;\exists a \in A: \;f(a)=a'\} \] \[ \textrm{nucleo di f}:=\ker f:=\{a\in A|\;f(a)=0'\in A'\} \] Sicuramente $\Im f, \ker f$ non sono vuoti, perche' contengono almeno $0', 0$.\\ Valgono le seguenti proprieta' \begin{enumerate} \item $\ker f$ e' un sottoanello di $A$, \[ \ker f \le A \] \begin{proof} \begin{align*} &x,y\in \ker f \;\Leftrightarrow \; f(x)=f(y)=0\\ &x-y\in \ker f ? \textrm{ Si, infatti}\\ &\quad f(x-y)=f(x)-f(y)=0\\ &xy\in \ker f ? \textrm{ Si, infatti}\\ &\quad f(xy)=f(x)f(y)=0 \end{align*} \end{proof} \item Questa e' una proprieta' piu' forte della precedente \[\forall x\in \ker f,\;\forall a\in A\;\Rightarrow \;xa,ax\in \ker f\] Ovvero $\ker f$ e' un ideale di $A$ (vedi \ref{ideale_yea}): \[\ker f \triangleleft A\]. \begin{proof} \[ f(xy)=\underbrace{f(x)}_{0}f(y)=0 \] \end{proof} \item $\Im f$ e' un sottoanello di $A'$. \[ \Im f \le A' \] \begin{proof} \begin{align*} & x',y' \in \Im f\;\Leftrightarrow \; \exists x,y\in A:\;f(x)=x',f(y)=y'\\ &x'-y'\in \Im f ? \textrm{ Si, infatti}\\ &\quad x'-y'=f(x)-f(y)=f(x-y) \in \Im f\\ &x'y'\in \Im f ? \textrm{ Si, infatti}\\ &\quad f(x'y')=f(x)f(y)=f(xy)\in \Im f \end{align*} \end{proof} \item La composizione di omomorfismi e' un omomorfismo, cioe' dati tre anelli $A, A', A''$ e \[ f:A\longrightarrow A'\;\;g:A'\longrightarrow A'' \] $g\circ f:A\longrightarrow A''$ e' un omomorfismo, infatti, \begin{proof} \begin{align*} &g(f(x+y))=g(f(x)+f(y))=g(f(x))+g(f(y))\\ &g(f(xy))=g(f(x)f(y))=g(f(x))g(f(y)) \end{align*} \end{proof} \item $f$ e' un omomorfismo iniettivo (immersione), se \[ f\equiv\textrm{ immersione}\;\Leftrightarrow \; \ker f = \{ 0\} \] Cioe', se l'unico elemento di $\ker f$ e' lo zero di $A$. \begin{proof} Dim $\Rightarrow $.\\ $f(0)=0'$, e poiche' $f$ e' iniettiva, allora lo zero l'unico elemento $0\rightarrow 0'$.\\ Dim $\Leftarrow $.\\ Dobbiamo dimostrare che \[\forall x, y\in A\; f(x)=f(y)\;\Rightarrow \;x=y\] Se $f(x)=f(y)$, allora \[ f(x)-f(y)=0\;\Rightarrow \;f(x-y)=0\;\Rightarrow \;x-y\in \ker f \] e poiche' $\ker f= \{0\}\;\Rightarrow \;x=y$ \end{proof} \end{enumerate} \subsection{Anello quoziente} Sia $A$ un anello e $S \le A$. Stabiliamo adesso la seguente rel. d'equivalenza tra due elementi del sottoanello $S$ di $A$.\\ \[ x,y\in A\;\;x\sim y \;\Leftrightarrow \;x-y\in S \] E' facile verificare che e' una rel d'equ \begin{proof} \[x\sim x\;\Leftrightarrow \;x-x=0 \in S\] e dato che $S$ e' un sottoanello $0\in S$ e' vera. \[ x\sim y \Rightarrow y\sim x \] infatti \begin{align*} &x\sim y \;\Leftrightarrow \;x-y\in S\\ &-(x-y)\in S\;\Rightarrow \; y-x\in S\;\Rightarrow \;y\sim x \end{align*} \[ x\sim y\land y\sim z\;\Rightarrow \; x\sim z \] infatti \begin{align*} &x\sim y \;\Leftrightarrow \;x-y\in S\\ &y\sim z \;\Leftrightarrow \;y-z\in S\\ &(x-y)+(y-z)\in S \;\Leftrightarrow \;x-z\in S \end{align*} Per l'ultima implicazione abbiamo sfruttato il fatto che \[a,b\in S\;\Rightarrow \;a+b\in S\] \end{proof} Allora, a questo punto possiamo creare il quoziente di $A$, ovvero, l'insieme di tutte le classi di equivalenza di $A$ secondo, questo insieme lo indichiamo con $A/_S$: \[ A/_S:=\{[a]|\;a\in A\} \] Definiamo anche il seguente insieme, chiamato laterale di $S$, fissando un $a\in A$: \[ a+S:=\{a+s|\;s\in S\} \] Ovvero e' l'insieme di tutti gli elementi di $S$ a cui abbiamo sommato $a\in A$. Vale questa uguaglianza tra insiemi: \[ [x]=x+S \] \begin{proof} Dimostriamo che $[x]\subseteq x+S$\\ \begin{align*} &y\in [x]\;\Leftrightarrow \;y\sim x\;\Leftrightarrow \;y-x\in S\\ &y-x=s\in S \;\Rightarrow \;y=s+x\in x+S\;\Leftrightarrow \; y\in x+S \end{align*} Dimostriamo che $x+S\subseteq[x]$\\ \begin{align*} &y\in x+S\;\Leftrightarrow \;y=x+s,\;s\in S\;\Leftrightarrow \;y-x=s\in S\\ &y-x=s\in S\;\Leftrightarrow \;y\sim x\;\Leftrightarrow \;y\in [x] \end{align*} Quindi: \[ [x]\subseteq x+S \;\land \;x+S\subseteq[x]\;\Rightarrow \;[x]=x+S \] \end{proof} Allora possiamo ridefinire $A/_S$ in questa maniera: \[ A/_S:=\{a+S|\;a\in A\} \] cioe' l'insieme di tutti i laterali di $S$.\\ Adesso cerchiamo di rendere $A/_S$ un anello. Definiamo l'addizione: \[ (a+S)+(b+S):=a+b+S \] Questa operazione e' ben posta. \begin{proof} Vogliamo dimostrare che l'addizione e' ben posta, cioe' che non dipende dai rappresentati degli addendi, ma solo dalle loro classi. Infatti, scegliamo $a'\in a+S$ (cioe' $[a']=[a]$) e anche $b' \in b+S$, vogliamo dimostrare che: \[ (a+S)+(b+S)=(a'+S)+(b'+S)\;\Leftrightarrow \;a+b+S=a'+b'+S \] che equivale a dire \[ (a+b)\sim (a'+b')\;\Leftrightarrow \; (a+b)-(a'+b')\in S\;\Leftrightarrow \;(a-a')+(b-b')\in S \] Poiche' per Hp $a\sim a'$ allora $(a-a')\in S$ e lo stesso per $(b-b')\in S$, quindi la loro somma \[ (a-a')+(b-b')\in S \] e questo dimostra la catena di doppie implicazioni \end{proof} Definiamo adesso il prodotto: \[ (a+S)(b+S):=ab+S \] Verifichiamo che e' ben posto: \begin{proof} Prendiamo $a'+S=a+S$, $b'+S=b+S$ e dimostriamo che \[ (a+S)(b+S)=(a'+S)(b'+S) \] Nel primo membro: \[ (a+S)(b+S)=ab+S \] nel secondo:\[ (a'+S)(b'+S)=a'b'+S\] quindi dobbiamo dimostrare che \[ ab+S=a'b'+S\;\Leftrightarrow \;ab-a'b' \in S \] Per Hp \[ a'+S=a+S\;\Rightarrow \;a'\sim a\;\Rightarrow \;a'\in [a]\;\Rightarrow \;a' \in a+S\;\Rightarrow \;a'=a+s_1,\;s_1\in S \] e anche: \[ b'=b+s_2,\;s_2\in S \] Quindi sostituendoli: \[ ab-a'b' \in S\;\Leftrightarrow \;ab-(a+s_1)(b+s_2) \in S\;\Leftrightarrow \; as_2+s_1b+s_1s_2 \in S \] Sicuramente $s_1s_2\in S$, ma per $as_2, \;bs_1$ non possiamo dire nulla, quindi non possiamo essere certi del fatto che \[as_2+s_1b+s_1s_2 \in S\] In conclusione, questo prodotto non e' ben posto \end{proof} Per riuscire ad avere un prodotto ben posto dobbiamo utilizzare delle ipotesi piu' forti. Se poniamo come ipotesi che $S \triangleleft A$, cioe' che $S$ sia un ideale di $A$ (vedi \ref{ideale_yea}), allora il prodotto diventa ben posto. Inoltre, e' facile verificare che le 6 proprieta' degli anelli valgono per $(A/_S,+.\cdot)$. Lo di $(A/_S,+.\cdot)$ e' $0+S=S$, infatti, $(a+S)+(0+S)=a+S$.\\ Ricapitolando, $(A/_S,+.\cdot)$ e' un anello, e si chiama l'\emph{anello quoziente} rispetto all'ideale $S$. \subsubsection{Esempio} Prendiamo $\mathbb{Z}$, allora fissato $n\in \mathbb{N}$, accade che \[ n\mathbb{Z}\triangleleft \mathbb{Z} \] dove $n\mathbb{Z}=\{\lambda n|\;\lambda\in \mathbb{Z}\}$, cioe' l'insieme di tutti i multipli di $n$. E' facile verificare che $n\mathbb{Z}$ e' l'ideale di $\mathbb{Z}$, infatti, differenze tra multipli di $n$ sono multipli di $n$ e multipli di multipli di $n$ sono sempre multipli di $n$.\\ Prendiamo allora $\mathbb{Z}/_{n\mathbb{Z}}$, questo non e' altro che: \[ \mathbb{Z}/_{n\mathbb{Z}}=\mathbb{Z}_n \] infatti, \[ x\sim x' \;\Leftrightarrow \; x-x' \in n\mathbb{Z}\;\Leftrightarrow \;x-x'=\lambda n\;\Leftrightarrow \;x=x'\;(\mathbb{Z}_n) \] e quindi \[ [x]_n=x+n\mathbb{Z} \] \subsection{Surriezione naturale} Dato l'anello $A$ e $S \triangleleft A$, definiamo un'applicazione che chiameremo \emph{surrezione naturale}: \[ \pi:A\mapsto A/_S \] \[ \pi(a)=[a]=a+S \] Questa funzione e' un omomorfismo ed e' anche surriettiva. \begin{proof} E' facile verificare che e' surriettiva, dimostriamo solo che e' un omomorfismo.\\ Devono valere le due proprieta': \[ \pi(a+b)=\pi(a)+\pi(b)\;\land \;\pi(ab)=\pi(a)\pi(b) \] allora \begin{align*} &\pi(a+b)=a+b+S\;\;\pi(a)=a+S,\pi(b)=b+S\\ &\qquad \pi(a)+\pi(b)=(a+S)+(b+S)=a+b+S=\pi(a+b)\\ &\pi(ab)=ab+S\;\quad \pi(a)\pi(b)=(a+S)(b+S)=ab+S=\pi(ab) \end{align*} \end{proof} \subsection{Ideale} \label{ideale_yea} Definiamo prima di tutto il concetto di \emph{Ideale}\\ Dato l'anello $A$ e $I \le A$ \[ I \triangleleft A\;\Leftrightarrow \;\forall i\in I, \;\forall a\in A\;\;ai, ia\in I \] Il sottoanello I di A e' un ideale di A se e solo se possiede la proprieta' di assorbimento, ovvero qualsiasi elemento di A moltiplicato per un elemento di I appartiene a I.\\ Esiste anche l'ideale destro in cui vale solo che \[ \forall a\in A\;\; ia\in I \] invece, nell'ideale sinistro: \[ \forall a\in A\;\; ai\in I \] Per verificare che un insieme $I \subseteq A$ (A anello) e' un ideale, basta controllare che: \[ I\equiv\textrm{ ideale di $A$} \Leftrightarrow \begin{cases} \forall x,y\in I\;\; x-y \in I\\ \forall x \in I, \;\forall a \in A\;\;ax, xa \in I \end{cases} \] \subsubsection{Proprieta' degli ideali} L'intersezione di due ideali e' ancora un ideale: \[ I,J\triangleleft A\;\Rightarrow \;I\cap J\triangleleft A \] \begin{proof} Consideriamo $i\in I\;j\in J$ e prendiamo un elemento \[t\in I \cap J\;\Leftrightarrow \;t\in I \land t\in J\] abbiamo che \[ ta,at \in I\;\land \;ta,at \in J \] ovvero \[ ta,at \in I \cap J \] e poiche' l'intersezione di sottoanelli e' ancora un sottoanello, concludiamo che \[ I\cap J \triangleleft A \] \end{proof} Dati $I,J\triangleleft A$ \label{ideal888178628} \[ I\cup J\triangleleft A\;\Leftrightarrow \;I \subseteq J\;\lor \;J\subseteq I \] \begin{proof} Dimostrare $\Leftarrow $ e' semplice, infatti se $J$ contiene $I$, allora $J\cup I = J \;\triangleleft\;A$.\\ Dimostriamo $\Rightarrow $ negando tutta l'implicazione: \[ I \cup J \ntriangleleft A\; \Leftarrow \; I \nsubseteq J\;\land \;J\nsubseteq I \] Le ipotesi di questa nuova implicazione equivalgono a: \[ I \nsubseteq J\;\Leftrightarrow \;\exists i\in I:\;i\notin J \] \[ J \nsubseteq I\;\Leftrightarrow \;\exists j\in J:\;j\notin I \] e quindi $i,j \in I\cup J$.\\ Se per assurdo $I \cup J \triangleleft A$, e quindi se $I \cup J $ fosse un sottonello \[ i-j\in I\cup J \] ovvero \[ i-j\in I \;\lor \; i-j\in J \] ma poiche' $j\notin I$ il primo caso e' assurdo, e poiche' $i\notin J$ anche il secondo lo e'. Quindi $I \cup J$ non e' un sottoanello di A, e quindi $I \cup J$ non e' un ideale di A. \end{proof} Terza proprieta': dato un anello $A$ \[ I\triangleleft A,\;S\le A\;\Rightarrow \;I\cap S\triangleleft S \] \begin{proof} Poiche' intersezione tra sottoanelli e' sempre un sottoanello, dobbiamo solo provare che: \[ \forall x \in I\cap S,\;\forall s \in S\;\Rightarrow \;sx,xs\in I\cap S \] quindi, \begin{align*} &x\in I\cap S\;\Leftrightarrow \;x\in I\;\land \;x\in S\\ &\forall a\in A,\;ax,xa\in I,\;\;s\in S\subseteq A\;\Rightarrow \;sx,xs\in I\\ &x\in S\;\Rightarrow \; sx, xs \in S\\ &sx,xs\in I\;\land\;sx, xs \in S\;\Rightarrow \;sx, xs \in I\cap S \end{align*} \end{proof} \subsection{Omomorfismo e ideali} Dati due anelli $A, A'$ e l'omomorfismo $f:A\longrightarrow A'$, valgono le seguenti proprieta': \begin{enumerate} \label{872jf82jhd} \item L'immagine di un sottoanello di $A$ e' un sotto anello di $A'$: \[ S\le A\;\Rightarrow \; f(S)\le A' \] \begin{proof} Dimostriamo usando la caratterizzazione dei sottoanelli: \begin{align*} &x',y'\in f(S)\;\;\exists x,y\in S:\;f(x)=x',\;f(y)=y'\\ &x'-y'=f(x)-f(y)=f(x-y) \in f(S)\\ &x'y'=f(xy)\in f(S) \end{align*} e poiche' $\Im f \le A'$, lo sara' anche $f(S)$, cioe': \[ f(S) \le \Im f \le A' \] \end{proof} \item La controimmagine di un sottoanello di $A'$ e' un sottoanello di $A$, e per di piu' contiene $\ker f$: \[ S\le A'\;\Rightarrow \;f^{-1}(S)\le A\;\land \;\ker f \subseteq f^{-1}(S) \] \begin{proof} Dimostriamo usando la caratterizzazione dei sottoanelli: \begin{align*} &x,y\in f^{-1}(S)\;\;\exists x',y'\in S:\;f^{-1}(x')=x, f^{-1}(y')=y\\ &x-y=f^{-1}(x')-f^{-1}(y')=f^{-1}(x'-y') \in f^{-1}(S)\\ &xy=f^{-1}(x')f^{-1}(y')=f^{-1}(x'y') \in f^{-1}(S) \end{align*} \end{proof} \item La controimmagine di un ideale di $A'$ e' un ideale di $A$, e per di piu' contiene $\ker f$: \[ I'\triangleleft A'\;\Rightarrow \;f^{-1}(I')\triangleleft A\;\land \;\ker f \subseteq f^{-1}(I') \] \begin{proof} Dobbiamo provare che \[ \begin{cases} x,y\in f^{-1}(I')\;\Rightarrow \;x-y \in f^{-1}(I')\\ x\in f^{-1}(I'),\;a\in A\;\;\Rightarrow \;ax,xa\in f^{-1}(I') \end{cases} \] Procediamo allora in questo modo: \begin{align*} &f(x)\in I',\;f(y)\in I'\;\Rightarrow \;f(x)-f(y) \in I'\;\Rightarrow \;f(x-y)\in I'\\ &\;\Rightarrow \;x-y\in f^{-1}(I') \end{align*} e sempre usando $f()$: \begin{align*} &f(a)\in A',\;f(x)\in I'\\ &f(a)f(x)\in I'\;\Rightarrow \;f(ax)\in I'\;\Rightarrow \;ax \in f^{-1}(I') \end{align*} \end{proof} \item Se $I$ e' un ideale di $A$, allora $f(I)$ e' un ideale dell'imagine di $f$: \[ I\triangleleft A\;\Rightarrow \; f(I)\triangleleft \Im f \] \begin{proof} Dobbiamo dimostrare che: \[ \begin{cases} x',y'\in f(I)\;\Rightarrow \;x'-y' \in f(I)\\ \forall x'\in f(I),\;\forall z'\in \Im f\;\;\Rightarrow \;x'z',z'x'\in f(I) \end{cases} \] Intanto riscriviamo tutte le nostre ipotesi in forma conveniente: \[ x'=f(x), \;x\in I,\;\;y'=f(y),\;\;z'=f(z) \] Quindi sostituendo: \begin{align*} &x'-y'=f(x)-f(y)=f(x-y)\in f(I) \end{align*} lo stesso per la seconda proprieta': \begin{align*} &x'z'=f(x)f(z)=f(xz)\\ &xz\in I\;\Rightarrow \;f(xz) \in f(I) \end{align*} \end{proof} \end{enumerate} \subsection{Teorema dell'omomorfismo} Data un omomorfismo $f:A\longrightarrow A'$, e' possibile fattorizzare $f$ come composizione di due funzioni, ovvero data la surriezione naturale $\pi$, esistera' un omomorfismo $\omega$ tale che $\omega \circ \pi=f$. Graficamente la situazione e' questa: \[ \xymatrix{ A \ar[d]^{\pi} \ar[r]^f & A'\\ A/_{\ker f} \ar[ur]_{\omega} } \] (nota: $\ker f \triangleleft A$) \begin{proof} Poniamo per convenienza $K=\ker f$. Definiamo $\pi$: \[ \pi:A\mapsto A/_{\ker f}\;\;\;pi(a)=K+a \] Definiamo $\omega$: \[ \omega:A/_{\ker f}\longrightarrow A'\;\;\omega(K+a)=f(a) \] Verifichiamo che e' ben posta: \begin{align*} &K+a=K+a'\;\Rightarrow \;\omega(K+a)=\omega(K+a') \;?\;\textrm{Si, infatti}\\ &\quad \omega(K+a)=f(a),\;\omega(K+a')=f(a')\\ & K+a=K+a'\;\Rightarrow \;a-a'\in K=\ker f\;\Rightarrow \;f(a-a')=0\;\Rightarrow \;f(a)-f(a')=0\\ &\quad \Rightarrow f(a)=f(a')\;\Rightarrow \;\omega(K+a)=\omega(K+a') \end{align*} Verifichiamo adesso che e' un omomorfismo, ovvero proviamo queste due proprieta': \[ \begin{cases} \omega((K+a)+(K+b))=\omega(K+a)+\omega(K+b)\\ \omega((K+a)(K+b))=\omega(K+a)\omega(K+b) \end{cases} \] procediamo: \begin{align*} & \omega((K+a)+(K+b))=\omega(a+b+K)=f(a+b)=f(a)+f(b)=\omega(K+a)+\omega(K+b)\\ & \omega((K+a)(K+b))=\omega(ab+K)=f(ab)=f(a)f(b)=\omega(K+a)\omega(K+b) \end{align*} Manca adesso di far vedere che $\omega\circ\pi=f$: \begin{align*} &\forall a\in A\;\;\omega(\pi(a))=\omega(K+a)=f(a) \end{align*} dobbiamo pero' essere sicuri che $\omega$ sia iniettivo, quindi adesso dimostriamo che $\ker \omega = \{ 0 \}$: \begin{align*} &\ker \omega = \{ a+K \;|\;\omega(a+K)=0 \}\\ &a+K\in \ker \omega,\;\;\omega(a+K)=f(a)=0\;\Rightarrow \;a\in\ker f=K\;\Rightarrow \;a+K=0+K\\ &\quad \Rightarrow \ker \omega = \{0+K\}= \{ \overline{0} \} \end{align*} ecco fatto. \end{proof} \subsubsection{Corollario I} \label{corIthmomo} \[ A/_{\ker f}\approx \Im f \] Ovvero, $A/_{\ker f}$ e' isomorfo a $\Im f$. \begin{proof} Consideriamo una restrizione di $f$: \[ f:A\mapsto \Im f \] Questa restrizione e' sicuramente surriettiva. Adesso applichiamo il teorema dell'omomorfismo: \[ \xymatrix{ A \ar[d]^{\pi} \ar[r]^f & \Im f\\ A/_{\ker f} \ar[ur]_{\omega} } \] Poiche' $f$ e' surriettiva, lo sara' anche $\omega$: \begin{align*} &z'=f(z),\;z \in A\\ &\omega(\pi(z))=\omega(K+z)=f(z)=z' \end{align*} L'ultima uguaglianza mostra che per ogni $z' \in f(z)$, esiste una $z \in A$, tale che $\omega(\pi(z))=z'$. In altre parole, $\omega$ e' surriettiva. Poiche' abbiamo prima dimostrato che $\omega$ e' iniettiva, allora $\omega$ diventa un isomorfismo. \end{proof} \subsubsection{Corollario II} \label{corIItommo} Se $f$ e' surriettiva: \[ f:A\mapsto A'\;\Rightarrow \;A/_{\ker f}\approx A' \] Questo e' vero semplicemente perche' $A' = \Im f$. \subsection{Teorema dell'isomorfismo II} Alcune premesse, dati: \[ S < A,\;\;I\triangleleft A, \;\;S+I=\{s+i\;|\;s\in S,\;i\in I\} \] Valgono le seguenti proprieta':\\ \[ S+I < A \] \begin{proof} Infatti, $(s+i)-(s'+i')=(s-s')+(i-i')\in S+I$ e lo stesso vale per il prodotto.\\ \end{proof} \[ I \subseteq S+I < A\;\Rightarrow \;I\triangleleft S+I \] \begin{proof} Questo perche' essendo $I$ ideale di $A$, lo e' anche sicuramente di $S+I$ che e' un sottonello di $A$.\\ \end{proof} \[ I\cap S \triangleleft S \] \begin{proof} Dobbiamo provare che \[ \begin{cases} x,y\in I\cap S,\;\Rightarrow \;x-y\in I\cap S\\ x\in I\cap S,\;s\in S\;\Rightarrow \; xs,sx\in I\cap S \end{cases} \] La prima e' semplice, infatti, $x\in I, S$ e$y\in I,S$.\\ Nella seconda sappiamo che $xs\in I$ perche' $I$ e' un ideale e $x\in I$, ma e' anche vero che $x\in S$ e quindi essendo $s\in S$ si ha che $xs\in I,S$. \end{proof} Data $\pi: A \longrightarrow A/_I$, vale il seguente fatto: \[ S f\T{ iniettiva } } \end{cor} \begin{proof} \eal{&\ker f \le K } ma per il thn \see{AcamposseAhaidealibanali}, gli unici ideali di $K$ sono quelli banali, quindi \eal{&\ker f = (0) \| \ker f = K} Se per assurdo $\ker f = K$, \eal{&\ker f = K\= \forall k\in K\;f(k)=0 \= \Im f =\pgra{0}} assurdo, contro Hp. Quindi, \eal{&\ker f = \pgra{0} \> f\T{ iniettiva }} \end{proof} \subsection{Ideale primo} \label{idealeprimocaratt} Dato $P\triangleleft A$, \[ P\equiv\textrm{ primo}\;\Leftrightarrow \; \Big( ab\in P\;\Rightarrow \; a\in P \lor b\in P\Big) \] \begin{thm} \label{primosseAPdominio} \[ P\equiv\textrm{ primo}\;\Leftrightarrow \;A/P\equiv\textrm{ dominio} \] \begin{proof} Dim $\Rightarrow $\\ Dobbiamo dimostrare che in $A/P$ vale la legge dell'annullamento del prodotto. \begin{align*} &(x+P),(y+P)\in A/P:\;(x+P)(y+P)=[0]\\ &xy+P=[0]\;\Leftrightarrow \;xy\in P\\ &xy\in P\;\Rightarrow \;x\in P \lor y\in P\;\;\textrm{ perche' P primo}\\ &x\in P\;\Leftrightarrow \;(x+P)=[0]\\ &y\in P\;\Leftrightarrow \;(y+P)=[0] \end{align*} Dim $\Leftarrow $\\ Poiche' abbiamo usato solo doppie implicazioni, tranne una sola volta, dobbiamo solamente dimostrare: \[ x\in P \lor y\in P \;\Rightarrow \;xy\in P \] Poiche' $P$ e' un ideale, e poiche' almeno $x$ o $y$ sono in $P$, segue immediatamente (per l'assorbimento) che $xy\in P$. \end{proof} \end{thm} \begin{prop} \label{Pprimossepprimo} Sia $D$ un $PID$. Dato $(p)\triangleleft D,\; p \neq 0$, si ha \[ (p)\equiv \textrm{ primo}\;\Leftrightarrow \;p\equiv \textrm{ primo} \] \end{prop} \begin{proof} \begin{pnecessaria} Dobbiamo dimostrare la seguente implicazione: \eal{&p\div ab \> p\div a \| p\div b} Supponiamo che $p\div ab$ \begin{align*} &p\div ab \= ab=\lambda p \= ab \in (p)\\ & ab\in (p) \ubrace{\>}{(p)\T{ primo }} a\in (p)\;\lor \;b\in (p) \= a=\mu_1 p \| b=\mu_2 p\=p\div a \| p\div b \end{align*} \end{pnecessaria} \begin{psufficiente} Dobbiamo dimostrare la seguente implicazione: \eal{&ab\in (p) \> a\in (p) \| b\in (p)} Sia $ab\in (p)$ \eal{&ab \in (p) \= p\div ab \ubrace{\>}{p\T{ primo}} p\div a \| p\div b\= a\in (p) \| b\in (p) } \end{psufficiente} \end{proof} \subsection{Ideale massimale} Dato $M\triangleleft A$, \[ M\equiv\textrm{massimale }\;\Leftarrow \; \Big( \exists I\triangleleft A,\;M\subseteq I\;\Rightarrow \;I=M\;\lor \;I=A \Big) \] Ovvero, $M$ e' massimale se tutti gli altri ideali di $A$ che lo contengono sono o $A$ oppure $M$ stesso, in altre parole, al di sopra di $M$ non esiste alcun ideale piu' grande. \begin{thm} In ogni anello comm unitario ci sono ideali massimali, anzi vale un risultato piu' forte: partendo da un qualsiasi ideale proprio di $A$ e' possibile trovare un ideale che lo contenga e che sia massimale. Cioe': \[ A\equiv \textrm{anello comm. unitario},\;\;I\triangleleft A,\;I\neq A,\;\Rightarrow \;I\subseteq M\equiv \textrm{ideale mass. di A} \] Prima di dimostrare questo teorema accenniamo il lemma di Zorn (che e' equivalente all'assioma della scelta):\\ sia $A$ un poset, \[ \textrm{ogni catena di elementi di A possiede un maggiorante}\;\Rightarrow \;\textrm{A possiede elementi massimali} \] (Nota: ``catena'' == ``totet'') \begin{proof} \textbf{Dim: } $I\subseteq M\equiv \textrm{ideale mass. di A}$\\ Consideriamo questo insieme: \[ F_I=\{\textrm{tutti gli ideali propri di A che contengono I}\} \] cioe' \[ F_I=\{N \;| \;N\triangleleft A, N\neq A,\;I \subseteq N\} \] che non e' vuoto perche' $I\in F_I$. Usando la relazione di inclusione, abbiamo il poset $(F_I, \subseteq )$.\\ Sia \[ \{J_\alpha\}_\alpha \;\equiv \textrm{ una catena di elementi di $F_I$} \] Se dimostriamo che $\{J_\alpha\}_\alpha$ e' un totet, allora potremo applicare Zorn.\\ Consideriamo \[ J=\bigcup_\alpha J_\alpha \] e' un maggiorante? Poiche' include tutti i $J_\alpha$, basta verificare che $J\in F_I$: \[ J\in F_I \Leftrightarrow \begin{cases} 1)\; J\triangleleft A\\ 2)\; J\neq A\\ 3)\;I\subseteq J \end{cases} \] \begin{proof} \textbf{Dim: } $3)$\\ \begin{align*} & I \subseteq J_\alpha \subseteq J\;\Rightarrow \;I\subseteq J \end{align*} \end{proof} \begin{proof} \textbf{Dim: } $1)$\\ \begin{align*} & \forall x,y \in J\;\Rightarrow \;x-y\in J?\\ &\qq x\in J_a, \; y\in J_b,\;\;J_a,J_b\in J\\ &\qq J_a\subseteq J_b\;\Rightarrow \;x\in J_b\\ & x\in J_b, y\in J_b,\;\Rightarrow \;x-y\in J_b\subseteq J \end{align*} \end{proof} \begin{proof} \textbf{Dim: } $2)$\\ \begin{align*} & \textrm{per assurdo } J=A\\ & 1\in A\;\;\textrm{A e' un anello unitario}\\ & \qq 1\in A=J\;\Leftrightarrow \;1\in J_b\;\Rightarrow \\ & \qq J_b = A\;\;\textrm{e' assurdo perche' $J_b\in F_I$ e $F_I$ contiene solo ideali propri } \end{align*} \end{proof} A questo punto, sappiamo che ogni catena di $F_I$ ha maggiorante, quindi applicando Zorn, deduciamo che $(F_I, \subseteq )$ ha almeno un massimale che chiamiamo $M$.\\ $M$ e' un ideale massimale? Proviamolo.\\ \begin{align*} & I\subseteq M \triangleleft A, \;M\neq A\;\;\textrm{ [per definizione]}\\ & M \triangleleft H \triangleleft A\;\Rightarrow \;H=M\;\lor \;H=A\;\;\textrm{ [e' quello che dobbiamo provare]}\\ & \textrm{supponiamo che } H\neq A\\ & \qq I\subseteq M \triangleleft H\triangleleft A\;\Rightarrow \; H\in F_I\\ & \qq M \subseteq H,\; H\subseteq M\;\Rightarrow \;M=H\;\;\textrm{ M e' il massimale di $F_I$} \end{align*} \end{proof} \end{thm} \begin{thm} \label{massimalesseAMcampo} \[ M\equiv\textrm{ massimale}\;\Leftrightarrow \;A/M\equiv\textrm{ campo} \] \begin{proof} Dim $\Rightarrow $\\ \begin{align*} & (a+M)\in A/M, (a+M)\neq 0\\ & M+(a) \textrm{ e' il piu' piccolo ideale contenente M e A}\\ & M+(a) = A\;\textrm{ per Hp di massimalita' di M}\\ & 1\in A\;\Rightarrow \;1\in M+(a)\;\Rightarrow \;1=m+aa'\\ & 1=m+aa'\;\Rightarrow \;1+M=m+aa'+M=aa'+M=(a+M)(a'+M)\\ & 1+M=(a+M)(a'+M)\\ &(a'+M)\equiv\textrm{ inverso di (a+M)} \end{align*} Dim $\Leftarrow $\\ \begin{align*} &B\triangleleft A:\;M\subset B\\ &\exists b\in B: \;b\notin M\;\Rightarrow \;b+M\neq [0]\\ &\exists b'+M\in A/M:\;\;(b'+M)(b+M)=1+M\;\;\textrm{ poiche' A/M e' un campo}\\ &(b'+M)(b+M)=1+M\;\Rightarrow \;bb'+M=1+M\;\Rightarrow \\ &\underbrace{bb'}_{\in B}-\underbrace{m}_{\in M\subset B}=1\in B\\ &1\in B\;\Rightarrow \;B=A\;\;\textrm{ per la prop di assorbimento} \end{align*} \end{proof} \end{thm} \begin{cor} \[ M\equiv\textrm{ massimale}\;\Rightarrow \;M \equiv\textrm{ primo} \] Semplicemente perche' ogni campo e' anche un dominio, e quindi basta applicare \see{massimalesseAMcampo} e \see{primosseAPdominio}. \end{cor} \subsection{Ideali e $\mathbb{Z}$} \begin{prop} \label{tuttigliidealidiZsonoPID} Tutti gli ideali di $\mathbb{Z}$ sono principali \end{prop} \begin{proof} \begin{align*} & I\triangleleft \mathbb{Z},\;a:=\textrm{ il piu' piccolo intero $>0$ di $I$}\\ & \textrm{dobbiamo dim che }I=(a)\\ &x\in I,\;x=aq+r\;\;0\le r\le a-1\\ &r=x-aq\in I \end{align*} $r>0$, $a$ non sarebbe piu' il ``piu' piccolo'', quindi \[ r=0\;\Rightarrow \;x=aq\;\Rightarrow \;I=(a)\] \end{proof} \begin{prop} Tutti gli ideali primi di $\mathbb{Z}$ sono solo quelli generati da $(p)$, con $p$ primo. \end{prop} \begin{proof} Basta usare la proposizione \see{Pprimossepprimo}. \end{proof} \section{Campo dei quozienti di D} Da ora in poi studieremo gli anelli commutativi che sono \emph{domini d'integrita'}, ovvero quegli anelli commutativi dove vale la legge di annullamento del prodotto. Adesso vedremo che e' possibile immergere un dominio in un campo, ovvero e' possibile trovare un omomorfismo iniettivo che va dal dominio al campo. (Questo e' quello che abbiamo fatto quando abbiamo dimostrato l'immersione di $\mathbb{Z}$ in $\mathbb{Q}$.) Sia $D$ un dominio e creiamo a partire da esso un insieme quoziente: \begin{align*} & (a,b),(c,d) \in D\times D^*\\ & (a,b)\sim(c,d)\;\Leftrightarrow \;ad=bc\\ & D\times D^* \Big/_{\sim}= K = \{ \textrm{tutte le classi d'equiv.} \}\\ & \frac{a}{b}:=[(a,b)] \end{align*} definiamo sull'insieme quoziente $K$ due operazioni: \begin{align*} & [(a,b)]+[(c,d)]:=[(ad+bc,bd)]=\frac{ad+bc}{bd}\\ & [(a,b)][(c,d)] :=[(ac,bd)]=\frac{ac}{db} \end{align*} Queste due operazioni risultano ben poste. \begin{proof} \begin{align*} & (a',b')\sim (a,b)\;\Rightarrow \;[(a', b')]=[(a,b)],\;\; a'b=b'a\\ & [(a',b')]+[(c,d)]=[(a'd+b'c,b'd)]\\ & [(a,b)]+[(c,d)]:=[(ad+bc,bd)]\\ & [(a'd+b'c, b'd)] = [(ad+bc,bd)] \;\Rightarrow \; (a'd+b'c)(bd) = (b'd)(ad+bc) \;\Rightarrow \; \\ & a'bd^2+bb'cd = ab'd^2+bb'cd \;\Rightarrow \;a'bd^2=ab'd^2\\ & (a,b),(a,b'), (c,d) \in D\times D^*\;\Rightarrow \;b,b',d\neq 0\\ &a'bd^2=ab'd^2\;\Rightarrow \;a'b=ab'\;\;\textrm{ per la legg. di annull.}\\ &a'b = ab'\;\;\textrm{ e' vero, per Hp} \end{align*} \end{proof} $(K,+,\cdot)$ risulta essere un campo, e si chiama il \emph{campo dei quozienti di $D$}, che si puo' indicare con $Q(D)$. (L'elemento neutro e' $\frac{b}{b}$, e l'inverso di $\frac{a}{b}$ e' $\frac{b}{a}$). A questo punto ricerchiamo l'immersione che ``affoga'' il dominio $D$ in $K$: \[ \varphi:D^*\longrightarrow K \] \[ \varphi(a)=[(ab,b)]=\frac{ab}{b},\;\;b\in D^* \] $\varphi$ e' un omomorfismo. \begin{proof} Prima proprieta': \begin{align*} & \varphi(a+b)=\frac{(a+b)c}{c}\\ & \varphi(a)+\varphi(b)=\frac{ad}{d}+\frac{be}{e}=\frac{ade+bed}{ed}=\frac{(a+b)ed}{ed}\\ & \frac{(a+b)c}{c} =? \frac{(a+b)ed}{ed}\;\;\textrm{ si, infatti}\\ &\quad (a+b)edc = (a+b)ced \end{align*} seconda: \begin{align*} & \varphi(ab)=\frac{abc}{c}\\ & \varphi(a)\varphi(b)=\frac{ad}{d}\frac{be}{e}=\frac{abde}{de}\\ &\frac{abc}{c} =? \frac{abde}{de}\;\textrm{ si, infatti}\\ &\quad (ab)dec = (ab)cde \end{align*} \end{proof} $\varphi$ e' iniettivo, ovvero $\ker \varphi =\{0\}$. \begin{proof} \begin{align*} & \ker \varphi = \{ a\in D^*\;|\;\varphi(a)=0 \}\\ &\varphi(a)=0\;\Rightarrow \;\frac{ab}{b}=\frac{0}{c}\;\Leftrightarrow \;abc=0\\ &b,c\neq 0\;\Rightarrow \;a=0\;\Rightarrow \;\ker \varphi = \{ 0 \} \end{align*} \end{proof} Abbiamo dimostrato quindi che $\varphi$ e' una immersione. \subsubsection{Esempi} $2\mathbb{Z}$ e' il dominio degli interi pari, il suo campo dei quozienti $Q(2\mathbb{Z})=\mathbb{Q}$ \begin{proof} \begin{align*} & (a,b)\in2\mathbb{Z}\times 2\mathbb{Z}^*\;\Rightarrow \;a=2m,b=2n\neq 0\\ & [(a,b)]=\frac{a}{b}=\frac{2m}{2n}=\frac{m}{n} \end{align*} Si puo' anche mostrare che esiste l'immersione: \[ \varphi:2\mathbb{Z} \longrightarrow Q(2\mathbb{Z})=\mathbb{Q} \] \[ \varphi(a)=\frac{a2}{2} \] \end{proof} \section{Principal Ideal Domain} \begin{defn} Sia $D$ un dominio, \[ D\equiv \textrm{ PID}\;\definizione{\=}\; \forall I\tleq D\;\;I\T{ e' principale } \] ovvero, ogni ideale di $D$ e' principale.\\ Esempio: $\mathbb{Z}$ e' un PID (\vedi{tuttigliidealidiZsonoPID}). \end{defn} \begin{defn} \ilabel{elemento!irriducibile} \ilabel{elemento!primo} Definizione di elemento primo per i domini: dato $D$ dominio, $p \in D,\;p \neq 0,\;p$ non invertibile, poniamo: \[ p\equiv\textrm{ primo}\definizione{\=} \Big( p/_{ab}\;\Rightarrow \;p/_a\;\lor \;p/_b \Big) \] Definizione di elemento irriducibile: sia $q\in D, q \neq 0, q$ non invertibile, poniamo: \eal{& q\equiv\textrm{ irriducibile}\definizione{\=}\textrm{ i suoi unici divisori sono gli invertibili o i suoi associati} \=\\ &\= \Big( q=ab \;\Rightarrow \;a\equiv\textrm{ invertibile}\;\lor \;b\equiv\textrm{ invertibile}\Big) } \end{defn} \begin{prop} In un dominio con unita', vale che \[ p\equiv\textrm{ primo}\;\Rightarrow \;p\equiv\textrm{ irriducibile} \] \end{prop} \begin{proof} \eal{&p=ab\>p\div ab \ubrace{\>}{p \T{ primo}} p\div a \| p\div b\\ &p\T{ primo } \ubrace{\>}{\T{per definizione}} p \neq 0 } \case{$p\div a$} \begin{prova} \eal{&p\div a\= p\lambda =a\\ &p=ab\= p=p\lambda b \=p(1-\lambda b)=0 \ubrace{\=}{D\T{ dominio }} p=0 \| 1-\lambda b=0 \ubrace{\>}{p \neq 0} \lambda b=1\>b\T{ invertibile} } \end{prova} \case{$p\div b$} \begin{prova} analogamente a prima. \end{prova} \end{proof} \begin{prop} \label{UFDirridequivprimo} Sia $D$ un PID o un UFD, e $p\in D^*$, allora \[ p\equiv\textrm{ irriducibile}\=p\equiv\textrm{ primo} \] \end{prop} \begin{proof} \label{dim111111} \case{$D$ PID} \begin{prova} Supponiamo che $p/_{ab}$ e che $p\nmid_{a}$, allora \begin{align*} & MCD(p,a)=1\\ & 1=\lambda p + \mu a\;\Rightarrow \;b=\lambda pb+\mu ab\\ & p/_{\lambda pb},\;\;p/_{\mu ab}\;\;\Rightarrow\;\;p/_b\;\Rightarrow \\ & p\equiv\textrm{ primo} \end{align*} \end{prova} \case{$D$ UFD} \begin{prova} Basta applicare la caratterizzazione degli UFD: \vedi{carattUFD}. \end{prova} \end{proof} \section{Domini euclidei} \[ D\equiv \textrm{ dominio euclideo (ED)}\;\Leftrightarrow \;\exists v:D^*\longrightarrow \mathbb{N}:\;\] \[\qquad\qquad \begin{cases} v(a)\le v(ab)\;\;a,b\in D^*\\ \forall a\in D,\;b\in D^*\;\;\exists q,r\in D^*:\;\;a=qb+r,\;\;r=0\;\lor \;v(r) D\T{ dominio unitario}} \end{prop} \begin{proof} \begin{align*} & \emptyset \neq \Im v \subseteq \mathbb{N}\\ & m=\min \Im v\;\;\textrm{ (m esiste perche' $\mathbb{N}$ e' ben ordinato)}\\ & m=v(d),\;\;d\in D^*\\ & \forall a \in D\;\;a=dq+r\;\;r=0\;\;\lor \;\;v(r) < v(d)\\ & v(r) < v(d) \;\; \textrm{ e' imp. perche' $v(d)=m$ e' il minimo!}\;\Rightarrow \;\\ & r=0\;\Rightarrow \;a=dq\;\;\\ & d=dq:=du\;\;\textrm{ (poiche' abbiamo considerato $\forall a \in D$)}\\ & \forall a\in D,\;\;au=dqu=dq=d=a\;\Rightarrow \;u=1 \end{align*} \end{proof} \begin{prop} \eal{&D\T{ dominio euclideo } \> D\T{ PID }} ovverro, ogni dominio euclideo e' un PID. \end{prop} \begin{proof} Dato \[ I\triangleleft D \] dobbiamo dimostrare che \[ I=\{\lambda i,\;\;i \in I^* \} \] (non serve considerare $I=(0)$, perche' altrimenti avremmo gia' finito), allora: \begin{align*} & \emptyset \neq v(I^*) \subseteq \mathbb{N}\\ & m = \min v(I^*)\;\Rightarrow \;\forall t \in v(I^*),\;\;m < t\\ & m = v(i),\;\;i\in I^* \end{align*} dimostriamo che $(i) \subseteq I$: \begin{align*} & \forall x \in (i),\;\;x=\lambda i\in I\;\;\textrm{ per la prop. di assorbimento degli ideali} \end{align*} dimostriamo che $I \subseteq (i)$: \begin{align*} & \forall x \in I,\;\;x=qi+r\\ & r=0\;\;\lor \;\;v(r) < v(i)=m\\ & r = x-qi \in I\;\;\textrm{ quindi ha senso considerare $v(r)$}\\ & v(r) < m \;\textrm{ e' imp. perche' m e' il minimo}\;\Rightarrow \;\\ & r=0\;\Rightarrow \;x=qi\in (i) \end{align*} \end{proof} \begin{prop} \[ \forall a,b\in D^*,\;\;\exists MCD(a,b)=d,\;\;d=\lambda a +\mu b \] \end{prop} \begin{proof} Dimostreremo in un colpo solo Bezout e l'esistenza del MCD. \begin{align*} & I = (a,b) = \{ ma+nb\;|\;m,n\in D^* \} \triangleleft D\\ & D \equiv \textrm{ PID}\;\Leftrightarrow \;\exists d\in I:\;I=(d)\\ & (a,b)=(d)\;\Rightarrow \;(a,b)\subseteq (d)\\ & a\in(a,b)\subseteq (d)\;\Rightarrow \;a=\lambda d\;\Rightarrow \;d/_a\\ & b\in(a,b)\subseteq (d)\;\Rightarrow \;b=\mu d\;\Rightarrow \;d/_b\\ &\\ & d\in(d) \subseteq (a,b)\;\Rightarrow \;d=ma+nb\\ &\\ & d'/_a \;\land \;d'/_b\;\Rightarrow \;d'/_{ma}\;\land \;d'/_{mb}\;\Rightarrow \;d'/_d\;\Rightarrow \\\ &d=ma+nb=MCD(a,b) \end{align*} \end{proof} \begin{prop} Un dominio euclideo e' un UFD. \end{prop} \begin{proof} Dimostreremo questa proprieta' piu' avanti. \end{proof} \begin{prop} \[ v(a)=v(ab)\;\Leftrightarrow \;b\equiv\textrm{ invertibile} \] \end{prop} \begin{proof} Dim $\Rightarrow $\\ Prendiamo $I=(a),\;\;J=(ab)$, allora \begin{align*} & J \subseteq I\;\Rightarrow \;ab\in I\\ & \textrm{ $a$ ha la valutazione minima in $I$}\\ & v(a)=v(ab)\;\Rightarrow \;\textrm{ $ab$ ha la valutazione minima in $I$}\;\Rightarrow \;\\ &a=q(ab)+r=(qb)a+r\\ &\qq v(r) < v(ab) \;\;\textrm{ [imp. perche' ab ha val. minima]}\\ &\qq v(r) < v(a) \;\;\textrm{ [imp. perche' a ha val. minima]}\\ &\Rightarrow \; r=0\;\Rightarrow \;a=qba\;\Rightarrow \;1=qb\\ &b\equiv\textrm{invertibile} \end{align*} Dim $\Leftarrow $\\ \begin{align*} & v(a)\le v(ab),\;\exists b^{-1}\\ & v(a) \le v(ab) \le v(abb^{-1})=v(a)\;\Rightarrow \\ & v(a)=v(ab) \end{align*} \end{proof} \begin{prop} \label{propamassimaleequivaleaprimo} Dato $(a)=I\triangleleft D$, $a \neq 0$, dove $D$ e' un $ED$, si ha \[ (a) \equiv \textrm{ massimale}\;\Leftrightarrow \; a\equiv \textrm{ irriducibile} \] E poiche' $ED \> UFD$ (\vedi{thmcatenadiimplicazioniKEDPIDUFD}), grazie alla \see{UFDirridequivprimo}, si ha \eal{& (a) \equiv \textrm{ massimale}\;\Leftrightarrow \;a\equiv\textrm{ primo} \= a\equiv \textrm{ irriducibile} } \end{prop} \begin{proof} Dim $\Rightarrow $\\ Dobbiamo dimostrare che \[a=bc\;\Rightarrow \;b\equiv\textrm{ invertible}\;\lor \;c\equiv\textrm{ invertibile}\] \begin{align*} & a=bc\;\Rightarrow \;(a)\subseteq (b)\;\Rightarrow \\ & \;\Rightarrow \;(b) = D\;\lor \; (b) = (a)\;\;\textrm{ poiche' (a) e' massimale per Hp}\\ & \textbf{If } (b) = D :\\ & \qquad 1\ubrace{\in}{\see{EDimplicadomunitario}} D\;\Rightarrow \;1\in (b)\;\Rightarrow \\ & \qquad 1=\lambda b \;\Rightarrow \; b\equiv\textrm{ invertibile }\\ & \textbf{If } (b) = (a):\\ & \qquad b=am\\ & \qquad a=bc\;\Rightarrow \;a=amc\;\Rightarrow 1=mc\;\Rightarrow \;\\ & c\equiv\textrm{ invertibile } \end{align*} \textbf{Dim: } $\Leftarrow $\\ \textbf{Ts: } \[ (a) \triangleleft J \triangleleft D\;\Rightarrow \;J = (a) \;\lor \; J =D \] \begin{prova} \begin{align*} & (a) \triangleleft J\;\Rightarrow \;a \in J\\ & J \equiv \textrm{PID, perche' D e' un ED}\;\Rightarrow \;J=(j)\\ & a\in J \;\Rightarrow \;a=\lambda j\\ & a\equiv \textrm{ irriducibile (per Hp)}\;\Rightarrow \;\\ & \qquad \lambda\equiv \textrm{invertibile} \;\lor \;j\equiv\textrm{ invertibile}\\ & \qquad \textbf{If: } \lambda\equiv \textrm{invertibile} :\\ & \qquad\qquad \lambda^{-1}a=j\;\Rightarrow \;j\in (a)\;\Rightarrow \;J\subseteq (a)\;\Rightarrow \;J=(a)\\ &\qquad \textbf{If: } j\equiv\textrm{ invertibile}\\ & \qquad\qquad (j)=D\;\textrm{ [per la proprieta' degli ideali: se $1 \in I$, allora $I = D$] } \end{align*} \end{prova} \end{proof} \begin{exemp} Ad esempio in $\mathbb{Z}$, \[ (m)=m\mathbb{Z}\equiv\textrm{massimale}\;\Leftrightarrow \;m\equiv\textrm{primo} \] Nota: $(0)$ e' primo, infatti se \[ab\in (0)\;\Rightarrow \;ab=0\;\Rightarrow \;a=0\;\lor \;b=0\;\Leftrightarrow \;a\in(0)\;\lor \;b\in(0)\] (proprio perche' siamo un un dominio d'integrita'. \end{exemp} \begin{prop} Dato $D$ dominio euclideo, $I,J \triangleleft D$, $I=(a), \;J=(b)$, vale che: \begin{align*} &I+J=\Big(MCD(a,b)\Big)\\ &I\cap J=\Big(mcm(a,b)\Big) \end{align*} \end{prop} \begin{prop} Dato $D$ anello, $I\triangleleft D$, $\frac{D}{I}$, \[ J\triangleleft D, \;I\subseteq J\;\;\Rightarrow\;\;J+I \triangleleft \frac{D}{I} \] \end{prop} \subsection{ED, PID e UFD} Ritorniamo alla proprieta' V: ogni ED e' un UFD. La dimostreremo come corollario di un fatto piu' generale: ogni PID e' un UFD. Per dimostrare questo, useremo una comoda caratterizzazione di un UFD. \label{9747289471} Ma prima di tutto diamo la definizione di UFD: \[ D\equiv\textrm{UFD}\;\Leftrightarrow \;\forall p\in D,\;p=q_1q_2\dots q_t,\;\;q_i\equiv \textrm{irriducibile} \] e inoltre la fattoriazzazione di $p$ e' unica a meno di invertibili o dell'ordine. Diamo anche la definizione di \emph{lunghezza} che ci servira' in seguito: sia $D$ un UFD, $a\in D, a \neq \textrm{invert.}$, fattorizziamo $a$, $a=p_1\dots p_t$, allora \[ \textrm{lunghezza di $a$}:=l(a):=t \] Ad esempio, in $\mathbb{Z}$, $l(12)=l(2^23)=l(2\cdot2\cdot 3)=3$. Vale anche questa banale proprieta': \[ a=bm\;\Leftrightarrow \;l(a) \ge l(b) \] \subsubsection{Caratterizzazione di un UFD} \label{carattUFD} \[ D\equiv\textrm{UFD}\;\Leftrightarrow \;\begin{cases} 1)\;\forall r \in D, r\equiv\textrm{irriducibile}\;\Rightarrow \;r\equiv\textrm{primo}\\ 2)\; \textrm{Vale la $c.c.a.f$ per gli ideali principali di D} \end{cases} \] La c.c.a.f e' la \emph{condizione delle catene ascendenti finite}, che dice che data una catena (in questo caso di ideali) \[ (a_1)\subseteq (a_2)\subseteq \dots\subseteq (a_n)\subseteq \dots \] allora \[\exists \overline{n}:\;\forall m>n,\;(a_m)=(a_n)\] cioe', da un certo $\overline{n}$, la catena si stabilizza, finisce. Dimostriamo questa caratterizzazione. \begin{proof} Dim $\Rightarrow $.\\ \textbf{Ts: } vale la $1)$ e la $2)$. \begin{proof} \textbf{Dim: } $1)$\\ \textbf{Ts: } $a\equiv\textrm{irriducibile}\Rightarrow a\equiv \textrm{primo}\;\Leftrightarrow \;\Big(a/_{bc}\;\Rightarrow \;a/_b\;\lor \;a/_c\Big)$\\ \begin{align*} & a/_{bc} \;\Rightarrow \;am=bc\\ & b=b_1b_2\dots b_r,\;b_i\equiv\textrm{irr. }\;\;\textrm{ [applicando la fattorizzazione}\\ & c=c_1c_2\dots c_s,\;\;c_j\equiv\textrm{irr.}\\ & m=m_1m_2\dots m_t,\;\;m_k\equiv\textrm{irr. }\\ & a=a\\ &\\ & am=bc\;\Leftrightarrow \;(b_1b_2\dots b_r)(c_1c_2\dots c_s)=(m_1m_2\dots m_t)a \end{align*} Poiche' la fatt. e' unica, il primo membro deve essere uguale al II a meno di invertibili, e poiche' $a$ e' irriducibile, e quindi non invertibile, deve essere l'associato di qualche $b_i$ o $c_j$, quindi: \begin{align*} & \textbf{If } a\equiv \textrm{associato di }b_i:\\ &\qq a=b_iu_i,\;\;u_i\equiv\textrm{invert.}\\ &\qq u_i^{-1}a=b_i\;\Leftrightarrow \;a/_{b_i}\;\Rightarrow \;a/_b \end{align*} allo stesso modo: \begin{align*} & \textbf{If } a\equiv \textrm{associato di }c_i:\\ &\qq a=c_iu_i,\;\;u_i\equiv\textrm{invert.}\\ &\qq u_i^{-1}a=c_i\;\Leftrightarrow \;a/_{c_i}\;\Rightarrow \;a/_c \end{align*} quindi: \[ a/_b\;\lor \;a/_c \] \end{proof} \begin{proof} \textbf{Dim: } $2)$\\ Consideriamo la catena: \begin{align*} & (a_1)\subseteq (a_2)\subseteq \dots\subseteq (a_n)\subseteq \dots\;\Rightarrow \\ &\qq a_1\in (a_2),\; a_2\in (a_3),\; a_3 \in (a_4),\;\dots\;\Rightarrow \\ &\qq a_1=\lambda_2a_2,\; a_2=\lambda_3a_3,\;a_3=\lambda_4a_4,\dots\\ &\\ &\qq l(a_1) \ge l(a_2) \ge l(a_3) \ge \dots \end{align*} Ora consideriamo l'insieme formato da tutte le lunghezze di ogni $a_i$: \[ A:=\{l(a_i)|\;i\in\mathbb{N} \} \subseteq \mathbb{N} \] e poiche' ogni $l(a_i)\in \mathbb{N}$, possiamo considerare il minimo di $A$: \[ \exists \overline{n}:\;\;\forall i,\;\;\overline{l}:=l(a_{\overline{n}}) \le l(a_i) \] Prendiamo adesso un $m\in \mathbb{N}:\;m>n$: \begin{align*} & (a_{\overline{n}})\subseteq (a_m)\\ &\qq l(a_m) \le l(a_n)\;\;\textrm{per quanto visto sopra}\\ &\qq l(a_n) \le l(a_m)\;\;\textrm{perche' $l(a_n)$ e' il minimo di A}\\ &\qq\qq \textrm{quindi: } l(a_n)=l(a_m)\\ &\qq a_{\overline{n}} = \lambda_ma_m\\ &\\ &\begin{cases} l(a_n)=l(a_m)\\ a_{\overline{n}} = \lambda_ma_m \end{cases}\;\Rightarrow \;\lambda_m \equiv\textrm{invert.}\\ &\qq \lambda_m^{-1}a_{\overline{n}}= a_m\;\Rightarrow \;(a_m)\subseteq (a_{\overline{n}})\;\Rightarrow \\\ &\qq (a_{\overline{n}})=(a_m) \end{align*} \end{proof} \begin{proof} \textbf{Dim: } $\Leftarrow $\\ \textbf{Ts: } $1) \;\land \;2)\;\;\Rightarrow \;\; D\equiv UFD$\\ \label{dim87656787656} Quindi dato $a\in D$, non invert., dobbiamo riuscirlo a fattorizzarlo in maniera ``unica''.\\ Prima di procedere, dimostriamo un altro fatto: \[ a\in D, \;a\neq \textrm{invert.}\;\Rightarrow \;a \textrm{ha almeno un divisore irriducibile} \] \begin{proof} Se $a$ e' irriducibile, allora abbiamo finito, altrimenti, sia $a=a_1b_1$.\\ Riguardo ad $a_1$ ci sono questi due possibili casi: \[ \begin{cases} a_1\equiv \textrm{irrid.}\;\Rightarrow \;\textrm{fine dim.}\\ a_1=a_2b_2 \end{cases} \] anche per $a_2$ esistono i due casi: i \[ \begin{cases} a_2\equiv \textrm{irrid.}\;\Rightarrow \;\textrm{fine dim: $a_2/a$}\\ a_2=a_3b_3 \end{cases} \] possiamo procedere all'infinito? No, perche' la $2)$ ci viene in aiuto: consideriamo la catena creata fin'ora: \[ (a_1)\subseteq (a_2)\subseteq \dots\subseteq (a_n)\subseteq \dots\; \] per la $2)$: \begin{align*} & \exists \overline{n}:\;m=\overline{n}+1,\;(a_m)=(a_{\overline{n}})\\ &\qq a_{\overline{n}+1}=\lambda a_{\overline{n}}\\ &\\ &a_{\overline{n}}=a_{\overline{n}+1}b_{\overline{n}+1}=\lambda a_{\overline{n}} b_{\overline{n}+1}\;\Rightarrow \\ &\qq \lambda, b_{\overline{n}+1}\;\equiv \textrm{ invertibili}\;\Rightarrow \;a_{\overline{n}}\equiv \textrm{irriducibile} \end{align*} quindi abbiamo dimostrato che $a_{\overline{n}}$, irriducibile, divide $a$. \end{proof} Ritorniamo alla nostra dimostrazione \ref{dim87656787656}.\\ Supponiamo che $a=a_1b_1$, dove stavolta $a_1\equiv \textrm{irriducibile}$.\\ Questa supposizione e' lecita perche' abbiamo dimostrato poco fa che $a$ ha almeno un divisore irriducibile.\\ Allora, per $b_1$ si presentano i due soliti casi: \[ \begin{cases} b_1\equiv \textrm{irrid.}\;\Rightarrow \;\textrm{fine dim: $a=a_1b_1$}\\ b_1=a_2b_2, \;\;a_2\equiv \textrm{irrid.} \end{cases} \] anche qui reiteriamo e abbiamo i casi di $b_2$: \[ \begin{cases} b_2\equiv \textrm{irrid.}\;\Rightarrow \;\textrm{fine dim: $a=a_1a_2b_2$}\\ b_2=a_3b_3, \;\;a_3\equiv \textrm{irrid.} \end{cases} \] Possiamo continuare all'infinito? No, perche' per la $2)$, la seguente catena finisce: \[ (b_1)\subseteq (b_2)\subseteq (b_3)\subseteq \dots \] cioe' \begin{align*} & \exists \overline{n}:\;(b_m)=(b_{\overline{n}}),\;\;m=\overline{n}+1\\ &\qq b_{\overline{n}+1}=\lambda b_{\overline{n}}\\ &b_{\overline{n}}=a_{\overline{n}+1}b_{\overline{n}+1}= a_{\overline{n}+1} \lambda b_{\overline{n}}\\ &\qq \lambda, a_{\overline{n}+1}\;\equiv \textrm{ invertibili}\;\Rightarrow \;b_{\overline{n}}\equiv \textrm{irriducibile} \end{align*} in definitiva \[ a=a_1a_2a_3\dots a_{\overline{n}}b_{\overline{n}} \] \end{proof} Ancora pero' non abbiamo utilizzato la $1)$. E' inutile? No! Ci manca da dimostrare l'unicita' della fattorizzazione \verb|;)|\\ \begin{proof} \textbf{Dim: } unicita' della fattorizzazione\\ \textbf{Ts: } $z=p_1p_2\dots p_r=q_1q_2\dots q_s,\;\;p_i,q_j\equiv \textrm{irr.}\;\Rightarrow$\[\qq\qq \;r=s\;\land \; \textrm{I membro e' uguale al II a meno dell'ordine e di invertibili}\] Per assurdo supponiamo che $rs$, quindi, $r=s$, e in particolare: \begin{align*} & p_1=q_1u_1\\ & p_2=q_2u_2\\ & \vdots\\ & p_r=q_ru_r \end{align*} Questo vuol dire che a meno di invertibili e dell'ordine il $I$ membro e il $II$ sono la stessa cosa, quindi la fattorizzazione di $z$ e' unica. \end{proof} La dimostrazione della caratterizzazione degli UFD e' conclusa. \end{proof} Adesso possiamo ritornare in \ref{9747289471}. \subsubsection{PID $\Rightarrow $ UFD} Vogliamo mostrare che \[ D\equiv PID\;\Rightarrow \;D\equiv UFD \] \begin{proof} Dire che $D\equiv UFD$ equivale a dimostrare le due proprieta' della caratterizzazione degli UFD.\\ La prima e' banale, perche' ogni $p\in D, \;p\equiv \textrm{ irriducibile}$ e' anche primo (vedi \ref{dim111111}).\\ Dimostriamo quindi la seconda proprieta', considerando questa catena di ideali: \[ (a_1)\subseteq (a_2)\subseteq \dots\subseteq (a_n)\subseteq \dots\; \] Adesso consideriamo l'unione di tutti questi ideali: \[ J=\bigcup_{i\in \mathbb{N}} (a_i) \] $J\triangleleft D\;?$ Non possiamo subito rispondere usando la proprieta' \ref{ideal888178628}, perche' la $J$ ha un numero infinito di elementi, allora lo dimostriamo direttamente: \begin{proof} \textbf{Dim: } $J\triangleleft D$\\ \begin{align*} & x,y\in J\;\Rightarrow \;x-y \in J \;?\\ &\qq x\in (a_i),\;y\in (a_j), in\;\;J=(a_n)\subseteq (a_m) \subseteq J\;\Rightarrow \\ &\qq (a_m)=J \end{align*} che e' quello che volevamo dimostrare. \end{proof} \subsection{ED $\Rightarrow $ PID $\Rightarrow $ UFD, e controesempi} Ricapitolando tutto quello visto fin'ora: \begin{thm} \label{thmcatenadiimplicazioniKEDPIDUFD} \[ \textrm{Campo}\;\;\Rightarrow \;\;\textrm{ED}\;\;\Rightarrow \;\;\textrm{PID}\;\;\Rightarrow \;\;\textrm{UFD}\;\;\Rightarrow \;\;\textrm{Dominio}\;\;\Rightarrow \;\;\textrm{Anello comm}\;\;\Rightarrow \;\;\textrm{Anello} \] Nessuna di queste implicazioni ha l'inverso. \end{thm} \begin{proof} \step{}{ \textbf{Dim: } $\textrm{Anello comm}\;\;\nLeftarrow \;\;\textrm{Anello}$ } \begin{prova} Basta considerare le matrici. \end{prova} \step{}{ \textbf{Dim: }$\textrm{Dominio}\;\;\nLeftarrow \;\;\textrm{Anello comm}$ } \begin{prova} Basta considerare $Z_{10}$. $\mathbb{Z}_{10}$ ha divisori dello zero, ad esempio $2\cdot 5 = 0$. \end{prova} \step{}{ \textbf{Dim: }$\textrm{Campo}\;\;\nLeftarrow \;\;\textrm{ED}$ } \begin{prova} Basta considerare $\mathbb{Z}$, dove abbiamo visto che e' un ED qui \ref{Zeuclid11213}. \end{prova} \step{}{ \textbf{Dim: }$\textrm{UFD}\;\;\nLeftarrow \;\;\textrm{Dominio}$ } \begin{prova} Consideriamo $D\subseteq R[x]$ (che e' un dominio): \[ D:=\{f(x) \in R[x] \;|\;f'(0)=0\} \] \\ Mostriamo che la $1)$ della caratterizzazione degli UFD non vale.\\ \begin{align*} & x^2, x^3 \in D,\;\;x\notin D\\ & x^2/_{x^3x^3=x^6=x^2x^4}\\ & x^3\neq x^2x\;\;\textrm{perche' $x \notin D$}\;\Rightarrow \;\\ & \qq x^2\nmid x^3 \;\Rightarrow \;x^2\neq \textrm{primo} \end{align*} Un'altro controesempio. Consideriamo $D\subseteq \mathbb{C}$, \[ D=\{a+ib\sqrt{3}\;|\;a,b\in\mathbb{Z}\} \] Vediamo che esistono due fattorizzazioni diverse di uno stesso elemento. \begin{align*} & 2, 1+i\sqrt{3}, 1-i\sqrt{3} \in D,\; \textrm{ e sono irriducibili}\\ & 4=2\cdot 2 = (1+i\sqrt{3})(1-i\sqrt{3}) \end{align*} \end{prova} \step{}{ \textbf{Dim: } $\textrm{PID}\;\;\nLeftarrow \;\;\textrm{UFD}$ } \begin{prova} $\mathbb{Z}[x]$, per il teorema di gauss ($A\equiv UFD\Rightarrow A[x]\equiv UFD$), e' un UFD. Pero' non e' un PID.\\ \textbf{Ts: } $\mathbb{Z}[x] \neq PID\;\Leftrightarrow \;\exists I \triangleleft \mathbb{Z}[x]:\;I\neq \textrm{principale}$ \begin{align*} & I:=(2,x)=\{2a(x)+xb(x)\;|\;a(x),b(x)\in\mathbb{Z}[x]\}\\ & \textrm{Per assurdo }\; I=(h(x))\\ & \qq \left(h(x)\right)=(2,x)\;\Rightarrow \;2\in(h(x))\;\Rightarrow \;2=\lambda h(x)\;\Rightarrow \\ & \qq h(x)/_2\;\Rightarrow \;h(x) = \pm 1\; \lor \;h(x)=\pm 2\\ &\qq \textbf{If } h(x) = \pm 1\\ &\qq\qq (1)=I=\mathbb{Z}[x] \;\;\textrm{[assurdo: I non ha termine noto dispari]}\\ &\qq \textbf{If } h(x) = \pm 2\\ &\qq\qq (2)=I=(2,x)\;\Rightarrow \;x=2\lambda(x) \;\Rightarrow \; \lambda(x)=\frac{1}{2}x\;\;\textrm{ [assurdo: $1/2 \notin \mathbb{Z}$]} \end{align*} \end{prova} \step{}{ \textbf{Dim: } $\textrm{ED}\;\;\nLeftarrow \;\;\textrm{PID}$ } \begin{prova} Il controesempio e' \[ D=\{a+ib\sqrt{19}\;|\;a,b\in2\mathbb{Z}\} \] la dimostrazione di questo controesempio e' troppo complessa per adesso. \end{prova} \end{proof} \section{Interi di Gauss} \begin{quote} Nelle profondita' dello spazio\dots \end{quote} Creiamo questo insieme: \[ \mathbb{Q}[i]=\{a+ib\;|\;a,b\in Q\}\subseteq \mathbb{C} \] e anche questo: \[ \mathbb{Z}[i]=\{a+ib\;|\;a,b\in \mathbb{Z}\}\subseteq \mathbb{C} \] Gli elementi di $\mathbb{Z}[i]$ sono gli \emph{interi di Gauss}.\\ $\mathbb{Q}[i]$ e' un dominio, perche' e' un sottoinsieme di $\mathbb{C}$, ma e' anche un campo perche' ha l'inverso: \[ \frac{a}{a^2+b^2} -i\frac{b}{a^2+b^2} \] $\mathbb{Z}[i]$ e' dominio, ma non un campo, infatti i suoi unici invertibili sono $\pm 1, \pm i$. \begin{proof} Consideriamo la formula dell'inverso: \[ \frac{a}{a^2+b^2} -i\frac{b}{a^2+b^2}\in Z[i] \;\Leftrightarrow \; \frac{a}{a^2+b^2}\in \mathbb{Z} \;\land \;\frac{b}{a^2+b^2}\in \mathbb{Z} \] allora \begin{align*} & a^2+b^2\neq 0\\ & \frac{a}{a^2+b^2}\in \mathbb{Z}\;\Leftrightarrow \;\frac{a}{a^2+b^2}=z,\;\;z\in \mathbb{Z}\;\Leftrightarrow \;\\ & a=z(a^2+b^2)\;\;\Leftrightarrow \;\;a=\pm 1,b=0,z=1 \end{align*} analogamente per l'altro caso \end{proof} \step{}{Ecco una prova piu' elegante} \begin{prova} Siano $x=m+ni,x'\in \mathbb{Z}[i]$ non invertibili, con $x'$ inverso di $x$, allora \begin{align*} & xx'=1\;\Rightarrow \;|xx'|=|x| |x'|=1\;\Rightarrow \;|x|=1\\ & |x|=1\;\Rightarrow \;m^2+n^2=1\;\Rightarrow \;\begin{cases} m=\pm 1& n=0\\ m=0&n=\pm 1 \end{cases} \end{align*} \qed \end{prova} Vale questa proprieta': \[ Q(\mathbb{Z}[i])=\mathbb{Q}[i] \] cioe' il campo dei quozienti di $\mathbb{Z}[i]$ e' $\mathbb{Q}[i]$. \begin{proof} \begin{align*} & Q(\mathbb{Z}[i])=\{\frac{a+ib}{c+id}\;|\;a,b,c,d\in\mathbb{Z} \}\\ & \frac{a+ib}{c+id}=\frac{(a+ib)(c-id)}{(c+id)(c-id)}=\\ &\qq=\frac{i(bc-ad)+(bd+ac)}{c^2+d^2}=\\ &\qq=\underbrace{\frac{bd+ac}{c^2+d^2}}_{\in \mathbb{Q}}+i\underbrace{\frac{bc-ad}{c^2+d^2}}_{\in \mathbb{Q}}\in \mathbb{Q}\;\Rightarrow \;\\ &Q(\mathbb{Z}[i])=\mathbb{Q}[i] \end{align*} \end{proof} \begin{thm} \[ \mathbb{Z}[i]\equiv ED \] Questo teorema e' importante perche' potremo applicare tutte le proprieta' degli ED, dei PID e degli UFD a $\mathbb{Z}[i]$. \begin{proof} \begin{align*} &\exists v:\mathbb{Z}[i]^*\longrightarrow \mathbb{N}\qq v(a+ib):=|a+ib|=a^2+b^2\\ &\\ & v(a+ib)\le v((a+ib)(c+id)) \;?\\ &\qq |a+ib|\le |(a+ib)(c+id)|=|a+ib| |c+id|\\ & z_1,z_2\neq 0\in\mathbb{Z}[i]\;\; \exists q,r \in \mathbb{Z}[i]:\;z_1=qz_2+r\;\;r=0\;\lor \;v(r)2$ primo. \[ p = a^2+b^2\;\;\Leftrightarrow \;\;p=1\;\;(\mathbb{Z}_4) \] \label{sumquadrpro} \begin{prova} \step{}{\textbf{Dim } $\Rightarrow $} \begin{prova} \begin{align*} &p = a^2+b^2\;\;\\ &\textrm{p e' dispari, quindi $a,b$ devono essere uno pari e l'altro dispari}\\ &\qq a=2m\;\;b=2n+1\\ & p = 4m^2+4n^2+4n+1 = 1 \;\;(\mathbb{Z}_4) \end{align*} \qed \end{prova} \step{}{\textbf{Dim $\Leftarrow $}} \begin{prova} \pfsketch Proveremo che $p$ non e' primo in $\mathbb{Z}[i]$ e che $p^2=(a^2+b^2)(c^2+d^2)$. Infine faremo vedere che $p=a^2+b^2$.\\ \step{}{\textbf{Step I}} \assume{ \begin{enumerate} \item $n\in \mathbb{N}$ \item $p=4n+1$ \item $p$ primo \end{enumerate}} \prove{$\exists x:\;x^2=-1\;\;(\mathbb{Z}_p)$} \begin{prova} \pf \pflet{$x=1\cdot 2 \cdot \cdots\cdot \frac{p-1}{2}$} \begin{align*} & \frac{p-1}{2}=2n\\ & x=(-1)(-2)(-3)\cdots(-2n)\qq & \textrm{[$2n$ e' pari]}\\ & x^2=xx=(1\cdot 2 \cdot\cdots\cdot2n)((-1)(-2)(-3)\cdots(-2n))\\ & x^2=(1\cdot 2 \cdot \cdots\cdot2n)((p-1)(p-2)(p-3)\cdots(p-2n))\;\;(\mathbb{Z}_p)\\ & p-2n=2n+1,\;\;p-2n-1=2n,\;\;p-2n-2=2n-1,\;\;\cdots,\;\;p-1=4n\\ & x^2=1\cdot 2 \cdot\cdots\cdot2n\cdot(2n+1)(2n+2)\cdots(4n)\;\;(\mathbb{Z}_p)\\ &x^2=4n! =(p-1)!\;\;(\mathbb{Z}_p)\\ &(p-1)! = -1 \;\;(\mathbb{Z}_p)\qq \T{[thm di Wilson]}\\ &x^2=-1\;\;(\mathbb{Z}_p) \end{align*} \qed \end{prova} \end{prova} \step{}{\textbf{Step II}} \prove{ $\exists y<\frac{p}{2}:\;\;y^2=-1\;\;(\mathbb{Z}_p)$ } \begin{prova} \pf \pflet{$x:\;\;x^2=-1\;\;(\mathbb{Z}_p)$} \case{ $x <\frac{p}{2}$ }~\qed \case{ $x>\frac{p}{2}$ } \pflet{$y=p-x$} \begin{align*} &y=p-x< \frac{p}{2}\\ &y^2=p^2+x^2-2px\\ &y^2=x^2=-1\;\;(\mathbb{Z}_p) \end{align*} \qed \end{prova} \step{}{$p$ non e' primo in $\mathbb{Z}[i]$} \pflet{ $z<\frac{p}{2}:\;\;z^2=-1\;\;(\mathbb{Z}_p)$ } \prove{ Se $p/_{ab}\;\Rightarrow \;\;p\nmid a\;\;\land \;\;p\nmid b$ } \begin{prova} \pf \begin{align*} & z^2=-1\;\;(\mathbb{Z}_p)\;\Leftrightarrow \;z^2+1=\lambda p\;\Leftrightarrow \\ &\qq p/_{z^2+1}\\ & z^2+1=(z+i)(z-i)\in(\mathbb{Z}[i])\\ &p\in \mathbb{Z}\subseteq \mathbb{Z}[i]\;\Rightarrow \;p/_{(z+i)(z-i)} \end{align*} \assume{ \begin{enumerate} \item $p/_{z-i}$ \end{enumerate} }\prove{ proviamo che si cade in assurdo } \qedstep \begin{prova} \begin{align*} & p/_{z-i}\;\Rightarrow \; z-i=\mu p,\;\;\mu\in\mathbb{Z}[i]\\ & \varepsilon p=\T{coniugato di $\mu p$},\;\; z+i=\textrm{coniugato di $z-i$}\;\Rightarrow \;\\ &\qq z+i=\varepsilon p\;\Rightarrow \; p/_{z+i}\\ & p/_{z+i}\;\land \;p/_{z-i}\;\Rightarrow \;p^2/_{z^2+1}\;\Rightarrow \\ &\qq m p^2=z^2+1=\lambda p\;\Rightarrow \\ &\qq m p = \lambda\;\Rightarrow \;p/_\lambda\;\;\;(1)\\ &z<\frac{p}{2}\;\Rightarrow \;z^2< \frac{p^2}{4}\;\Rightarrow \;\\ &\qq z^2+1<\frac{p^2}{4}+1\;\Rightarrow \;\lambda p<\frac{p^2}{4}+1