%        File: algebraI.tex
%     Created: Sat Oct 07 10:00 AM 2006 C
% Last Change: Sat Oct 07 10:00 AM 2006 C
%
\documentclass[a4paper]{article}
\usepackage{prova}
\usepackage{color,graphicx}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{txfonts}
\usepackage{xypic}
\RequirePackage{ifpdf} % running on pdfTeX?
\ifpdf
\usepackage[pdftex,bookmarks=true,
		   bookmarksnumbered=false,
		   bookmarksopen=false,
		   colorlinks=true,
		   linkcolor=webred] {hyperref}
\definecolor{webgreen}{rgb}{0, 0.5, 0} % less intense green
\definecolor{webblue}{rgb}{0, 0, 0.5} % less intense blue
\definecolor{webred}{rgb}{0.5, 0, 0}   % less intense red
\fi
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{ax}{Axiom}

\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]

\theoremstyle{remark}
\newtheorem{rem}{Remark}[section]
\newtheorem*{notation}{Notation}


\newcommand{\I}{\mathcal{I}}
\newcommand{\qq}{\qquad}
\newcommand{\T}[1]{\textrm{#1}}

\title{Algebra I}
\author{AlpT (@freaknet.org)}
\begin{document}

\pagenumbering{roman}
\maketitle{}
\clearpage
\tableofcontents
\clearpage
\pagenumbering{arabic}


\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 e' possibile definire senza ricorrere
a nessun'altra precedente definizione.
Questo vuol dire che non dobbiamo preoccuparci di spiegare come e perche'
abbiamo definito un concetto primitivo. Diciamo semplicemente che e' cosi', e
basta.
\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 cosa che sia stata ben definita, ovvero
qualsiasi cosa che possa essere usata almeno una volta in una computazione.

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

\subsubsection{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}


\subsubsection{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)$.

\subsubsection{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}$.

\subsubsection{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}

\subsubsection{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 (A \setminus B) \]
			
			Lo stesso vale per $A$ e $C$:
			\[ (x \notin C), (x\in A) \Rightarrow (A \setminus C) \]

			Possiamo quindi riscrivere la [1]:
			\[ x \notin (B \cup C) \Rightarrow (x \notin B) \land 
			(x \notin C) \Rightarrow (A \setminus B) \land (A
			\setminus C) \Rightarrow (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}
\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}

\subsubsection{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 si puo' definire come una collezione di sottoinsiemi di X non vuoti, 
mutuamente disgiunti e tali che la loro unione e' l'insieme X stesso. I sottoinsiemi che 
costituiscono una partizione vengono detti parti, classi o blocchi della partizione.

In modo piu' formale possiamo dire che una partizione di un insieme ''X'' e'
una funzione $\,\pi\,$ che ad ogni elemento $\,x\in X\,$ associa un sottoinsieme $\,\pi(x)\,$ tale che 
sia $\,x \in \pi(x)\,$ e $\,\cap_{x \in X}\pi(x)=\emptyset\,$.

Il numero di tutte le partizioni dell'insieme che ha $n$ elementi e' dato
dalla formula di Dobinski:
\[
	{1 \over e}\sum_{k=0}^\infty {k^n \over k!}
\]

\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)}
\label{sec:function}
\label{sec:map}

\[
f: X \rightarrow Y
\]

La funzione $f$ e' una legge che permette di associare agli elementi
dell'insieme $X$, uno e un solo elemento di $Y$.

Possiamo esprimere lo stesso concetto utilizzando il linguaggio insiemistico:
\[
	f \subseteq X \times Y \,|\, \forall x \in X \; {\exists}^1 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$.

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

\subsubsection{Le funzioni di programmazione}

La funzione insiemistica e' molto simile a quella dei linguaggi di
programmazione.
Una funzione di un linguaggio di programmazione e' un insieme di istruzioni
che operano su un elemento che appartiene a un particolare dominio e
restituiscono un altro elemento che appartiene a un codominio.

Ad esempio:
\[
f(x)=2x
\]
In C possiamo scrivere:
\begin{center}
\begin{verbatim}
int f(int x)
{
        return 2*x;
}
\end{verbatim}
\end{center}

\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' iniettiva} \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' surriettiva}\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' surriettiva}\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$.

\subsubsection{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
\]

\subsubsection{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 due funzioni $f: A\rightarrow B, \quad g:B\rightarrow A$:
		\[f\circ g = i_B\;\Leftrightarrow \;
		f\equiv\textrm{surriettiva}\]
		Se, invece, $g\circ f = i_A$, allora:
		\[
		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{Esempio}
\begin{align*}
	&D = \{ 0, 1 \} \\
	&\mathbb{L}=\left\{  \textrm{C, Perl, TCL, Awk, Python, Bash,
	Lisp} \right\} \\
	&D^{\mathbb{L}}
\end{align*}
Una qualsiasi funzione $f \in D^{\mathbb{L}}$ dara' sempre come risultato o
$0$ o $1$.

\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 assegnamo una relazione d'equivalenza $R$:
\[
	A \varepsilon R
\]

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$.
\subsubsection{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*}
	&b \notin [a] \mbox{ ovvero } (b \stackrel{R}{\nsim} a) \\
	&[b] = \{ x \in A | x \stackrel{R}{\sim} b \} \\
	&[a] \cap [b] = \emptyset
\end{align*}
\begin{proof}
	Supponiamo per assurdo che
	\[
		[a] \cap [b] \neq \emptyset
	\]
	da questo segue che:
	\begin{align*}
		&\exists c \in [a],[b] &\Rightarrow \\
		&\Rightarrow \quad c \stackrel{R}{\sim} a, c
		\stackrel{R}{\sim} b\qquad \forall a\in A, \forall b \in B \\
		&\Rightarrow \quad c \stackrel{R}{\sim} a, b
		\stackrel{R}{\sim} c \\
		&\Rightarrow \quad b \stackrel{R}{\sim} a
	\end{align*}
	Il che e' assurdo perche' per la definizione che abbiamo dato, $b$ non
	e' in relazione con $a$
\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$.
\end{enumerate}

\subsection{Insieme quoziente di A}
\label{sec:quotient_set_rel}
Sia $A$ un insieme, $\varepsilon$ una relazione di A, diremo insieme quoziente
di $A$ rispetto a $\varepsilon$, l'insieme i cui elementi sono le classi
d'equivalenza di $A$.

L'insieme quoziente di A e' anche una sua partizione (vedi
\ref{sec:partition_rel}).

%
% 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 totalemente ordinato.

\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
	\]
\subsubsection{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$ 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
	\]

\subsubsection{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:
\[ x \in A \,|\, 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.

\subsubsection{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:
\[ x \in A \,|\, 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.

\subsubsection{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.
\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.


\section{L'insieme $\mathbb{N}$}
\label{sec:N}
\subsection{Assiomatizzazione di Peano}
\label{sec:peano}

L'insieme $\mathbb{N}$, che contiene tutti i numeri naturali, puo' essere
definito accuratamente utilizzando gli assiomi di Peano.

Consideriamo un insieme $\mathbb{N}$ che goda delle seguenti proprieta':
\begin{enumerate}
	\item Esiste la seguente applicazione:
		\[ 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 il simbolo $0$.
		In altre parole, lo zero e' l'unico elemento che non e' il
		successivo di nessun altro elemento.
	\item \textbf{Principio di induzione}.
		Consideriamo un sottoinsieme $U \subseteq \mathbb{N}$ tale
		che: \begin{enumerate}
			\item $0 \in U$
			\item $u \in U$ 
			\item $s(u) \in U$
		\end{enumerate}
		Se $U$ gode di queste tre proprieta', allora $U = \mathbb{N}$
\end{enumerate}

Un insieme $\mathbb{N}$, con le suddette proprieta' si dira' l'insieme dei
numeri naturali.

\subsection{Dimostrazione per induzione}
\label{sec:induzione}
Supponiamo che voglia provare che una certa proprieta' $P(n)$ valga $\forall n
\in \mathbb{N}$. L'algoritmo da seguire per la dimostrazione e' il seguente:
\begin{enumerate}
	\item Dimostro che $P(0)$ e' vera
	\item Suppongo vera $P(u)$
	\item Dimostro che $P(s(u))$ e' vera
	\item A questo punto possiamo affermare che $U = \mathbb{N}$
\end{enumerate}

\subsubsection*{Esempio}
In quest'esempio dimostreremo che la somma dei primi $n$ numeri dispari e'
pari a $n^2$.

\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{Induzione e buon ordinamento}
Il principio di induzione e quello del buon ordinamento
(\ref{sec:well_ordered_set}) sono assiomi equivalenti, ovvero e' possibile
dimostrare l'uno a partire dall'altro e viceversa.

\begin{proof}
	Partiamo dal principio di induzione e dimostriamo quello del buon
	ordinamento.
	Prendiamo un sottoinsieme \[\emptyset \neq U \subseteq N\]
	\begin{align*}
		& T = \left\{ \textrm{Insieme dei minoranti di U} \right\}\\
		& 0 \in T
	\end{align*}
	Sappiamo che $T\neq N$, infatti
	\[ \exists t \in T | s(t) \notin T \]
	Per definizione di minorante:
	\[ t \le u, \quad \forall u \in U \]
	Se $t \in U$, allora $t$ sarebbe un minimo di $U$. Poiche' $U$ e' un
	generico insieme, vorrebbe dire che ogni sottoinsieme di $N$ ha un
	minimo e che quindi, per definizione $N$ e' ben ordinato.
	In sostanza dobbiamo dimostrare che $t \in U$.
	Procediamo per assurdo supponendo che $ t \notin U $, ovvero:
	\begin{align*}
		&t < u, \quad \forall u \in U\\
		&t+1 \le u, \quad \forall u \in U\\
		&s(t) \in T\\
	\end{align*}
	Ma come abbiamo visto in precedenza, $t+1=s(t) \notin T$, quindi la
	nostra ipotesi $t \notin U$ e' falsa, ovvero $t \in U$ e' vera.
	
	q.e.d
\end{proof}

\subsection{Addizione}
\label{sec:add}
Definiamo l'operazione (vedi \ref{sec:binary_op}) di addizione che indichiamo
con il simbolo $+$.
\[ add: N \times N \rightarrow N \]
\[ m+n \in N \quad \forall (m,n) \in N\times N \]

Costruiamo per induzione su $n$, l'operazione di addizione.
\begin{description}
	\item[Base dell'induzione]: $m+0 = m$
	\item[Conoscendo $m+u$], $m+s(u)= s(m+u)$
\end{description}

\subsubsection*{Esempio}
$m+1=s(m+0)=s(m) \Rightarrow m+1 = s(m)$

\subsubsection{Proprieta' dell'addizione}
\begin{description}
	\item[Associativa]: $(m+n)+p=m+(n+p)$
		\begin{proof}
			Dimostriamo la proprieta' associativa per induzione su
			$p$.
			\begin{enumerate}
	\item $(m+n)+0=m+(n+0)$, poiche' per la definizione di addizione
		$m+0=m$, possiamo riscriverla come:
		\[ m+n = m+n \]
		Quindi la proprieta' associativa e'
		dimostrata per $p=0$
	\item Supponiamo che $(m+n)+p=m+(n+p)$ sia vera.
	\item Dimostriamo la precedente per $p+1$:
		\begin{align*}
			&(m+n)+s(p)=m+(n+s(p))\\
			&s(\underbrace{(m+n)+p}_{m+(n+p)})=m+s(n+p)\\
			&s(m+(n+p))=m+s(n+p)\\
			&m+s(n+p)=m+s(n+p)\\
			&0=0
		\end{align*}
\end{enumerate}
		\end{proof}
	\item[Commutativa]: $m+n=n+m$
	\item[Legge di cancellazione]: $m+p=n+p \Rightarrow m=n$
\end{description}

\subsection{Moltiplicazione}
\label{sec:mul}
\[ mul: N \times N \rightarrow N \]
\[ mn \in N \quad \forall (m,n) \in N\times N \]

Costruiamo per induzione su $n$, l'operazione di moltiplicazione.
\begin{description}
	\item[Base dell'induzione]: $m0 = 0$
	\item[Conoscendo $mu$], $ms(u)= mu+m$
\end{description}

\subsubsection*{Esempio}
\[m1=ms(0)=m0+m=m\]
\[m2=ms(1)=m1+m=m+m\]
\[m3=ms(2)=m2+m=m+m+m\]

\subsubsection{Proprieta' della moltiplicazione}
\begin{description}
	\item[Associativa]: $(mn)p=m(np)$
	\item[Commutativa]: $mn=nm$
	\item[Distributiva del prodotto rispetto all'addizione]:
		$m(n+p)=mn+mp$
	\item[Legge di cancellazione]: Se $m=n \Rightarrow mp=np$\\
		Se $mp=np \land p\neq 0 \Rightarrow m=n$
\end{description}

\subsection{Elemento neutro}
Lo $0$ e' l'elemento neutro dell'addizione perche' $m+0=m$.

Lo $1$ e' l'elemento neutro della moltiplicazione perche' $m1=m$.

\section{Teoria della divisibilita'}
\subsection{Divisibilita'}
Definiamo la relazione d'ordine di divisibilita':
\[ a/_b \Leftarrow \exists n\in \mathbb{N}^{*} | an=b \]

\subsubsection{Proprieta'}
\label{sec:divis_prop}
\begin{enumerate}
	\item Poiche' la divisibilita' e' una relazione d'ordine, gode della
		proprieta' antisimmetrica e quindi: $a/_b \land b/_a
		\Rightarrow b=a$.
	\item Se $c/_a$ allora $c/_{ma}$, ovvero $c$ divide anche i multipli di
		$a$.
	\item Se $c/_x$ e $c/_y$, allora $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 Se $c/_x$ e $c/_y$ e $x=y+z$ allora $c/_z$
		\begin{proof}
			\begin{align*}
				&x=cq_1+r_1, \quad y=cq_2+r_2\\
				&x=y+z \quad \Rightarrow  \quad
				cq_1+r_1=cq_2+r_2+z\\
				&c(q_1-q_2)+(r_1-r_2)=z \quad \Rightarrow
				\quad c/_z
			\end{align*}
		\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$.

\subsubsection{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 $r<b$.
	\begin{align*}
		&q'b>a\\
		&a<q'b\\
		&a=qb+r\\
		&qb+r<q'b\\
		&qb+r<(q+1)b\\
		&qb+r<qb+b\\
		&r<b
	\end{align*}
\end{proof}
\begin{proof}
	Dimostriamo adesso che il $q$ ed $r$ sono unici.
	Supponiamo per assurdo che:
	\begin{align*}
		&r<b\\
		&r'<b'\\
		&q\neq q' \Rightarrow q < q'\Rightarrow q+n=q', \; n\neq 0\\
		&a=qb+r=q'b+r'\\
		&qb+r=(q+n)b+r'\\
		&qb+r=bq+nb+r'\\
		&r=nb+r'\\
		&(r=nb+r') \ge b\\
		&r \ge b\\
	\end{align*}
	E l'ultima diseguaglianza e' un assurdo perche' abbiamo prima
	dimostrato che $r < b$. Quindi $q$ e $r$ sono unici.
\end{proof}

\subsection{Algoritmo Euclideo per il MCD}
Dati $a,b \neq 0$, ecco l'algoritmo in Calc:
\begin{verbatim}
define MCD(a,b) { 
        return !b ? a : MCD(b, a%b); 
}
\end{verbatim}

Le operazioni che esegue:
\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
\end{align*}
Il MCD di $a,b$ sara' l'ultimo resto non nullo, ovvero $r_n$.

\begin{proof}
	Intanto osserviamo che l'algoritmo finisce sempre compiendo un numero
	finito di passi, infatti, come abbiamo visto nella sezione
	\ref{sec:divisione_algo}, sappiamo che $r<b$, quindi:
	\begin{align*}
		&r_1<b\\
		&r_2<r_1\\
		&r_3<r_2\\
		&\quad \vdots
	\end{align*}
	Dato che stiamo opernando in $\mathbb{N}$, prima o poi si arrivera'
	allo zero. Il numero massimo di passaggi e' $b$.

	Dobbiamo dimostrare che $r_n$ e' il $MCD(a,b)$, quindi deve accadere
	che $r_n/_a$ e $r_n/_b$.
	Prima di tutto sappiamo che $r_n/_{r_{n-1}}$ perche':
	\[ r_{n-1}=r_{n}q_{n+1}+0 \]
	E quindi divide anche $r_{n-1}q_{n}$ e se stesso $r_n$, quindi per la
	proprieta' della divisibilita' divide anche $r_{n-1}q_{n}+r_n$ che
	corrisponde a $r_{n-2}$.\\
	Per lo stesso motivo $r_n$ divide $r_{n-2}q_{n-1}$ e $r_{n-1}$, e
	quindi divide $r_{n-3}$.
	Procedendo a questo modo si risale tutta la scala delle operazioni e
	si arriva a $r_n/_a$ e $r_n/_b$. Ovvero abbiamo dimostrato che $r_n$
	e' un divisore comune di $a$ e di $b$. Adesso dobbiamo dimostrare che
	se esiste un altro divisore comune, allora dividera' $r_n$.
	Supponiamo che quest'altro divisore comune si chiami $c$.
	\begin{align*}
		&a=\lambda c\\
		&b=\mu c\\
		&a=bq_1+r_1 \quad \Rightarrow  \quad \lambda c=\mu cq_1+r_1
		\quad \Rightarrow  c/_{r_1}\\
	\end{align*}
	Quindi $c/_{r_1}$ (c divide $r_q$), e dato che $b=r_1q_2+r_2$, vuol dire che
	$c/_{r_2}$, e poiche' $r_1=r_2q_3+r_3$ allora $c/_{r_3}$. Procendendo
	in questa maniera si arriva a $c/_{r_n}$.
\end{proof}

\section{Teoria degli insiemi}

\subsection{Cardinalita' (o Potenza)}
Con la notazione, $\underline{n}$ intendiamo il seguente insieme:
\[
\underline{n} = \left\{ 0,1,2,\dots,n-1 \right\}
\]
Cosi ad esempio, $\underline{4}=\left\{ 0,1,2,3 \right\}$.

Diamo la definizione di cardinalita' dell'insieme $A$, che indichiamo con
$|A|$:
\[
	|A|=\underline{n} \quad \Leftrightarrow \quad \exists f: A \leftrightarrow \underline{n}
\]
Ovvero, l'insieme $|A|$ ha cardinalita' $n$ se esiste un'applicazione biettiva
che associa a ogni elemento di $A$ un elemento di $\underline{n}$.
Se l'insieme $A$ e' finito, $|A|$ e' uguale al numero degli elementi contenuti
in $A$, se invece non e' finito si scrive \[|A|=\infty\]

\subsection{Insieme finito (infinito)}
Un insieme $A$ e' finito se e' possibile porlo in relazione biunivoca con un
$\underline{n} \in \mathbb{N}$, altrimenti si dice infinito.\\
E' possibile usare anche questa definizione:
un insieme $A$ si dice infinito se e' possibile porre in relazione biunivoca
l'insieme stesso con un suo sottoinsieme proprio ($\neq A$).
\subsubsection{Esempio}
Poiche' possiamo porre in corrispondenza biunivoca l'insieme $2\mathbb{N}$ con
l'insieme $\mathbb{N}$ deduciamo che $2\mathbb{N}$ e' infinito.
($2\mathbb{N}$ e' l'insieme dei numeri pari).
\subsection{Insieme numerabile}
$A$ si dice numerabile se:
\[ \exists \;\;\varphi: A \leftrightarrow \mathbb{N} \]
\subsubsection{Proprieta'}
\begin{enumerate}
\item In ogni insieme infinite esiste un sottoinsieme numerabile.
\begin{proof}
	Supponiamo che X sia il nostro insieme infinito. Allora prendiamo un
	elemento $b_1 \in X$. Poi prendiamo un altro elemento $b_2$ dal
	sottoinsieme $X\setminus \{b_1\}$. Poi $b_3 \in (X\setminus
	\{b_1\})\setminus \{b_2\}.$ E cosi' via.\\
	Per l'assiamo della scelta esistera' un unico insieme che contiene:
	\[
	b_1, b_2, \dots, b_t
	\]
	E questo e' proprio il nostro insieme numerabile.
\end{proof}

	\item Se $X$ e' infinito e $A$ e' finito o numerabile, allora $|X \cup A|=|X|$.
\begin{proof}
	Dobbiamo dimostrare che esiste una funzione biettiva tra $X \cup A$ e
	$X$.\\
	Sia $B \subset X$ numerabile (abbiamo visto nella proprieta' 1
	che in un insieme infinito $B$ esiste). Quindi sia\[
	B=\{b_1, b_2, \dots, b_t\}
	\]
	Adesso scegliamo questa applicazione:
	\[
	f(x) = \begin{cases}
		x & x \notin B\\
		b_{2i} & x \in B\\
		b_{2i+1} & x \in A
	\end{cases}
	\]
	A questo punto e' facile vedere come prendendo dei qualsiasi valori da
	$X \cup \{ a_1, a_2, \dots, a_s \}$ questa applicazione rimanga
	biettieva.
\end{proof}
\item Ogni classe di equivalenza e' un insieme numerabile
\item Unione di insieme numerabili e' un insieme non numerabile
\end{enumerate}

\subsection{Insiemi equipotenti}
Due insieme $A$ e $B$ sono equipotenti se e' possibile stabilire una relazione
biunivoca tra di loro, ovvero se:
\[
|A|=|B|\quad \Leftrightarrow   \quad \exists \;\;\varphi: A\leftrightarrow B
\]
Possiamo quindi dire che $A$ e' numerabile se e' equipotente a $\mathbb{N}$.

Definiamo anche le seguenti relazioni:
\begin{align*}
	&|A|\le |B|\quad \Leftrightarrow   \quad \exists \;\;\varphi:
	A\hookrightarrow B\\
	&|A| < |B|\quad \Leftrightarrow   \quad \exists \;\;\varphi:
	A\hookrightarrow B, \;\; \nexists \psi: A \mapsto B\\
	&|A| \ge  |B|\quad \Leftrightarrow   \quad \exists \;\;\varphi:
	A\mapsto B\\
	&|A| > |B|\quad \Leftrightarrow   \quad \exists \;\;\varphi:
	A\mapsto B, \;\; \nexists \psi: A \hookrightarrow B\\
\end{align*}

\subsubsection{Proprieta'}
\begin{enumerate}
	\item $|A| < |P(A)| \quad \forall A$
		\begin{proof}
			Per definizione bisogna 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 in $P(A)$:
			\begin{align*}	
				&B=\left\{ x\in A| x\notin P(A)
				\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 P(A)$,
					ovvero $y \notin \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 P(A)$ e quindi $y\in P(A)$,
					ovvero $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}
Cantor ha mostrato come $\mathbb{N}$ e $\mathbb{N} \times \mathbb{N}$ siano
equipotenti. Infatti, basta usare queste formule:
\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*}
\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}

\subsubsection{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)]
\]
\subsubsection{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}
\]
\subsubsection{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$.\\
Un numero $p \in \mathbb{Z}$ e' primo se e' vera la seguenete implicazione:
\[
	p/_{ab} \;\;\Rightarrow \;\; p/_a \;\lor\;p/_b
\]
Un numero e' primo se e solo se e' irriducibile:
\[
	\textrm{primo} \Leftrightarrow \textrm{irriducibile}
\]

\begin{proof}
	Dimostriamo il verso $\Rightarrow$.\\
	Ipotesi: $p$ e' primo, quindi:
	\[
		p=ab\;\;p/_a\lor p/_b
	\]
	Se $p/_a$, allora:
	\begin{align*}
		&a=\lambda p\\
		&p=ab \;\Rightarrow \; p=\lambda pb\\
		&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\\
		&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'
\]
\subsubsection{Proprieta'}
\begin{enumerate}
	\item 
\[mcm(a,b)\cdot MCD(a,b)=ab\]
\item Possiamo calcolare il MCD e il mcm in questo modo:
	\label{mcmMCD123}
\begin{align*}
	&a=q_1^{m_1}q_2^{m_2}\cdots q_s^{m_s},\;\;m_i\ge 0\\
	&b=p_1^{t_1}p_2^{t_2}\cdots p_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*}
\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}
\[
	d=MCD(a,b) \;\;\Rightarrow\;\; d=\lambda a+\mu b
\]

\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<n$, allora $m=q_1q_2\cdots q_r$, dove $q_i$ e'
	primo.\\
	Ts: \[n=\begin{cases}
		\textrm{primo}\\
		\textrm{non primo, riducibile}
	\end{cases}\]
	Nel secondo caso, $n$ ammette dei divisori diversi da $\pm 1$ e da $n$,
	quindi scriviamo:
		\[n=ab\]
	Ma $a,b < n$, e quindi per Hp:
	\begin{align*}
		&a=q_1q_2\cdots q_r\\
		&b=p_1p_2\cdots p_s\\
		&n=ab=q_1q_2\cdots q_rp_1p_2\cdots p_s
	\end{align*}
	Quindi abbiamo dimostrato l'induzione, ovvero che ogni numero
	$\mathbb{Z}$ si puo' scrivere come prodotto di primi. Ci resta da
	verificare l'unicita'.\\
	Supponiamo che $n$ si possa fattorizzare in due modi diversi:
	\begin{align*}
		&r,s \in \mathbb{N}, \; r<s\\
		&n=q_1q_2\cdots q_r\\
		&n=p_1p_2\cdots p_s\\
		&q_1q_2\cdots q_r=p_1p_2\cdots p_s
	\end{align*}
	Ricordiamoci che abbiamo supposto che $r< s$\\
	Intanto $q_1/_{q_1}$ e anche $q_1/_{p_i}$. Per semplicita' poniamo
	$i=1$. Ma sia $p_1$ che $q_1$ sono primi, quindi deduciamo che poiche'
	$q_1/_{p_1}$ allora $q_1=p_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 $r<s$. Poiche' possiamo ripetere questa stessa
	dimostrazione per $r>s$ 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}
\subsection{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}
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]$.
\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}
Consideriamo la seguente equazione in $\mathbb{Z}_n$:
\[
[a][x]=[b]
\]
Questa equazione ammette una e una sola soluzione se $MCD(a,n)=1$, ovvero se
$[a]_n$ e' invertibile.

\begin{proof}
	Per Hp esiste l'inverso di $[a]$ che chiamiamo $[a']$, allora:
	\begin{align*}
	&[a'][a][x]=[a'][b]\\
	&[x]=[a'][b]
	\end{align*}
	Vogliamo dimostrare che e' unica. Supponiamo per assurdo che esistano
	due soluzioni:
	\begin{align*}
		&[a][x_1]=[b]\\
		&[a][x_2]=[b]\\
		&[a][x_1]=[a][x_2]\;\Rightarrow \;[a'][a][x_1]=[a'][a][x_2]\;\Rightarrow \;\; [x_1]=[x_2]
	\end{align*}
\end{proof}

In generale se $\left(d=MCD(a,n) \right)/_b$ allora l'equazione ammette $d$ soluzioni
distinte, altrimenti se non e' vero che $d/_b$, l'equ non ammette
soluzionio.\\ Data la soluzione $x_0$, tutte le altre sono:
\[
x_i=x_0+\frac{n}{d}i\;\;(\mod n)
\]
L'algoritmo per calcolarle e' il seguente:
\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}

\subsection{Teorema cinese del resto}
Abbiamo un sistema di equazioni modulari:
\[
\begin{cases}
	a_1x=b_1\;\; (\mathbb{Z}_{m_1})\\
	\vdots\\
	a_nx=b_n\;\; (\mathbb{Z}_{m_t})
\end{cases}
\]
La domanda e', qual'e' la $x$ che soddisfi contemporaneamente tutte le
soluzioni?\\
Prima di tutto questo sistema ammette soluzioni se ogni sua singola equazione
e' risolvibile e cioe' $MCD(a_i, m_j)=1$.\\
Risolvendo ogni singola equazione abbiamo il sistema:
\[
\begin{cases}
	x_1=c_1\;\; (\mathbb{Z}_{m_1})\\
	\vdots\\
	x_n=c_n\;\; (\mathbb{Z}_{m_t})
\end{cases}
\]
Ora, il teorema dei cinesi afferma che se $MCD(m_i,m_j)=1\;\;i\neq j$, allora
il sistema ammette soluzioni. Nota che non e' un ``se e solo se''. Infatti
questa condizione potrebbe non essere verificata, ma il sistema potrebbe
anche ammettere alcune soluzioni.
\begin{proof}
	Proviamolo e contemporaneamente diamo il metodo risolutivo del
	sistema.\\
	\begin{align*}
		&R=m_1m_2\dots m_t\;\;\textrm{corrisponde al
		$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 soluzioni, 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_1R1+\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$, quindi:
	\[
	x=x1R1=c_1 \;\;(\mathbb{Z}_{m_1})
	\]
	Lo stesso vale per tutte le altre equazioni, cioe':
	\[
	x=c_i\;\;(\mathbb{Z}_{m_i})
	\]
	Allora tutte le infinite soluzioni del sistema sono:
	\[
	x+\lambda R
	\]
	perche' in ogni $m_i$ succede che $R=0$ e quindi $x=c_i$.

\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)
\section{Equazioni diofantee}
\[
	ax+by=c,\;\;\;a,x,b,y,c\in \mathbb{Z}
\]
e' una equazione diofantea.
\\
Una equazione diofantea ha infinite soluzioni se e solo se:
\[
	MCD(a,b)/_c
\]
\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)$.  ???Ma questo significa che anche $a/d$ divide
	$(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 piu' semplice (almeno per noi umani) e' quello di usare
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}
Yeahaha, si parte!
\subsection{La funzione di Eulero}
Ecco la funzione di Eulero:
\[
\varphi(n)=|U_n|
\]
Dove $U_n$ era stato definito nel paragrafo \ref{sec:invertible_set}. In altre
parole, $\phi(n)$ e' il numero di tutti i coprimi a $n$, minori di $n$.
Esiste una formula efficiente per calcolare questo numero:
\[
\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}$ e' la fattorizzazione di $n$.
\begin{proof}
	Dimostriamo la formula.\\
	Per prima cosa osserviamo che se $MCD(m,n)=1$ allora
	$\varphi(nm)=\varphi(n)\varphi(m)$. Questo e' vero perche',
	$\mathbb{Z}_{mn}$ e  $\mathbb{Z}_n\times\mathbb{Z}_m$ sono due insiemi
	che si possono legare da una applicazione biettiva, cioe':
	\[
	f:\mathbb{Z}_{mn} \leftrightarrow \mathbb{Z}_n\times\mathbb{Z}_m
	\]
	\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.
\item Iniettivita':\\
	Dobbiamo dimostrare che $f(x)=f(y) \;\Rightarrow \;x=y$, cioe':
	\begin{align*}
		&f(x)=(a,b)=f(y)=(c,d)\;\Rightarrow (a=c,b=d)\\
		&\dots \textrm{da continuare}
	\end{align*}
	\end{enumerate}
	Poiche' per ogni coprimo in $\mathbb{Z}_{mn}$, minore di $mn$, esiste
	una coppia $(a,b) \in \mathbb{Z}_m\times \mathbb{Z}_n$, allora 
	\[
		\varphi(nm)=\varphi(n)\varphi(m)
	\]
	Quindi 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:
	\[
		m<p^h,\;\;MCD(m,p^h)\neq 1\;\Leftrightarrow \;m=\lambda p
	\]
	Tutti i possibili $m$, cioe' i multipli di $p$ minori di $p^h$ sono
	$p^{h-1}$, infatti:
	\begin{align*}
		&px<p^h\\
		&x<p^{h-1}
	\end{align*}
	
	Quindi tutti i coprimi con $p^h$ sono:
	\[
	\varphi(p^h)=p^h-p^{h-1}=p^h\left( 1-{1\over p} \right)
	\]
	E cosi' ritorniamo alla tesi:
	\begin{align*}
	&\varphi(n={p_1}^{m_1}{p_2}^{m_2}\dots {p_t}^{m_t})=\\
	& \qquad ={p_1}^{m_1}\left(1-{1 \over p_1}\right){p_2}^{m_2}\left(1-{1 \over p_2}\right)\dots{p_t}^{m_t}\left(1-{1 \over p_t}\right)\\
	&\varphi(n)=n\left(1-{1 \over p_1}\right)\left(1-{1 \over p_2}\right)\dots\left(1-{1 \over p_t}\right)
	\end{align*}
\end{proof}
\subsection{Teorema di Fermat}
\[
p \equiv \textrm{primo}, \; a \neq \lambda p \;\;\Rightarrow \;\;a^{p-1}=1
\;\;(\textrm{in } \mathbb{Z}_p)
\]
Ovvero, se p e' primo e non divide a, allora $a^{p-1}$ e' congruo 1 modulo p.
Il teorema di Fermat e' un caso particolare del teorema di Eulero.
Una sua forma equivalente e':
\[
p \equiv \textrm{primo}, \; a \in \mathbb{Z} \;\;\Rightarrow \;\;a^p=a
\;\;(\textrm{in } \mathbb{Z}_p)
\]

\subsection{Teorema di Eulero}
\[
MCD(a,n)=1\;\;\Rightarrow \;\; a^{\varphi(n)} =1 \;\;(\mathbb{Z}_n)
\]
\begin{proof}
	Dimostriamo $\Leftrightarrow $.\\
	Poniamo $t=\varphi(n)=|U_n|$, inoltre:
	\[
	U_n=\{u_1,\dots,u_t\}
	\]
	$U_n$ e' l'insieme degli invertibili distinti in $\mathbb{Z}_n$, quindi
	$MCD(u_i,n)=1$. Allora, per Hp, anche $a\in U_n$.\\
	Se moltiplichiamo due $u_iu_j$ otteniamo sempre un invertibile $\in
	U_n$:
	\begin{align*}
		&u_j{u_j}^{-1}=1\\
		&u_i{u_i}^{-1}=1\\
		&u_ju_i{u_j}^{-1}{u_i}^{-1}=1
	\end{align*}
	Quindi $au_i$ e' sempre $\in U_n$, cioe':
	\[
	au_1, au_2, \dots, au_t \in U_n
	\]
	Ci domandiamo se $\{au_1, au_2, \dots, au_t\}$ sia proprio $U_n$.
	Supponiamo per assurdo che non lo sia, cioe' $au_i=au_j,\;i\neq j$, allora:
	\begin{align*}
		&aa^{-1}u_i=aa^{-1}u_j\\
		&u_i=u_j
	\end{align*}
	Ma questo e' assurdo, perche' per ipotesi abbiamo detto che ogni
	elemento di $U_n$ e' distinto. 
	Poiche' $|\{au_1, au_2, \dots, au_t\}|=|U_n|$, concludiamo che i due
	insiemi coincidono.
	Allora possiamo scrivere:
	\begin{align*}
		&au_1au_2\dots au_t=u_1u_2\dots u_t\\
		&a^t(u_1u_2\dots u_t)=(u_1u_2\dots u_t)\\
		&a^t=1
	\end{align*}
	Cioe' la tesi.
\end{proof}
\subsection{Proprieta' dei primi}
\begin{enumerate}
	\item Sono infiniti.
		\begin{proof}
			Supponiamo che non lo siano e creiamo l'insieme che li
			contiene tutti:
			\[
			P=\{p_1,p_2,\dots,p_t\}
			\]
			Ma il numero $q=p_1p_2\dots p_t+1$ e' primo rispetto ai
			primi definiti in $P$, infatti, $q\equiv 1 \;(\mod
			p_i)$
	\end{proof}
\item $2^m+1$ e' primo sole se $m=2^n$.
	\begin{proof}
	Per assurdo $m=ph, \;p\neq 2$, allora $m$ e' dispari: $m=2h+1$. Allora:
	\[
	2^{(2h+1)h}+1={2^h}^{2h+1}+1
	\]
	L'ultima e' una somma di potenze dispari e quindi si puo' scrivere
	come:
	\[
	{2^h}^{2h+1}+1=(2^h+1)(\dots)
	\]
	Quindi $2^m+1$ non e' primo, perche' prodotto di due fattori.
	\end{proof}
	Ancora non e' stato provato se $2^{2^n}+1$ e' primo per $n>4$.
\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 1<d<p:\;\;d/_p\; \Rightarrow \;d/_{\lambda p}
	\]
	Inoltre $d/_{(p-1)!+1}$, ma questo e' assurdo, perche' siccome
	$d/_{(p-1)!}$ dovrebbe anche essere $d/_1$.
\end{proof}
\begin{proof}
	Dimostriamo $\Rightarrow $.\\
	Quando $p$ e' primo, tutti gli elementi in $\mathbb{Z}^{*}_p$ sono
	invertibili. Quali sono gli elementi invertibili che hanno come
	inverso se stessi? Ovvero,
	\begin{align*}
		&xx=1 \;\Leftrightarrow \; x^2=1\;\Leftrightarrow \;
		x^2-1=0\;\;(\mathbb{Z}^{*}_p)\\
		&(x-1)(x+1)=0\\
		&x=1\;\lor \;x=-1=p-1\;\;(\mathbb{Z}^{*}_p) \;\textrm{in $Z_p$
		vale la legge dell'annullamento del prodotto}
	\end{align*}
	Cioe', $x=\pm 1$ sono gli elementi invertibili che hanno come
	        inverso se stessi.
		Invece, l'invertibile di $y\neq \pm1$ sara' $y^{-1}\neq y \in
		0,\dots,p-1$, quindi:
	\begin{align*}
&	2\cdot3\cdot4\cdot\dots\cdots(p-2)=1\;\;(\mathbb{Z}^{*}_p)\\
&1\cdot2\cdot3\cdot4\cdot\dots\cdots(p-2)(p-1)=(p-1)\;\;(\mathbb{Z}^{*}_p)\\
&(p-1)! = (p-1)\;\;(\mathbb{Z}^{*}_p)
\end{align*}


\end{proof}


\subsection{R.S.A}
Ecco un'applicazione moderna dei teoremi sui numeri primi: la criptografia a
chiave asimmetrica RSA.
\subsection{La chiave pubblica}
La chiave pubblica e' una coppia di numeri $(n.e)$.
$n$ e' un prodotto di due primi $p\cdot q$.\\
$e$ e' invece un numero coprimo con $(p-1)$ e $(q-1)$, cioe'
\[
MCD(e,p-1)=1\;\;\land \;\;MCD(e,q-1)=1
\]
\subsection{Messaggio criptato}
$M$ e' il nostro messaggio e deve essere $< n$ e inoltre deve essere coprimo
con $n$. Il messagio criptato $M'$ e' semplicemente:
\[
M'=M^e \;\;(\mathbb{Z}_n)
\]
\subsection{Chiave privata}
La chiave privata e' costituita da $(\varphi(n), d)$, dove
$\varphi(n)=(p-1)(q-1)$ e' la
funzione di eulero applicata a $n$.\\
$d$ e' l'inverso di $e$ in $\mathbb{Z}_{\varphi(n)}$.
Quindi:
\[
de=1\;\;(\mathbb{Z}_{\varphi(n)})
\]
e inoltre:
\[
de-1=\lambda {\varphi(n)}\;\;\Rightarrow \;\;de=1+\lambda {\varphi(n)}
\]
Nota: l'inverso di $e$ esiste sicuramente in $\mathbb{Z}_{\varphi(n)}$ perche'
$e$ e' coprimo con $(p-1)$ e $(q-1)$.

\subsection{Messaggio decriptato}
Per decriptare il messagio basta fare:
\[
M={M'}^d\;\;(\mathbb{Z}_n)
\]
\begin{proof}
	Dimostriamo che la procedura per decriptare il messaggio e' valida:
	\begin{align*}
		&{M'}^d={{M}^e}^d={M}^{ed}\;\;(\mathbb{Z}_n)
	\end{align*}
	Per quello che abbiamo visto nel precedente paragrafo, possiamo
	scrivere $ed$ come $1+\lambda {\varphi(n)}$, 	quindi:
	\[
	{M}^{ed}={M}^{1+\lambda {\varphi(n)}}=M{\left(M^{\varphi(n)}\right)}^{\lambda}
	\]
	Poiche' $M$ e' coprimo con $n$, allora per il teorema di Eulero,
	$M^{\varphi(n)}=1\;\;(\mathbb{Z}_n)$, quindi:
	\[
	M{M^{\varphi(n)}}^{\lambda}=M\left({M^1}\right)^{\lambda}=M^2=M\;\;(\mathbb{Z}_n)
	\]
\end{proof}
\section{L'insieme $\mathbb{Q}$}
Prendiamo due coppie $(a,b), (c,d) \in \mathbb{Z}$, con l'unica condizione che
$(c,d)\neq 0$.\\
Definiamo la seguente relazione di equivalenza:
\[
(a,b)\sim(c,d)\;\;\Leftrightarrow \;\;ad=bc
\]
La classe $[(a,b)]$ la denoteremo con $\frac{a}{b}$.\\
Ed ecco nato $\mathbb{Q}$:
\[
\mathbb{Q}=\mathbb{Z}\times \mathbb{Z}^{*}/_{\sim}
\]
Definiamo le operazioni.
\subsection{Addizione}
\[
\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd},\;\;b\neq 0,c\neq 0
\]
Questa e' una definizione ben posta, perche' se prendiamo due classe
equivalenti a $\frac{a'}{b'}$ e ad $\frac{c'}{d'}$, la loro somma sara' identica a
quella fra $\frac{a}{b}$ e ad $\frac{c}{d}$.
\subsubsection{Proprieta'}
\begin{enumerate}
	\item + e' commutativa
	\item + e' associativa
	\item In + esiste l'elemento neutro:
		\[
		\frac{a}{b}+\frac{0}{b}=\frac{a}{b}
		\]
		L'elemento neutro e' $\frac{0}{b},\;\;b\neq 0$
	\item In + esiste l'opposto:
		\[
		\frac{a}{b}+\frac{-a}{b}={0\over b}
		\]
\end{enumerate}
Queste quattro proprieta' rendono $(\mathbb{Q}, +)$ un gruppo abeliano
commutativo.
\subsection{Moltiplicazione}
\[
\frac{a}{b}\cdot\frac{c}{d}=\frac{ac}{bd},\;\;b\neq 0,c\neq 0
\]
Anche questa e' una definizione ben posta.
\subsubsection{Proprieta'}
\begin{enumerate}
	\item $\cdot$ e' commutativa
	\item $\cdot$ e' associativa
	\item In $\cdot$ esiste l'elemento neutro:
		\[
		\frac{a}{b}\cdot\frac{c}{c}=\frac{a}{b}
		\]
		L'elemento neutro e' $\frac{c}{c}=\frac{1}{1},\;\;c\neq 0$
	\item $\cdot$ e' distributivo rispetto alla somma
\end{enumerate}
Queste proprieta' unite a quelle dell'addizione rendono $(\mathbb{Q}, +,
\cdot)$ un anello abeliano commutativo.\\

L'ultima proprieta': in $\cdot$ esiste l'inverso, anzi, per ogni numero
$\mathbb{Q}$ diverso da $0$ esite il suo inverso:
		\[
		\frac{a}{b}\cdot\frac{b}{a}={c \over c},\;\;a\neq 0,b\neq 0
		\]
Come conseguenza, vale la legge dell'annullamento del prodotto.\\
Con quest'ultima proprieta' $\mathbb{Q}$ e' diventato un campo.
\subsection{Immersione di $\mathbb{Z}$ in $\mathbb{Q}$}
Insiemisticamente, e' sbagliato scrivere che $\mathbb{Z} \subseteq Q$. E'
pero' vero che $\mathbb{Z}$ e' immerso in $\mathbb{Q}$.
\begin{proof}
	Per provare questo dobbiamo trovare una funzione iniettiva:
	\[
	f:\mathbb{Z}\hookrightarrow \mathbb{Q}
	\]
	tale che 
	\[
	f(x+y)=f(x)+f(y)\;\;\land \;\;f(xy)=f(x)f(y)
	\]
	La funzione cercata e':
	\[
	f(x)=\frac{x}{1}
	\]
\end{proof}
\section{L'insieme $\mathbb{R}$}
In $\mathbb{Q}$, non tutti i sottoinsiemi hanno l'estremo inferiore.
$\mathbb{R}$ colma questa lacuna.\\
Un elemento di $\mathbb{R}$ e' una coppia $(A,B)$ che e' una sezione di
$\mathbb{Q}$, ovvero 
\begin{align*}
	&A\cup B=\mathbb{Q}\\
	&A \cap B = \emptyset\\
	&\forall a \in A, \;\;\forall b \in B,\;\;a<b
\end{align*}
Ad esempio $\sqrt{2}$ e' la coppia \[(\{x \in \mathbb{Q}| \;x^2 < 2 \}, \;\{x
\in \mathbb{Q}^{+}|\;\;x^2>2\})\]
$\mathbb{R}$ e' un campo ed e' anche un campo ordinato, cioe' valgono queste
due proprieta':
\begin{align*}
	&a\le b\\
	&a+c\le b+c\\
	&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 orinati 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)=0$. 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
\]
\[
g(x)=\sum_{i=0}^{d'} b_ix^i
\]
\[
c_t=\sum_{i=0}^{d+d'} a_ib_{t-i}
\]
\[
(f\cdot g)(x)=\sum_{i=0}^{\max(d,d')}c_ix^i
\]
\par

Con queste operazioni, $(\I_k,+,\cdot)$ e' un dominio di integrita',
cioe' 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'), ed poiche' esiste la legge
dell'annullamento del prodtto e' un dominio di integrita'.
\subsection{Poliniomio}
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 (in
$\mathbb{Z}_3$ che gli corrispondono 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,\;\;f(\alpha)=g(\alpha)
	\]
	Allora,
	\[
	F(\alpha)=f(\alpha)-g(\alpha)=0
	\]
	quindi $\alpha$ e' una radice di $F(x)$, ma questo e' in assurdo con
	il corollario del teorema di ruffini (vedi \ref{cor_ruff}), perche'
	vuol dire che esistono infinite radici, invece, ruffini dice che ce ne
	sono al piu' $\deg F(x)$.
\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.
\subsubsection{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 $m<n$ allora  abbiamo $f(x)=0\cdot
	g(x)+f(x)$. Quindi da adesso supponiamo $m \ge n$.\\
	Procediamo per induzione:
	\begin{enumerate}
		\item Base: la base e' stata gia' dimostrata con $f(x)=0$.
		\item Hp: supponiamo che per i polinomi di grado $< m$ il
			teorema sia vero.
		\item Dimostriamo allora per il polinomio $f(x)$ che ha grado
			$m$.\\
			Scegliamo questo opportuno polinomio:
			\[
			F(x)=f(x)-a_mb_n^{-1}x^{m-n}g(x)
			\]
			Il coefficiente $a_mb_n^{-1}x^{m-n}$ serve per
			togliere $b_mx^n$ da $g(x)$, infatti,
			$(a_mb_n^{-1}x^{m-n})(b_nx^n)=a_mx^m$.
			Poiche' $a_mx^m$ e' presente in $f(x)$, quando
			facciamo $f(x)-a_mx^m$, viene eliminato da $F(x)$,
			quindi $\deg F(x) < m$. Allora per l'Hp induttiva,
			possiamo scrivere:
			\begin{align*}
				&f(x)-a_mb_n^{-1}x^{m-n}g(x)=q'(x)g(x)+r(x)\\
				f(x)=&a_mb_n^{-1}x^{m-n}g(x)+q'(x)g(x)+r(x)\\
				=&\left(a_mb_n^{-1}x^{m-n}+q'(x)\right)g(x)+r(x)
			\end{align*}
			Inoltre sempre per l'Hp induttiva $\deg r(x) < \deg
			g(x)$  oppure $r(x)=0$
		\end{enumerate}
\end{proof}
\subsection{Polinomi associati}

\[
f(x), g(x) \equiv \textrm{ associati }\;\Leftrightarrow \; f(x)/_{g(x)} \land
g(x)/_{f(x)}
\]
L'associato di $f(x)$ e' \[
f(x)a,\;\;\forall a \in K^{*}
\]
\subsection{Polinomi primi}
\[
f(x) \equiv \textrm{primo}\;\Leftrightarrow \; \left(f(x)/_{g(x)h(x)}
\Rightarrow f(x)/_{g(x)}\;\lor\;f(x)/_{h(x)} \right)
\]
\subsection{Poliniomio irriducibile}
\[
f(x)=g(x)h(x) \equiv \textrm{irriducibile}\;\Leftrightarrow \; h(x) \equiv
\textrm{invertibile} \;\lor \; g(x) \equiv  \textrm{invertibile} 
\]
Ovvero $f(x)$ e' irriducibile se tutti i suoi fattori, tranne uno, sono
costanti non nulle.
Un polinomio di primo grado e una costante sono entrambi irriducibili.\\
Vale sempre il seguente teorema:
\[
f(x) \equiv  \textrm{irriducibile}\;\Leftrightarrow \;f(x)\equiv \textrm{primo}
\]
\subsection{MCD di polinomi}
Il MCD di due polinomi e' definito come quello che abbiamo usato su
$\mathbb{Z}$: 
\[
d=MCD(f(x), g(x) )\; \Leftrightarrow \; d/_{f(x)} \;\land \; d/_{g(x)} \;\land
\; \left(d'/_{f(x)} \land  d'/_{g(x)} \;\Rightarrow \;
d'/_d\right)
\]
Il MCD si puo' calcolare con l'algoritmo euclideo, che si puo' applicare sui
polinomi. (In questo caso l'algoritmo compie un numero finito di passi perche'
il grado del resto diminuisce sempre piu', fino a quando si arriva al
resto-polinomio-nullo).\\
Dall'algoritmo euclideo si ricava sempre l'identita' di Bezout:
\[
MCD(f(x), g(x) ) = \lambda(x) f(x) + \mu(x)g(x)
\]
\subsection{Fattorizzazione unica di un polinomio}
Cosi' come in $\mathbb{Z}$ un polinomio si puo' fattorizzare in maniera unica.
Stavolta, pero', non solo a meno dell'ordine e del segno, ma anche a meno di
invertibili.\\
Ad esempio:
\[
x^2-1=(x-1)(x+1)=\left(\frac{1}{2}x-\frac{1}{2}\right)\left(2x+2\right)=x^2-1
\]
La dimostrazione e' identica a quella usata in $\mathbb{Z}$.
\subsection{Teorema di Ruffini}
$\alpha \in \mathbb{Z}$ e' una radice di $f(x)$ se $f(\alpha)=0$.\\
Il teorema di Ruffini dice che:
\[
f(\alpha)=0\;\Rightarrow\;f(x)=(x-\alpha)f'(x)
\]
Come corollario deduciamo che se $\deg f(x) \ge 2\;\land \;f(\alpha)=0$ allora
$f(x)$ e' riducibile.
\begin{proof}
	Per l'algoritmo di divisione di un polinomio possiamo scrivere:
	\[
	f(x)=(x-\alpha)q(x)+r(x)
	\]
	Se $\deg r(x) < \deg(x-\alpha)$ allora $\deg r(x) < 1$, ovvero
	$r(x)=c$ e' un polinomio costante.
	\begin{align*}
	&	f(\alpha)=(\alpha-\alpha)q(x)+r(x)\\
	&f(\alpha)=0,\;\;r(x)=c\\
	& 0=0\cdot q(x)  +c\\
	&0=c
	\end{align*}
	E questo e' assurdo, quindi l'algoritmo di divisione ci dice che
	necessariamente $r(x)=0$, ovvero
	\[
	f(x)=(x-\alpha)q(x)
	\]
	\end{proof}

\label{cor_ruff}
Come corollario possiamo dire che $f(x)\neq 0\in K$ di grado $n$, ha al piu'
$n$ radici.
\begin{proof}
	Lavoriamo per induzione.\\
	Base: $n=0$, il polinomio di grado $0$ ha $0$ radici.\\
	Hp: tutti i polinomi di grado $m<n$ hanno al piu' $m$ radici.\\
	Ts: Il polinomio $f(x)$ con grado $m$, si puo' scrivere come:
	$f(x)=(x-\alpha)q(x)$. $\deg q(x)=n-1$, quindi per l'Hp induttiva ha
	al piu' $n-1$ radici. Ma dato che $\alpha$ e' una radice, $f(x)$ avra'
	al piu' $1+n-1=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<n$ hanno esattamente $m$ radici.\\
	Ts: Prendiamo $f(x) \in \mathbb{C}[x], \;\;\deg f(x) = n$.
	Per il teorema fondamentale dell'algebra sappiamo che $f(x)$ ha
	almeno una radice $f(\alpha_1)$, allora per ruffini:
	\[
	f(x)=(x-\alpha_1)h(x)
	\]
	Poiche' $\deg h(x) = n -1 < n$, entra in gioco l'Hp induttiva, e
	quindi $h(x)$ ha esattamente $n-1$ radici. Dato che $\alpha_1$ e' una
	radice di $f(x)$, $f(x)$ avra' in totale $n$ radici.
\end{proof}

\subsubsection{Coniugato di un polinomio}
Dato \[
f(x)=a_0+a_1x+\dots+a_dx^d \;\in \mathbb{C}[x]
\]
chiamiamo $\overline{f(x)}$ coniugato di $f(x)$
\[
\overline{f(x)}=\overline{a_0}+\overline{a_1}x+\dots+\overline{a_d}x^d
\]
Dove $\overline{a_i}$ e' il coniugato di $a_i$.\\
Vale la seguente proprieta':
\[
f(\alpha)=0 \;\;\Rightarrow \;\;\overline{f(\overline{\alpha})}=0
\]
$\alpha$ e' radice di $f(x)$ e $\overline{\alpha}$ e' radice di
$\overline{f(x)}$.
\subsubsection{Fattorizzazione in $\mathbb{C}$}
In $\mathbb{C}[x]$, conoscendo le radici di $f(x)$, possiamo fattorizzare
$f(x)$ in: 
\[
f(x)=(x-a_1)\dots(x-a_r)g_1(x)\dots g_t(x)
\]
dove $a_i \in \mathbb{R}$ sono le radici reali di $f(x)$ e 
\[g_i(x)=x^2-(\alpha_i+\overline{\alpha_i})x+\alpha_i\overline{\alpha_i}\]
e dove $\alpha_i$ sono le radici complesse di $f(x)$.


\subsection{Irriducibilita' di un polinomio in $\mathbb{R}$}
Osserviamo  che $\mathbb{R}[x] \subseteq \mathbb{C}[x]$.\\
Data $f(x) \in \mathbb{R}[x] \subseteq \mathbb{C}[x]$, accade che 
\[f(x)=\overline{f(x)}\],
perche' i coefficienti di $f(x)$ sono nella forma
$(a,0)$ e quindi $(a,0)=(a,-0)$.\\
Questo significa che se un polinomio in
$\mathbb{R}[x]$ ammette una radice complessa, allora ammettera' anche la sua coniugata.
Quindi in $\mathbb{R}[x]$ le radici complesse vanno sempre a coppia.\\

Accade che:
\[f(x) \in \mathbb{R}[x] \equiv  \textrm{irriducibile}\;\Leftrightarrow \;
\deg f(x) = 1 \;\lor \; \left(\deg f(x) = 2 \;\land \;\Delta < 0\right)\]
In tutti gli altri casi e' riducibile, cioe' per \[\deg f(x) > 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 uniche radici 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{\frac{r}{s} }^n=0\\
		&a_0s^n+a_1s^{n-1}+\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}
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.

\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$. Possono accadere
	due casi:
	\[
	p/_{a_i} \;\lor \; p/_{b_j}
	\]
	ma tutte e due casi sono assurdi, perche' $f(x)$ e $g(x)$ sono
	primitivi, e quindi $p$ non puo' dividere tutti i loro coefficienti.
\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]$}
Se $f(x)$ e' primitivo allora:
\[
f \textrm{ irriducibile in } \mathbb{Z}[x] \;\Leftrightarrow \; \textrm{
irriducibile in } \mathbb{Q}[x]
\]
\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]
	\]
	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}
	\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<r<d\;\land \;0<s<d
	\]
	$g(x), h(x)$ sono polinomi primitivi, perche' per Hp $f(x)$ lo e'
	pure e quindi per il Lemma di Gauss anche loro devono esserlo.
	$a_0=b_0c_0$ e per Hp il primo $p$ divide $a_0$, cioe'
	\[
	p/_{a_0}\;\Rightarrow \; p/_{b_0}\;\lor \; p/_{c_0}
	\]
	In questo caso pero', possiamo sicuramente affermare che $p\nmid c_0$,
	infatti, se cosi' fosse accadrebbe che:
	\begin{align*}
		&p=\lambda b_0,\;\;p=\mu c_0\\
		&p*p=(\lambda \mu) b_0c_0 \;\Rightarrow \; p^2/_{a_0}
	\end{align*}
	Ma per Hp $p^2\nmid_{a_0}$.\\
	Adesso ricordandoci che $g(x)$ e' primitivo, possiamo dedurre che $p$
	potra' dividire al piu' tutti i suoi coefficienti, tranne uno, cioe':
	\[
	p/_{b_0}, \;p/_{b_1}, \dots, p/_{b_{i-1}}, \;p\nmid b_i
	\]
	Adesso, consideriamo
	\[
	a_i=c_0b_i+c_1b_{i-1}+\dots+c_{i-1}b_1+c_ib_0
	\]
	Per Hp sappiamo che $p/_{a_i}$ e abbiamo visto che $p$ divide tutti i
	$b_j,\; j=0,\dots,i-1$, quindi dividera' anche
	\[
	K=c_1b_{i-1}+\dots+c_{i-1}b_1+c_ib_0
	\]
	allora, dividera' pure' $a_i-K$, ma poiche'
	\[
	a_i-K=c_0b_i
	\]
	segue che
	\[
	p/_{c_0}\;\lor \;p/_{b_i}
	\]
	Ma in entrambi i casi abbiamo visto che questo e' impossibile, quindi
	tutto questo e' assurdo.
\end{proof}
\subsection{Criterio di riduzione modulo p}
\label{criteriomodp}
Prima di tutto premettiamo alcune definizioni.\\
Un polinomio si dice monico se il coefficiente dell'indeterminata di grado
massimo e' 1.\\
In $\mathbb{Z}_n[x]_d$, possono esistere $n^{d+1}$ polinomi distinti, dove $d$
e' il loro grado, infatti, ogni coefficiente di un'indeterminata puo' assumere 
i valori da $0,1,\dots,n-1$, percio' se abbiamo $d+1$ coefficienti, tutte le
possibili combinizioni sono \[\underbrace{n\cdot n \cdots n}_{d+1 \textrm{volte}} \]
Se invece stiamo considerando polinomi monomici in $\mathbb{Z}_n[x]_d$, allora
in totale sono $n^{d}$, perche' il coefficiente di $x^d$ sara' sempre $1$.\\

Facciamo un esempio di come si controlla se un polinomio in $\mathbb{Z}n[x]$
e' irriducibile. Consideriamo il polinomio \[f(x)=x^4+x+4 \in \mathbb{Z}_5[x]\]
Prima di tutto controlliamo se ha radici:
\begin{align*}
	&f(0)=4\qquad f(1)=1\qquad f(2)=2\\
	&f(3)=(-2)^{4}-2+4=18=3\qquad f(4)=(-1)^4-1+4=4
\end{align*}
Quindi non ha radici in $\mathbb{Z}_5[x]$, e quindi sappiamo che non si puo'
scomporre come prodotto di un polinomio di terzo grado e uno di primo.
Adesso controlliamo se si puo' scomporre come prodotto di due polin. di
secondo grado, ovvero dobbiamo risolvere questo:
\[
x^4+x+4=(x^2+ax+b)(x^2+cx+d)= x^4+(a+c)x^3+(b+ac+d)x^2+(bc+ad)x+bd
\]
che corrisponde a risolvere questo:
\[
\begin{cases}
	a+c=0\\
	b+ac+d=0\\
	bc+ad=1\\
	bd=4
\end{cases} \Rightarrow 
\begin{cases}
	c=-a\\
	b-a^2+d=0\\
	a(d-b)=1\\
	bd=4
\end{cases}
\]
$bd=4$ e' vera solo in questi casi:
\[
\begin{matrix}
	b=1&d=4\\
	b=2&d=2\\
	b=3&d=3\\
	b=4&d=1
\end{matrix}
\]
Se fossero veri il secondo e il terzo caso allora $a(d-b)=1$ non avrebbe
senso, perche' $a\cdot 0\neq 1$. Se, invece, fosse vero il primo o l'ultimo
caso si avrebbe che $b-a^2+d=5-a^2=-a^2=0\;\Rightarrow \;a=0$. Ma questo rende
sempre assurdo $a(d-b)=1$. Quindi, in conclusione, il sistema non ammette
soluzioni e percio' il polinomio e' irriducibile in $\mathbb{Z}_5[x]$.\\

Adesso arriviamo al criterio vero e proprio.\\
\label{Criteriomodulop}
Sia \[f(x)=a_0+a_1x+\dots+a_dx^d\;\in\mathbb{Z}[x]\]
e sia primitivo, allora
\[
\exists p, \textrm{ primo}:\;\; p\nmid {a_d}, \;\;\land \;\;f(x) \textrm{
irriducibile in } \mathbb{Z}_p[x]\;\;\Rightarrow \;\;f(x) \textrm{
irriducibile in } \mathbb{Z}[x]
\]
\begin{proof}
	Dimostriamo per assurdo, e supponiamo quindi che $f(x)$ sia riducibile
	in $\mathbb{Z}$, ovvero:
\[
	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<r<d\;\land \;0<s<d
	\]
	$g(x), h(x)$ sono polinomi primitivi, perche' per Hp $f(x)$ lo e'
	pure e quindi per il Lemma di Gauss anche loro devono esserlo.
	$a_d=b_rc_s$ e per Hp il primo $p$ non divide $a_d$, cioe'
	\[
	p\nmid {a_d}\;\Rightarrow \; p\nmid {b_r}\;\land  \; p\nmid {c_s}
	\]
	Adesso andiamo in $\mathbb{Z}_p[x]$.
	\[
	\deg [f(x)]_p = d
	\]
	Ovvero il grado di $f(x)$ in $\mathbb{Z}_p[x]$ non cambia, perche'
	dato che $p\nmid {a_d}$ la classe $[a_d]\neq 0$ e quindi
	l'indeterminata col grado $d$ non viene eliminata. Lo stesso accade
	per $[g(x)], [h(x)]$ perche' \[p\nmid {b_r}\;\land  \; p\nmid {c_s}\]
	Quindi, 
	\[
	[f(x)]=[g(x)][h(x)]
	\]
	ma questo e' assurdo perche' abbiamo scomposto $f(x) \in
	\mathbb{Z}_p[x]$ quando per Hp avevamo supposto che questo non era
	possibile.
\end{proof}
Un esempio. Considera \[
f(x)=x^4+25x^3+6x+84\in \mathbb{Q}[x]
\]
Poniamo $p=5$:
\[
[f(x)]_5 = x^4+x+4 \in \mathbb{Z}_5[x]
\]
ma, per quanto abbiamo calcolato prima, sappiamo che $x^4+x+4$ e' irriducibile
in $\mathbb{Z}_5[x]$, quindi $f(x)$ e' irriducibile in $\mathbb{Z}[x]$ e
conseguentemente in $\mathbb{Q}[x]$.

\section{Anelli}
\quote{One ring to rule them all}

Dato un insieme $A$ e due operazioni binarie interne su $A$ indicate con $+$ e
$\cdot$, possono valere queste proprieta':
\begin{enumerate}
	\item + e' associativa:
		\[
		\forall a,b,c \in A\;\;(a+b)+c=a+(b+c)
		\]
	\item + e' commutativa:
		\[
		\forall a,b \in A\;\;a+b=b+a
		\]
	\item Esiste l'elemento neutro dell'addizione:
		\[
\exists 0_A\in A:\; \forall a\in A \;\;0_A+a=a+0_A=a
		\]
	\item In + esiste l'opposto:
		\[
\forall a \in A \;\exists -a \in A|\;a+(-a)=(-a)+a=0_A
		\]
	\item $\cdot$ e' associativa:
		\[
		\forall a,b,c \in A\;\;(ab)c=a(bc)
		\]
	\item $\cdot$ e' distributiva rispetto all'addizione:
		\[
		\forall a,b,c \in A\;\;a(b+c)=ab+ac \; \land \; (a+b)c=ac+bc
		\]
	\item $\cdot$ e' commutativa:
		\[
		\forall a,b\in A\;\;ab=ba
		\]
	\item Esiste l'elemento neutro del prodotto:
		\[
\exists 1_A\in A:\;\;\forall a \in A\;\;1_Aa=a1_A=a
		\]
\end{enumerate}
a
Le proprieta' dalla 1 alla 4  rendono $(A, +)$ un gruppo abeliano (cioe' un gruppo commutativo).\\
Le proprieta' dalla 1 alla 6 rendono $(A, +, \cdot)$ un anello.\\
Le proprieta' dalla 1 alla 7 rendono $(A, +, \cdot)$ un anello commutativo.\\
Le proprieta' dalla 1 alla 6 e la otto rendono $(A, +, \cdot)$ un anello
unitario.\\
Le proprieta' dalla 1 alla 8 rendono $(A, +, \cdot)$ un anello commutativo
unitario.\\
\begin{thm}
Dato un anello $(A, +, \cdot)$ qualsiasi, possiamo dedurre che
\[
0\cdot x = x \cdot 0 = 0\;\;\forall x\in A
\]
\begin{proof}
	\begin{align*}
		&y=0x=(0+0)x\quad \textrm{prop. 3}\\
		&(0+0)x=0x+0x=y+y\quad \textrm{prop. 6}\\
		&y=y+y\\
		&(-y)+y=y+y+(-y)\\
		&y+y+(-y)=y+(y+(-y))\quad \textrm{prop. 1}\\
		&y+(y+(-y))=y+0=y\quad \textrm{prop. 4,3}\\
		&(-y)+y=y\;\Rightarrow \;0=y\\
		&0x=0
	\end{align*}
\end{proof}
\end{thm}
Puo' accadere che il prodotto di due elementi non nulli sia uguale a 0, ad
esempio in $\mathbb{Z}_{10}$ $2\cdot 5=0$, o anche in $M \in Q^{2,2}$ 
\[
\begin{pmatrix}
	0&0\\
	0&1
\end{pmatrix}\begin{pmatrix}
	5&0\\
	0&0
\end{pmatrix}=\begin{pmatrix}
	0&0\\0&0
\end{pmatrix}
\]
Questo significa che in generale la legge dell'annulamento del prodotto
\[
ab=0\;\Rightarrow \; a=0\lor b=0
\]
non vale.
Allora, dato un elemento $u \in A, u\neq 0$
\[
u \equiv \textrm{ divisore dello zero} \;\Leftrightarrow \;\exists u',u'' \neq
0|\;uu'=0=u''u=0
\]
Un \emph{dominio d'integrita'} e' un anello commutativo, non necessariamente
unitario, dove non esistono divisori dello zero, ovvero dove vale la legge
dell'annullamento del prodotto.\\

Sia $A$ un anello unitario, allora
\[
u \in A\equiv\textrm{ invertibile}\;\Leftrightarrow \;\exists u' \in
A:\;uu'=u'u=1_A
\]
$u'$ si denotera' con $u^{-1}$.\\
Per quanto abbiamo dimostrato prima ($0x=0$), lo zero non potra' mai essere un
elemento invertibile.\\
La proprieta' $9)$ e': tutti gli elementi dell'anello $(A,+, \cdot)$ unitario,
tranne lo zero, sono invertibili.\\
Un \emph{corpo} e' un anello unitario in cui tutti gli elementi diversi da
zero sono invertibili.\\
Un \emph{campo} e' un corpo commutativo, cioe' e' un corpo in cui il prodotto
e' commutativo. Quindi in un campo valgono tutte e nove le proprieta'.
Inoltre un campo e' un dominio d'integrita'.
\begin{proof}
	Se $a\neq 0, \;\;ab=0$, allora, poiche' siamo in un campo $\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{Dimini 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*}

\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}
In realta', esiste una caratterizzazione piu' semplice di un sottoanello che
richiede di verificare solo due proprieta':
\[
S\equiv \textrm{ sottoanello}\;\Leftrightarrow \;\forall x,y\in S\;\begin{cases}
	x-y\in S\\
	xy\in S
\end{cases}
\]
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*}
\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}.\\
\subsubsection{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}
	\item Questa terza proprieta' non vale in generale
		\[f(1)=1'\]
		ma solo per alcuni casi.\\
		Se $A, A'$ sono dei domini unitari e $f$ e' un omomorfismo non
		nullo, allora vale.
		\begin{proof}
			Infatti, 
			\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{proof}
		Se $f$ e' una surrezione allora vale.
		\begin{proof}
			$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{proof}
\end{enumerate}
\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 S\;\Leftrightarrow \;
		y\in 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 dimostrare 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 \;ax,xa\in I\cap S
	\]
	quindi,
	\begin{align*}
		&x\in I\cap S\;\Leftrightarrow \;x\in I\;\land \;x\in S\\
		&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-y)=f(x)-f(y)\in I'\;\Rightarrow 
				\;f^{-1}(f(x)-f(y))=x-y \in f^{-1}(I')
			\end{align*}
			e sempre usando $f()$:
			\begin{align*}
				&f(ax)=f(a)f(x)\\
				&f(a)\in A',\;f(x)\in I'\;\;\Rightarrow
				\;f(a)f(x)\in I'\\
				&\quad \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':
			\[
			x'z'=f(x)f(z)=f(xz) \in f(I)
			\]
		\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}
\[
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<A\;\Rightarrow \;\pi(S)<A/_I\Rightarrow \pi^{-1}(\pi(S))=S+I < A
\]
\begin{proof}
	$\pi(S)<A/_I$ e $\pi^{-1}(\pi(S)) < A$ sono vere per le proprieta'
	dimostrate in \ref{872jf82jhd}.
	\begin{align*}
		&\pi(S)=\{I+s \in A/_I\;|\;s\in S\}\\
		&\pi^{-1}(\pi(S))=\{ a \in A \;|\; \pi(a)=I+a=I+s,\;s\in
		S\;\Leftrightarrow \;a-s\in I\}=\\
		&\qquad = \{ a \in S+I \}
	\end{align*}
	Tutte le $a$ che stanno in $\pi^{-1}(\pi(S))$ sono in definitiva $\{ a
	\in S+I \}$, perche' rispettano la condizione $a-s\in I$, infatti:
		\[(s'+i')-s=(s'-s)+i'\]
		e poiche' $I\triangleleft A$,\[\underbrace{(s'-s)}_{\in
		S\subseteq A}+i' \in I\]
\end{proof}
\begin{thm}
	Ora arriviamo al teorema dell'isomorfismo II.\\
	\[
	S<A,\;I\triangleleft A\;\Rightarrow \;\frac{S+I}{I}\approx S/_{I\cap S}
	\]
	\begin{proof}
		Consideriamo questa funzione:
		\[
		f:S\mapsto {S+I}/_{I}
		\]
		\[
		f(s)=s+0+I=s+I \in \frac{S+I}{I}, A/_I
		\]
		Questa funzione e' surriettiva, infatti,
		\begin{align*}
			&\forall x+I\in \frac{S+I}{I},\;x=s+i,\;s\in S,i \in I\\
			&x+I=s+i+I=(s+I)+(i+I)=s+I\;\Rightarrow x+I=s+I\\
			&f(s)=s+I=x+I
		\end{align*}
		Quindi per il corollario II (\ref{corIItommo}):
		\[
		S/_{\ker f} \approx \frac{S+I}{I}
		\]
		quindi ci resta da dimostrare che $\ker f={I\cap S}$:
		\begin{align*}
			&\ker f = \{ s \in S | f(s)=s+I=0 \;\Leftrightarrow
			\;s\in I\}= \{ s \in S \cap I \} = S\cap I
		\end{align*}
	\end{proof}
\end{thm}
\subsection{Teorema dell'isomorfismo III}
Premesse a questo teorema. Consideriamo:
\[
I\triangleleft  J \triangleleft A
\]
Ecco tutti i sottoanell/ideali che possiamo costruire a partire da $I,J,A$:
\[
A/_J, \;\;A/_I,\;\;J/_I,\;\;J/_I \triangleleft  A/_I,\;\;{A/_I}\Big/{J/_I}
\]
Il teorema dice:
\[
I\triangleleft  J \triangleleft A\;\Rightarrow \;{A/_I}\Big/{J/_I}\approx A/_J
\]
\begin{proof}
	Consideriamo questa composizione di surriezioni naturali:
	\[
	A \stackrel{\pi}{\longrightarrow} A/_I \stackrel{\pi'}{\longrightarrow} {A/_I}\Big/{J/_I}
	\]
	$\pi\circ\pi'$ e' un omomorfismo surriettivo e quindi per il primo
	teorema:
	\[
	A/_{\ker \pi\circ\pi'} \approx {A/_I}\Big/{J/_I}
	\]
	Quindi non rimano altro che dimostrare che $\ker \pi\circ\pi'=J$.
	Dimostriamolo per doppia inclusione.\\
	\begin{align*}
		&j\in J,\;\;\pi(\pi'(j))=\pi(j+I)=\underbrace{j+I}_{\in
		J/_I}+J/_I=J/_I=0\;\;\Rightarrow \;\;j\in\ker \pi\circ\pi'\\
		&\qquad\Rightarrow \;J \subseteq  \ker \pi\circ\pi'
	\end{align*}
	l'altra inclusione:
	\begin{align*}
		&x\in\ker \pi\circ\pi'\;\;\pi(\pi'(x))=0\;\Rightarrow
		\;x+I+J/_I=0\\
		&x+I\in J/_I\;\Rightarrow \;x+I=j+I\;\Rightarrow x-j\in
		I\subseteq J\;\Rightarrow \;x-j=j'\;\Rightarrow \;x=j'-j\in J
	\end{align*}
	Quindi $\ker \pi\circ\pi'=J$
\end{proof}
\section{Ideali generati}
Da questo momento in poi, gli anelli che consideriamo sono anelli
commutativi.\\

Prendiamo un anello commutativo $A$ e un suo qualsiasi sottoinsieme non vuoto
$T \subseteq  A$, allora, nasce l'insieme di tutte le combinazioni lineari
degli elementi di T con quelli di A:
\[
(T)=\{a_1t_1+\dots+a_nt_n\;|\;a_i\in A,\;t_i\in T\}
\]
Vale che 
\[
(T)\triangleleft A
\]
E' facile verificarlo usando le due proprieta'.\\ $(T)$ viene chiamato
\emph{l'ideale di A generato da T }.\\

\subsection{Sistema di generatori}
Dato $A$, anello commutativo unitario, e $I\triangleleft  A$ e $S \subseteq A$
(sottoinsieme) di $I$,
\[
S\subseteq  I \triangleleft A
\]
se ogni elemento di $x\in I$ si puo' esprimere come 
\[
x=\sum_{i=1}^{n}a_is_i\;\;a_i\in A, s_i\in S
\]
allora $S$ si chiamera' \emph{sistema di generatori} per $I$.

Se $n\in \mathbb{N}$, $S$ e' un sistema di generatori finito e si dira'
finitamente generato (f.g.).

Se $I$ e' generato da un solo elemento, ($n=1$), allora si dira'
\emph{ideale principale}.

\begin{thm}
	\[
	A \equiv \textrm{ campo} \;\Leftrightarrow \; \textrm{gli unici ideali
	di A sono } \{0,A\}
	\]
	($\{0,A\}$ vengono anche chiamati gli ideali banali).

	\begin{proof}
		Dim $\Rightarrow $\\
		Sia $B\triangleleft A, B\neq 0$. Dimostreremo che
		necessariamente per $B\neq 0$, deve essere $B=A$, e quindi in caso
		contrario $B=0$.\\
		\begin{align*}
			& b\in B,\;\;\exists b'\in B:\;bb'=1\;\textrm{ (A e'
			un capmo)}\\
			& bb'=1 \in B\;\;\textrm{ (B e' un'ideale, quindi
			assorbe)}\\
			& \forall a\in A,\;1*a\in B\;\Rightarrow \; B=A
		\end{align*}
		Dim $\Leftarrow $\\
		\begin{align*}
			& I=(a)\;\;\textrm{Ideale principale di A generato da
			$a\in A$}\\
			& \textrm{Per Hp } I=A\;\Rightarrow \;(a)=A\\
			&1\in A\;\Leftrightarrow \;1\in(a)\;\Rightarrow
			\;1=aa'\;\Rightarrow \;A\equiv
			\textrm{campo}
		\end{align*}
	\end{proof}
\end{thm}
\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}
	\[
	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}
\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: ``ogni catena di elementi di A possiede un
	        maggiorante'' == ``gli elementi della catena formano un
		totet'')
	\begin{proof}
		\textbf{Dim: } $I\subseteq M\equiv \textrm{ideale mass. di
		A}$\\
		Consideriamo questo insieme:
		\[
		F_I=\{tutti gli ideali propri di A\}\neq 0
		\]
		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.\\
		Il massimale della catena e' sicuramente \[
		J=\bigcup_\alpha J_\alpha
		\]
		e' anche un maggiorante?, ovvero $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}
	\[
	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\\
			&b\in B\;\Rightarrow \;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.
\end{cor}
\subsection{Ideali e $\mathbb{Z}$}
Tutti gli ideali di $\mathbb{Z}$ sono principali
\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}

Tutti gli ideali primi di $\mathbb{Z}$ sono solo quelli generati da $(p)$, con
$p$ primo.
\begin{proof}
	Dimostriamo che \[
	P\triangleleft \mathbb{Z},\;P\equiv\textrm{ primo},\;P=(p)\;\;\Rightarrow
	\;\;p\equiv\textrm{ primo}
	\]
	\begin{align*}
		& P \triangleleft \mathbb{Z},\;\;P=(p)\;\;\;\;ab\in P\\
		& ab\in P\;\Rightarrow \;a\in P\;\lor \;b\in P       \\
		& a \in P\;\Rightarrow \;a \in (p)\;\Rightarrow \;a=\lambda p\\
		& b \in P\;\Rightarrow \;b \in (p)\;\Rightarrow \;b=\lambda p \\
		& p/a\;\lor \;p/b\;\Rightarrow \;\;p\equiv\textrm{ primo}
	\end{align*}
	e' facile vedere anche il viceversa.
\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{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)<v(b)
\end{cases}
\]
In sostanza, stiamo costruendo un dominio in cui valga l'algoritmo euclideo
della divisione. A ogni elemento di $D^*$ associamo una sua grandezza. Nella
divisione imponiamo che $v(r)<v(b)$, cosi' facendo potremmo ritrovare tutto
cio' che avevamo gia' visto sulla divisione: MCD, Bezout, primi=irriducibili.
L'unica differenza e' che questo discorso potra' essere applicato non solo a
$\mathbb{Z}$ e a $K[x]$, ma anche a un'infinita' di altri domini.
($v(a)$ si chiama \emph{valutazione} di $a$).

\subsection{Esempi di domini euclidei}
$\mathbb{Z}$ e' un dominio euclideo. Ma ancor piu' in generale
$K$, campo, e' un dominio euclideo.
\begin{proof}
	\begin{align*}
		& v:K^*\longrightarrow \mathbb{N}
		& v(a):=1\\
		& v(a)=1\le v(ab)=1\\
		& q=ab^{-1}\;\;a=qb+r=ab^{-1}b+0=a
	\end{align*}
\end{proof}
Vediamo come $\mathbb{Z}$ sia un dominio euclideo:
\label{Zeuclid11213}
\begin{proof}
	\begin{align*}
		& v:\mathbb{Z}^*\longrightarrow \mathbb{N}\\
		& v(a):=|a|\\
		& a,b\in \mathbb{Z}^*\;\;v(a)=|a|\le v(ab)=|a| |b|\;\;b\ge 1 \\
		& a=qb+r\;\;r=0\lor 0\le r < |b|\;\;\textrm{ per la divisione
		in $\mathbb{Z}$}\\
		& v(r)=|r| < v(b)=|b|
	\end{align*}
\end{proof}
Infine, vediamo come $K[x]$ sia pure un dominio euclideo:
\begin{proof}
	\begin{align*}
		& v:K[x]^*\longrightarrow \mathbb{N}\\
		& v(f(x)):=\deg f(x)\\
		& v(f(x))=\deg f(x) \le  v(f(x)g(x))=\deg f(x)g(x)=\deg f(x)
		+\deg g(x)\\
		& f(x)=q(x)g(x)+r(x)\;\;r(x)=0\;\lor \;\deg r(x)  <\deg g(x)\\
		& v(r(x)) =\deg r(x) < v(g(x)) = \deg g(x)
	\end{align*}
\end{proof}
\subsection{Proprieta' dei domini euclidei}
Prima di vedere alcune proprieta' dei domini euclidei, diamo la definizione di
PID:
dato $D$, dominio
\[
D\equiv \textrm{ PID}\;\Leftrightarrow \; \textrm{ ogni suo ideale e'
principale}
\]
PID=Principal Ideal Domain.\\
($\mathbb{Z}$ e' un PID)

\textbf{Proprieta' I}: in $D$, dominio euclideo, esiste l'elemento unita'.
\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}

\textbf{Proprieta' II}: Ogni dominio euclideo e' un PID.
\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}
\textbf{Proprieta' III}:
\[
\forall a,b\in D^*,\;\;\exists MCD(a,b)=d,\;\;d=\lambda a +\mu b
\]
\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}
Ed ora diamo la definizione di elemento primo per i domini:
dato $D$ dominio,
\[
p\in D,\;\;p\equiv\textrm{ primo}\;\Leftrightarrow \;
\Big( p/_{ab}\;\Rightarrow \;p/_a\;\lor \;p/_b \Big) 
\]
definizione di elemento irriducibile:
\[
q \in D,\;\;q\equiv\textrm{ irriducibile}\;\Leftrightarrow \;\textrm{ i suoi
unici divisori sono gli invertibili o i suoi associati}
\]
\[
q \in D,\;\;q\equiv\textrm{ irriducibile}\;\Leftrightarrow \;
\Big(q=ab\;\Rightarrow \;a\equiv\textrm{ invertibile}\;\lor
\;b\equiv\textrm{ invertibile}\Big)
\]
In un dominio qualsiasi vale che 
\[
p\equiv\textrm{ primo}\;\Rightarrow \;p\equiv\textrm{ irriducibile}
\]
\textbf{Proprieta' IV}: ma solo in un PID (e quindi in un ED) siamo sicuri che 
\[
p\equiv\textrm{ irriducibile}\;\Rightarrow \;p\equiv\textrm{ primo}
\]
(e anche del viceversa)
\label{dim111111}
\begin{proof}
	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{proof}
\textbf{Proprieta' V}: Un dominio euclideo e' un UFD.

Dimostreremo questa proprieta' piu' avanti.

\textbf{Proprieta' VI}: \[
v(a)=v(ab)\;\Leftrightarrow \;b\equiv\textrm{ invertibile}
\]
\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 \;\\
		& I=J\;\Rightarrow \; I \subseteq   J\;\Rightarrow
		\;a=\lambda ab\;\Rightarrow \\
		& 1=\lambda b \;\Rightarrow \; 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}
\textbf{Proprieta' VII}: Dato $(a)=I\triangleleft  D$, dove $D$ e' un ED
(Euclidean Domain), quando $I$ e' massimale?
\[
(a) \equiv \textrm{ massimale}\;\Leftrightarrow \;a\equiv\textrm{
primo}\;\Leftrightarrow \;a\equiv \textrm{ irriducibile}
\]
\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\in 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{proof}
		\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{proof}
\end{proof}
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'.

\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}
\[
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' $b_i,c_j,m_k$ sono tutti
		irr.  solamente $a$ puo' 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\in a_3 \in \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 $r<s$.
		\begin{align*}
			& p_1/_{\textrm{I membro}=\textrm{II
			membro}}\;\Rightarrow \;p_1/q_1\;\;\textrm{[a meno di
			riordinare le $q_i$]}\\
			& p_1\equiv \textrm{primo}\;\;\textrm{per la
			$1)$!}\;\Rightarrow \\
			&\qq p_1=q_1u_1,\;u_1\equiv \textrm{inv.}\\
			&\qq q_1u_1p_2\dots p_r=q_1q_2\dots q_s\;\Rightarrow
			\;u_1p_2\dots p_r=q_2\dots q_s\\
			& \textrm{Reiterando tutto questo, finiamo in: }\\
			& \qq u_1u_2\dots u_r=q_{r+1}\dots
			q_s\;\;\textrm{ che e' assurdo!}
		\end{align*}
		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), i<j\\
		&\qq (a_i)\subseteq (a_j)\;\Rightarrow \;x\in
		(a_j)\;\Rightarrow \\
		&\qq x-y \in(a_j)\subseteq J\\
		&d\in D,\;xd\in J?\\
		&\qq x\in(a_i),\;xd\in(a_i)\subseteq J\;\;\textrm{[propr. di
		assorbimento}
	\end{align*}
\end{proof}
Poiche' per Hp $D\equiv PID$, allora anche $J$ lo e', e quindi $J=(j)$, ma
allora
\begin{align*}
	& J=(j),\;\;j\in(a_n)\;\Rightarrow \;(j)\subseteq
	(a_n)\;\Rightarrow \\
	&\qq J \subseteq (a_n)\subseteq J\;\Rightarrow \;J=(a_n)\\
	& \textrm{Dato }m>n\;\;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 $\Leftrightarrow $ UFD, e controesempi}
Ricapitolando tutto quello visto fin'ora:
\[
\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.
\begin{proof}
	\textbf{Dim: }$\textrm{Anello comm}\;\;\nLeftarrow
	\;\;\textrm{Anello}$\\
	Basta considerare le matrici.
\end{proof}
\begin{proof}
	\textbf{Dim: }$\textrm{Dominio}\;\;\nLeftarrow  \;\;\textrm{Anello
	comm}$\\
	Basta considerare $Z_{10}$. $\mathbb{Z}_{10}$ ha divisori dello zero,
	ad esempio $2\cdot 5 = 0$.
\end{proof}
\begin{proof}
	\textbf{Dim: }$\textrm{Campo}\;\;\nLeftarrow  \;\;\textrm{ED}$\\
	Basta considerare $\mathbb{Z}$, dove abbiamo visto che e' un ED qui
	\ref{Zeuclid11213}.
\end{proof}
\begin{proof}
	 \textbf{Dim: }$\textrm{UFD}\;\;\nLeftarrow  \;\;\textrm{Dominio}$\\
	 Consideriamo $D\subseteq R[x]$ (che e' un dominio):
	 \[
	 D:=\{f(x) \in R[x] \;|\;f'(x)=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^2\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{proof}
\begin{proof}
	\textbf{Dim: }	$\textrm{PID}\;\;\nLeftarrow  \;\;\textrm{UFD}$\\
	$\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 pari}\\
		&\qq \textbf{If } h(x) = \pm 2\\
		&\qq\qq (2)=I=(2,x)\;\Rightarrow \;x=2\lambda(x) \;\;\textrm{ assurdo}
	\end{align*}
\end{proof}
\begin{proof}
	\textbf{Dim: }	$\textrm{ED}\;\;\Rightarrow \;\;\textrm{PID}$\\
	Il controesempio e' 
	\[
	D=\{a+ib\sqrt{19}\;|\;a,b\in2\mathbb{Z}\}
	\]
	la dimostrazione di questo controesempio e' troppo complessa per
	adesso.
\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}
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)<v(z_2)
		\end{align*}
		Ritorniamo in $\mathbb{Q}[i]$:
		\begin{align*}
			& z_2\neq 0\in\mathbb{Z}[i]\subseteq
			\mathbb{Q}[i]\;\Rightarrow \;z_2\in\mathbb{Q}[i]\\
			& \exists z_2^{-1}\in \mathbb{Q}[i]\\
			& z_1z_2^{-1}\in \mathbb{Q}[i]\;\Leftrightarrow
			\;z_1z_2^{-1}=\frac{m}{n}+i\frac{r}{s}\\
			&
			\frac{m}{n}+i\frac{r}{s}=u+\frac{m'}{n}+i(v+\frac{r'}{s})
		\end{align*}
		Quest'ultimo passaggio si puo' fare, ad esempio, aggiungendo e
		sottraendo $1+i$, cioe':
		\begin{align*}
			& u=v=1\\
			&\frac{m}{n}+1-1=\frac{m-n}{n}+1,\;\;m-n=m'\\
			&i(\frac{r}{s}+1-1)=\frac{r-s}{s}+1,\;\;r-s=r'
		\end{align*}
		In questo modo abbiamo che 
		\[
		\Big|\frac{m'}{n}\Big|,\Big|\frac{r'}{s}\Big|\Leftarrow
		\frac{1}{2}
		\]
		continuiamo,
		\begin{align*}
			&
			z_1z_2^{-1}=u+\frac{m'}{n}+i(v+\frac{r'}{s})=\frac{m'}{n}+iv+u+i\frac{r'}{s}=\\
			&\qq = u+iv+\left(\frac{m'}{n}+i\frac{r'}{s}\right)\\
			&\textrm{moltiplichiamo ambo i membri per
			$z_2$}:\\
			&\qq
			z_1=\underbrace{z_2(u+iv)}_{=q\in
			\mathbb{Z}[i]}+\underbrace{z_2\left(\frac{m'}{n}+i\frac{r'}{s}\right)}_{=r}\\
			&\qq r=z_1-q\in \mathbb{Z}[i]\;\; \textrm{[cosi' abbiamo diviso $z_1$ per $z_2$}\\
		\end{align*}
		controlliamo che $v(r)<v(z_2)$:
		\begin{align*}
			&
			v(r)=v(z_2)v\left(\left(\frac{m'}{n}+i\frac{r'}{s}\right)\right)=v(z^2)\left(\left(\frac{m'}{n}\right)^2+i\left(\frac{r'}{s}\right)^2\right)=\\
			&\qq
			=v(z_2)(\frac{1}{4}+\frac{1}{4})=\frac{1}{2}v(z_2)\\
			&v(r)=\frac{1}{2}v(z_2)<v(z_2)
		\end{align*}
	\end{proof}
\end{thm}
\subsection{Somma di quadrati}
Stranamente per rispondere a una semplicemente domanda, abbiamo bisogno
dell'aiuto degli interi di Gauss! La domanda e': \emph{dato $n$ e' vero che} 
\[
n=a^2+b^2,\;\;a,b\in \mathbb{Z}
\]
Cioe', e' vero che posso scrivere $n$ come somma di due quadrati? Quali sono
questi due quadrati?

Dimostriamo un teorema preliminare
\begin{thm}
	Dato $p>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\\
				& 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 
			per assurdo assumiamo $p$ primo, cioe' assumiamo che
			$p/_{(z+i)(z-i)}\;\Rightarrow \;p/_{z+i}\;\lor
			\;p/_{z-i}$
		\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<p^2\;\Rightarrow \\
					&\qq\lambda < p\;\;\;(2) \\
				\end{align*}
				La (1) e (2) sono in contrasto, 	assurdo!
				\qed
			\end{prova}
			\qed
		\end{prova}

		\step{}{Divisori di $p^2$}
		\begin{prova}
			Poiche' $p$ non e' primo in $\mathbb{Z}[i]$ e poiche'
			$\mathbb{Z}[i]$ e' un ED, allora $p$ e' riducibile (in
			$\mathbb{Z}[i]$), ovvero:
			\[
			p=(a+ib)(c+id),\;\;\;a+ib,c+id\equiv \textrm{non invert.}
			\]
			Poiche' gli unici invertibili in $\mathbb{Z}[i]$ sono
			$\pm i, \pm i$, allora
			\[
			a+ib,c+id\neq \pm i, \pm i\;\Rightarrow \;a,b,c,d\neq
			\pm 1
			\]
			prendendo il congiugato di $p$ abbiamo:
			\[
			p=(a-ib)(c-id)
			\]
			allora
			\begin{align*}
				&p=(a+ib)(c+id)\\
				&p=(a-ib)(c-id)\\
				&p^2=pp=(a+ib)(a-ib)(c+id)(c-id)=(a^2+b^2)(c^2+d^2)\;\Rightarrow \\
				&\qq (a^2+b^2)/_{p^2}
			\end{align*}
			ma poiche' $p$ e' primo in $\mathbb{Z}$, gli unici
			divisori di $p^2$ in $\mathbb{Z}$ sono:
			\[
			D=\{1,p,p^2\}
			\]
			$1$ lo scartiamo perche' sappiamo che $(a^2+b^2)\neq
			1$.\\
			Se $(a^2+b^2)=p^2$, si avrebbe che 
			\[
			p^2=p^2(c^2+d^2)
			\]
			ma anche in questo caso sappiamo che $c^2+d^2\neq
			1$.\\
			Quindi l'unico divisore lecito e' $p$, cioe'
			\[
			a^2+b^2=p
			\]
			che e' proprio quello che volevamo dimostrare ;)
			\qed
		\end{prova}
	\end{prova}
\end{thm}
\begin{thm}
	Adesso possiamo trattare tutti i numeri.\\
	Dato $n\in\mathbb{Z}$, e la sua fattorizzazione \[
	n=2^tq_1^{m_1}q_2^{m_2}\dots q_r^{m_r}p_1^{n_1}p_2^{p_2}\dots
	p_s^{n_s}\]
	dove
	\[
	t\ge 0,\;\;\forall i\;q_i=1\;(\mathbb{Z}_4),\;\;p_i=3\;(\mathbb{Z}_4)
	\]
	allora
	\[
	n=a^2+b^2\;\Leftrightarrow \;\forall i,\;n_i\in 2\mathbb{N}
	\]
	In altre parole, $n$ e' somma di quadrati, se e solo se, gli esponenti
	dei suoi fattori primi che sono della forma $4\lambda+3$, hanno
	esponente pari.\\
	Nota: un primo $p$, poiche' dispari, e' sempre nella forma
	\[p=1\;(\mathbb{Z}_4)\;\lor \;p=3\;(\mathbb{Z}_4)\]
	\step{}{Dimostriamo solo $\Leftarrow $}
	\begin{prova}
		\pf
		\step{}{Il prodotto della somma di due quadrati e' ancora
		somma di due quadrati}
		\prove{
		$(a^2+b^2)(c^2+d^2)=(x^2+y^2)$
		}
		\begin{prova}
			\pf
			Basta considerare la norma dei numeri complessi:
			\begin{align*}
				& a^2+b^2 = |a+ib|\\
				& c^2+d^2 = |c+id|\\
				&|a+ib| |c+id| = |(a+ib)(c+id)| = |x^2+y^2|\\
			\end{align*}
			\qed
		\end{prova}
		Quindi,\\
		$2^t$ e' sempre somma di quadrati:
		\[
		2^t=\begin{cases}
			2^{t-1}+2^{t-1}&t\notin 2\mathbb{N}\\
			0+2^t&t\in 2\mathbb{N}
		\end{cases}
		\]
		Tutti i $q_i$ sono somma di quadrati (l'abbiamo dimostrato in
		\ref{sumquadrpro}).\\
		E infine, tutti i  $p_i$ sono somma di quadrati perche' hanno
		l'esponente pari, e quindi sono quadrati:
		\[
		n_i=2s,\;\;p_i^{n_i}=0+p_i^{2s}
		\]
		\qed
	\end{prova}
\end{thm}
\subsubsection{Esempio}
Scomponiamo $1530$ come somma di quadrati:
\begin{align*}
	 1530 =& 2\cdot3^2\cdot 5\cdot17\\
	 1530 =& |1+i|\cdot|3|\cdot|1+i2|\cdot|1+i4| =\\
	=& |(3+i3)(1+i2)(1+i4)| = |-39-i3| = 39^2+3^2
\end{align*}
\[
1530=39^2+3^2
\]
Nota: la scomposizione non e' necessariamente unica:
\begin{align*}
	 1530 =& |1+i|\cdot|3|\cdot|1+i2|\cdot|1-i4| =\\
	 =& |(3+i3)(1+i2)(1-i4)| = |33+i21| = 33^2+21^2
\end{align*}
\[
1530=33^2+21^2
\]

\section{Polinomi UFD}
Alcune premesse:\\
In un UFD, e' possibile calcolare il MCD (anche se non siamo in un ED): e'
sufficiente usare il metodo descritto in \ref{mcmMCD123}.\\

L'insieme dei polinomi a indeterminate $x,y$ e a coefficienti in $K$ si puo'
pensare come l'insieme dei polinomi a indeterminata $x$ e a coefficienti in
$k[x]$. Esempio:\\
\[
x^3+xy^2+2x^2+y^2+4x-4y+5\;\;\in \mathbb{R}[x,y]
\]
$\mathbb{R}[x,y]$ lo possiamo pensare come $(\mathbb{R}[x])[y]$:
\[
(x+1)y^2-4y+x^3+4x+5\;\;\in \mathbb{R}[x][y]
\]
qui, $(x+1)\in \mathbb{R}[x]$ e' un coefficiente della indeterminata $y^2$,
e $x^3+4x+5$ e' il termine noto.
Se, invece, consideriamo $(\mathbb{R}[y])[x]$:
\[
x^3+2x^2+(y^2+4)x+y^2+5 \in \mathbb{R}[y][x]
\]

Adesso ci poniamo la seguente domanda: dato $A\equiv UFD$ e' vero che $A[x]
\equiv UFD$?
\subsection{Teorema di Gauss}
Il teorema di Gauss risponde affermativamente:
\[
A\equiv UFD\;\Rightarrow \;A[x]\equiv UFD
\]

\begin{prova}
	\pf
La dimostrazione del teorema e' identica a quella che abbiamo fatto per
$\mathbb{Z}[x]$:
\begin{enumerate}
	\item Avevo dimostrato il Lemma di Gauss (vedi \ref{lemma_del_gaussino})
	\item il suo corollario (vedi \ref{corlemgauss})
	\item e il teorema (vedi \ref{ThmGaussdimoZ})
\end{enumerate}
Le uniche accortezze a cui bisogna fare attenzione sono le seguenti
sostituzioni:
\[ \mathbb{Z}\longrightarrow A \]
\[\mathbb{Z}[x] \longrightarrow A[x]\]
\[ \mathbb{Q}[x] \longrightarrow  Q(\mathbb{A}[x]) \]
Dove $Q(\mathbb{A}[x])$ e' il campo dei quozienti di $\mathbb{A}[x]$.
($Q(\mathbb{A}[x])$ e' un campo, quindi e' UFD).
\qed
\end{prova}
\subsubsection{Esempi}
\begin{enumerate}
	\item $\mathbb{Z}[x]$ e' UFD
	\item Dato $K$ campo, $K[x]$ e' UFD, ma lo e' anche $K[x,y]$ perche'
		lo possiamo esprimere come $(K[x])[y]$, dove $K[x]$ e' UFD, e
		quindi per Gauss $(K[x])[y]$ e' sempre UFD.
	\item Allora possiamo reiterare e quindi
		\[
		K[x_1,x_2,\dots,x_n] \;\equiv \;UFD
		\]
\end{enumerate}
\subsection{Criteri di irriducibilita'}
Valgono gli stessi criteri di irriducibilita' che abbiamo visto in
$\mathbb{Z}[x]$, e le loro dimostrazioni:
\begin{enumerate}
	\item Criterio di Eisenstein (vedi \ref{Eisenstein}):\\
		Sia $A\equiv UFD$ e 
		\[f(x)=a_0+a_1x+\dots+a_dx^d\;\in\mathbb{A}[x]\]
		e sia primitivo, allora
		\[
		\begin{cases}
			\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{A}[x]
		\]
	\item Criterio di riduzione modulo $p$ (vedi \ref{Criteriomodulop}):\\
Sia $A\equiv UFD$ e \[f(x)=a_0+a_1x+\dots+a_dx^d\;\in\mathbb{A}[x]\]
e sia primitivo, allora
\[
\exists p, \textrm{ primo}:\;\; p\nmid {a_d}, \;\;\land \;\;f(x) \textrm{
irriducibile in } \frac{A}{(p)}[x]\;\;\Rightarrow \;\;f(x) \textrm{
irriducibile in } \mathbb{A}[x]
\]
dove $(p)$ e' l'ideale principale generato da $p$, $\frac{A}{(p)}$ e' $A$
quozientato da $(p)$, e inoltre $\frac{A}{(p)}$ e' un campo perche' $p$ e'
primo (vedi \ref{idealeprimocaratt}).
\end{enumerate}
\subsection{Algoritmo di divisione in un UFD}
Dato $A[x]\equiv UFD$, se $A$ non e' un campo, $A[x]$ non sara' necessariamente un $ED$.
Questo significa che in $A[x]$ l'algoritmo di divisione non vale sempre. Esistono pero' dei casi in cui vale:\\
dati \[f(x)=a_mx^m+\dots+a_0, \;\;\;g(x)=b_nx^n+\dots+b_0 \in A[x]\]
l'algoritmo di divisione si puo' applicare su \[f(x)=q(x)g(x)+r(x)\] se il
coefficiente dell'indeterminata di grado massimo di $g(x)$ e' invertibile,
cioe' se $\exists b_n^{-1}$.
\begin{prova}
	\pf
	Basta osservare che $b_m^{-1}$ e' l'unico invertibile richiesto nella
	dimostrazione fatta in \ref{divisionealgopolin}
	\qed
\end{prova}
\end{document}