2059 lines
200 KiB
TeX
Executable file
2059 lines
200 KiB
TeX
Executable file
%28feb2013,10mar,20mar,31mar,4apr,6apr(v2),12mag,20mag,27giu,28gen2014,2feb, 18apr2016
|
||
\documentclass{article}
|
||
\usepackage{amsmath,amsfonts,amssymb,amsthm,amscd}
|
||
\usepackage[italian]{babel}
|
||
\usepackage{ifpdf}
|
||
\ifpdf
|
||
\usepackage[pdftex, linktocpage=true, pdfborder={0 0 0}]{hyperref}
|
||
\hypersetup{%
|
||
pdfauthor={A. Berarducci},
|
||
pdftitle={Elementi di Teoria degli Insiemi},
|
||
pdfsubject ={},
|
||
pdfkeywords={}
|
||
}
|
||
\pdfcompresslevel=9
|
||
\else
|
||
\usepackage[hypertex, linktocpage=true]{hyperref}
|
||
\fi
|
||
|
||
%\usepackage[pdftex, linktocpage]{hyperref}
|
||
|
||
\title{{\bf Elementi di Teoria degli Insiemi, 2015-16}}
|
||
\author{Alessandro Berarducci}
|
||
\date{20 Maggio 2013, 18 Aprile 2016}
|
||
|
||
\DeclareMathOperator{\R}{\mathbb R}\DeclareMathOperator{\continuo}{\mathbf c}
|
||
\DeclareMathOperator{\N}{\mathbb N}
|
||
\DeclareMathOperator{\Q}{\mathbb Q}
|
||
\DeclareMathOperator{\Z}{\mathbb Z}
|
||
\DeclareMathOperator{\Tt}{\mathbb T}
|
||
\DeclareMathOperator{\ms}{{\mathbb S}^{(d)}}
|
||
\newcommand{\F}{{\bf 0}}
|
||
\newcommand{\V}{{\bf 1}}
|
||
|
||
|
||
\DeclareMathOperator{\sta}{st} \DeclareMathOperator{\Int}{Int}
|
||
\DeclareMathOperator{\Fin}{Fin} \DeclareMathOperator{\Inf}{Inf}
|
||
\DeclareMathOperator{\Sup}{Sup}
|
||
\DeclareMathOperator{\Graph}{Graph} \DeclareMathOperator{\im}{im}
|
||
\DeclareMathOperator{\dom}{dom} \DeclareMathOperator{\id}{id}
|
||
\DeclareMathOperator{\parti}{{\cal P}}
|
||
\newcommand{\compl}[1]{{#1}^{\complement}}
|
||
\newcommand{\rest}[1]{\hspace {-0.2em} \upharpoonright_{#1}}
|
||
\swapnumbers
|
||
|
||
\theoremstyle{plain}
|
||
\newtheorem{theorem}{Teorema}
|
||
\newtheorem*{theorem*}{Teorema}
|
||
\newtheorem{lemma}[theorem]{Lemma}
|
||
\newtheorem{observation}[theorem]{Osservazione}
|
||
\newtheorem{proposition}[theorem]{Proposizione}
|
||
\newtheorem{corollary}[theorem]{Corollario}
|
||
\newtheorem{conjecture}[theorem]{Congettura}
|
||
\newtheorem{claim}[theorem]{Sottolemma}
|
||
\newenvironment{Claim}{\\ \noindent\textsc{Claim}:\em}{\\}
|
||
%\newenvironment{pclaim}{\noindent {\em Proof of Claim}:}{\hfill $\square${\em Claim} \\ \phantom \hspace{1cm}}
|
||
\newenvironment{pclaim}[1][{\noindent\textsc{Proof}.}]{\begin{trivlist}
|
||
\item[\hskip \labelsep {#1}]}{\hfill \qed$\,_\textrm{claim}$ \end{trivlist}}
|
||
\newtheorem{question}[theorem]{Question}
|
||
\newtheorem{fact}[theorem]{Fatto}
|
||
|
||
\theoremstyle{definition}
|
||
\newtheorem{remark}[theorem]{Osservazione}
|
||
\newtheorem{nota}[theorem]{Nota}
|
||
\newtheorem{definition}[theorem]{Definizione}
|
||
\newtheorem{notation}[theorem]{Notazione}
|
||
\newtheorem{convention}[theorem]{Convenzione}
|
||
\newtheorem{example}[theorem]{Esempio}
|
||
\newtheorem{exercise}[theorem]{Esercizio}
|
||
\newtheorem{vuoto}[theorem]{}
|
||
\newtheorem{assumption}[theorem]{Ipotesi}
|
||
\newtheorem{axiom}[theorem]{Assioma}
|
||
\newtheorem{paradox}[theorem]{Paradosso}
|
||
|
||
%\renewcommand{\proofname}{Dim}
|
||
|
||
\numberwithin{theorem}{section}
|
||
\newcommand{\bt}{\begin{theorem}}
|
||
\newcommand{\et}{\end{theorem}}
|
||
\newcommand{\bl}{\begin{lemma}}
|
||
\newcommand{\el}{\end{lemma}}
|
||
\newcommand{\bfa}{\begin{fact}}
|
||
\newcommand{\efa}{\end{fact}}
|
||
\newcommand{\bexa}{\begin{example}}
|
||
\newcommand{\eexa}{\end{example}}
|
||
\newcommand{\bexe}{\begin{exercise}}
|
||
\newcommand{\eexe}{\end{exercise}}
|
||
\newcommand{\bprop}{\begin{proposition}}
|
||
\newcommand{\eprop}{\end{proposition}}
|
||
\newcommand{\bp}{\begin{proof}}
|
||
\newcommand{\ep}{\end{proof}}
|
||
\newcommand{\bc}{\begin{corollary}}
|
||
\newcommand{\ec}{\end{corollary}}
|
||
\newcommand{\bd}{\begin{definition}}
|
||
\newcommand{\ed}{\end{definition}}
|
||
\newcommand{\br}{\begin{remark}}
|
||
\newcommand{\er}{\end{remark}}
|
||
|
||
\newcommand{\liff}{\leftrightarrow}
|
||
\newcommand{\limplies}{\to}
|
||
\newcommand{\st}{\mid}
|
||
\newcommand{\ii}{\`{\i} }
|
||
\newcommand{\nin}{\not\in}
|
||
\newcommand{\ca}[1]{{\mathcal #1}}
|
||
\newcommand{\tipo}{ot}
|
||
|
||
|
||
\usepackage{tocloft}
|
||
\newlength{\tocwidth}
|
||
\setlength{\tocwidth}{25em}
|
||
\renewcommand{\cftsecdotsep}{\cftdotsep}
|
||
%% dots for sections
|
||
%\renewcommand{\cftsecfont}{}
|
||
\renewcommand{\cftsecaftersnumb}{\mdseries}
|
||
%% normal font for section(instead of bold)
|
||
\renewcommand{\cftsecpagefont}{}
|
||
%% normal font for section page number
|
||
\makeatletter
|
||
%\renewcommand{\cftsecleader}{\@cftdotfill {\cftsecdotsep}\hspace{-0.9em}}
|
||
\providecommand{\cftdotfill}{\@cftdotfill}
|
||
\makeatother
|
||
\renewcommand{\cftsecleader}{\cftdotfill {\cftsecdotsep}\hspace{-0.9em}}
|
||
%% normal font for section dots
|
||
\setlength{\cftbeforesecskip}{0.5ex}
|
||
%% space between entries
|
||
%\cftsetpnumwidth{1.5em}
|
||
%\cftsetrmarg{1.6em}
|
||
%% space for writing page numers
|
||
|
||
\renewcommand{\cfttoctitlefont}{\normalfont\large\bfseries}
|
||
\setlength{\cftbeforetoctitleskip}{0ex}
|
||
\setlength{\cftaftertoctitleskip}{1ex}
|
||
|
||
\newcommand{\case}[4]{\left\{ \begin{array}{ll} #1 & #2 \\ #3 & #4
|
||
\end{array}\right.}
|
||
|
||
%\listfiles
|
||
|
||
\begin{document}
|
||
\maketitle
|
||
|
||
\begin{center}
|
||
%\begin{minipage}{\tocwidth}
|
||
\small
|
||
\tableofcontents
|
||
%\end{minipage}
|
||
\end{center}
|
||
|
||
\section{Introduzione} La teoria degli insiemi nasce con Georg Cantor (i primi articoli risalgono al 1874) ed \`e stata successivamente assiomatizzata da Ernst Zermelo (1904, 1908), con successive integrazioni e sviluppi da parte di Fraenkel, Skolem, von Neumann ed altri matematici. Essa pu\`o essere vista come uno dei tanti settori della matematica, con i suoi risultati specifici sui numeri ordinali e cardinali, ma la sua importanza risiede soprattutto nel fatto che gli insiemi forniscono un fondamento per l'intera matematica. Tutti i concetti matematici possono infatti essere interpretati in termini insiemistici e, ci\`o fatto, qualunque dimostrazione matematica pu\`o essere formalizzata, almeno in linea di principio, entro la teoria assiomatica degli insiemi. Si pu\`o non essere d'accordo con questa impostazione, ma \`e bene sapere che essa \`e stata resa possibile da una serie di lavori che, a partire dalla rifondazione del calcolo infinitesimale ad opera di Weierstrass, Cantor e Dedekind, hanno gradualmente condotto ad una nuova concezione sui fondamenti della matematica che ancora non \`e stata superata.
|
||
|
||
Esistono tre principali assiomatizzazioni della teoria degli insiemi, che sono per\`o strettamente imparentate: la teoria di Zermelo-Fraenkel (ZF), la teoria di G\"odel-Bernays (GB) (anche detta teoria NBG di von Neumann, Bernays e G\"odel), e la teoria di Morse-Kelley (MK). Delle tre, quella privilegiata in questo testo \`e GB, che trovo pi\`u efficace di ZF da un punto di vista didattico. Le differenze tra i diversi approcci riguardano sostanzialmente il modo in cui viene affrontano il problema della distinzione tra insiemi e classi e lo status che viene attribuito alle classi. Mentre in ZF possiamo parlare di classi solo ricorrendo a circonlocuzioni (in quanto il suo linguaggio non ha variabili su classi), in GB e in MK esse sono entit\`a teoriche a pieno titolo. A titolo di esempio, il fatto che la classe dei numeri ordinali non sia un insieme, che \`e dimostrabile in questi termini in GB, pu\`o essere formulato in ZF solo ricorrendo alla perifrasi ``non esiste un insieme che contiene come elementi tutti gli ordinali''. \footnote{Ci\`o \`e fattibile in quanto la propriet\`a ``$x$ \`e un ordinale'' \`e esprimibile in ZF, sebbene a tale propriet\`a non venga fatta corrispondere una classe.} Le differenze tra ZF e GB sono in ogni caso pi\`u formali che sostanziali: se ci si limita alle affermazioni che coinvolgono solo gli insiemi e non le classi, ZF e GB dimostrano esattamente le stesse cose. \footnote{La teoria MK \`e invece strettamente pi\`u potente.}
|
||
|
||
Il nostro scopo \`e quello di fornire un'esposizione motivata ed intuitiva, ma al tempo stesso precisa e succinta (obiettivi non facilmente conciliabili), della teoria assiomatica degli insiemi GB, presentandone i risultati fondamentali sui numeri ordinali e cardinali, e facendo vedere come gli oggetti basilari della matematica possano essere ricostruiti in termini insiemistici (relazioni, funzioni, numeri naturali, numeri reali, eccetera).
|
||
|
||
Un ruolo fondamentale lo giocher\`a l'induzione transfinita e il teorema di ricursione, che esporr\`o prima in forma semplice (definizioni ricorsive sui numeri naturali) e poi in forma sempre pi\`u generale, fino ad arrivare al teorema di ricursione per relazioni ben fondate. La ricursione transfinita su numeri ordinali ne sar\`a un caso particolare. In questo percorso metter\`o in evidenza il ruolo dei vari assiomi, tra cui l'assioma della scelta, di cui dimostreremo l'equivalenza con il lemma di Zorn.
|
||
|
||
I numeri cardinali verranno prima presentati nella versione di Frege, come classi di equivalenza rispetto alle bigezioni (cosa che pu\`o essere fatta in GB ma non in ZF), e solo successivamente, quando ne nascer\`a l'esigenza, come ordinali iniziali.
|
||
Mentre per dimostrare i primi risultati (ad esempio il fatto che i numeri reali non sono numerabili) sar\`a sufficiente la versione di Frege, per alri risultati si renderanno necessari gli ordinali iniziali. Identificare i cardinali con gli ordinali iniziali permette in particolare di mostrare che non esiste alcuna successione decrescente infinita di cardinali. Da ci\`o segue che esiste un pi\`u piccolo cardinale tra quelli non numerabili, che per\`o non sappiamo se coincida con la cardinalit\`a dei reali: si tratta della cosiddetta ``ipotesi del continuo'', per la cui discussione rimandiamo a testi pi\`u avanzati come il ``Set Theory'' di Thomas Jech.
|
||
|
||
Una precisazione metodologica:
|
||
ho cercato di presentare GB come teoria assiomatica nel senso euclideo o pre-hilbertiano del termine, ovvero ponendomi nell'ottica che i suoi assiomi corrispondano ad affermazioni contenutistiche su una supposta ``realt\`a'' degli insiemi.
|
||
%Tuttavia ho cercato di manterere un livello di esposizione che renda possibile una doppia lettura.
|
||
Tuttavia chi abbia un minimo di familiarit\`a con la logica matematica non avr\`a difficolt\`a a rileggere GB come teoria formale del primo ordine. La scelta della doppia lettura mi \`e sembrata il miglior compromesso in considerazione dell'annosa questione se la logica preceda la teoria degli insiemi o viceversa: la semantica delle teorie del primo ordine si basa sugli insiemi, ma la teoria degli insiemi \`e essa stessa una teoria del primo ordine (e come tale \`e suscettibile di una pluralit\`a di interpretazioni). Per realizzare il compromesso ho fatto precedere alla presentazione di GB dei brevi capitoli sulle notazioni logiche (connettivi e quantificatori), dandone una semantica intuitiva basata su esempi tratti dal linguaggio naturale. Ritengo che questa scelta, non presupponendo conoscenze antecedenti di logica, sia quella che permette la pi\`u ampia flessibilit\`a nell'utilizzo del testo.
|
||
|
||
Se questa impostazione mi soddisfa a livello didattico, a livello teorico rimane il problema di come uscire dalla circolarit\`a sopra evidenziata. Una possibilit\`a, suggerita dalle riflessioni di Hilbert, \`e quella del ``bootstrapping'', ben familiare a chi si occupa del problema di come faccia un computer ad avviare i suoi programmi se per avviare un programma serve un altro programma. Fuori di metafora: serve solo una minima parte di GB per definire la sintassi a la semantica dei linguaggi del primo ordine. Questa minima parte pu\`o essere assunta in modo contenutistico, e poi se lo si desidera si \`e liberi di pensare al resto di GB in modo formale. Per limiti di tempo devo per\`o lasciare lo sviluppo di queste considerazioni ad altra sede.
|
||
|
||
Ho scritto questo testo pensando in primo luogo ai miei studenti dei corsi di Logica e Teoria degli Insiemi presso il Dipartimento di Matematica dell'Universit\`a di Pisa, ma nello scriverlo ho cercato anche di intrattenere un dialogo ideale con alcuni colleghi e amici. Spero quindi che esso possa essere letto a vari livelli e apprezzato anche da chi si avvicini da autodidatta, o da semplice curioso, alla materia.
|
||
|
||
|
||
\section{Paradosso dell'iperalbero}
|
||
\label{iperalbero}
|
||
Una delle ``scoperte'' fondamentali della teoria degli insiemi \`e che non tutti gli insiemi sono sullo stesso livello, ma occorre distinguere almeno due livelli: insiemi e classi. Come vedremo gli insiemi sono quelle classi che possono appartenere ad altre classi. Se non si fanno distinzioni si incorre in vari paradossi, tra cui il cosiddetto ``paradosso dell'iperalbero'', che presento in questa sezione come piccolo antipasto alla teoria. A differenza di altri paradossi pi\`u noti (tra cui il paradosso di Russell che vedremo in seguito) esso ha un carattere ``geometrico'' o ``visivo'' che rende la sua paradossalit\`a ancora pi\`u sorprendente. Se provvisti di sufficiente intuizione matematica, letteralmente non si crede ai propri occhi.
|
||
|
||
Immaginate un albero genealogico. C'\`e il capostipite, i suoi figli, i figli dei figli, e cos\`{\i} via. Astraendo un po' si arriva alla seguente definizione.
|
||
|
||
\bd
|
||
Un albero \`e un insieme di oggetti, chiamati nodi dell'albero, su cui \`e definita una relazione padre-figlio (o la corrispondente versione al femminile) che gode della seguente propriet\`a. Ogni nodo, tranne la radice, ha uno e un solo padre. La radice non ha padre. Ogni nodo ha zero o pi\`u figli. I nodi con zero figli si chiamano foglie dell'albero.
|
||
\`E ammessa la possibilit\`a che un nodo abbia infiniti figli. I discendenti di un nodo $x$ sono quelli che si ottengono a partire da lui tramite un cammino finito, ovvero una successione finita di nodi che parte da $x$ e in cui ogni nodo \`e figlio del precedente. Richiediamo, nella definizione di albero, che ogni nodo sia un discendente della radice (il capostipite).
|
||
\ed
|
||
|
||
\bd Un albero \`e ben fondato se non ha cammini infiniti. \ed
|
||
|
||
Dunque in un albero ben fondato un oggetto prezioso che passi di generazione in generazione dal padre ad uno dei figli, prima o poi rimarrebbe senza legittimo proprietario per mancanza di eredi.
|
||
%I figli della radice si chiamano nodi di prima generazione, i figli dei figli sono i nodi di seconda generazione, i figli dei figli dei figli sono i nodi di terza generazione, eccetera.
|
||
Osserviamo che le generazioni potrebbero non esaurirsi mai, senza che con ci\`o esista un cammino infinito. Ad esempio la radice potrebbe avere infiniti figli, e ciascuno dei suoi figli potrebbe avere una discendenza finita, che per\`o si estingue a scadenze sempre pi\`u lunghe a seconda del figlio, senza quindi che l'intera discendenza della radice si estingua mai.
|
||
|
||
\bprop \label{se-stesso} Se un albero contiene una copia di se stesso come sottoalbero, allora non \`e ben fondato. \eprop
|
||
\bp Partendo dalla radice dell'albero mi sposto sulla radice della sua copia, e da l\ii itero il procedimento, ovvero mi sposto sempre verso il sottoalbero che \`e copia di quello da cui sono partito, producendo in tal modo un cammino infinito. \ep
|
||
|
||
%\caption{Un albero con un sottoalbero a lui isomorfo}%{An annulus with a ray removed}
|
||
\begin{picture}(341,121)
|
||
\put(200,115){\line(-1,-1){80}}
|
||
\put(200,115){\line(1,-1){20}}
|
||
\put(180,95){\line(1,-1){20}}
|
||
\put(160,75){\line(1,-1){20}}
|
||
\put(140,55){\line(1,-1){20}}
|
||
\put(180,79){\makebox(80,15)[t]{}}
|
||
\put(160,60){\makebox(80,14)[t]{}}
|
||
\put(140,40){\makebox(80,15)[t]{}}
|
||
\put(120,20){\makebox(80,15)[t]{}}
|
||
\put(95,5){\makebox(60,15)[t]{$\vdots$}}
|
||
\put(15,75){\makebox(150,15)[t]{}}
|
||
\end{picture}
|
||
\begin{center} Un albero che ha una copia di se stesso come sottoalbero. \end{center}
|
||
|
||
\bd
|
||
L'iperalbero \`e definito nel modo seguente. Consideriamo la classe $C$ di tutti gli alberi ben fondati (o, per meglio dire, un rappresentante per ogni classe di isomorfimo di tali alberi). Consideriamo un nuovo nodo $r$ e stabiliamo che i figli di $r$ siano le radici degli alberi della classe $C$. Otteniamo in questo modo un nuovo albero, la cui radice \`e $r$, e che contiene come sottoalberi gli alberi di C. Ogni albero ben fondato ha dunque una copia tra i sottoalberi dell'iperalbero.
|
||
\ed
|
||
|
||
\begin{paradox}
|
||
Ci chiediamo se l'iperalbero sia ben fondato.
|
||
Poich\`e ogni cammino nell'iperalbero va a finire, dopo un passo, in uno dei suoi sottoalberi (che sono ben fondati), ne segue che l'iperalbero \`e ben fondato. Ma essendo tale, una copia dell'iperalbero deve comparire come uno dei sottoalberi di se stesso. Tuttavia un albero che contiene una copia di se stesso come sottoalbero non pu\`o essere ben fondato (Proposizione \ref{se-stesso}), il che \`e una paradosso.
|
||
\end{paradox}
|
||
|
||
Nella teoria assiomatica degli insiemi il paradosso si ``risolve'' per mezzo di una distinzione tra insiemi e classi che impedisce la possibilit\`a di costruire l'iperalbero all'interno della teoria. Un problema molto simile lo troveremo quando considereremo la classe di tutti i numeri ordinali, che in qualche modo \`e un ``iperordinale'', ovvero sta agli ordinali come l'iperalbero sta agli alberi ben fondati. Parlando a livello informale il problema si pone in questi termini: i numeri ordinali servono per contare gli insiemi (sia finiti che infiniti), e la domanda \`e se possano essi stessi essere contati. Come vedremo ci\`o equivale a chiedersi se la classe ON di tutti gli ordinali sia essa stessa un ordinale. Se non si distinguesse tra insiemi e classi si incorrerebbe nel paradosso di Burali-Forti, secondo il quale la classe ON degli ordinali \`e effettivamente un ordinale, e l'assurdo sta nel fatto che, se ON fosse un ordinale, sarebbe l'ordinale pi\`u grande di tutti, che per\`o non pu\`o esistere in quanto posso sempre aggiungere uno. La soluzione proposta dalla teoria assiomatica degli insiemi \`e che, sebbene la classe ON abbia quasi tutte le propriet\`a richieste per essere un ordinale, gliene manca una: non \`e un insieme. Si tratta, se vogliamo, di una soluzione burocratica: si pongono degli assiomi che impediscono (almeno si spera) la costruzione di entit\`a paradossali. Si tratta per\`o anche di una soluzione pragmatica: si riesce fortunatamente a far ci\`o senza al contempo impedire la costruzione di tutte quelle entit\`a che servono ai matematici.
|
||
|
||
\section{Connettivi logici}
|
||
|
||
Assumiamo la concezione ``classica'' secondo cui una proposizione \`e o vera o falsa (principio del terzo escluso), ma non pu\`o essere sia vera che falsa (principio di non contraddizione). Diremo che una proposizione $P$ ha il {\em valore di verit\`a} {\bf 1} se essa \`e vera, e il {\em valore di verit\`a $\bf 0$} se essa \`e falsa. Un predicato \`e una proposizione che dipende da alcuni parametri, come ad esempio ``$x > 3$, che \`e vero o falso a seconda di chi sia $x$. Useremo spesso dei nomi simbolici come $P,Q,\ldots$ per denotare generiche proposizioni e predicati. Per evidenziare la eventuale dipendenza da un parametro $x$ scriveremo anche $P(x), Q(x)$ eccetera. Ad esempio ``$P(x)$'' potrebbe essere il predicato ``$x>3$''. Se ci sono pi\`u parametri useremo notazioni come $P(x,y)$ o simili. Ad esempio ``$P(x,y)$'' potrebbe essere ``$x>y$''.
|
||
|
||
I connettivi servono per costruire proposizioni e predicati complessi a partire da proposizioni e predicati pi\`u semplici. I connettivi di cui faremo
|
||
maggiore uso sono indicati con i simboli $\lnot, \land, \lor,
|
||
\limplies, \liff$ (oltre ai quantificatori che tratteremo pi\`u tardi). La loro traduzione approssimativa in italiano \`e
|
||
la seguente:
|
||
\begin{center}
|
||
``$\lnot A$'' significa ``non $A$'' (negazione),
|
||
|
||
``$A \land B$'' significa ``$A$ e $B$'' (congiunzione),
|
||
|
||
``$A \lor B$'' significa ``$A$ o $B$'' (disgiunzione),
|
||
|
||
``$A \to B$'' significa ``se $A$, allora $B$'' (implicazione),
|
||
|
||
``$A \liff B$'' significa ``$A$ se e solo se $B$'' (doppia implicazione).
|
||
\end{center}
|
||
|
||
Le seguenti {\em tavole di verit\`a} precisano il significato dei connettivi secondo la logica classica.
|
||
Iniziamo con la tavola delle negazione:
|
||
\begin{center}
|
||
%\medskip
|
||
$\begin{array}{c|c}
|
||
A & \lnot A \\ \hline
|
||
\F & \V \\
|
||
\V & \F
|
||
\end{array}$
|
||
\end{center}
|
||
La tavola dice che la proposizione $\lnot A$ \`e vera se $A$ \`e falsa, ed \`e
|
||
invece falsa se $A$ \`e vera. La negazione inverte il valore di verit\`a. Diamo
|
||
ora le tavole degli altri connettivi.
|
||
\begin{center}
|
||
%\medskip
|
||
$\begin{array}{cc|cccc}
|
||
A & B & A \land B & A \lor B & A \to B & A \liff B \\ \hline
|
||
\F & \F & \F & \F & \V & \V \\
|
||
\F & \V & \F & \V & \V & \F \\
|
||
\V & \F & \F & \V & \F & \F \\
|
||
\V & \V & \V & \V & \V & \V
|
||
\end{array}$
|
||
\end{center}
|
||
Le prime due colonne indicano i quattro possibili valori di verit\`a
|
||
di $A$ e $B$. Le altre colonne indicano i corrispondenti valori degli
|
||
enunciati composti $A \land B$, $A \lor B$, $A \to B$, $A \liff B$.
|
||
|
||
Le tavole della congiunzione e della disgiunzione non richiedono particolari commenti, salvo forse osservare che la disgiunzione \`e intesa in senso inclusivo, ovvero affinch\'e $A \lor B$ sia vera basta che una tra $A$ e $B$ sia vera, incluso il caso in cui lo sono entrambe.
|
||
|
||
Pi\`u delicato \`e il caso dell'implicazione. Dalle tavole risulta che l'implicazione $A \to B$ \`e falsa solo nel caso in cui la premessa $A$ \`e vera e il conseguente
|
||
$B$ \`e falso. In particolare se la premessa $A$ \`e falsa,
|
||
l'implicazione $A \to B$ \`e vera. Ad esempio l'implicazione ``$x \textrm{ \`e pari} \to \textrm{il quadrato di } x \textrm{ \`e pari}$'', \`e vera per ogni numero intero $x$ (anche per gli $x$ dispari!).
|
||
|
||
Per dimostrare una implicazione $A\to B$ si pu\`o assumere ``in via ipotetica'' che $A$ sia vera, e cercare di dimostrare $B$ (notando che se $A$ fosse invece falsa l'implicazione sarebbe comunque vera in base alle tavole). Se si riesce a dimostrare $B$ all'interno della dimostrazione subordinata in cui $A$ \`e assunta vera, si pu\`o a quel punto ``scaricare l'ipotesi $A$'' (ovvero uscire dalla dimostrazione subordinata) e concludere che $A\to B$ \`e vera. La validit\`a di questo metodo argomentativo \`e giustificata dalle tavole.
|
||
|
||
Dai discorsi appena fatti si capisce che una dimostrazione matematica non ha sempre una struttura lineare, ma ha in generale una struttura annidata contenente al suo interno dimostrazioni subordinate (anche a pi\`u livelli), ciascuna delle quali inizia con l'introduzione di ulteriori ipotesi che poi vengono scaricate quando si torna alla dimostrazione principale (o a quella di livello immediatamente superiore). Occorre pertanto sempre fare attenzione a quali sono le ipotesi in vigore in ciascun momento della dimostrazione.
|
||
|
||
\section{Quantificatori}
|
||
I quantificatori sono speciali connettivi che hanno il ruolo di esprimere quanti oggetti verificano un dato predicato (da cui il nome ``quantificatori''). Ad esempio, supponendo che il dominio del discorso siano i cittadini con diritto di voto, possiamo applicare il quantificatore ``per la maggioranza degli $x$'' al predicato ``$x \textrm{ vota il partito del progresso }$'' ottenendo la proposizione ``(per la maggioranza degli $x$)($x$ vota il partito del progresso)'', o pi\`u semplicemente ``la maggioranza vota il partito del progresso''.
|
||
|
||
Useremo il termine ``propriet\`a'' come sinonimo di ``predicato'', riferendolo per\`o principalmente a predicati ad un solo argomento (in sequito incontreremo predicati a pi\`u argomenti).
|
||
|
||
I quantificatori di cui faremo maggior uso sono $\forall x$ (per ogni $x$) ed $\exists x$ (esiste almeno un $x$). Dato un predicato $P$, la proposizione $$\exists x P(x)$$ esprime il fatto che esiste almeno un
|
||
oggetto $a$ nel dominio del discorso che verifica il predicato, ovvero
|
||
tale che valga $P(a)$. La proposizione $$\forall x P(x)$$ dice che per
|
||
tutti gli oggetti $a$ nel dominio del discorso vale $P(a)$.
|
||
|
||
Se abbiamo un predicato di due argomenti, ovvero della forma $Q(x,y)$, la proposizione $$\exists x \, Q(x,y),$$ sar\`a vera o falsa a seconda di chi sia $y$. Ad esempio se $y =$ Maria, la proposizione $\exists x (x \textrm{ \`e figlio di } y)$, sar\`a vera o falsa a seconda che Maria abbia effettivamente un figlio.
|
||
|
||
Le variabili ``legate'', ovvero quelle che cadono sotto l'effetto di un quantificatore,
|
||
possono essere ridenominate senza alterare il significato dell'enunciato. Ad esempio $\exists x P(x)$ significa la stessa cosa di $\exists y P(y)$, ovvero che esiste un oggetto del dominio del discorso verificano $P$. Se considero un predicato $Q$ di due argomenti, e scrivo $\exists x \,Q(x,y)$, posso ridenominare la $x$ (perch\'e \`e legata) ma non la $y$, che \`e invece ``libera'', ovvero non legata. Se scrivo ``$\exists x (x \textrm{ \`e figlia di } y)$'', sto affermando che la persona $y$ ha una figlia (osserviamo che la ``$x$'' non compare affatto in questa parafrasi), che \`e la stessa cosa che dire ``$\exists z (z \textrm{ \`e figlia di } y)$'', mentre \`e diverso dal dire ``$\exists x (x \textrm{ \`e figlia di } w)$'', che esprime invece il fatto che \`e $w$ (anzich\'e $y$) ad avere una figlia.
|
||
Come si vede da questi esempi, le variabili libere si comportano come ``nomi'', mentre quelle legate sono espedienti linguistici che, pur non avendo un significato proprio, giocano il ruolo di segnaposto, ovvero fanno capire a quale parte del predicato si riferisce il quantificatore.
|
||
|
||
Per predicati a pi\`u argomenti possiamo avere diverse combinazioni di $\forall$ e
|
||
$\exists$ ed \`e importante tenere conto dell'ordine in cui si alternano i quantificatori.
|
||
Ad esempio $$\forall x \exists y P(x,y)$$ significa che, dato un $x$,
|
||
posso sempre trovare un $y$, che in genere dipender\`a da $x$, tale
|
||
che $P(x,y)$. Se invece scrivo $$\exists y \forall x P(x,y)$$ sto dicendo che
|
||
esiste un $y$ che va bene per tutti gli $x$, ovvero un
|
||
$y$ tale che, per ogni $x$, vale $P(x,y)$. In particolare, se il dominio
|
||
delle variabili \`e un insieme di persone, e $P(x,y)$ \`e il predicato ``$y$ \`e uno dei genitori di $x$'', allora $\forall x \exists y P(x,y)$ dice
|
||
che ogni persona ha un genitore, mentre $\exists y \forall x P(x,y)$ dice che esiste
|
||
una persona $y$ che \`e genitore di tutti (inclusa se stessa).
|
||
|
||
Sin dall'antichit\`a sono state studiate le leggi che regolano il comportamento dei quantificatori in combinazione con i connettivi $\lnot, \land, \lor, \to$. Aristotele ne aveva enucleate alcune (i sillogismi). Per una lista completa (frutto dei lavori di Frege e dei suoi successori) rimandiamo a qualunque testo di logica che tratti del calcolo dei predicati.
|
||
Vale tuttavia la pena ricordare almeno il comportamento dei quantificatori $\forall$ ed $\exists$ rispetto alla negazione.
|
||
Secondo le regole della logica classica $\lnot \forall x P(x)$ equivale a $\exists x \lnot P(x)$ (``non \`e vero che tutti gli $x$ verificano $P$'' equivale a ``esiste almeno un $x$ che non verifica $P$''). Similmente $\lnot \exists x P(x)$ equivale a $\forall x \lnot P(x)$. Siccome le doppie negazioni si elidono, si ottiene anche che $\forall x P(x)$ equivale a $\lnot \exists x \lnot P(x)$ (``tutti gli $x$ verificano $P$'' \`e la stessa cosa di ``non esiste alcun $x$ che non verifichi $P$''). Dualmente, $\exists x P(x)$ equivale a $\lnot \forall x \lnot P(x)$.
|
||
|
||
Ricordiamo infine le regole pi\`u significative che riguardano i quantificatori $\exists$ e $\forall$ presi isolatamente.
|
||
Mentre per dimostrare un enunciato della forma $\exists x P(x)$ basta trovare un oggetto $a$ che verifica il predicato $P$ (come quando dimostriamo che esiste un numero primo maggiore di $99$ dando $101$ come esempio), pi\`u problematico \`e il caso del $\forall x P(x)$, in quanto nella maggior parte dei casi non \`e possibile passare in rassegna tutti i possibili $x$ e provarli uno per uno. Si usa allora il seguente trucco, che richiede di comprendere bene la distinzione tra nomi e cose denotate. Se dico \guillemotleft Alessandro va al cinema\guillemotright \ mi riferisco alla persona, ma se dico \guillemotleft``Alessandro'' ha quattro sillabe\guillemotright, mi riferisco al nome della persona. Ovviamente non posso parlare di qualcosa se non nominandola, e se voglio parlare di un nome devo usare il nome del nome, ovvero mettere il nome tra virgolette. Ora per dimostrare $\forall x P(x)$ basta riuscire a dimostrare $P(a)$ senza fare ipotesi su $a$, ovvero senza sapere di quale oggetto ``a'' sia il nome. Supponiamo ad esempio che, dato un predicato $Q(x)$, io voglia dimostrare $\forall x(Q(x) \lor \lnot Q(x))$. A tal fine mi basta dimostrare $Q(a)\lor \lnot Q(a)$ senza sapere chi sia $a$. Questo \`e facile in quanto, pur non sapendo se $Q(a)$ sia vero o falso (in quanto non conosco $a$), in base alle tavole del $\lnot$ posso sicuramente dire che se $Q(a)$ \`e falso $\lnot Q(a)$ \`e vero e viceversa, e quindi in ogni caso $Q(a) \lor \lnot Q(a)$ \`e vero in base alle tavole del $\lor$. In qualche caso dovr\`o basarmi su proposizioni precedentemente dimostrare o assunte come assioma. Se ad esempio voglio dimostrare che dato un numero reale $a$, il suo quadrato $a^2$ \`e maggiore o uguale a zero, non mi serve sapere quale numero sia $a$, ma mi basta distinguere tre casi a seconda che $a$ sia positivo negativo o zero, e ricordare che positivo per positivo \`e positivo, e negativo per negativo \`e ancora positivo.
|
||
|
||
\section{Oggetti e classi nel linguaggio di tutti i giorni}
|
||
Fissato un ``universo del discorso'' e una propriet\`a $P(x)$, possiamo considerare la classe degli oggetti $a$, nell'universo del discorso, per cui vale $P(a)$. Tale classe \`e indicata con la notazione ``$\{x: P(x)\}$''. Ad esempio, se sto parlando di persone (ovvero se le mie variabili variano su persone), la classe degli insegnanti \`e indicata con la notazione ``$\{x : x \textrm{ \`e un insegnante}\}$''. Nella notazione $\{x: P(x)\}$ la ``$x$'' si comporta come una variabile legata e pertanto pu\`o essere ridenominata: $\{x: P(x)\}$ \`e la stessa cosa di $\{y: P(y)\}$. In generale la $P$ potrebbe contenere dei parametri, ovvero $P(x)$ potrebbe essere della forma $Q(x,a)$. In tal caso la classe $\{x: Q(x,a)\}$ dipender\`a da $a$. Ad esempio $\{x : x \textrm{ \`e amico di $a$} \}$ \`e la classe degli amici di $a$, che dipende ovviamente da chi \`e $a$.
|
||
|
||
In generale sciviamo ``$a\in X$'' per esprimere il fatto che l'oggetto $a$ appartiene alla classe $X$.
|
||
Quindi anzich\`e dire ``$a$ \`e un insegnante'', possiamo dire ``$a\in \{x : x \textrm{ \`e un insegnante}\}$'', ovvero ``$a$ appartiene alla classe degli insegnanti''.
|
||
|
||
Assumeremo per le classi il seguente assioma:
|
||
|
||
\begin{axiom}[Assioma di estensionalit\`a] Due classi sono uguali se hanno gli stessi elementi.
|
||
\end{axiom}
|
||
|
||
In base all'assioma di estensionalit\`a, se $P$ e $Q$ sono due propriet\`a sotto cui cadono gli stessi oggetti, le corrispondenti classi sono uguali. Se per puro caso nel nostro universo del discorso gli oggetti tondi fossero esattamente quelli blu, allora in base all'assioma di estensionalit\`a la classe degli oggetti tondi coinciderebbe con la classe degli oggetti blu, sebbene la propriet\`a ``$x$ \`e tondo'' non coincida con la propriet\`a ``$x$ \`e blu''.
|
||
|
||
\bd Date due classi $X$ ed $Y$ diciamo che $X$ \`e inclusa in $Y$ (o che $X$ \`e una sottoclasse di $Y$) se ogni elemento di $X$ \`e un elemento di $Y$, ovvero $$\forall x (x \in X \to x \in Y).$$
|
||
Scriviamo $$X \subseteq Y$$ per esprimere il fatto che $X$ \`e inclusa in $Y$. Ci\`o equivale a dire che non vi sono elementi di $X$ che non appartengono ad $Y$. \ed
|
||
|
||
\br In base all'assioma di estensionalit\`a, $X=Y$ se e solo se $X\subseteq Y$ e $Y \subseteq X$. \er
|
||
|
||
Date due propriet\`a $P$ e $Q$, dire che vale l'inclusione $\{x: P(x)\} \subseteq \{x: Q(x)\}$ equivale a dire che, per ogni oggetto $x$, vale l'implicazione $P(x) \to Q(x)$. L'uguaglianza $\{x: P(x)\} = \{x: Q(x)\}$ corrisponde invece alla doppia implicazione $\forall x (P(x) \liff Q(x))$.
|
||
|
||
\bd Scriveremo $X\subset Y$ (inclusione stretta) se vale l'inclusione $X\subseteq Y$ ma $X$ non \`e uguale ad $Y$. \ed
|
||
|
||
|
||
\section{L'algebra di Boole delle classi}
|
||
|
||
Fissiamo una classe di oggetti $V$ come universo del discorso. Dire $a\in V$ equivale a dire che $a$ \`e un oggetto del nostro universo del discorso. Tutte le classi sono sottoclassi di $V$, ovvero sono incluse nella classe universale $V$.
|
||
|
||
Dato un oggetto $x\in V$ ed una classe $X\subseteq V$, scriviamo $x\nin X$ come abbreviazione per $\lnot (x\in X)$. La classe complementare $$\compl{X} = \{x: x \nin X\}$$ \`e definita come la classe degli oggetti, nell'universo del discorso $V$, che non appartengono ad $X$.
|
||
Pi\`u in generale date due classi $X$ ed $Y$ possiamo formare la loro differenza $$Y\setminus X = \{x: x \in Y \land x\nin X\}$$ e osservare che $$\compl{X} = V \setminus X.$$
|
||
|
||
Possiamo inoltre considerare l'unione $$X \cup Y = \{x: x \in X \vee x \in Y\}$$ delle due classi, definita come la classe i cui elementi sono gli oggetti che appartengono ad $X$ o ad $Y$ (senza escludere che appartengano ad entrambi), e la loro intersezione $$X \cap Y = \{x: x \in X \wedge x \in Y\}$$ i cui elementi sono gli oggetti che appartengono sia ad $X$ che ad $Y$. Se $X$ ed $Y$ non hanno elementi in comune la loro intersezione $X \cap Y$ \`e la classe vuota. Essa pu\`o essere definita come la classe definita da un qualunque predicato contraddittorio. Ad esempio se $P(x)$ \`e il predicato $x\neq x$ allora la classe $\{x: P(x) \}$ \`e vuota, ovvero non ha elementi.
|
||
|
||
|
||
\bprop Una classe vuota $X$ \`e inclusa in qualsiasi altra classe $Y$. \eprop
|
||
\bp In base alla definizione di inclusione tra classi, occorre dimostrare che, per ogni oggetto $a$, vale l'implicazione $a\in X \to a\in Y$. Tale implicazione \`e sempre vera (in base alle tavole di verit\`a) in quanto la sua premessa ``$a \in X$'' \`e sempre falsa (essendo $X$ vuota).
|
||
|
||
Detto in altri termini, se $X$ non fosse inclusa in $Y$, ci dovrebbe essere un elemento che appartiene ad $X$ ma non ad $Y$, ma questo \`e assurdo in quanto nessun elemento appartiene ad $X$. \ep
|
||
|
||
Ne segue che due classi vuote sono incluse l'una nell'altra e pertanto sono uguali in base all'assioma di estensionalit\`a. Esiste dunque un'unica classe vuota.
|
||
|
||
\bd La classe vuota $\emptyset$ \`e l'unica classe che non ha elementi. Essa pu\`o essere definita da un qualsiasi predicato contraddittorio. Abbiamo dunque $\emptyset = \{x: x\neq x\}$. \ed
|
||
|
||
Data una classe qualsiasi $X$, valgono le inclusioni $\emptyset \subseteq X$ e $X \subseteq V$.
|
||
In altre parole ogni classe include la classe vuota ed \`e inclusa nella classe universale $V$.
|
||
|
||
\bprop Valgono le seguenti identit\`a (esprimenti il fatto che le classi formano una ``algebra di Boole''):
|
||
%Valgono le seguenti propriet\`a.
|
||
\begin{enumerate}
|
||
\setlength{\itemsep}{-3pt}
|
||
\setlength{\parskip}{-1pt}
|
||
\item (leggi commutative)
|
||
\begin{enumerate} \item $X \cup Y = Y \cup X$, \item $X \cap Y = Y \cap X$. \end{enumerate}
|
||
\item (leggi associative)
|
||
\begin{enumerate}
|
||
\item $(X \cap Y) \cap Z = X \cap (Y \cap Z)$, \item $(X \cup Y) \cup Z = X \cup (Y \cup Z)$.
|
||
\end{enumerate}
|
||
\item (leggi distributive)
|
||
\begin{enumerate} \item $X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z)$, \item $X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)$. \end{enumerate}
|
||
\item (identit\`a)
|
||
\begin{enumerate} \item $X \cup \emptyset = X$, \item $X \cap V = X$.
|
||
\end{enumerate}
|
||
\item (complemento)
|
||
\begin{enumerate} \item $X \cup \compl{X} = V$, \item $X \cap \compl{X} = \emptyset$.
|
||
\end{enumerate}
|
||
\end{enumerate}
|
||
\eprop
|
||
\bp (Cenno) Visto che $\land,\lor, \complement,$ sono definiti facendo ricorso ai connettivi logici $\land, \lor, \lnot,$ occorre far ricorso alle corrispondenti propriet\`a di questi ultimi. Consideriamo ad esempio la legge distributiva $$X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z).$$ Per dimostrarla si fissi un generico oggetto $x$ e si considerino le proposizioni $P,Q,R$ cos\`{\i} definite: $P$ \`e la proposizione ``$x\in X$'', come $Q$ prendiamo ``$x\in Y$'', e come $R$ prendiamo ``$x\in Z$''. In base alle definizioni di $\cup$ e $\cap$, la proposizione $$x\in X \cup (Y \cap Z)$$ equivale a $$x\in X \lor (x\in Y \land x\in Z),$$ ovvero alla proposizione $$P \lor (Q \land R).$$ Quest'ultima, in base alle tavole di verit\`a dei connettivi logici, equivale a $$(P \lor Q) \land (P \lor R),$$ come si pu\`o facilmente verificare assegnando a $P,Q,R$ i valori ``vero'' o ``falso'' negli otto modi possibili, e controllando che le due proposizioni composte risultano in ciascun caso entrambe vere o entrambe false in base alle tavole. Espandendo le definizioni di $P,Q,R$ otteniamo
|
||
$$(x\in X \lor x\in Y) \land (x\in X \lor x\in Z),$$ che a sua volta equivale a
|
||
$$x\in X \cup (Y \cap Z).$$
|
||
Abbiamo cos\ii dimostrato che $x\in X \cup (Y \cap Z)$ se e solo se $x\in (X \cup Y) \cap (X \cup Z)$, e visto che questo vale per ogni possibile oggetto $x$, ne segue per estensionalit\`a che $X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z)$.
|
||
\ep
|
||
|
||
Nella sezione sui quantificatori abbiamo detto che le variabili libere sono ``nomi'' di oggetti, ma questa \`e in effetti una ipersemplificazione. In certi casi esse sono nomi di ``oggetti ipotetici'', come si vede nel seguente esercizio.
|
||
|
||
\bexe Data una classe $X$, si dimostri che $X\subseteq \compl{X} \to X= \emptyset$. \eexe
|
||
\bp Basta dimostrare $X=\emptyset$ assumendo $X\subseteq \compl{X}$. Assumiamo dunque $X\subseteq \compl{X}$. Se per assurdo $X\neq \emptyset$, allora $\exists x (x\in X)$, ovvero $X$ contiene almeno un oggetto\footnote{Se non conoscete le dimostrazioni per assurdo potete ragionare nel modo seguente. I casi sono due: o $X=\emptyset$ e abbiamo finito. Oppure $X \neq \emptyset$. Consideriamo dunque questo secondo caso.}. Consideriamo un tale ipotetico oggetto e chiamiamolo ``$a$'' \footnote{Questa \`e una delle mosse permesse dalle leggi della logica: sapendo $\exists x P(x)$ possiamo scegliere un tale $x$ e dargli un nome. Ci\`o non va confuso con l'assioma della scelta studieremo nel seguito}. Dunque $a\in X$. Ma essendo $X\subseteq \compl{X}$ abbiamo $\forall x(x\in X \to x\in \compl{X})$. Questo deve valere per ogni $x$ e dunque anche per $a$. Dunque $a\in X \to a \in \compl{X}$ \footnote{Abbiamo applicato un'altra legge logica: il passaggio da $\forall x P(x)$ a $P(a)$.}.
|
||
Siccome stiamo assumendo che la premessa $a\in X$ sia vera, anche la conclusione $a\in \compl{X}$ deve essere vera in base alla tavola di verit\`a del $\to$. Dunque $a$ appartiene sia ad $X$ che al suo complemento $\compl{X}$. Questo \`e assurdo per la definizione di $\compl{X}$. Abbiamo dunque concluso la dimostrazione, ma riflettiamo: di quale oggetto ``$a$'' pu\`o essere il nome visto che in definitiva abbiamo dimostrato che $X$ \`e vuoto?
|
||
\ep
|
||
|
||
|
||
\section{Quantificatori limitati}
|
||
%\begin{notation}
|
||
Introduciamo i quantificatori limitati ``$\exists a\in X$'' e ``$\forall a \in X$'' (dove $X$ \`e una classe) nel modo seguente.
|
||
Dato un predicato $P(x)$, conveniamo che ``$(\exists a\in X)P(a)$'' sia un'abbreviazione per ``$\exists a (a \in X \land P(a))$'', che possiamo leggere come ``esiste $a$ appartenente ad $X$ tale che $P(a)$''. Ci\`o equivale a dire che la classe $X$ interseca la classe $\{a: P(a)\}$, ovvero $X \cap \{a: P(a)\} \neq \emptyset$.
|
||
|
||
Dualmente definiamo ``$(\forall a\in X) P(a)$'' come abbreviazione per ``$\forall a (a \in X \to P(a))$'', che possiamo leggere come ``per ogni $a$ appartenente ad $X$ vale $P(a)$''. Ci\`o equivale a dire che vale l'inclusione $X \subseteq \{a: P(a)\}$.
|
||
%\end{notation}
|
||
|
||
|
||
\section{Primi assiomi: estensionalit\`a, astrazione, comprensione}
|
||
Nei capitoli precedenti abbiamo visto come, fissato un ``universo del discorso'', possiamo considerare gli oggetti e le classi di tale universo. Ad esempio se consideriamo l'universo delle persone, gli oggetti saranno le singole persone, e le classi saranno classi di persone, ad esempio la classe degli insegnanti.
|
||
|
||
Vorremmo ora prendere come universo $V$ del discorso, l'universo di tutti gli oggetti matematici. Ci\`o non \`e semplice in quanto la nozione stessa di oggetto matematico \`e piuttosto problematica: ad esempio non \`e facile rispondere alla domanda se una classe di oggetti matematici sia essa stessa un oggetto matematico. Sicuramente la classe di tutte le funzioni reali continue lo \`e (e viene studiata dai matematici in quanto tale). Ma la classe di tutti gli oggetti matematici? O la classe di tutti gli alberi ben fondati? (L'abbiamo incontrata nella sezione sull'iperalbero, ricordate?)
|
||
|
||
Seguiremo pertanto l'approccio assiomatico, ovvero, avendo in mente l'ambito matematico, non definiremo n\`e cosa sia un oggetto, n\`e cosa sia una classe, n\`e che cosa sia la relazione di appartenenza, lasciando che siano gli assiomi che via via daremo a suggerire implicitamente il significato di questi termini. Postuleremo dunque l'esistenza di una classe universale $V$ di tutti gli oggetti (matematici), e daremo degli assiomi che forniscono informazioni su $V$, i suoi elementi, e le sue sottoclassi. Della classe $V$ non faranno parte n\'e le persone, n\'e i pianeti, n\'e alcun oggetto fisico, ma solo ed esclusivamente oggetti matematici come i numeri naturali, i numeri reali, le funzioni, eccetera. Alcune delle sottoclassi di $V$ saranno esse stesse elementi di $V$ e verranno chiamate ``insiemi''. Risulter\`a inoltre che sar\`a possibile economizzare: possiamo assumere (sebbene non sia strettamente indispensabile) che non vi siano ``urelementi'', ovvero oggetti che non siano essi stessi insiemi. Ci\`o pu\`o sembrare paradossale in quanto ogni insieme \`e un insieme di oggetti, e senza oggetti non vi sono nemmeno gli insiemi. Tuttavia almeno l'insieme vuoto c'\`e sempre ed \`e un oggetto, e vedremo che, a partire da esso, e considerando insiemi i cui elementi siano altri insiemi, possiamo modellare tutti gli oggetti matematici che ci interessano.
|
||
|
||
Senza ulteriori preamboli passiamo a dare i primi assiomi. Il primo assioma \`e per l'appunto che esiste una classe universale $V$ tale che ogni oggetto appartiene a $V$. Nelle versioni ufficiali di GB esso non compare in quanto si deduce dagli altri assiomi, ma per chiarezza ho deciso di includerlo. Possiamo quindi pensare alla parola ``classe'' come ``sottoclasse di $V$'', e alla parola ``oggetto'' come ``elemento di $V$''.
|
||
Il primo assioma della lista ufficiale lo abbiamo gi\`a precedentemente incontrato:
|
||
|
||
\begin{axiom}[Assioma di estensionalit\`a] Due classi sono uguali se hanno gli stessi elementi.
|
||
\end{axiom}
|
||
|
||
Il secondo assioma (che \`e in effetti uno ``schema di assiomi'', uno per ogni $P$), \`e il seguente:
|
||
|
||
\begin{axiom}[Schema di assiomi di astrazione] Data una propriet\`a ben definita $P$, esiste una classe i cui elementi sono gli oggetti $x$ che verificano $P$.
|
||
Tale classe \`e unica per l'assioma di estensionalit\`a e usiamo la notazione $\{x: P(x)\}$ per denotarla. Per definizione, $a\in \{x:P(x)\}$ se e solo se vale $P(a)$. In simboli:
|
||
$$a \in \{x: P(x)\} \iff P(a)$$
|
||
dove usiamo $\iff$ come sinonimo di $\liff$, ovvero per dire che le due affermazioni che compaiono ai lati del simbolo sono entrambe vere o entrambe false (si vedano le tavole di verit\`a).
|
||
|
||
Prima di procedere oltre, vanno fatte alcune precisazioni su cosa si intenda per propriet\`a ben definita. Nella teoria assiomatica di G\"odel-Bernays, che \`e quella trattata in queste note, per propriet\`a ben definita intendiamo qualsiasi propriet\`a che si possa esprimere (rispettando la sintassi) usando l'appartenenza $\in$, l'uguaglianza $=$, le variabili, e gli usuali connettivi logici $\land$ (congiunzione), $\lor$ (disgiunzione), $\to$ (implicazione), $\liff$ (doppia implicazione), $\lnot$ (negazione), $\exists x$ (quantificatore esistenziale), $\forall x$ (quantificatore universale), dove le variabili quantificate variano su oggetti (ovvero elementi di $V$) e non su classi. In MK ammettiamo invece che le propriet\`a che intervengono nello schema di astrazione contengano anche quantificatori su classi. Per il momento non \`e il caso di essere pi\`u precisi, salvo osservare che, tra le propriet\`a ammissibili nello schema di astrazione, non rientrano quelle propriet\`a che fanno riferimento alla realt\`a fisica come ``$x$ \`e un insetto'', o simili. Lo schema proposto sar\`a in ogni caso sufficiente per gli scopi della matematica.
|
||
|
||
Se non avessimo postulato a parte l'esistenza di $V$, essa potrebbe essere dedotta dall'assioma di astrazione definendo $V$ come la classe $\{x: x=x\}$. Tale classe contiene tutti gli oggetti in quanto, secondo la logica classica, ogni oggetto \`e uguale a se stesso.
|
||
|
||
Una precisazione importante \`e che nello schema di astrazione ammettiamo la possibilit\`a che in $P(x)$ compaiano altre variabili non quantificate, oltre la $x$, che svolgono il ruolo di parametri, come nel seguente esempio.
|
||
%Ad esempio, fissata una propriet\`a a due argomenti $Q(x,y)$ ed un oggetto (o una classe) $b$, possiamo considerare la classe $\{x: Q(x,b)\}$ di tutti gli oggetti $x$ che stanno nella relazione $Q(x,b)$ con $b$.
|
||
\end{axiom}
|
||
|
||
\bexa Date due classi $A, B$, l'esistenza della classe unione $A \cup B = \{x: x\in A \lor x\in B\}$, segue dallo schema di astrazione prendendo come $P(x)$ la propriet\`a (con parametri $A,B$) definita dalla disgiunzione $x\in A \lor x\in B$. Similmente otteniamo l'esistenza della classe intersezione $A\cap B$ e della classe complemento $A^\complement$.
|
||
\eexa
|
||
|
||
%\bd La classe universale $V$ di tutti gli oggetti pu\`o essere definita come la classe $\{x: x = x\}$. Siccome ogni oggetto \`e uguale a se stesso, ogni oggetto appartiene a $V$, e ogni classe \`e inclusa in $V$.
|
||
%\ed
|
||
|
||
Si potrebbe pensare che la definizione di propriet\`a ben definita sia troppo restrittiva e che ci possano essere classi $A \subseteq V$ che non possano essere definite da alcuna propriet\`a. Tuttavia questo \`e vero solo se ci limitiamo a propriet\`a definite senza parametri. Infatti, data una qualsiasi classe $A$, possiamo ovviamente ``definire'' $A$ usando come parametro $A$ stesso:
|
||
$$A = \{x: x \in A\}$$
|
||
come segue immediatamente dall'assioma di estensionalit\`a.
|
||
|
||
Esiste in effetti una perfetta corrispondenza tra classi e propriet\`a: data una propriet\`a $P(x)$ posso formare la classe corrispondente $\{x: P(x)\}$, e viceversa, data una classe $A$, posso considerare la propriet\`a corrispondente $x\in A$. Il vero contenuto dell'assioma di astrazione in GB non \`e tanto quello di ``costruire'' classi a partire dalle propriet\`a, quanto quello di dire che ogni operazione che posso fare sulle propriet\`a ha un corrispettivo nelle classi. Ad esempio il fatto che posso prendere la disgiunzione $P(x) \lor Q(x)$ di due predicati corrisponde al fatto che posso prendere l'unione $A \cup B$ di due classi (ottenuta come la classe degli oggetti $x$ che verificano il predicato $x\in A\lor x\in B$).
|
||
La filosofia della teoria degli insiemi \`e di ispirazione platonica, ovvero si assume che $V$ e le sue sottoclassi esistano gi\`a, non vengono costruite a partire dalle definizioni (il bello della matematica \`e che non ci si deve credere sul serio per poter utilizzare la teoria).
|
||
|
||
Cogliamo l'occasione per sottolineare che lo schema di astrazione non \`e un singolo assioma, ma una lista infinita di assiomi, uno per ogni propriet\`a ben definita $P$. Tuttavia si pu\`o dimostrare che basta una lista finita di istanze dello schema per poter dedurre tutte le altre, e ci\`o rende GB, a differenza di ZF e di MK, finitamente assiomatizzabile.
|
||
|
||
Gli assiomi che abbiamo fin qui dato presuppongono un universo del discorso $V$ consistente di ``oggetti'' dalla natura non ancora specificata. In particolare non abbiamo detto se le classi stesse siano oggetti. Nel seguito daremo altri assiomi che stabiliranno sotto quali condizioni una classe $X$ possa essere considerata un oggetto (ovvero per quali $X\subseteq V$ si abbia $X\in V$). L'intento sar\`a quello di avere un universo di oggetti il pi\`u vasto possibile (per gli scopi della matematica), ma come vedremo non potr\`a in ogni caso essere talmente vasto da poter contenere come oggetti anche tutte le classi, pena incorrere in paradossi. Parlando informalmente, qualsiasi cosa sia $V$, le sottoclassi di $V$ sono in un certo senso ``di pi\`u'' degli elementi di $V$, e quindi non \`e possibile che ogni classe sia un oggetto (pu\`o essere utile fare un confronto con il teorema di Cantor, sebbene esso si applichi a insiemi e non a $V$ stesso: le parti di un insieme sono pi\`u numerose degli elementi dell'insieme). In definitiva risuter\`a che alcune classi sono oggetti (e verranno chiamate ``insiemi''), ma altre no (e verranno chiamate ``classi proprie'').
|
||
|
||
%Volendo si potrebbe fare a meno delle classi e parlare solamente di insiemi e propriet\`a (questo \`e l'approccio seguito nella teoria assiomatica di Zermelo-Fraenkel).
|
||
%Ad esempio, invece di dire che $a\in \{x: P(x)\}$, basta dire che vale $P(a)$.
|
||
%Tuttavia in molti casi risulta pi\`u semplice parlare esplicitamente di classi, come nella teoria di G\"odel-Bernays (che a parte questa differenza di linguaggio \`e sostanzialmente equivalente alla teoria di Zermelo-Fraenkel).
|
||
|
||
|
||
\bd Un insieme \`e una classe che \`e anche un oggetto, ovvero \`e uno degli elementi della classe universale $V$ di tutti gli oggetti. Equivalentemente, visto che tutte le classi sono incluse in $V$, un insieme \`e una classe che appartiene ad almeno un'altra classe. Una classe propria \`e una classe che non \`e un insieme. \ed
|
||
|
||
Ci possiamo ora chiedere se la classe universale $V=\{x: x=x\}$ sia un oggetto, ovvero se $V\in V$. Visto che $V=V$ sembrerebbe di s\`{\i}, essendo $x=x$ la propriet\`a definitoria della classe $V$. Tuttavia questo \`e un errore. Infatti secondo le nostre convenzioni la variabile $x$ in un'espressione della forma $\{x: P(x)\}$, e quindi in particolare nell'espressione $\{x:x=x\}$, varia su oggetti, e non possiamo quindi concludere che $V\in \{x: x = x\}$ senza prima aver stabilito se $V$ sia un oggetto. Vedremo che in effetti $V$ non \`e un oggetto. Abbiamo bisogno di un risultato preliminare.
|
||
|
||
\bd La classe di Russell \`e la classe $\{x : x\nin x\}$. \ed
|
||
|
||
\bt La classe di Russell non \`e un insieme. \et
|
||
\bp
|
||
Sia $R = \{x: x\nin x\}$. Per ogni oggetto $a$ abbiamo per definizione $a\in R$ se e solo se $a\nin a$. Se $R$ fosse un oggetto potremmo prendere $a=R$ ottenendo $R\in R$ se e solo se $R\nin R$, il che \`e assurdo. \ep
|
||
|
||
\begin{axiom}[Assioma di comprensione] Una sottoclasse di un insieme \`e un insieme. \end{axiom}
|
||
|
||
Dato un insieme $A$ e una proprie\`a $P$ indichiamo con $\{x\in A: P(x)\}$ la classe $\{x: x \in A \land P(x)\}$, ovvero la classe consistente di quegli elementi di $A$ che verificano il predicato $P$. Siccome tale classe \`e inclusa in $A$, per l'assioma di comprensione $\{x\in A: P(x)\}$ \`e un insieme. Si noti che l'assioma di comprensione pu\`o solo servire a generare sottoinsiemi di altri insiemi, e quindi avremo bisogno di altri assiomi per ottenere degli insiemi di partenza a cui applicare il procedimento.
|
||
|
||
\bc La classe $V$ di tutti gli oggetti non \`e un insieme (ovvero \`e una classe propria). \ec
|
||
\bp Ogni classe \`e inclusa in $V$, quindi se $V$ fosse un insieme tutte le classi sarebbero insiemi, ma sappiamo che la classe $R$ di Russell non lo \`e. \ep
|
||
|
||
\begin{nota}
|
||
Alla fine del 1800 Gottlob Frege propose una assiomatizzazione della teoria degli insiemi che aveva come unici assiomi l'estensionalit\`a e l'astrazione e in cui non esisteva distinzione tra insiemi e classi. In una famosa lettera del 1901 Bertrand Russell gli fece notare che la sua assiomatizzazione era contraddittoria. La dimostrazione si basava sulla classe di Russell $R = \{x: x\nin x\}$. Come abbiamo visto l'ipotesi che tale classe sia un insieme conduce ad un assurdo.
|
||
\end{nota}
|
||
|
||
|
||
\section{Insieme vuoto, coppia, unione}
|
||
|
||
Il seguente assioma garantisce che esiste almeno un insieme.
|
||
|
||
\begin{axiom}[Insieme vuoto] La classe vuota \`e un insieme. \end{axiom}
|
||
|
||
Per dimostrare l'esistenza di altri oggetti abbiamo bisogno di ulteriori assiomi. Diamo intanto una definizione.
|
||
Dati due oggetti $a,b$, sia $\{a,b\}$ la classe $\{x: x = a \vee x = b\}$. Tale classe ha solamente $a,b$ come elementi e viene chiamata la coppia degli elementi $a$ e $b$.
|
||
|
||
\begin{axiom}[Coppia] Dati due oggetti $a,b$, la coppia $\{a,b\}$ \`e un insieme.
|
||
\end{axiom}
|
||
|
||
Non richiediamo che $a,b$ siano oggetti distinti: possiamo anche prendere $a=b$, ottenendo il singoletto di $a$, ovvero l'insieme $\{a,a\}$. Il singoletto di $a$ viene comunemente indicato con la notazione $\{a\}$ e contiene solamente $a$ come elemento.
|
||
|
||
In generale quando diciamo ``dati due oggetti $a,b$'', con la parola ``due'' intendiamo in realt\`a ``degli'', ovvero non escludiamo (a meno di dirlo esplicitamente) il caso che $a$ e $b$ siano in effetti lo stesso oggetto (che quindi \`e uno, e non due). Il fatto di usare lettere diverse per denotarli (o denotarlo) vuol solo dire che {\em potrebbero} essere diversi, non che lo siano. Scrivere $a=b$ significa che l'oggetto denotato dalla lettera ``$a$'' coincide con l'oggetto denotato dalla lettera ``$b$'', e non che la lettera ``$a$'' sia uguale alla lettera ``$b$'' (ovviamente non lo \`e). In ogni caso $a=a$ \`e sempre vero, in quanto lo stesso nome denota lo stesso oggetto. Facciamo per\`o attenzione: la relazione di uguaglianza \`e una relazione tra gli oggetti, non tra i loro nomi, ma per parlare di oggetti li devo nominare.
|
||
|
||
\begin{axiom}[Unione binaria] Dati due insiemi $X$ ed $Y$, la loro unione $X \cup Y$ \`e un insieme. \end{axiom}
|
||
|
||
Avendo a disposizione le coppie e l'unione binaria possiamo formare le triple $\{a,b,c\} = \{a,b\}\cup \{c\}$, le quadruple $\{a,b,c,d\} = \{a,b,c\} \cup \{d\}$ e via dicendo.
|
||
Dobbiamo per\`o avere degli oggetti $a,b,c,d$ da cui partire. Dove li prendiamo? Per ora abbiamo definito un solo oggetto: l'insieme vuoto $\emptyset$. Abbiamo per\`o anche il singoletto $\{\emptyset\}$, che non \`e vuoto in quanto contiene come elemento $\emptyset$. A livello intuitivo questo corrisponde al fatto che una scatola vuota non \`e la stessa cosa di una scatola che contiene al suo interno una scatola vuota. Abbiamo poi $\{\{\emptyset\}\}$ (il singoletto del singoletto del vuoto), oppure l'insieme di due elementi $\{\emptyset, \{\emptyset\}\}$, e procedendo in questo modo otteniamo una quantit\`a potenzialmente illimitata di insiemi distinti. Li possiamo immaginare come scatole cinesi una entro l'altra e terminanti sempre con la scatola vuota. Tuttavia l'analogia tra insiemi e scatole ha dei limiti: uno stesso oggetto pu\`o appartenere a pi\`u insiemi, ma non pu\`o essere contenuto in due scatole diverse. Gli insiemi si possono intersecare, le scatole no.
|
||
|
||
Si noti che, avendo a disposizione l'unione binaria, la coppia $\{a,b\}$ si ottiene per unione dai singoletti di $a$ e $b$, ovvero $\{a,b\} = \{a\} \cup \{b\}$.
|
||
|
||
Introdurremo ora il cosiddetto ``assioma dell'unione'', che in presenza dell'assioma della coppia implica l'assioma dell'unione binaria, rendendolo ridondante.
|
||
|
||
%\br $\lnot (\exists a \in X)P(a)$ equivale a $(\forall a \in X)\lnot P(a)$. \er
|
||
\bd Data una classe di insiemi $X$ (ovvero una classe i cui elementi sono insiemi) definiamo $\bigcup X$ (unione di $X$) come la classe di quegli oggetti che appartengono ad almeno un elemento di $X$. Quindi $x\in \bigcup X$ se e solo se $\exists a\in X$ tale che $x\in a$.
|
||
Un'altra notazione per $\bigcup X$ \`e $\bigcup_{A\in X}A$.
|
||
\ed
|
||
|
||
Ad esempio se $A,B$ sono due insiemi e $X = \{A,B\}$, allora $\bigcup X = A\cup B$. Infatti per definizione $x\in \bigcup X$ se $x$ appartiene ad uno degli elementi di $X$, ovvero $x\in A$ o $x\in B$, il che equivale a dire che $x\in A\cup B$.
|
||
|
||
\begin{axiom}[Assioma dell'unione] Se $X$ \`e un insieme di insiemi, $\bigcup X$ \`e un insieme. \end{axiom}
|
||
|
||
Nel seguito useremo talvolta come sinonimi ``famiglia di insiemi'' ed ``insieme di insiemi''. Quindi l'assioma dell'unione dice che l'unione di una famiglia di insiemi \`e un insieme.
|
||
Si noti che se $X$ fosse una classe propria potremmo ugualmente formare l'unione $\bigcup X$ in base allo schema di astrazione (ponendo $\bigcup X = \{x: (\exists y\in X)(x\in y)\}$), ma essa risulterebbe in generale una classe, mentre l'assioma dell'unione dice che se partiamo da un insieme otteniamo un insieme.
|
||
|
||
\bd Se $X$ \`e una classe di insiemi, definiamo $\bigcap X$ (intersezione di $X$) come la classe di quegli oggetti che appartengono a ciascuno degli elementi di $X$. Quindi $x\in \bigcap X$ se e solo se $\forall A \in X$ vale $x\in A$. \ed
|
||
|
||
\br Se $X$ \`e la classe vuota, $\bigcap X$ \`e la classe universale $V$ (verificate!). Se $X$ \`e una classe non vuota di insiemi, allora la classe $\bigcap X$ \`e un insieme in base all'assioma di comprensione in quanto \`e inclusa in ciascuno degli insiemi di $X$ (non abbiamo bisogno di uno specifico assioma come nel caso dell'unione).
|
||
\er
|
||
|
||
Gli assiomi fin qui dati non garantiscono l'esistenza di alcun oggetto che non sia un insieme (ad esempio non garantiscono l'esistenza di penne stilografiche).
|
||
Poich\'e uno degli scopi della teoria degli insiemi \`e dimostrare l'esistenza degli usuali oggetti matematici (numeri naturali, numeri reali, funzioni), abbiamo due possibilit\`a: o postuliamo l'esistenza di oggetti non-insiemistici (i cosiddetti ``urelementi'') e diamo per essi opportuni assiomi (ad esempio gli assiomi di Peano per i numeri naturali), oppure mostriamo come sia possibile modellare tutti gli oggetti della matematica in modo insiemistico. Sono possibili entrambe le strade, ma scegliamo la seconda. Diamo pertanto il seguente assioma:
|
||
|
||
\begin{axiom} Non esistono urelementi, ovvero ogni oggetto \`e un insieme. \end{axiom}
|
||
|
||
In presenza di questo assioma dire ``classe di insiemi'' \`e come dire ``classe'', e quindi l'assioma dell'unione assume la forma pi\`u semplice:
|
||
|
||
\begin{axiom}[Assioma dell'unione] Se $X$ \`e un insieme, $\bigcup X$ \`e un insieme. \end{axiom}
|
||
|
||
Se il lettore preferisce la versione con urelementi, non avr\`a difficolt\`a ad adattare gli assiomi tenendo conto della possibile presenza di urelementi. In questo caso la cosa principale a cui bisogna porre attenzione \`e che per gli urelementi non vale l'assioma di estensionalit\`a (altrimenti gli urelementi sarebbero tutti uguali e coinciderebbero con l'insieme vuoto, visto che non hanno elementi).
|
||
|
||
\section{I numeri naturali}
|
||
|
||
\bd Gli assiomi di Peano per i numeri naturali (che non fanno parte degli assiomi della teoria degli insiemi) sono i seguenti.
|
||
\begin{enumerate}
|
||
\item $0$ \`e un numero naturale.
|
||
\item Se $n$ \`e un numero naturale anche il suo successore $S(n)$ lo \`e (useremo anche la notazione $n+1$ per indicare il successore di $n$).
|
||
\item Se due numeri naturali hanno lo stesso successore sono uguali.
|
||
\item $0$ \`e l'unico numero naturale che non \`e un successore.
|
||
\item Assioma di induzione: Sia $X$ un insieme di numeri naturali che contiene $0$ ed \`e chiuso per successore (nel senso che, per ogni numero naturale $n$, $n\in X\to S(n)\in X$). Allora $X$ contiene ogni numero naturale $n$.
|
||
\end{enumerate}
|
||
\ed
|
||
|
||
L'assioma di induzione \`e ci\`o che giustifica le ``dimostrazioni per induzione'' che spero conosciate gi\`a: per dimostrare che una certa propriet\`a $P(x)$ vale per tutti i numeri naturali, uno dei metodi (non l'unico!) \`e ragionare nel modo seguente. Si cerca di dimostrare la {\em base dell'induzione} $P(0)$, e il {\em passo induttivo} $\forall x\in \N \big(P(x)\to P(S(x))\big)$. Se ci si riesce, in base all'assioma di induzione si pu\`o concludere che l'insieme $X = \{x\in \N: P(x)\}$ contiene ogni numero naturale, ovvero che $\forall x \in \N P(x)$. Avremo modo di familiarizzarci con questa tecnica nel seguito.
|
||
|
||
Il nostro scopo \`e quello di definire i numeri naturali in termini insiemistici in modo che risultino verificate le propriet\`a espresse dagli assiomi di Peano. Diamo la seguente definizione dovuta a von Neumann.
|
||
|
||
\bd \label{eccetera} $0 = \emptyset$, $1 = \{0\}$, $2 = \{0,1\}$, $3 = \{0,1,2\}$ e cos\`{\i} via.
|
||
In generale il successore $s(n)$ di $n$ \`e definito come $n \cup \{n\}$.
|
||
Ad esempio $s(3) = 3 \cup \{3\} = \{0,1,2\} \cup \{3\} = \{0,1,2,3\} = 4$. \ed
|
||
|
||
Esistono altre definizioni dei numeri naturali in termini insiemistici, oltre a quella di von Neumann. Ad esempio si potrebbe definire il successore di $n$ come il singoletto $\{n\}$ anzich\'e come $n\cup \{n\}$. La definizione di von Neumann ha il vantaggio che il numero $n$ ha esattamente $n$ elementi, nel senso comune del termine. Ad esempio il numero $4=\{0,1,2,3\}$ ha esattamente quattro elementi.
|
||
|
||
Osserviamo che sebbene gli assiomi sin qui dati ci forniscano infiniti insiemi (i numeri naturali), essi non ci forniscono ancora un insieme infinito. In particolare ancora non sappiamo se esista un insieme che contenga tutti i numeri naturali come elementi (in quanto la classe dei numeri naturali potrebbe non essere un insieme, ovvero potrebbe essere inclusa in $V$ senza appartenere a $V$). Questo ci \`e garantito dal seguente assioma.
|
||
|
||
\begin{axiom}[Assioma dell'infinito] \label{infinito} Esiste un insieme $X$ tale che
|
||
\begin{enumerate}
|
||
\item $\emptyset\in X$,
|
||
\item Se $a\in X$ allora $a\cup \{a\} \in X$.
|
||
\end{enumerate}
|
||
\end{axiom}
|
||
|
||
In base all'assioma l'insieme $X$ contiene $\emptyset$ e, se contiene $n$, contiene anche il successore di $n$ (secondo la definizione di von Neumann). Possiamo quindi concludere che $X$ contiene tutti i numeri naturali di von Neumann $0,1,2,3, \ldots$. Notiamo tuttavia che $X$ potrebbe contenere anche altri elementi oltre ai numeri naturali. Per trovare un insieme $X$ che contenga esclusivamente i numeri naturali dobbiamo innanzitutto definire in modo preciso cosa significhi ``$n$ \`e un numero naturale'' (la locuzione ``e cos\`{\i} via'' nella Definizione \ref{eccetera} non pu\`o essere presa come sostituto di una definizione precisa). Potremmo essere tentati di definirli come quegli oggetti che si ottengono da $\emptyset$ applicando ``un numero finito di volte'' la funzione successore. Dovremmo per\`o in questo caso dare una definizione di ``numero finito di volte'' che non faccia riferimento ai numeri naturali stessi.
|
||
Fortunatamente possiamo uscire dalla circolarit\`a nel modo seguente.
|
||
|
||
\bd Sia $\omega = \bigcap \ca F$, dove $\ca F$ \`e la classe di tutti gli insiemi $X$ tali che $\emptyset \in X$ ed $X$ \`e chiuso per successore (ovvero se $x\in X$ anche $x\cup \{x\}\in X$). Diciamo che $n$ \`e un numero naturale se $n\in \omega$. Si noti che $\ca F$ \`e non vuota per l'assioma dell'infinito, e che se $X$ \`e uno qualsiasi degli elementi di $\ca F$, abbiamo $\omega \subseteq X$. Ne segue che $\omega$ \`e un insieme per l'assioma di comprensione.
|
||
\ed
|
||
|
||
Notiamo che $\omega$ stesso appartiene alla classe $\ca F$, ovvero $\omega$ contiene $\emptyset$ ed \`e chiuso per successore (verificate!).
|
||
La definizione appena data di $\omega$ \`e pertanto ``impredicativa'', ovvero per definire $\omega$ si fa riferimento ad una classe $\ca F$ di oggetti che contiene $\omega$ stesso come elemento. La possibilit\`a di dare definizioni impredicative impedisce in generale di interpretare le definizioni come ``costruzioni'' degli oggetti definiti. Non possiamo dire che $\omega$ \`e ``costruito'' a partire da $\ca F$ in quanto $\omega$ doveva gi\`a esistere come uno degli elementi di $\ca F$. La giusta intepretazione \`e invece che sia $\omega$ che $\ca F$ esistevano gi\`a da sempre come elementi della classe universale $V$, e lo scopo della definizione \`e unicamente quello di ``isolare'' $\omega$ tra gli elementi di $V$, fornendone una descrizione che lo caratterizza.
|
||
|
||
Esistono scuole di pensiero che rifiutano le definizioni impredicative. Poincar\'e ad esempio era convinto che in esse risiedesse la fonte dei paradossi. Tuttavia in teoria degli insiemi esse sono accettate, e per il momento non si sono viste conseguenze nefaste. Sarebbe tuttavia possibile dare una definizione di $\omega$ un po' pi\`u predicativa. Prima si definiscono gli ordinali (li vedremo nel seguito), poi si definiscono gli ordinali finiti come quelli che non ammettono ordinali limite pi\`u piccoli di loro, e infine si definisce $\omega$ come l'insieme degli ordinali finiti. Il vantaggio di questa seconda definizione \`e che, anche senza l'assioma dell'infinito, $\omega$ risulta ben definito in GB in quanto classe (sebbene senza l'assioma dell'infinito non si possa dimostrare che tale classe sia un insieme).
|
||
|
||
Osserviamo che, in base alla definizione che ne abbiamo dato, $\omega$ \`e incluso in qualsiasi insieme $X$ che contiene $\emptyset$ ed \`e chiuso per successore. Infatti un tale $X$ appartiene alla famiglia $\ca F$ (quella che interviene nella definizione di $\omega$), ed essendone l'intersezione $\omega$ \`e incluso in ciascuno degli elementi di $\ca F$. Si pu\`o in effetti dimostrare un risultato pi\`u forte:
|
||
|
||
\br
|
||
L'insieme $\omega$ \`e incluso in qualsiasi classe $X$ che contiene $\emptyset$ ed \`e chiusa per successore. \er
|
||
\bp Sappiamo gi\`a che il risultato vale se $X$ \`e un insieme. Ci possiamo ricondurre a questo caso considerando $X' = X \cap \omega$. Anche $X'$ contiene $\emptyset$ ed \`e chiuso per successore, ed essendo incluso nell'insieme $\omega$ \`e un insieme per l'assioma di comprensione. Dunque per quanto visto $\omega \subseteq X'$, il che equivale a dire che $\omega \subseteq X$. \ep
|
||
|
||
\bt I numeri naturali di von Neumann sono un ``modello degli assiomi di Peano'', ovvero verificano le propriet\`a espresse dagli assiomi di Peano. \et
|
||
\bp Iniziamo con l'induzione. Sia $X \subseteq \omega$ un insieme che contiene $0$ ed \`e chiuso per successore. Essendo $\omega$ il pi\`u piccolo di tali insiemi, $X = \omega$.
|
||
Avendo verificato l'induzione, nel verificare gli altri assiomi possiamo procedere per induzione.
|
||
|
||
Il punto pi\`u delicato il seguente.
|
||
Supponiamo che $x,y$ abbiano lo stesso successore. Dobbiamo dimostrare che $x=y$. Innanzitutto dimostriamo, per induzione su $x\in \omega$, che $\bigcup (s(x) ) = x$, dove $s(x) = x \cup \{x\}$.
|
||
Il caso $x = \emptyset$ \`e immediato. Supponiamo dunque che $x=s(y)$ e che la tesi valga per $y$. Abbiamo $\bigcup(s(x)) = \bigcup(x \cup \{x\}) = \bigcup x \cup \bigcup(\{x\})$. Per ipotesi induttiva $\bigcup x = y$, mentre ovviamente $\bigcup(\{x\}) = x$. Dunque $\bigcup(s(x)) = y \cup x = y \cup s(y) = y \cup y \cup \{y\} = y \cup \{y\} = x$. Abbiamo cos\ii dimostrato che $\bigcup$ si comporta da predecessore.
|
||
Supponendo ora che $s(x) = s(y)$ otteniamo $\bigcup(s(x)) = \bigcup(s(y))$, e dunque $x=y$.
|
||
|
||
Resta da dimostrare che $0 = \emptyset$ \`e l'unico elemento di $\omega$ che non \`e un successore. Questo si dimostra per induzione applicata alla sequente propriet\`a $P(x)$: $x\neq 0 \to (\exists y\in \omega) (x=s(y))$. Per $x=0$ la propriet\`a $P$ vale ``a vuoto'', essendo la premessa dell'implicazione falsa. Chiaramente se la propriet\`a $P$ vale per $z$, essa vale per $s(z)$ (difatti la propriet\`a vale per $s(z)$ anche senza sfruttare l'ipotesi che valga per $z$). Quindi per induzione $P$ vale per ogni numero naturale.
|
||
\ep
|
||
|
||
Nel seguito scriveremo indifferentemente $\omega$ o $\N$ a meno che non ci siano specifiche ragioni di distinguere tra numeri naturali di von Neumann (per i quali useremo sempre $\omega$) e un generico modello degli assiomi di Peano.
|
||
|
||
%In seguito vedremo che anche i ``numeri ordinali'' si comportano per molti versi come i numeri naturali verificando una variante dell'assioma di induzione, dove per\`o il passo induttivo \`e pi\`u complicato per tener conto di quei numeri ordinali maggiori di zero che non hanno un predecessore (i cosiddetti ordinali limite).
|
||
|
||
\section{La relazione d'ordine sui numeri naturali}
|
||
Oltre ad uno zero e un successore, i numeri naturali hanno anche una
|
||
struttura d'ordine, ovvero dati due numeri naturali possiamo dire se uno \`e maggiore o minore dell'altro.
|
||
L'idea \`e che $x<y$ ($x$ \`e minore di $y$) se $y$ si pu\`o ottenere da $x$ applicando ``un certo numero di volte'' la funzione
|
||
successore. Diamo ora la definizione precisa (essa si applica a qualunque modello degli assiomi di Peano, non solo dunque ai numeri naturali di von Neumann).
|
||
|
||
\begin{definition} Definiamo una relazione $\leq$ sui numeri
|
||
naturali come segue: $x\leq y$ ($x$ \`e minore o uguale a $y$) se qualsiasi
|
||
sottoinsieme di $\N$ chiuso per successore e contenente $x$ contiene
|
||
necessariamente anche $y$. Se $x \leq y$ diciamo anche che $y$ \`e maggiore o uguale ad $x$, e scriviamo $y\geq x$.
|
||
I numeri maggiori o uguali ad $x$ costituiscono dunque il pi\`u piccolo insieme
|
||
chiuso per successore e contenente $x$.
|
||
Scriviamo $x<y$ ($x$ \`e strettamente minore di $y$)
|
||
se $x\leq y$ e $x\neq y$.
|
||
\end{definition}
|
||
|
||
\bexe \label{ordine} $\leq$ \`e una relazione d'ordine totale su $\N$,
|
||
cio\`e valgono le seguenti quattro propriet\`a:
|
||
\begin{enumerate}
|
||
\item $x\leq x$ (riflessivit\`a);
|
||
\item se $x\leq y$ e $y\leq z$ allora $x\leq z$ (transitivit\`a);
|
||
\item se $x\leq y$ e $y\leq x$ allora $x=y$ (antisimmetria);
|
||
\item dati due numeri naturali qualsiasi $x,y$ abbiamo $x\leq y$ oppure $y\leq x$ (totalit\`a).
|
||
\end{enumerate}
|
||
\eexe
|
||
%\begin{proof} Esercizio. \end{proof}
|
||
|
||
Nello svolgere l'esercizio il lettore \`e pregato di affidarsi esclusivamente alle definizioni, agli assiomi, e alle leggi della logica, senza fare affidamento sull'intuizione geometrica, ovvero l'intuizione che gli consente di immaginare i numeri naturali disposti lungo una retta e in cui ``maggiore di'' vuol dire ``sta a destra di'' (non \`e questa la definizione che abbiamo dato di minore). Il tentativo di bandire l'intuizione geometrica dai fondamenti della matematica \`e una delle costanti della filosofia della matematica del 1900; basti qui ricordare il nome di Bertrand Russell e gli intellettuali del ``circolo di Vienna'', tra cui Rudolf Carnap. Questa impostazione ha per\`o anche portato a degli eccessi (i ``Principia Mathematica'' di Russell) e, in tempi pi\`u recenti, a delle rivalutazioni dell'approccio intuitivo, per lo meno a livello didattico.
|
||
|
||
Come al solito definiamo $x<y$ come $x\leq y \land x\neq y$.
|
||
|
||
\bexe \label{successore} Per ogni $x\in \N$ abbiamo:
|
||
\begin{enumerate}
|
||
\item $0\leq x$.
|
||
\item $x<s(x)$.
|
||
\item Non vi \`e alcun alcun $z\in \N$ con $x<z<S(x)$.
|
||
\end{enumerate}
|
||
\eexe
|
||
|
||
\begin{lemma} \label{principio-del-minimo} Vale il {\bf principio del minimo}:
|
||
ogni insieme non vuoto $X$ di numeri naturali ha un minimo elemento, ovvero esiste un $n\in X$ tale che
|
||
per ogni $m\in X$ si ha $n\leq m$. \end{lemma}
|
||
\begin{proof} Supponiamo per assurdo che esista un
|
||
insieme non vuoto $X$ di numeri naturali senza un minimo elemento. Consideriamo
|
||
un tale ipotetico insieme $X$, e sia $Y$ l'insieme di quei numeri naturali che
|
||
sono strettamente minori di ogni elemento di $X$. Chiaramente $Y$ contiene lo
|
||
$0$. Inoltre se $Y$ contiene un numero $n$ deve contenere anche il suo
|
||
successore $S(n)$, altrimenti per il Lemma \ref{successore} $S(n)$ sarebbe il minimo di $X$ (non essendovi altri elementi tra $n$ e $S(n)$). Dunque in base
|
||
al principio di induzione $Y$ coincide con $\N$. Ma visto che $X$ \`e disgiunto
|
||
da $Y$, ne segue che $X$ \`e vuoto, contro le nostre ipotesi.
|
||
\end{proof}
|
||
|
||
\br (Induzione forte) Il principio del minimo giustifica le dimostrazioni per ``induzione forte'': per dimostrare che una proposizione $P$ vale per ogni numero naturale, basta riuscire a dimostrare, dato un generico $n$, il seguente {\em passo induttivo}: se $P(m)$ vale per tutti gli $m<n$, allora vale anche $P(n)$.
|
||
|
||
Si noti che se $n=0$ ci\`o equivale a dimostrare direttamente $P(0)$, quindi nell'induzione forte il caso base \`e incluso nel passo induttivo.
|
||
|
||
Per giustificare le dimostrazioni per induzione forte si ragiona per assurdo: supponendo di essere riusciti a dimostrare il passo induttivo, se $P$ non valesse per ogni $n$, ci sarebbe un minimo $n$ per cui non vale $P(n)$. Per ciascun $m<n$ deve dunque valere $P(m)$, ma allora per il passo induttivo vale anche $P(n)$, da cui l'assurdo.
|
||
\er
|
||
|
||
L'induzione (forte o normale) e il principio del minimo sono in effetti equivalenti: ci\`o che si pu\`o dimostrare con uno di questi procedimenti si pu\`o dimostrare con gli altri.
|
||
|
||
I lemmi precedenti valgono per qualsiasi modello degli assiomi di Peano, ma i numeri di von Neumann abbiamo delle propriet\`a in pi\`u, come le seguenti:
|
||
|
||
|
||
\bexe Dati $n,m\in \omega$, abbiamo $n<m$ secondo la definizione sopra datane, se e solo se $n\in m$. Ad esempio $3 \in 5 = \{0,1,2,3,4\}$. Inoltre ogni elemento di un numero naturale $n$ di von Neumann, \`e esso stesso un numero naturale di von Neumann. Dunque per ogni $n\in \omega$ sia ha $$n = \{x: x\in n\} = \{x\in \omega: x<n\}.$$ \eexe
|
||
|
||
|
||
\section{Relazioni e Funzioni}
|
||
%Gli insiemi della forma $\{a,b\}$, la cui esistenza \`e garantita dall'assioma della coppia, sono coppie ``non ordinate'', ovvero $\{a,b\} = \{b,a\}$. Vorremmo ora introdurre una nozione di coppia ordinata in cui abbia senso parlare di primo e secondo elemento. Ci\`o pu\`o essere fatto nel modo seguente.
|
||
\bd[Coppia di Kuratowksi] Dati due oggetti $a,b$ definiamo $(a,b)=\{\{a\},\{a,b\}\}$ e chiamiamo $(a,b)$ la coppia ordinata di $a$ e $b$. \ed
|
||
|
||
La propriet\`a fondamentale delle coppie ordinate \`e espressa dal seguente esercizio.
|
||
|
||
\bexe Se $(a,b) = (c,d)$ allora $a= b$ e $c = d$. \eexe
|
||
|
||
Si noti la differenza con la coppia non ordinata $\{a,b\}$. Ad esempio mentre $\{0,1\} = \{1,0\}$, abbiamo $(0,1) \neq (1,0)$. Nelle coppie ordinate ha senso parlare di primo e secondo elemento, ma nelle coppie non ordinate (quelle dell'assioma della coppia) tali nozioni non hanno senso.
|
||
Esistono altri modi di definire la coppia ordinata $(a,b)$ in modo che valga la propriet\`a fondamentale. Per i nostri scopi una vale l'altra.
|
||
|
||
\bd Date due classi $X$ ed $Y$ definiamo il loro prodotto cartesiano $X\times Y$ come la classe i cui elementi sono le coppie ordinate $(a,b)$ con $a\in X$ e $b\in Y$.
|
||
\ed
|
||
\br Per esprimere in formule la definizione sopra data si usa scrivere $$X \times Y = \{(a,b): a \in X \land b \in Y\}.$$ Notiamo tuttavia che per dimostrare formalmente che $X\times Y$ \`e una classe dovremmo trovare una definizione della forma $X\times Y = \{x: P(x)\}$ dove $x$ \`e una variabile e $P$ \`e una opportuna propriet\`a. A tal fine basta scrivere $$X\times Y = \{x : (\exists a \in X)(\exists b\in Y) \; x = (a,b)\},$$
|
||
dove la formula dopo i due punti esprime il fatto che $x$ \`e della forma $(a,b)$ con $a\in X$ e $b\in Y$.
|
||
\er
|
||
|
||
\bd Una relazione $R$ tra due classi $X$ ed $Y$ \`e una sottoclasse di $X\times Y$. Diremo che $a,b$ sono in relazione (rispetto ad $R$) se $(a,b) \in R$. Scriveremo anche $aRb$ oppure $R(a,b)$ per esprimere il fatto che $a,b$ sono in relazione. Se $X = Y$, ovvero $R\subseteq X \times X$, diremo che $R$ \`e una relazione binaria su $X$. \ed
|
||
|
||
\bd Una funzione $F$ da una classe $X$ ad una classe $Y$ \`e una relazione $F \subseteq X \times Y$ che gode delle seguenti propriet\`a: per ogni $x\in X$ esiste uno ed un solo $y\in Y$ tale che $(x,y) \in F$.
|
||
Useremo la notazione $F:X \to Y$ per esprimere il fatto che $F$ \`e una funzione da $X$ ad $Y$. Se $F:X\to Y$ ed $x\in X$, indichiamo con $F(x)$ l'unico oggetto $y\in Y$ tale che $(x,y)\in F$. Quindi $y = F(x)$ se e solo se $(x,y)\in F$.
|
||
La classe $X$ viene chiamata dominio di $F$ e la classe $Y$ il suo codominio. L'immagine di $F$ \`e la classe consistente degli oggetti della forma $F(x)$ con $x\in X$, ovvero la classe $\{y: (\exists x \in X)(y = F(x))\}$. Per indicare l'immagine di $F$ si usa anche la notazione $\{F(x): x \in X\}$, o pi\`u semplicemente $\im(F)$.
|
||
|
||
Diremo che $F$ \`e {\em iniettiva} se per per ogni $b$ nella sua immagine esiste uno ed un solo $x$ nel suo dominio tale che $F(x) = b$, ovvero da $F(x) = F(y)$ segue $x=y$. Diremo poi che $F$ \`e {\em surgettiva} se l'immagine coincide con il codominio, ed \`e {\em biunivoca} (o bigettiva) se \`e sia iniettiva che surgettiva, ovvero ad ogni elemento del codominio corrisponde uno ed un solo elemento del dominio.
|
||
\ed
|
||
|
||
Talvolta parleremo di funzioni senza specificare il dominio e il codominio. In questa accezione una funzione $F$ \`e semplicemente una classe di coppie ordinate tale che non vi sono due coppie in $F$ con la stessa prima componente e seconde componenti diverse. ll dominio di $F$ \`e la classe $\dom(F) = \{x: (\exists y) (x,y) \in F\}$ e la sua immagine \`e $\im(F) = \{y: (\exists x \in X)(y = F(x))\}$, mentre non ha molto senso parlare del codominio (pu\`o essere $V$, o $\im(F)$, o qualsiasi classe intermedia). Si noti che $F$ \`e sempre surgettiva se considerata come funzione da $\dom(F)$ a $\im(F)$, mentre pu\`o non esserla se cambiamo il codominio.
|
||
|
||
Analoghi discorsi valgono per le relazioni: se non specifichiamo il dominio e il codominio una relazione binaria $R$ non \`e altro che una classe di coppie ordinate e il dominio di $R$ \`e la classe degli $x\in V$ tali che esiste un $y\in V$ con $(x,y)\in R$.
|
||
|
||
\bd Data una funzione $F: X\to Y$ e una sottoclasse $Z\subseteq X$, la restrizione di $F$ a $Z$ \`e la funzione $F\rest{Z}: Z\to Y$ definita da $F\rest{Z} = F \cap (Z\times Y)$, ovvero l'insieme delle coppie di $F$ la cui prima componente \`e in $Z$. \ed
|
||
|
||
|
||
\br Date due funzioni $F,G$, l'intersezione $F\cap G$ \`e una funzione se e solo se $F$ e $G$ coincidono su $\dom(F) \cap \dom(G)$, nel senso che le rispettive restrizioni a questa intersezione coincidono. Ci\`o equivale a dire che $F(x) = G(x)$ per ogni $x\in \dom(F)\cap \dom(G)$. In generale, data una famiglia $\ca C$ di funzioni, l'unione $\bigcup \ca C$ \`e una funzione se prese comunque due funzioni in $\ca C$ esse coincidono sull'intersezione dei loro domini. Infatti \`e ovvio che $\bigcup \ca C$ \`e un insieme di coppie, e resta dunque solo da dimostrare che se $(x,y)$ ed $(x,y')$ sono entrambi in $\bigcup C$, allora $y=y'$. Ci\`o segue dal fatto che per definizione di unione $(x,y)$ appartiene ad una delle $F\in \ca C$ e $(x,y')$ ad una delle $G\in \ca C$ (senza escludere il caso $F=G$), e poich\'e che $F$ e $G$ coincidono sull'intersezione dei loro domini, dobbiamo avere $y=y'$. \er
|
||
|
||
Le funzioni si prestano a modellare il concetto di successione. In genere le successioni vengono indicate usando i puntini di sospensione $a_0,a_1,\ldots, a_n$, ma \`e pi\`u corretto dire che, dato $n\in \omega$, una successione $(a_i:i<n)$ di oggetti $a_i$, non \`e altro che la funzione con dominio $n = \{i:i<n\}$ che manda $i$ in $a_i$. Non dobbiamo confondere $(a_i: i<n)$, che \`e una funzione, con $\{a_i: i<n\}$, che \`e la sua immagine. Pi\`u in generale, dato un insieme di indici $I$, indichiamo con $(a_i:i\in I)$ la funzione da $I$ a $V$ che manda $i\in I$ in $a_i$, e con $\{a_i:i\in I\}$ l'immagine di tale funzione. In altre parole i sottoindici indicano l'applicazione di una funzione al suo argomento: $a_i$ \`e la funzione $a$ applicata ad $i$. Ogni insieme si pu\`o scrivere in molti modi come immagine di una funzione (basta ad esempio considerare la funzione identit\`a dall'insieme in se stesso), e pertanto, ove convenga, ogni insieme si pu\`o scrivere nella forma $\{a_i:i\in I\}$ per un certo insieme di indici $I$. Analoghi discorsi valgono per le classi.
|
||
|
||
\section{Assioma potenza e di rimpiazzamento}
|
||
|
||
\begin{axiom}[Assioma potenza] \label{potenza} Dato un insieme $X$, la classe $\parti (X) = \{Y: Y \subseteq X\}$ dei sottoinsiemi di $X$ \`e un insieme.
|
||
\end{axiom}
|
||
|
||
\begin{axiom}[Assioma di rimpiazzamento] Se $F: X \to Y$ \`e una funzione tra classi e il suo dominio $X$ \`e un insieme, allora la sua immagine $\im(F)$ \`e un insieme.
|
||
\end{axiom}
|
||
|
||
Come prima applicazione dell'assioma di rimpiazzamento dimostriamo la seguente proposizione.
|
||
|
||
\bprop Se $A$ ed $B$ sono insiemi, $A\times B$ \`e un insieme. \eprop
|
||
\begin{proof}
|
||
Fissato $b\in B$, per l'assioma di rimpiazzamento esiste l'insieme
|
||
$\{(a,b) \mid a\in A\}$, che non \`e altro che $A\times \{b\}$. Ancora per l'assioma di
|
||
rimpiazzamento esiste l'insieme $F = \{A\times \{b\} \mid b\in B\}$. Infine
|
||
per l'assioma dell'unione esiste l'insieme $\bigcup F =
|
||
\bigcup_{b\in B} A\times \{b\} = A \times B$. \end{proof}
|
||
|
||
La dimostrazione appena data funziona per qualunque definizione di $(a,b)$ che verifichi la propriet\`a fondamentale delle coppie ordinate.
|
||
Se utilizziamo le coppie di Kuratowski esiste una seconda dimostrazione che usa l'assioma potenza anzich\'e l'assioma di rimpiazzamento. Basta infatti osservare che
|
||
se $a\in A$ e $b\in B$, allora $\{a\}$ ed $\{a,b\}$ appartengono a $\parti(A\cup B)$ e quindi $(a,b) = \{\{a\},\{a,b\}\} \subseteq \parti (A\cup B)$, ovvero $(a,b) \in \parti \parti (A\cup B)$. Riassumendo abbiamo:
|
||
|
||
\br $A\times B \subseteq \parti \parti (A \cup B)$.\er
|
||
|
||
|
||
\bc Se $F: X \to Y $ \`e una funzione tra classi e $X$ \`e un insieme, allora $F$ \`e un insieme. \ec
|
||
\bp Per l'assioma di rimpiazzamento $\im(F)$ \`e un insieme, ed essendo $F$ inclusa nell'insieme $X \times \im(F)$, anche $F$ \`e un insieme. \ep
|
||
|
||
Il seguente risultato ha bisogno dell'assioma delle parti.
|
||
|
||
\bprop Se $X$ ed $Y$ sono insiemi, la classe $C$ di tutte le funzioni da $X$ ad $Y$ \`e un insieme. \eprop
|
||
\bp Se $f$ \`e una funzione da $X$ ad $Y$, allora $f$ \`e inclusa in $X\times Y$, e quindi $f\in \parti(X\times Y)$. Abbiamo quindi $C\subseteq \parti(X\times Y)$, da cui $C\in \parti \parti (X\times Y)$. \ep
|
||
|
||
\section{Definizioni ricorsive sui numeri naturali}
|
||
|
||
Consideriamo la funzione fattoriale. Essa viene normalmente definita per induzione, o meglio per ``ricursione'', come segue: $0! = 1$, $(n+1)! = (n+1) \cdot n!$. All'interno della teoria assiomatica degli insiemi questo genere di definizioni, in cui il valore di una funzione $f$ su un dato argomento $n$ viene definito utilizzando i valori della funzione stessa su alcuni argomenti ``precedenti'' \`e giustificato dal ``Teorema di Ricursione''. Nella sua forma pi\`u semplice detto teorema afferma che \`e possibile definire una funzione $f$ sui numeri naturali fornendo il valore di $f(0)$ e dando una
|
||
regola $H$ che permette di determinare $f(n+1)$ conoscendo $n$ ed $f(n)$.
|
||
Pi\`u formalmente abbiamo:
|
||
|
||
\bt \label{ricN} Sia $A$ una classe. Data una funzione $H\colon \omega\times A \to A$ ed un elemento $a\in A$, esiste una ed una sola funzione $f\colon \omega \to A$ tale che $f(0) = a$ ed $f(n+1) = H(n,f(n))$. \et
|
||
\bp
|
||
L'unicit\`a della $f$ \`e facile da dimostrare. Se infatti $g: \omega \to A$ verifica le stesse equazioni ricorsive della $f$, ovvero $g(0) = a$ e $g(n+1) = H(n,g(n))$, allora per induzione su $n$ si ottiene facilmente $f(n) = g(n)$ per ogni $n\in \omega$.
|
||
|
||
Prima di dimostrare l'esistenza ci occorre un risultato preliminare. Mostriamo, per induzione su $m\in \omega$, che esiste una ed una sola funzione $f$, con dominio $\{x\in \omega: x\leq m\}$, che verifica le equazioni $f(0) = a$ ed $f(n+1) = H(n,f(n))$ per ogni $n$ nel suo dominio.
|
||
Il caso $m=0$ \`e ovvio. Basta considerare la funzione $\{(0,a)\}$ (ovvero la funzione che manda $0$ in $a$). Supponendo per ipotesi induttiva che $f: \{x\in \omega: x\leq m\} \to A$ verifichi le equazioni (e sia l'unica che le verifichi), cerchiamo una funzione $g: \{x\in \omega: x\leq m+1\} \to A$ che verifichi le equazioni. Posto che $g$ esista, sugli elementi $x$ minori o uguali ad $m$ si deve necessariamente avere $g(x) = f(x)$ (per l'unicit\`a fino ad $m$). Resta da definire $g(m+1)$. Siccome vogliamo che $g(m+1) = H(m,g(m))$, e visto che dobbiamo avere $g(m) = f(m)$, occorre necessariamente porre $g(m+1) = H(m,f(m))$. Questo dimostra che se $g$ esiste \`e unica. Per mostrare che esiste, basta considerare la funzione $g = f\cup \{(m+1, H(m,f(m)))\}$, ovvero la funzione $g$ che coincide con $f$ sugli elementi $\leq m$ e manda $m+1$ in $H(m,f(m))$.
|
||
|
||
Avendo dimostrato che, per ogni $m$, esiste una ed una sola funzione $f: \{x\in \omega: x\leq m\} \to A$ che verifica le equazioni ricorsive, possiamo trovarne una definita su tutto $\omega$ come segue. Definiamo $F: \omega \to A$ ponendo $F(n) = f(n)$ dove $f$ \`e l'unica funzione che verifica le equazioni ricorsive fino ad $n$. Il ``dove'' che appare nella definizione di $F$ pu\`o essere esplicitato come segue: $F$ \`e la classe di tutte le coppie $(n,a)$ tali che esiste una $f:\{x: x\leq n\}\to A$ tale che $f(n) = a$ ed $f$ verifica le equazioni ricorsive fino ad $n$. La $F: \omega \to A$ cos\`i defnita \`e a priori una funzione classe, tuttavia visto che il suo dominio $\omega$ \`e un insieme, essa \`e un insieme per l'assioma di rimpiazzamento.\footnote{Se $A$ \`e un insieme non serve l'assioma di rimpiazzamento. In questo caso per dimostrare che $F$ \`e un insieme basta osservare che $F\subseteq \omega \times A$ e che se $A$ \`e un insieme $\omega\times A$ \`e un insieme.}
|
||
\ep
|
||
|
||
\begin{example}
|
||
Possiamo definire per induzione sul secondo argomento la somma di
|
||
numeri naturali nel modo seguente $$x+0 = x, \quad x + S(y) = S(x+y).$$ Per applicare il teorema di ricursione si fissa $x$ e si definisce per ricursione la funzione $f$ (che dipender\`a dal parametro $x$)
|
||
che manda $y$ in $x+y$. Basta porre $f(0) = x$ ed $f(S(n)) = S(f(n))$ (in questo caso la $H$ del Teorema \ref{ricN} applicata ad $n,f(n)$ fornisce in output $S(f(n))$, senza utilizzare $n$ stesso).
|
||
|
||
Avendo definito la somma possiamo definire il prodotto per induzione
|
||
sul secondo argomento nel modo seguente $$x\cdot 0 = 0, \quad x \cdot S(y) =
|
||
x\cdot y + x.$$
|
||
|
||
Analogamente avendo il prodotto possiamo definire per
|
||
induzione l'esponenziale: $$x^0 = 1, \quad x^{n+1} = x^n \cdot x.$$
|
||
|
||
Infine la funzione fattoriale: $0! = 1, \quad (n+1)! = n! \cdot (n+1)$.
|
||
\end{example}
|
||
|
||
\bexe Dati due numeri naturali $x,y$ con $x\leq y$, esiste uno ed un solo $z$ tale che $x+z =y$ e definiamo la sottrazione ponendo per definizione $y-x= z$. \eexe
|
||
|
||
|
||
\section{Ricursione forte}
|
||
|
||
Consideriamo ora un esempio differente:
|
||
|
||
\bexa La successione di Fibonacci $F: \omega \to \omega$ \`e definita da $F(0) = 1$, $F(1) = 1$, $F(n+2) = F(n+1) + F(n)$. \eexa
|
||
|
||
Per dimostrare l'esistenza e l'unicit\`a della funzione di Fibonacci il Teorema \ref{ricN} non basta e abbiamo bisogno di un risultato pi\`u generale che ci consente di definire funzioni $f$ tali che $f(n)$ dipenda da pi\`u valori precedenti (nel caso di Fibonacci da due valori precedenti). In generale possiamo ammettere che $f(n)$ dipenda dall''intera successione $(f(i):i< n)$ dei valori precedenti. Visto che tale successione non \`e altro che la restrizione di $f$ all'insieme $\{i: i< n\}$, la definizione di $f$ prende la forma $f(n) = H(n,f\rest{\{i: i<n\}})$. In particolare per $n=0$ abbiamo $f(0) = H(0,\emptyset)$, quindi non abbiamo bisogno di specificare separatamente il valore di $f(0)$.
|
||
|
||
\bt Sia $A$ una classe. Data una funzione $H\colon \omega\times V \to A$, esiste una ed una sola funzione $f\colon \omega \to A$ tale che $$f(n) = H(n,f\rest{\{i: i<n\}})$$ per ogni $n \in \omega$. \et
|
||
Notiamo che il secondo argomento di $H$ \`e una funzione $f\rest{\{i: i<n\}}$ da $n$ ad $A$, dove $n$ pu\`o variare. Quindi in generale $H$ riceve come secondo argomento una funzione da qualche $n\in \omega$ ad $A$. Per non stare a specificare con esattezza, per semplicit\`a abbiamo assunto che $H$ sia una funzione con dominio $\omega \times V$.
|
||
|
||
\bp In seguito dimostreremo un risultato ancora pi\`u generale. Diamo comunque un cenno di dimostrazione.
|
||
Diciamo che una funzione $g$ \`e buona se esiste $m\in \omega$ tale che $\dom(g) = m$ e $g$ verifica l'equazione ricorsiva
|
||
$$g(n) = H(n,g\rest{\{i: i<n\}})$$
|
||
per ogni $n\in \dom(g)$. Per induzione si dimostra che per ogni $m$ esiste una ed una sola funzione buona con dominio $m$. In effetti se abbiamo una funzione buona con dominio $m$ l'equazione ricorsiva permette di estenderla ad $m+1$ in quanto ci fornisce una regola per calcolare il suo valore su $m+1$ a partire dai valori precedenti. Definiamo ora $f$ come l'unione di tutte le funzioni buone. Lasciamo al lettore la verifica che $f$ \`e una funzione da $\omega$ ad $A$ e verifica l'equazione ricorsiva. Si ricordi che per dimostrare che un'unione di funzioni \`e una funzione occorre dimostrare che a due a due esse coincidono nel loro dominio comune (l'intersezione dei due domini), ma questo \`e facile per la parte sull'unicit\`a.
|
||
\ep
|
||
|
||
|
||
\section{Unicit\`a a meno di isomorfismo dei numeri naturali}
|
||
Abbiamo visto che i numeri naturali di von Neumann sono un modello degli assiomi di Peano ma potrebbero essercene altri, ad esempio quello ottenuto definendo lo zero come $\emptyset$ e il successore di $x$ come $\{x\}$.
|
||
|
||
\bt Sia $(N',S',0')$ un modello degli assiomi di Peano, non necessariamente uguale al modello $(\omega, S,0)$ dei numeri naturali di von Neumann. Allora esiste una funzione biunivoca $h: \omega \to N'$. \et
|
||
|
||
\bp Definiamo per ricursione $h: \omega \to N'$ ponendo $h(0) = 0'$ e $h(S(n)) = S'(h(n))$. \`E facile dimostrare, ragionando per induzione, che $h$ \`e crescente, e quindi iniettiva. Per dimostrare che \`e surgettiva si consideri la sua immagine $\im(h) \subseteq N'$. Essa contiene $0'$ ed \`e ovviamente chiusa per $S'$, in quanto se $y = h(n)$, allora $S'(y) = h(S(n))$. Ne segue, per induzione in $(N',S',0')$ (che ci \`e data dagli assiomi di Peano), che $\im(h) = N'$. \ep
|
||
|
||
Si noti che la $h$ definita nella dimostrazione non solo \`e biunivoca, ma \`e un ``isomorfismo'' tra $(\omega,S,0)$ ed $(N',S',0')$, ovvero manda $0$ in $0'$ e preserva il successore, nel senso che se $m=S(n)$, allora $h(m) = S'(h(n))$.
|
||
|
||
In generale tutte le strutture matematiche sono sempre studiate ``a meno di isomorfismo''. Data una teoria assiomatica, essa non potr\`a mai avere un solo modello, in quanto insieme ad esso vi saranno tutti i modelli a lui isomorfi. Gli assiomi possono solo determinare i rapporti reciproci tra gli elementi del modello, ma non la natura degli elementi isolatamente presi, che quindi possono essere rimpiazzati con altri elementi mantenendo i rapporti reciproci (e in ci\`o consistono gli isomorfismi).
|
||
|
||
\section{Assioma della scelta}
|
||
L'assioma della scelta ha segnato la nascita della teoria assiomatica degli insiemi in due lavori di Zermelo del 1904 e del 1908. Inizialmente esso \`e stato accolto con grande scetticismo, ma oggi \`e accettato senza riserve dalla quasi totalit\`a dei matematici.
|
||
|
||
\begin{axiom}[Assioma della scelta] Dato un insieme $X$ i cui elementi sono insiemi non vuoti a due a due disgiunti, esiste un insieme $S$ che interseca ciascuno degli elementi di $X$ in un singolo elemento. \end{axiom}
|
||
|
||
La motivazione per l'assioma \`e chiara: se gli insiemi della famiglia $X$ sono non vuoti, possiamo immaginare di scegliere idealmente un elemento in ciascun di loro per formare l'insieme $S$. L'assioma della scelta ha varie versioni equivalenti:
|
||
|
||
\begin{axiom}[Assioma della scelta, forma equivalente] \label{ac2} Data una famiglia $(X_i: i \in I)$ di insiemi non vuoti $X_i$, esiste una funzione $f$ che associa a ciascun $i\in I$ un elemento $f(i)$ di $X_i$. \end{axiom}
|
||
|
||
Per dedurre questa seconda forma a partire dalla prima basta considerare gli insiemi disgiunti $X_i\times \{i\}$. Per la prima versione dell'assioma esiste un insieme $S$ che interseca ciascun $X_i \times \{i\}$ in un singolo punto $(a,i) \in X_i\times \{i\}$, ed \`e quindi sufficiente considerare la funzione $f$ che manda $i$ nell'unico $a$ tale che $(a,i) \in S$.
|
||
|
||
Nella formulazione appena data si ammette la possiblit\`a che $f(i) \neq f(j)$ anche nei casi in cui $X_i = X_j$. Se insistiamo che la scelta dipenda solo dall'insieme $X_i$ e non dall'indice $i$, otteniamo la seguente versione che si dimostra equivalente alle precedenti:
|
||
|
||
\begin{axiom}[Assioma della scelta, forma equivalente] \label{ac2'} Data una famiglia $\ca F$ di insiemi non vuoti, esiste una funzione $g$ che associa a ciascun $X\in \ca F$ un elemento $g(X)\in X$. In particolare, fissato un insieme non vuoto $A$, possiamo considerare la famiglia $\ca F = \parti (A) \setminus \{\emptyset\}$ di tutti i sottoinsiemi non vuoti di $X$ ottenendo una funzione $g: \parti (A) \setminus \{\emptyset\} \to A$ che associa a ciascun sottoinsieme non vuoto $X\subseteq A$ un elemento $g(A)\in A$.
|
||
\end{axiom}
|
||
|
||
In molti casi l'esistenza della funzione di scelta $g$ pu\`o essere dimostrata senza far ricorso all'assioma della scelta. Supponiamo ad esempio di prendere $A = \N$. In questo caso non serve l'assioma della scelta per mostrare l'esistenza di una funzione $g: \parti(\N)\setminus \{\emptyset\} \to \N$ tale che $g(X)\in X$ per ogni sottoinsieme non vuoto $X$ di $\N$. Basta infatti definire $g(X)$ come il minimo elemento di $X$ rispetto all'ordine $\leq$ di $\N$. Se per\`o tentiamo di dimostrare l'esistenza di una funzione di scelta per i sottoinsiemi dell'insieme $\R$ dei numeri reali (che in seguito definiremo all'interno della teoria degli insiemi), ci rendiamo subito conto che la cosa non \`e cos\`{\i} semplice. Vorremmo una funzione $g$ che dato un insieme non vuoto $X \subseteq \R$ restituisca un elemento $g(X)\in X$. Se $X$ \`e di una forma particolare, ad esempio un intervallo aperto con estremi $a,b\in \R$, basta prendere il punto di mezzo $\frac {a+b} 2$, ma non essendo possibile dare una regola che funzioni per tutti gli $X$, l'unico modo per dimostrare l'esistenza della $g$ \`e usare l'assioma della scelta.
|
||
|
||
L'assioma della scelta \`e spesso usato per passare da una situazione in cui i quantificatori sono disposti nell'ordine $\forall \exists$, ad una in cui sono disposti nell'ordine $\exists \forall$, come nella formulazione seguente.
|
||
|
||
\begin{axiom}[Assioma della scelta, altra forma equivalente] \label{ac3}
|
||
Siano $X,Y$ due insiemi e sia $R\subseteq X\times Y$ una relazione tra $X$ ed $Y$. Supponiamo che $$(\forall x \in X)(\exists y \in Y) R(x,y).$$ Allora esiste $f:X\to Y$ tale che $(\forall x\in X) R(x,f(x))$. \end{axiom}
|
||
|
||
Detto in altre parole l'assioma asserisce che ogni relazione $R$ include una funzione $f$ con lo stesso dominio.
|
||
Si noti che dato $x\in X$ ci possono in genere essere molti $y \in Y$ con $xRy$. La funzione $f$ sceglie uno dei tanti $y$ in funzione di $x$. In generale non esiste un'unica funzione di scelta (a meno che la relazione $R$ sia essa stessa una funzione). L'assioma di scelta asserisce che ne esiste almeno una, e sapendo che esiste sta poi a noi ``sceglierne'' una, dove questo secondo passaggio pu\`o essere fatto in base alle leggi della logica.
|
||
%La formulazione \ref{ac3} rende esplicito il fatto che l'assioma della scelta consente uno scambio di quantificatori: da $\forall x \exists y R(x,y)$ a $\exists f \forall x R(x,f(x))$.
|
||
|
||
Per dedurre la \ref{ac3} dalla \ref{ac2} basta considerare, per ciascun $x\in X$, l'insieme $Y_x = \{y: R(x,y)\}$. Otteniamo in tal modo una famiglia $(Y_x: x\in X)$ di insiemi non vuoti e possiamo considerare una funzione $f$ che associa a ciascun $x\in X$ un elemento di $Y_x$.
|
||
%In certe assiomatizzazioni esiste una forma pi\`u forte dell'assioma della scelta (detta scelta globale) in cui si ammette il caso in cui $X$ ed $Y$ siano classi ed $f$ \`e una funzione classe.
|
||
\bd Data una famiglia di insiemi $(X_i: i \in I)$ (vista come funzione che manda $i\in I$ in $X_i$) definiamo il prodotto cartesiano $\Pi_{i\in I}X_i$ come l'insieme di tutte le funzioni $a: I \to \bigcup_{i\in I} X_i$ tali che per ogni $i\in I$, $a(i) \in X_i$. Ogni elemento $a\in \Pi_{i\in I}X_i$ \`e pertanto una ``$I$-upla'' $(a(i): i\in I)$ la cui $i$-esima coordinata \`e $a(i)$. \ed
|
||
|
||
Il fatto che di tali $I$-uple ne esista almeno una \`e dato dalla \ref{ac2}. Otteniamo pertanto il seguente:
|
||
|
||
\br L'assioma della scelta equivale al seguente enunciato: per ogni famiglia $(X_i:i\in I)$ di insiemi non-vuoti, il prodotto cartesiano $\Pi_{i\in I}X_i$ \`e non vuoto. \er
|
||
|
||
Anche il seguente enunciato equivale all'assioma della scelta.
|
||
|
||
\bl \label{destra}<EFBFBD>Data una funzione surgettiva $f: X \to Y$ tra due insiemi, esiste una funzione iniettiva $g: Y \to X$ tale che $f(g(y)) = y$ per ogni $y\in Y$ (diciamo che $g$ \`e una inversa destra di $f$).
|
||
\el
|
||
\bp Dato $y\in Y$ consideriamo l'insieme non vuoto $X_y = \{x\in X: f(x) = y\}$. Per l'assioma della scelta esiste una funzione $g$ che associa a ciascun $y\in Y$ un elemento di $X_y$. \ep
|
||
|
||
Lasciamo al lettore la verifica dell'altro verso dell'equivalenza.
|
||
|
||
\section{Numeri cardinali (nel senso di Frege)}
|
||
|
||
\bd \label{card}
|
||
Dati due insiemi $X$ e $Y$, scriviamo $|X| = |Y|$ se esiste un funzione biunivoca da $X$ ad $Y$, e diciamo in tal caso che $X$ \`e {\em equipotente} ad $Y$, o che ha la stessa cardinalit\`a di $Y$. Scriviamo $|X| \leq |Y|$ se esiste una funzione iniettiva da $X$ ad $Y$, o equivalentemente se $X$ \`e equipotente ad un sottoinsieme di $Y$. Infine scriviamo $|X|<|Y|$ se vale $|X|\leq |Y|$ ma $|X|\neq |Y|$, ovvero esiste una funzione iniettiva da $X$ ad $Y$ ma non ne esiste una, possibilmente diversa, che sia biunivoca. \ed
|
||
|
||
L'uso delle notazioni $\leq$ e $<$ non \`e ancora pienamente giustificato in quanto dovremo dimostrare, per le relazioni appena definite, le propriet\`a degli ordini. La propriet\`a riflessiva $|X|\leq |X|$ e quella transitiva $|X|\leq |Y| \land |Y| \leq |Z| \to |X| \leq |Z|$, sono di facile verifica. Nel seguito dimostreremo la propriet\`a antisimmetrica $|X| \leq |Y| \land |Y| \leq |X| \to |X| = |Y|$ (Teorema di Cantor-Bernstein), e la totalit\`a, ovvero il fatto che vale sempre una delle due alternative $|X|\leq |Y|$ o $|Y|\leq |X|$ (Corollario \ref{Card-tot}). Fino a che non le avremo dimostrate non potremo dunque usare queste ultime propriet\`a.
|
||
|
||
\br Un insieme $X$ pu\`o essere equipotente ad un suo sottoinsieme proprio. Ad esempio l'insieme dei numeri naturali \`e equipotente all'insieme dei numeri pari. \er
|
||
|
||
Osserviamo che nella Definizione \ref{card} non abbiamo definito $|X|$, ma solo uguaglianze e disuguaglianze che coinvolgono tale notazione, quindi il segno di $=$ che compare nella definizione di $|X|=|Y|$ \`e per il momento solo un abuso di notazione.
|
||
|
||
\bd (Cardinali di Frege)
|
||
Seguendo Frege possiamo definire $|X|$ come la classe i cui elementi sono gli insiemi equipotenti ad $X$. Chiamiamo $|X|$ la cardinalit\`a di $X$ (nel senso di Frege). In questo modo $|X| = |Y|$ nel senso della Definizione \ref{card}, se effettivamente $|X|$ ed $|Y|$ sono uguali come classi, ovvero hanno gli stessi elementi. Questo giustifica l'uso del simbolo di uguaglianza. Per quanto riguarda il $\leq$, possiamo mantenere la Definizione \ref{card}, ma per mostrare che la definizione \`e ben posta occorre mostrare che se $|X|=|X'|$ e $|X|\leq |Y|$ allora $|X'|\leq |Y|$ (altrimenti $|X|\leq |Y|$ esprimerebbe solo un rapporto tra $X$ ed $Y$, e non tra $|X|$ e $|Y|$). Lasciamo al lettore le facili verifiche. \ed
|
||
|
||
Osserviamo che, nella definizione di Frege, $|X|$ risulta una classe propria e non un insieme. Questo comporta certi svantaggi: ad esempio la collezione dei cardinali minori di un dato cardinale $|X|$ risulterebbe una ``iperclasse'' i cui elementi sono classi (anche se $X$ avesse un numero finito di elementi!).
|
||
Nel seguito daremo una definizione alternativa della cardinalit\`a di un insieme dovuta a von Neumann, in modo che $|X|$ risulti sempre un insieme, ma continuino a valere le propriet\`a espresse dalla \ref{card}. Per il momento useremo solo le propriet\`a espresse dalla \ref{card} e quindi sar\`a indifferente quale definizione usare.
|
||
|
||
\bt \label{surg} $|Y| \leq |X|$ se e solo se $Y$ \`e vuoto o esiste una funzione surgettiva $f$ da $X$ ad $Y$. \et
|
||
|
||
\bp[Dimostrazione del Teorema \ref{surg}]
|
||
Un verso richiede l'assioma della scelta: se esiste una funzione surgettiva da $X$ ad $Y$ per l'assioma della scelta ne esiste una iniettiva nel verso opposto (Lemma \ref{destra}), e dunque $|Y| \leq |X|$.
|
||
|
||
Per l'altro verso assumiamo $|Y| \leq |X|$. Per definizione esiste dunque una funzione iniettiva $g: Y \to X$. Assumendo che $Y$ non sia vuoto, fissiamo un $a\in Y$ e definiamo una funzione $f: X \to Y$ ponendo $f(y) = a$ se $y$ non \`e nell'immagine di $f$, e $f(y) = x$ se $y=g(x)$. La defizione \`e ben posta in quanto, per l'iniettivit\`a di $g$, ci\`o pu\`o capitare per un solo $x$. Abbiamo cos\ii ottenuto una $f:X\to Y$ surgettiva.\footnote{La possibili\`a di ``scegliere'' $a$ non richiede l'assioma della scelta, ma fa parte delle leggi logiche: se so che $\exists y (y\in Y)$ posso immaginare di ``scegliere'' un tale $y$ e dargli un nome.} \ep
|
||
|
||
\section{Teorema di Cantor-Bernstein}
|
||
Nel prossimo teorema verifichiamo la propriet\`a antisimmetrica del $\leq$ tra cardinali.
|
||
|
||
\begin{theorem}
|
||
Se due insiemi sono ciascuno in corrispondenza biunivoca con
|
||
una parte dell'altro, allora si pu\`o trovare una corrispondenza biunivoca tra i
|
||
due. In altre parole se $|A| \leq |B|$ e $|B| \leq |A|$, allora $|A| = |B|$. \end{theorem}
|
||
|
||
\begin{proof} Siano $f \colon A \to B$ e $g\colon B\to A$ funzioni
|
||
iniettive. Definiamo induttivamente $A_0 = A$, $B_0 = B$, $A_{n+1} =
|
||
g(B_n)$ ($=$ l'immagine di $g$ ristretta a $B_n$), $B_{n+1} =
|
||
f(A_n)$. Otteniamo in tal modo due successioni decrescenti $$A = A_0 \supseteq A_1 \supseteq A_2 \ldots,$$ $$B = B_0 \supseteq B_1 \supseteq B_2 \ldots$$ come si verifica facilmente per induzione (se decrescono fino ad $n$ decrescono anche al passo successivo). Si vede facilmente (posponiamo per il momento le verifiche) che per ogni $n$ la differenza $A_{2n} \setminus A_{2n+1}$ \`e in corrispondenza biunivoca, tramite $f$, con $B_{2n+1} \setminus B_{2n+2}$, e analogamente $B_{2n} \setminus B_{2n+1}$ \`e in corrispondenza biunivoca, tramite $g$, con $A_{2n+1} \setminus A_{2n+2}$. Mettendo insieme queste corrispondenze biunivoche ne otteniamo una da $\bigcup_n (A_n \setminus A_{n+1})$ a $\bigcup_n (B_n \setminus B_{n+1})$. Rimangono da gestire gli eventuali punti di $A$ e $B$ che non appartengono a queste unioni, ovvero i punti di $A_\infty = \bigcap_{n\in \omega}A_n$ e $B_\infty = \bigcap_{n\in \omega} B_n$.
|
||
Si verifica per\`o facilmente che la restrizione di $f$ a $A_\infty$ \`e una funzione biunivoca verso $B_\infty$ (e similmente $g$ \`e una corrispondenza biunivoca da $B_\infty$ in $A_\infty$). Otteniamo in tal modo una corrispondenza biunivoca da $A$ a $B$ definita per casi.
|
||
|
||
Veniamo ai dettagli: siccome $f$ \`e iniettiva e $B_{i+1}$ \`e l'immagine tramite $f$ di $A_i$, abbiamo $x\in A_i \iff x \in B_{i+1}$, e quindi in particolare $x\in A_{2n}\iff f(x) \in B_{2n+1}$. Similmente $x\nin A_{2n+1}\iff x\nin B_{2n+2} $. Quindi $f$ manda $A_{2n}\setminus A_{2n+1}$ biunivocamente in $B_{2n+1} \setminus B_{2n+2}$. Similmente $g$ manda $B_{2n} \setminus B_{2n+1}$ biunivocamente in $A_{2n+1} \setminus A_{2n+2}$.
|
||
|
||
Se ora $x\in A_{\infty}$ e per assurdo $f(x)\nin B_\infty$, dovremmo avere $f(x)\nin B_n$ per qualche $n>0$ e quindi $x\nin A_{n-1}$, il che \`e assurdo in quanto $x\in A_{\infty}$.
|
||
|
||
Per mostrare che $f: A_\infty \to B_\infty$ \`e surgettiva, consideriamo un $y\in B_\infty$ e sia $x\in A$ tale che $f(x)=y$. Tale $x$ esiste in quanto $B_\infty \subseteq B_1 = f(A_0)$. Basta dunque mostrare che $x\in A_\infty$. Se cos\`{\i} non fosse, $x\nin A_n$ per qualche $n$, e otteniamo la contraddizione $y = f(x) \nin B_{n+1}$. La surgettivit\`a di $g$ si dimostra analogamente.
|
||
\end{proof}
|
||
|
||
Usando il teorema di Cantor-Bernstein si dimostra:
|
||
|
||
\bc
|
||
Se in una successione finita di disuguaglianze $|A_1|\leq |A_2| \leq
|
||
\ldots \leq |A_n|$ abbiamo $|A_n| = |A_1|$, allora tutti gli $A_i$
|
||
hanno la stessa cardinalit\`a. \ec
|
||
|
||
\bc
|
||
Se in una successione finita di disuguaglianze $|A_1|\leq |A_2| \leq
|
||
\ldots \leq |A_n|$ c'\`e almeno una disuguaglianza stretta, allora
|
||
$|A_1| < |A_n|$. \ec
|
||
\bp Chiaramente $|A_1|\leq |A_n|$ e se avessimo $|A_1| = |A_n|$ per l'esercizio precedente tutti gli $A_i$ avrebbero la stessa cardinalit\`a. \ep
|
||
|
||
Anche se ancora non abbiamo definito i numeri reali, propongo il seguente esercizio a chi li conosca gi\`a. Esso pu\`o essere risolto utilizzando il teorema di Cantor-Bernstein.
|
||
|
||
\bexe Si trovi una corrispondenza biunivoca tra un invervallo aperto e un intervallo chiuso dei numeri reali. \eexe
|
||
|
||
\section{Insiemi finiti e numerabili}
|
||
|
||
\bd Un insieme $X$ \`e finito se esiste $n\in \omega$ e una funzione biunivoca $f$ da $n$ ad $X$, ovvero $|n| = |X|$ (ricordiamo che $n= \{i:i<n\}$). \ed
|
||
|
||
\bexe \label{Ufin} Dati $m,n\in \omega$, se $X$ ed $Y$ sono insiemi finiti disgiunti equipotenti ad $m$ ed $n$ rispettivamente, allora $X\cup Y$ \`e equipotente ad $m+n$. \eexe
|
||
|
||
Per risolvere l'esercizio si ricordi che $m+n$ \`e stato definito per ricursione sul secondo argomento. Si dovr\`a quindi procedere per induzione su $n$.
|
||
|
||
\bexe Se $X$ ed $Y$ sono insiemi finiti equipotenti ad $m$ ed $n$ rispettivamente, allora $X\times Y$ \`e equipotente ad $m\cdot n$. \eexe
|
||
|
||
\bl Se $X$ \`e finito lo sono anche tutti i sottoinsiemi di $X$. \el
|
||
\bp L'ipotesi dice che $|X| = |n|$ per un certo $n\in \omega$. Posso quindi assumere $X = n$ e considero un sottoinsieme $Y$ di $n = \{i:i<n\}$. Ragiono per induzione su $n$. Il caso $n=0$ \`e ovvio. Considero il caso $n=m+1$. Per ipotesi induttiva $Y\cap m$ \`e finito. Dunque anche $Y$ \`e finito in quanto si ottiene da $Y\cap m$ aggiungendo al pi\`u un elemento (e posso quindi usare \ref{Ufin}). \ep
|
||
|
||
In modo simile si dimostra:
|
||
|
||
\bexe Se $X$ \`e finito ed \`e equipotente ad $n$, allora per ogni $Y\subseteq X$ esiste $n'\leq n$ tale che $Y$ \`e equipotente ad $n'$. \eexe
|
||
|
||
\bl Se $X$ \`e equipotente a $n\in \omega$ e $Y$ \`e un sottoinsieme proprio di $X$, allora $Y$ \`e equipotente a qualche $n'<n$. \el
|
||
\bp Possiamo assumere che $X = n$ e $Y$ sia un sottoinsieme proprio di $n$. Dimostriamo il nostro asserto per induzione su $n$. Se $n=0$ la tesi vale a vuoto in quanto $0$ non ha sottoinsiemi propri. Supponiamo dunque che $n=m+1$. Ci sono due casi. Se $Y = m$ non c'\`e nulla da dimostrare: la funzione identit\`a \`e la bigezione cercata. Se invece $Y\neq m$, allora $Y \cap m$ \`e un sottoinsieme proprio di $m$. In questo secondo caso per ipotesi induttiva $Y\cap m$ \`e equipotente a qualche $m'<m$. Ma $Y$ si ottiene da $Y\cap m$ aggiungendo al pi\`u un elemento, e dunque $Y$ \`e equipotente ad $m'$ o ad $m'+1$, che in entrambi i casi \`e $<m+1$. \ep
|
||
|
||
Il seguente risultato \`e il cosiddetto ``principio dei cassetti'', o della piccionaia. Se $m<n$ e mettiamo $n$ oggetti in $m$ cassetti, almeno un cassetto deve contenere pi\`u di un oggetto.
|
||
|
||
\bl Se $X$ \`e finito e $Y$ \`e un sottoinsieme proprio di $X$, allora $|Y|<|X|$.
|
||
\el
|
||
\bp
|
||
Alla luce del precedente risultato basta mostrare che se $m<n$ sono due elementi di $\omega$, allora non esiste una bigezione da $n$ ad $m$. Consideriamo per assurdo una tale bigezione $f: n \to m$. A meno di comporre $f$ con una permutazione di due elementi di $m$ con $f(m-1)$) possiamo supporre che $f$ mandi il massimo di $n$ nel massimo di $m$ (altrimenti ci riduciamo a questo caso scambiando di posto $f(m-1)$ con $m-1$). Togliendo i massimi di $n$ ed $m$ ci si riconduce al caso $n-1$ e si conclude per induzione.
|
||
\ep
|
||
|
||
Grazie al principio dei cassetti, dato un insieme finito $X$, esiste un unico $n\in \omega$ in corrispondenza biunivoca con $X$, che possiamo chiamare ``il numero degli elementi di $X$''.
|
||
|
||
\bd Un insieme $X$ \`e numerabile se esiste una funzione biunivoca da $X$ all'insieme $\omega$ dei numeri naturali. \ed
|
||
|
||
La cardinalit\`a di un insieme numerabile viene indicata con il simbolo $\aleph_0$. Quindi $|\omega| = \aleph_0$.
|
||
|
||
Per gli insiemi infiniti non vale il principio dei cassetti:
|
||
|
||
\br Esistono sottoinsiemi propri di $\omega$ che hanno la stessa cardinalit\`a di $\omega$, ad esempio i numeri pari. \er
|
||
|
||
\bexe Se $|X| \leq \aleph_0$, allora $X$ \`e finito o numerabile. \eexe
|
||
|
||
\bl $\omega \times \omega$ \`e numerabile. \el
|
||
\bp Ordiniamo $\omega \times \omega$ ponendo $(x',y') < (x,y)$ se $\max\{x',y'\} < \max\{x,y\}$ oppure i massimi sono uguali e $y'<y$, oppure i massimi e le seconde componenti sono uguali e $x'<x$. In quest'ordine si vede facilmente l'insieme delle coppie strettamente minori di $(x,y)$ \`e finito, e per la precisione, posto $n=\max\{x,y\}$, esso \`e equipotente ad $n\cdot n + x$ se $x<y$, o ad $n\cdot n + x+y$ se $x\geq y$. Associando a $(x,y)$ questo valore, otteniamo una corrispondenza biunivoca da $\omega \times \omega$ ad $\omega$. \ep
|
||
|
||
Ci sono molte altre corrispondenze biunivoche che possono darsi da $\omega\times \omega$ ad $\omega$. Quella sopra proposta ha il vantaggio di potersi generalizzare con facilit\`a agli ``ordinali iniziali'' che vedremo nel seguito.
|
||
|
||
\bexe L'unione e l'intersezione di due insiemi numerabili \`e numerabile. Il prodotto cartesiano di due insiemi numerabili \`e numerabile. In particolare $\omega \times \omega$ \`e numerabile. \eexe
|
||
|
||
In generale il seguente risultato ha bisogno dell'assioma della scelta.
|
||
|
||
\begin{theorem}
|
||
Un'unione numerabile di insiemi di cardinalit\`a $\leq \aleph_0$ ha
|
||
cardinalit\`a $\leq \aleph_0$.
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Per ogni $n\in \omega$ sia $A_n$ un insieme di cardinalit\`a $\leq
|
||
\aleph_0$. Dobbiamo mostrare che l'unione $\bigcup_{n\in \omega}A_n$ ha
|
||
cardinalit\`a $\leq \aleph_0$. Scegliamo, per ogni $n$, una funzione
|
||
surgettiva $f_n \colon \omega \to A_n$ (che esiste in quanto $|A_n| \leq \aleph_0$). Consideriamo la funzione $f\colon
|
||
\omega \times \omega \to \bigcup_n A_n$ che manda $(n,m)$ inf
|
||
$f_n(m)$. Chiaramente $f$ \`e surgettiva, e poich\'e $|\omega\times
|
||
\omega|=\aleph_0$ ne concludiamo che $|\bigcup_n A_n| \leq \aleph_0$.
|
||
\end{proof}
|
||
|
||
Osserviamo che la funzione $f\colon \omega \times \omega \to \bigcup_n A_n$ dipende dall'intera successione $(f_n: n\in \omega)$, per dimostrare l'esistenza della quale \`e in generale necessario l'assioma della scelta. La situazione \`e la seguente. Il fatto che, per ogni $n$, esista una funzione surgettiva $g:\omega \to A_n$ non richiede la scelta (in quanto segue dall'ipotesi che $A_n$ \`e numerabile). Tuttavia l'assioma della scelta viene usato per dimostrare l'esistenza della successione $(f_n: n\in \omega)$, vista come funzione che associa ad ogni $n\in \omega$ una funzione surgettiva $f_n: \omega \to A_n$.
|
||
Naturalmente se abbiamo maggiori informazioni sugli $A_n$ (come spesso accade nei casi concreti), possiamo essere in grado di definire la successione $(f_n: n \in \omega)$ senza utilizzare l'assioma della scelta.
|
||
|
||
Anche per il seguente teorema abbiamo bisogno dell'assioma della scelta.
|
||
|
||
\begin{theorem} \label{minimo-infinito}
|
||
Ogni insieme infinito $A$ ha un sottoinsieme numerabile. Quindi
|
||
$\aleph_0$ \`e minore o uguale di ogni altro cardinale
|
||
infinito. \end{theorem}
|
||
\begin{proof}
|
||
Possiamo definiamo induttivamente (grazie al teorema di ricursione) una successione $(a_n \mid n \in \omega)$
|
||
prendendo come $a_0$ un qualsiasi elemento di $A$, e ``scegliendo''
|
||
come $a_{n+1}$ un elemento dell'insieme non vuoto $A\setminus \{a_i
|
||
\mid i \leq n\}$. Si noti che l'insieme \`e effettivamente non vuoto altrimenti $A$ sarebbe finito.
|
||
Per formalizzare la dimostrazione possiamo supporre
|
||
che $a_{n+1}$ sia l'elemento dell'insieme $A\setminus \{a_i
|
||
\mid i \leq n\}$ fornito da una prefissata funzione di scelta $g: \parti(A) \setminus \{\emptyset\} \to A$.
|
||
\end{proof}
|
||
|
||
\br \label{warn}
|
||
Per essere precisi occorrerebbe definire $a_{n+1}$ distinguendo due casi: se l'insieme $A\setminus \{a_i
|
||
\mid i \leq n\}$ \`e non vuoto, poniamo $a_{n+1} = g(A\setminus \{a_i
|
||
\mid i \leq n\})$, e nel caso contrario definiamo $a_{n+1} = b$ dove $b$ \`e un qualsiasi oggetto non appartenente ad $A$ fissato all'inizio. In questo modo la successione $(a_n:n\in \omega)$ risulta in ogni caso ben definita (come funzione da $\omega$ ad $A\cup \{b\}$) grazie al teorema di ricursione, e successivamente sar\`a possibile dimostrare per induzione che in effetti il valore $b$ non \`e mai assunto. In tal modo evitiamo di mischiare definizioni e dimostrazioni. Lo stesso problema si porr\`a altre volte nel seguito, ma una volta capito il trucco possiamo sorvolare su questi dettagli.
|
||
\er
|
||
|
||
\bexe Si dimostri, senza usare l'assioma della scelta, che se $(X_i: i\in I)$ \`e una famiglia di insiemi numerabili parametrizzata da un insieme finito $I$, allora $\bigcup_{i\in I} X_i$ \`e numerabile. \eexe
|
||
|
||
Suggerimento: si proceda per induzione sul numero di elementi di $I$.
|
||
|
||
\section{Teorema di Cantor}
|
||
|
||
\bt[Cantor] \label{cantor} Per ogni insieme $X$, $|\parti (X)| > |X|$. \et
|
||
\bp Per dimostrare $|X| \leq \parti (X)$ basta considerare la funzione iniettiva che associa ad ogni $x\in X$ il suo singoletto $\{x\}\in \parti (X)$. Rimane da dimostrare che non esiste una funzione biunivoca da $X$ a $\parti (X)$. Mostreremo che non ne esiste neppure una che sia semplicemente surgettiva. Supponiamo dunque di avere una funzione che associa ad ogni elemento $a\in X$ un sottoinsieme $X_a$ di $X$. Basta mostrare che la famiglia degli $X_a$ non esaurisce tutte le parti di $X$. Per ogni $a\in X$ possiamo chiederci se $a$ appartenga o no ad $X_a$. Consideriamo l'insieme $D= \{a\in X : a \nin X_a\}$. Tale $D$ \`e un sottoinsieme di $X$. Se appartenesse alla famiglia $\{X_a: a\in X\}$ ci sarebbe un $u \in X$ tale che $D = X_u$. Ma $u\in D$ se e solo se $u\nin X_u$. Assurdo.
|
||
\ep
|
||
|
||
Dal teorema di Cantor segue in particolare che $\parti(\omega)$ non \`e numerabile.
|
||
|
||
\section{Operazioni sui numeri cardinali}
|
||
|
||
\bl Dati due insiemi $A$ e $B$, la classe $\{f \mid f:A \to B\}$ delle funzioni da $A$ a $B$, \`e un insieme. \el
|
||
\bp Tale classe \`e inclusa in $\parti (A \times B)$. \ep
|
||
|
||
\bd Dati due insiemi $A$ e $B$ definiamo la loro unione disgiunta $A\sqcup B$ come $A\times\{0\} \cup B \times \{1\}$.
|
||
Definiamo somma, prodotto, ed esponenziazione tra cardinali nel modo seguente:
|
||
\begin{enumerate}
|
||
\item $|A| + |B| = |A\sqcup B|$;
|
||
\item $|A|\cdot |B| = |A\times B|$;
|
||
\item $|A|^{|B|} = |\{f\mid f:B\to A\}|$.
|
||
\end{enumerate}
|
||
\ed
|
||
|
||
\bexe Si dimostri che le definizioni sono ben poste. Ad esempio nel caso della somma occorre dimostrare che se $A'$ \`e equipotente ad $A$ e $B'$ \`e equipotente a $B$, allora $A\sqcup B$ \`e equipotente a $A' \sqcup B'$. \eexe
|
||
|
||
Il seguente esercizio mostra che in generale non \`e possibile definire la sottrazione di cardinali, sebbene si possa fare per i cardinali finiti.
|
||
|
||
\bexe Si dimostri che $|A|+|B| = |A|+|C|$ non implica in generale $|B| = |C|$. \eexe
|
||
|
||
\bprop $|\parti(X)| = 2^{|X|}$ dove qui $2$ indica la cardinalit\`a dell'insieme $2 = \{0,1\}$. \eprop
|
||
\bp Dobbiamo trovare una corrispondenza biunivoca tra $\parti(X)$ e l'insieme $\{f: f:X \to 2\}$. A tal fine basta associare a ciascun sottoinsieme $A$ di $X$ la sua funzione caratteristica $\chi_A: X \to 2$ definita da: $\chi_A(x) = 0$ se $x\nin A$ e $\chi_A(x) = 1$ se $x\in A$. \ep
|
||
|
||
Dal teorema di Cantor otteniamo:
|
||
|
||
\bc $2^{|X|} > |X|$. \ec
|
||
|
||
In particolare $2^{\aleph_0} > \aleph_0$. Una dimostrazione diretta di quest'ultimo risultato si pu\`o ottenere come segue. Data una famiglia di funzioni $f_n: \omega \to 2$ parametrizzata da numeri naturali $n\in \omega$, basta dimostrare che esiste una funzione $f:\omega \to 2$ diversa da tutte le $f_n$. Basta a tal fine considerare la funzione diagonale $\delta: \omega \to 2$ definita da $\delta(n) = 0$ se $f_n(n)=1$ e $\delta(n) = 1$ se $f_n(n) = 0$. Tale $\delta$ differisce da $f_n$ almeno per l'argomento $n$, e quindi \`e diversa da ciascuna $f_n$.
|
||
|
||
\bexe Si dimostri che valgono le seguenti propriet\`a trovando le opportune corrispondenze biunivoche.
|
||
\begin{enumerate}
|
||
\item (propriet\`a distributiva) $|C|\cdot (|A| + |B|) = |C|\cdot |A| + |C|\cdot |B|$,
|
||
\item $|A|^{|B|+|C|} = |A|^{|B|} \cdot |A|^{|C|}$,
|
||
\item $|A|^{|B|\cdot |C|} = (|A|^{|B|})^{|C|}$.
|
||
\end{enumerate}
|
||
\eexe
|
||
\bp (Cenno) Scriviamo $Fun(X,Y)$ per indicare l'insieme delle funzioni da $X$ ad $Y$. Per il punto 3 osserviamo che, data una funzione binaria $g: B\times C \to A$, possiamo scrivere $g(b,c) = h(c)(b)$ dove $h$ \`e una funzione unaria che applicata a $c\in C$ fornisce in output una funzione $h(c): B\to A$, che a sua volta applicata a $b\in B$ fornisce in output $g(b,c) \in A$. La corrispondenza $g\mapsto h$ \`e una bigezione da $Fun(B \times C, A)$ a $Fun(C, Fun(B,A))$, come richiesto per il punto 3. \ep
|
||
%Possiamo anche definire somme e prodotti infiniti nel modo seguente:
|
||
|
||
%\bd Data una famiglia $(A_i: i\in I)$ di insiemi, poniamo $\sum_{i\in I}|A_i| = |\bigcup_{i\in I} A_i\times \{i\}|$, e poniamo $\Pi_{i\in I} |A_i| = |\Pi_{i\in I} A_i|$. \ed
|
||
|
||
|
||
%\section{Relazioni di equivalenza}
|
||
\section{Relazioni di equivalenza}
|
||
%
|
||
\bd Una relaziona di equivalenza $E$ su un insieme $X$ \`e una relazione binaria $E\subseteq X \times X$ tale che per ogni $x,y,z\in X$ si ha: $xEy \land yEz \to xEz$ (transitivit\`a); $xEy\liff yEx$ (simmetria); $xEx$ (riflessivit\`a). La classe di equivalenza di $x\in X$ \`e l'insieme $[x]_E = \{y\in X: xEy\}$. L'insieme quoziente $X/E$ \`e l'insieme $\{[x]_E : x \in X\}$ delle classi di equivalenza.
|
||
\ed
|
||
|
||
Esiste una funzione surgettiva $f: X \to X/E$ che manda ciascun $x\in X$ nella sua classe $[x]_E$, e dunque per l'assioma di rimpiazzamento $X/E$ \`e un insieme. Lo stesso ragionamento mostra che $|X/E| \leq |X|$.
|
||
|
||
\bexe Si dimostri che $X/E$ \`e un insieme senza usare l'assioma di rimpiazzamento, ma usando in suo luogo l'assioma delle parti. \eexe
|
||
|
||
\bd Una partizione di un insieme $X$ \`e una famiglia di insiemi a due a due disgiunti la cui unione \`e $X$. \ed
|
||
|
||
\bexe Data una relazione di equivalenza $E$ su $X$ le classi di equivalenza $\{[x]_E : x \in X\}$ formano una partizione di $X$. Viceversa, data una partizione $P$ di $X$, esiste una ed una sola relazione di equivalenza $E$ su $X$ tale che $P$ sia la famiglia delle classi di equivalenza di $E$. \eexe
|
||
|
||
\section{Numeri interi e razionali}
|
||
|
||
\bd
|
||
A partire dai numeri naturali $\N$ costruiamo i numeri interi $\Z$ come segue. Sia $E$ la relazione di equivalenza su $\N\times \N$ cos\`{\i} definita: $(n,m)E(n',m')$ se e solo se $n+m' = m+n'$, e si definisca $\Z = (\N\times \N)/E$. L'idea \`e che $[(n,m)]_E$ corrisponde al numero intero $n-m$.
|
||
Possiamo mandare iniettivamente $\N$ in $\Z$ associando ad $n \in \N$ la classe $[(n,0)]_E\in \Z$. In questo modo $\Z$ non include letteralmente $\N$, ma solo la sua immagine tramite la funzione suddetta. Tuttavia per abuso di notazione quando si parla di $\Z$ si identifica $\N$ con la sua immagine in $\Z$.
|
||
Come esercizio si definiscano la somma e il prodotto e l'ordine in $\Z$ in modo che valgano le usuali propriet\`a.
|
||
\ed
|
||
|
||
\bd
|
||
Definiamo l'insieme $\Q$ dei numeri razionali nel modo seguente. Sia $E$ la relazione di equivalenza su $\Z\times (\Z \setminus \{0\})$ cos\`{\i} definita: $(n,m)E(n',m')$ se e solo se $n\cdot m' = m\cdot n'$. Si definisca $\Q = (\Z\times (\Z \setminus \{0\})/E$. L'idea \`e che $[(n,m)]_E$ corrisponde al numero razionale $n/m$. Come esercizio si definiscano la somma e il prodotto e l'ordine in $\Q$ in modo che valgano le usuali propriet\`a. Si pu\`o immergere $\Z$ in $\Q$ tramite la funzione iniettiva che manda $z\in \Z$ in $[(z,1)]_E\in \Q$.
|
||
\ed
|
||
|
||
\bl $|\Q| = |\Z| = |\N| = \aleph_0$. \el
|
||
\bp Tutto segue facilmente dal fatto che l'unione e il prodotto cartesiano di due insiemi numerabili \`e numerabile e che un quoziente di un insieme numerabile \`e numerabile (se non \`e finito). \ep
|
||
|
||
|
||
\section{Numeri reali}
|
||
Diamo per nota la nozione di campo ordinato. La definizione si pu\`o trovare in ogni testo introduttivo di algebra (o sul web). Definiremo i numeri reali in termini insiemistici in modo che si abbia:
|
||
|
||
\begin{fact}
|
||
I numeri reali costituiscono un campo ordinato $\R$ che contiene $\Q$ come sottocampo e verifica le seguenti propriet\`a.
|
||
\begin{enumerate}
|
||
\item (Assioma di Archimede) Il sottoinsieme $\Q$ dei numeri razionali \`e denso in $\R$, ovvero tra due elementi di $\R$ c'\`e sempre un elemento di $\Q$.
|
||
\item (Assioma di continuit\`a) Ogni insieme $X\subseteq \R$ limitato superiormente ha un estremo superiore (ovvero tra gli elementi
|
||
maggiori di ogni elemento di $X$ ve ne \`e uno minore di tutti gli altri).
|
||
\end{enumerate}
|
||
\end{fact}
|
||
|
||
Usiamo le seguenti abbreviazioni: $\aleph_0 = |\omega|$, $\continuo = |\R|$.
|
||
Dall'assioma di Archimede otteniamo:
|
||
|
||
\bl $\continuo \leq 2^{\aleph_0}$.
|
||
\el
|
||
\begin{proof} Consideriamo la funzione $f\colon \R \to \parti (\Q)$ che associa ad ogni $r\in \R$ l'insieme $\{x\in \Q\mid x<r\}$. La funzione $f$ \`e
|
||
iniettiva perch\'e i razionali sono densi in $\R$. Ne segue che $|\R| \leq |{\cal P}(\Q)| = 2^{\aleph_0}$. \end{proof}
|
||
|
||
Dall'assioma di continuit\`a otteniamo:
|
||
|
||
\bl $2^{\aleph_0} \leq \continuo$. \el
|
||
\begin{proof} Data una successione binaria $a = (a_i | i\in \N)$ (con $a_i\in \{0,1\}$ per ogni $i$) associamo ad $a$ il numero reale $x_a = \Sigma_{i\in \N} a_i 1/10^{i}$ (definito come l'estremo superiore al variare di $n$ delle somme parziali finite $\Sigma_{i\leq n} a_i 1/ {10}^{i}$). La funzione che manda $a$ in $x_a$ \`e iniettiva. Siccome la cardinalit\`a dell'insieme delle successioni binarie \`e $2^{\aleph_0}$, otteniamo la disuguaglianza cercata (attenzione: in generale un numero reale pu\`o avere due sviluppi decimali diversi, ma questo pu\`o capitare solo se uno degli sviluppi finisce con un $9$ periodico, mentre noi ci siamo limitati a sviluppi in cui compaiono solo le cifre $0$ ed $1$).
|
||
\end{proof}
|
||
|
||
Mettendo insieme le due disuguaglianze otteniamo:
|
||
|
||
\bt $\continuo = 2^{\aleph_0}$. \et
|
||
|
||
Vogliamo dimostrare che nel nostro universo di insiemi $V$ esiste effettivamente un campo ordinato $\R$ che verifica gli assiomi di continuit\`a e di Archimede.
|
||
|
||
\bd Definiamo $\R$ in termini insiemistici come segue. Diciamo che un sottoinsieme $X$ di $\Q$ \`e un taglio di Dedekind se verifica le seguenti propriet\`a: i) ogniqualvolta $X$ contiene un
|
||
dato razionale contiene anche tutti quelli minori di lui; (ii) $X$ \`e limitato superiormente, ovvero esiste un razionale $q$ (dipendente da $X$) tale che tutti gli elementi di $X$ sono minori di $q$; (iii) $X$ non ha un massimo. Definiamo $\R$ come l'insieme dei tagli di Dedekind di $\Q$. Definiamo l'ordine $\leq$ tra numeri reali come l'inclusione tra tagli di Dedekind.
|
||
L'idea \`e la seguente: visto che vogliamo che una copia isomorfa di $\Q$ sia inclusa in $\R$, identifichiamo $q\in \Q$ con il taglio di Dedekind dei numeri razionali $<q$. Chiamiamoli ``tagli razionali''. I numeri irrazionali di $\R$ sono i tagli di Dedekind che non sono razionali. Ad esempio $\sqrt 2$ sar\`a il taglio costituito da tutti i razionali negativi e da tutti quelli positivi il cui quadrato \`e $<2$. La somma $X+Y$ di due tagli di Dedekind \`e il taglio costituito da tutte le somme $x+y$ al variare di $x\in X$ e $y\in Y$.
|
||
Lasciamo al lettore l'esercizio di definire il prodotto su $\R$: occorrer\`a distinguere alcuni casi a seconda che i numeri siano positivi o negativi.
|
||
\ed
|
||
|
||
A rigore l'$\R$ costruito con i tagli di Dedekind non include $\Q$ ma solo la sua immagine tramite la funzione iniettiva che manda $q\in \Q$ in $q_{\R} = \{x\in \Q: x<q\}\in \R$.
|
||
Tuttavia potremmo ridefinire $\R$ in modo che contenga letteralmente $\Q$. Basta sostituire ciascun $q_{\R} \in \R$ con il corrispondente $q\in \Q$. Questo rende per\`o le definizioni pi\`u complicate. Risulta pi\`u comodo, quando si parla di $\R$, pensare a $\Q$ come all'insieme dei $q_{\R}$, con le operazioni definite copiando quelle di $\Q$. Stessi ragionamenti valgono per le ``inclusioni'' $\N \subseteq \Z \subseteq \Q \subseteq \R$.
|
||
|
||
\bexe I numeri reali $\R$ definiti come sopra, e dotati delle operazioni di somma e prodotto, sono un campo ordinato che verifica gli assiomi di archimede e di continuit\`a. \eexe
|
||
|
||
\bl \label{sommaomega} Sia $X$ un insieme infinito. Allora $|X| + \aleph_0 = |X|$. \el
|
||
\bp Siccome $X$ \`e infinito, $\aleph_0 \leq |X|$ (per \ref{minimo-infinito}). Possiamo dunque scrivere $X= A \cup N$ con $N$ numerabile e disgiunto da $A$. Chiaramente $|X| = |A|+\aleph_0$. Ne segue che $|X| + \aleph_0 = (|A|+ \aleph_0) + \aleph_0 = |A|+ (\aleph_0 + \aleph_0) = |A|+\aleph_0 = |X|$. \ep
|
||
|
||
\begin{theorem} L'insieme dei numeri irrazionali ha cardinalit\`a $\continuo$.
|
||
\end{theorem}
|
||
\bp L'insieme $\R\setminus \Q$ dei numeri irrazionali \`e infinito in quanto contiene $\{\sqrt 2 +q: q\in \Q\}$. Per il Lemma \ref{sommaomega} $|\R\setminus \Q| + \aleph_0 = |\R\setminus \Q|$. D'altra parte $|\R\setminus \Q| + \aleph_0 = |\R\setminus \Q| + |\Q| = |\R|$. \ep
|
||
|
||
In modo analogo si dimostra:
|
||
|
||
\bl \label{menoN} Se da un insieme $X$ pi\`u che numerabile togliamo un insieme numerabile $N \subseteq X$, otteniamo un insieme $X\setminus N$ della stessa cardinalit\`a di $X$. \el
|
||
\bp $X\setminus N$ \`e infinito, altrimenti $X = (X\setminus N) \cup N$ sarebbe numerabile. D'altra parte $|X| = |X\setminus N| + |N| = |X\setminus N| + \aleph_0$ e per il Lemma \ref{sommaomega} possiamo concludere che $|X| = |X\setminus N|$. \ep
|
||
|
||
\begin{exercise}
|
||
L'insieme dei numeri reali algebrici \`e numerabile (un numero reale
|
||
si dice algebrico se \`e uno zero di un polinomio a coefficienti in
|
||
$\Q$). L'insieme dei numeri reali trascendenti (=non algebrici)
|
||
ha cardinali\`a $\continuo$. \end{exercise}
|
||
\bp Un polinomio a coefficienti di $\Q$ di grado $\leq n$ \`e determinato dalla successione finita dei suoi coefficienti, che sono $n+1$. Ne segue che l'insieme dei polinomi di grado $n$ ha cardinalit\`a $|\Q^{n+1}| = \aleph_0$. Al variare di $n$ otteniamo un'unione numerabile di insiemi numerabili, quindi i polinomi sono in quantit\`a numerabile. D'altra parte ogni polinomio ha un numero finito di zeri. I numeri algebrici si ottengono dunque come unione numerabile di insiemi finiti e formano quindi un insieme numerabile. Il complemento \`e pertanto della cardinalit\`a del continuo per il Lemma \ref{menoN}. \ep
|
||
|
||
Il seguente esercizio fornisce una seconda dimostrazione del fatto che $|\R| \geq 2^{\aleph_0}$ che non usa gli sviluppi decimali ma solo la completezza dell'ordine $<$ su $\R$.
|
||
|
||
\bexe Sia $(X,\leq)$ un insieme totalmente ordinato tale che tra ogni due punti ce ne \'e sempre un terzo e ogni sottoinsieme $A\subseteq X$ limitato superiormente ha un estremo superiore. Si dimostri che, se $X$ ha almeno due elementi, allora $|X| \geq 2^{\aleph_0}$. \eexe
|
||
\bp (Suggerimento) Si costruisca entro $X$ una sorta di ``insieme di Cantor'' (sul quale non dovrebbe essere difficile documentarsi), e si trovi una funzione iniettiva dall'insieme delle funzioni $f: \omega \to 2$ verso l'insieme di Cantor. \ep
|
||
%svolgere
|
||
|
||
\section{Buoni ordini}
|
||
|
||
\begin{definition}
|
||
Una relazione binaria $\leq$ su un insieme (o una classe) $A$ si dice un ordine parziale se per ogni $x,y,z\in A$ si ha $x \leq x$ (propriet\`a riflessiva),
|
||
$x\leq y \land y \leq z \to x \leq z$ (propriet\`a transitiva), $x\leq y \land
|
||
y \leq x \to x=y$ (propriet\`a antisimmetrica).
|
||
Un ordine totale \`e un ordine parziale tale che
|
||
per ogni $x,y\in A$ si ha $x\leq y \lor y\leq x$. \end{definition}
|
||
|
||
\bexa L'inclusione $\subseteq$ tra insiemi \`e un ordine parziale, mentre la relazione d'ordine $\leq$ sui numeri naturali \`e un ordine totale. La relazione di appartenenza $\in$ tra insiemi non \`e un ordine parziale perch\'e ad esempio non verifica la propriet\`a transitiva. \eexa
|
||
|
||
Dato un ordine parziale $(A,\leq)$ e dati $x,y\in A$ definiamo una
|
||
relazione $<$ (minore stretto) come segue
|
||
\begin{equation} x<y \iff x \leq y \land x \neq y. \end{equation}
|
||
Osserviamo che
|
||
\begin{equation} x \leq y \iff x < y \lor x = y \end{equation}
|
||
|
||
Quindi da $\leq$ possiamo ottenere $<$ e viceversa.
|
||
|
||
Si verifica che $<$ gode della propriet\`a transitiva $x< y \land y <
|
||
z \to x < z$ e antiriflessiva $x\not<x$. Diciamo che $(A,<)$ \`e un
|
||
ordine parziale stretto (o irriflessivo) quando verifica queste propriet\`a. Si ha che
|
||
$(A,\leq)$ \`e un ordine totale se e solo se per l'ordine stretto
|
||
$(A,<)$ ad esso associato vale la propriet\`a $x<y \lor x=y \lor y<x$.
|
||
In tal caso diciamo che $(A,<)$ \`e un ordine stretto totale.
|
||
|
||
Talvolta ometteremo la parola ``stretto'' lasciando che sia la scelta
|
||
del simbolo $\leq$ oppure $<$ a chiarire se si tratti di un ordine o
|
||
di un ordine stretto.
|
||
|
||
\begin{definition} Un ordine totale $(A,\leq)$ si
|
||
dice un buon ordine, o un insieme bene ordinato, se ogni sottoinsieme
|
||
non vuoto $X$ di $A$ ha un minimo, ovvero un elemento $a$ tale
|
||
$\forall x\in A \; a\leq x$.
|
||
|
||
Se $(A,\leq)$ \`e un buon ordine e $<$ \`e la relazione d'ordine stretto corrispondente a $\leq$ diremo che $(A,<)$ \`e un buon ordine stretto, o irriflessivo.
|
||
\end{definition}
|
||
|
||
\bd Dato un ordine totale $(A,\leq)$, un sottoinsieme $J$ di $A$ si dice un {\em segmento iniziale} se ogni elemento di $A$ che sia minore di qualche elemento di $J$ appartiene esso stesso a $J$. Equivalentemente, $J$ \`e un segmento iniziale di $A$ se ogni elemento di $A$ che non appartiene a $J$ \`e maggiore di tutti gli elementi di $J$. Un segmento iniziale proprio di $A$ \`e un segmento iniziale che non coincide con $A$. \ed
|
||
|
||
\bexe Se $(A,\leq)$ \`e un buon ordine e $J$ \`e un suo segmento proprio, allora esiste un $a\in A$ tale che $J = \{x\in A: x<a\}$. Ci\`o non \`e in generale vero se $(A,\leq)$ \`e un ordine totale che non sia un buon ordine (si consideri un insieme di numeri razionali senza un estremo superiore razionale). \eexe
|
||
|
||
Per ora gli unici buoni ordini che abbiamo incontrato sono i numeri naturali (con l'usuale ordine) e gli ordini totali con un numero finito di elementi. Per trovare altri esempi diamo le seguenti definizioni.
|
||
|
||
\bd (Somma di ordini)
|
||
Dati due ordini totali $(A,\leq_A)$ e $(B,\leq_B)$
|
||
definiamo un nuovo ordine totale $(A+B,\leq)=(A,\leq_A)+(B,\leq_B)$ come
|
||
segue. Il dominio $A+B$ \`e definito come $A\times \{0\} \cup B\times
|
||
\{1\}$. L'ordine su $A+B$ \`e definito stabilendo che $(a,0)<(b,1)$
|
||
per ogni $a\in A$ e $b\in B$, mentre per coppie con la stessa seconda
|
||
componente si segue l'ordine delle prime componenti rispetto agli
|
||
ordini $\leq_A$ e $\leq_B$ (cio\`e $(a,0)\leq (a',0)$ se $a\leq_A a'$ e
|
||
$(b,1)\leq(b',1)$ se $b\leq_Bb'$). \ed
|
||
|
||
\bexe
|
||
Si mostri che se $(A,\leq_A)$ e $(B,\leq_B)$ sono buoni ordini anche
|
||
$(A,\leq_A)+(B,\leq_B)$ lo \`e.
|
||
\eexe
|
||
|
||
\bd (Prodotto lessicografico) Dati due ordini totali $(A,\leq_A)$ e $(B,\leq_B)$
|
||
definiamo un nuovo ordine $(A\times B,\leq) = (A,\leq_A)\times (B,\leq_B)$ come
|
||
segue. Il dominio $A\times B$ \`e il prodotto cartesiano costituito da
|
||
tutte le coppie $(a,b)$ con $a\in A$ e $b\in B$. Ordiniamo tali coppie
|
||
confrontando innanzitutto le seconde componenti secondo l'ordine di
|
||
$B$, e a parit\`a di seconde componenti confrontando le prime
|
||
componenti secondo l'ordine di $A$. Formalmente: $(a,b)<(a',b')$ se
|
||
$b<_B b'$ oppure se $b=b'$ e $a<_A a'$. \ed
|
||
|
||
\bexe
|
||
Si mostri che se $(A,\leq_A)$ e
|
||
$(B,\leq_B)$ sono buoni ordini, anche il loro prodotto lessicografico $(A\times B,\leq)$ lo \`e.
|
||
\eexe
|
||
|
||
\begin{definition}
|
||
Sia $(A,\leq)$ un buon ordine e siano $x,y \in A$. Diciamo che $y$ \`e il
|
||
successore immediato di $x$ se $x<y$ e non esiste alcun $z\in A$ con $x<z<y$. In
|
||
questo caso diciamo anche che $x$ \`e il precedessore immediato di $y$.
|
||
Gli elementi di $A$ sono di tre tipi: 1) Il minimo di $A$; 2) Gli elementi successore, definiti come quelli
|
||
che hanno un predecessore immediato; 3) Gli elementi limite, ovvero quelli diversi
|
||
dal minimo che non hanno predecessore immediato.
|
||
\end{definition}
|
||
|
||
|
||
|
||
\br Dato un buon ordine $(A,\leq)$ senza un massimo, ogni elemento ha un successore immediato; basta infatti considerare il minimo elemento tra quelli maggiori di $x$. Si noti anche che se $x\in A$ \`e un elemento limite, allora $x$ \`e l'estremo superiore dell'insieme degli elementi strettamente minori di $x$. \er
|
||
|
||
\begin{exercise}
|
||
In $(\N, \leq) + (\N, \leq)$ ogni elemento ha un successore immediato, e ci sono
|
||
esattamente due elementi che non hanno predecessore immediato, di cui uno \`e il
|
||
minimo e l'altro \`e un elemento limite.
|
||
|
||
In $(\N, \leq) \times (\N, \leq)$, con l'ordine lessicografico, vi sono infiniti elementi limite.
|
||
\end{exercise}
|
||
|
||
|
||
\section{Tipi d'ordine}
|
||
|
||
\begin{definition}
|
||
Dati due insiemi totalmente ordinati $(A,\leq_A)$ e $(B,\leq_B)$, una funzione
|
||
$f\colon A\to B$ si dice crescente se $x<y$ implica $fx < fy$ per ogni
|
||
$x,y\in A$. Se $f$ \`e anche biunivoca diremo che $f$ \`e un isomorfismo.
|
||
\end{definition}
|
||
|
||
Si noti che una funzione crescente \`e necessariamente iniettiva e che nella definizione di
|
||
funzione crescente possiamo equivalentemente richiedere la doppia implicazione:
|
||
$x<y$ se e solo se $fx < fy$.
|
||
|
||
\bd[Tipo d'ordine] Se esiste un isomorfismo $f: (A, \leq_A) \to (B, \leq_B)$, diremo che $(A,\leq_A)$ e $(B,\leq_B)$ hanno lo stesso tipo d'ordine. \ed
|
||
|
||
Ad esempio i numeri naturali con l'usuale ordinamento hanno lo stesso tipo d'ordine del sottoinsieme dei numeri pari.
|
||
|
||
\bl\label{crescente} Se $(W,\leq)$ \`e un buon ordinamento e $f\colon W \to W$ \`e
|
||
una funzione crescente (cio\`e $x<y$ implica $fx < fy$), allora $f(x)
|
||
\geq x$ per ogni $x \in W$. \el
|
||
|
||
\begin{proof} Supponiamo che $fx < x$ per qualche $x$ e sia $z$ il minimo di
|
||
tali $x$. In particolare $fz < z$. Poich\`e $f$ \`e crescente, $ffz <
|
||
fz$. Ma allora l'elemento $w = fz$ contraddice la minimalit\`a di
|
||
$z$. \end{proof}
|
||
|
||
\bl \label{limitato} Sia $(A,\leq)$ un buon ordine e sia $B\subseteq A$ un sottoinsieme superiormente limitato di $A$. Allora $(A,\leq)$ non \`e isomorfo a $(B,\leq \; \rest{B})$. \el
|
||
\bp Sia $a$ un elemento di $A$ maggiore di tutti gli elementi di $B$. Se $f:(A,\leq) \to (B,\leq \; \rest{B})$ fosse un isomorfismo, allora in particolare $f$ sarebbe una funzione crescente da $A$ ad $A$, e quindi per il Lemma \ref{crescente} $f(a) \geq a$. Questo \`e assurdo perch\'e $f(a) \in B$ e gli elementi di $B$ sono tutti minori di $a$. \ep
|
||
|
||
\bd Dati due insieme bene ordinati $(A,\leq_A)$ e $(B,\leq_B)$,
|
||
Se esiste un isomorfismo da $(A,\leq_A)$ ad un segmento iniziale proprio di $(B,\leq_B)$, diremo che il tipo d'ordine di $(A,\leq_A)$ \`e strettamente minore di quello di $(B,\leq_B)$.\ed
|
||
|
||
Per il lemma precedente, il tipo d'ordine di un insieme bene ordinato $(A, \leq_A)$ non \`e mai strettamente minore di se stesso, quindi la terminologia \`e coerente. Nel seguito dimostreremo che i tipi d'ordine di insiemi bene ordinati sono sempre confrontabili: due insiemi bene ordinati o sono isomorfi o uno dei due \`e isomorfo ad un segmento iniziale proprio dell'altro.
|
||
|
||
Possiamo provvisoriamente definire i numeri ordinali come i tipi d'ordine degli insiemi bene ordinati, dove il tipo d'ordine di un insieme bene ordinato $(X,\leq)$ \`e la classe di equivalenza di tutti i buoni ordini isomorfi ad $(X,\leq)$. Nel seguito definiremo dei particolari buoni ordini chiamati ``ordinali di von Neumann'' e vedremo che ve ne \`e esattamente uno in ogni classe di equivalenza. Potremo allora ridefinire il tipo d'ordine di $(X,\leq)$ come l'unico ordinale di von Neumann isomorfo ad $(X,\leq)$.
|
||
|
||
\section{Insiemi transitivi}
|
||
Per definire gli ordinali di von Neumann abbiamo bisogno della nozione di insieme transitivo.
|
||
|
||
|
||
\begin{definition} \label{trans}
|
||
Un insieme $\alpha$ si dice transitivo se per ogni $x,y$ con $x\in y \in \alpha$
|
||
si ha $x \in \alpha$. Equivalentemente $\alpha$ \`e
|
||
transitivo se $x \in \alpha \to x \subseteq \alpha$. Un'altra definizione equivalente \`e: $\alpha$ \`e transitivo se $\bigcup \alpha \subseteq \alpha$. \end{definition}
|
||
|
||
\bt Sia $X$ un insieme. Allora esiste un insieme transitivo $Y$ con $X\subseteq Y$. Inoltre tra tutti gli insiemi transitivi che contengono $X$ ne esiste uno pi\`u piccolo di tutti (rispetto all'inclusione) che viene chiamato {\em chiusura transitiva} di $X$. \et
|
||
\bp Definiamo grazie al teorema di ricursione una successione di insiemi $(X_n: n \in \omega)$ ponendo $X_0 = X$ ed $X_{n+1} = \bigcup X_n$. Sia $Y = \bigcup_{n\in \omega} X_n$ e mostriamo che $Y$ \`e transitivo. A tal fine supponiamo $x\in y \in Y$. Allora esiste $n\in \omega$ con $y\in X_n$ e siccome $x\in y$ si ha $x\in \bigcup X_n = X_{n+1} \subseteq Y$. Quindi $Y$ \`e transitivo. Mostriamo che l'insieme $Y$ cos\`{\i} costruito \`e in effetti il pi\`u piccolo insieme transitivo contenente $X$. A tal fine prendiamo un altro insieme transitivo $Y'$ che include $X$ e dimostriamo che $Y\subseteq Y'$. \`E sufficiente mostrare, per induzione su $n\in \omega$, che $X_n\subseteq Y'$. Il caso $n=0$ \`e ovvio. Supponendo per ipotesi induttiva che $X_n \subseteq Y'$. Allora $\bigcup X_n \subseteq \bigcup Y' \subseteq Y'$, dove la seconda inclusione segue dal fatto che $Y'$ \`e transitivo. Per induzione $X_n\subseteq Y'$ per ogni $n\in \omega$ e quindi $Y \subseteq Y'$.
|
||
\ep
|
||
|
||
\section{Ordinali di von Neumann}
|
||
|
||
\begin{definition} \label{ordinale}
|
||
Un insieme $\alpha$ \`e un ordinale se \`e transitivo (Definizione \ref{trans}) e $\alpha$ \`e bene ordinato dall'appartenenza, nel senso che $(\alpha, \in \; \rest{\alpha})$ \`e un buon ordine stretto. \end{definition}
|
||
|
||
Il fatto che $\in$ sia un buon ordine stretto sugli elementi di $\alpha$ implica in particolare che se $x,y,z$ sono elementi di $\alpha$ con $x\in y\in z$, allora $x\in z$, ovvero $\in \; \rest{\alpha}$ \`e una relazione transitiva. Inoltre se $\alpha$ \`e un ordinale ed $x\in \alpha$, non pu\`o essere che $x\in x$ (in quanto $\in \; \rest{\alpha}$ \`e un ordine stretto). Quindi in particolare non pu\`o capitare che $\alpha\in \alpha$.
|
||
|
||
\bprop Per ogni ordinale $\alpha$ abbiamo $\alpha \nin \alpha$. \eprop
|
||
|
||
Nel seguito introdurremo un assioma, chiamato assioma di fondazione, che implica che la stessa propriet\`a vale per tutti gli insiemi, non solo per gli ordinali, ma per il momento non ne abbiamo bisogno.
|
||
|
||
\begin{example}
|
||
I seguenti insiemi sono ordinali: $0=\emptyset$, $1 = \{0\}$, $2 =
|
||
\{0,1\}$, $3 = \{0,1,2\}$ etc. Anche $\omega$ \`e un ordinale. \end{example}
|
||
|
||
\begin{lemma}
|
||
Se $\alpha$ \`e un ordinale e $x\in \alpha$ allora $x$ \`e un
|
||
ordinale.\end{lemma}
|
||
\begin{proof}
|
||
Per mostrare che $x$ \`e transitivo supponiamo che $z\in y\in
|
||
x$. Applicando la transitivit\`a di $\alpha$ vediamo che $x,y,z$ sono
|
||
tutti elementi di $\alpha$ (prima mostro che $y\in \alpha$, poi usando
|
||
questo fatto anche $z\in \alpha$). Ora poich\'e tra
|
||
elementi di $\alpha$ la relazione $\in$ gode della propriet\`a
|
||
transitiva (essendo un ordine stretto), otteniamo $z\in x$. Quindi $x$ \`e
|
||
transitivo.
|
||
|
||
Resta da dimostrare che $(x,\in)$ \`e un buon ordine stretto. A tal fine
|
||
basta osservare che da $x\in \alpha$ segue $x \subseteq \alpha$ (essendo
|
||
$\alpha$ transitivo) e che un sottoinsieme di un buon ordine \`e un
|
||
buon ordine (con l'ordine indotto). \end{proof}
|
||
|
||
\begin{lemma}\label{minore-ord}
|
||
Siano $\alpha$ e $\beta$ due ordinali. Sono equivalenti:
|
||
\begin{enumerate}
|
||
\item $\alpha \in \beta$,
|
||
\item $\alpha \subset \beta$ (inclusione stretta),
|
||
\item $\alpha$ \`e un segmento iniziale proprio di $\beta$ (rispetto
|
||
all'ordine stretto dato da $\in$).
|
||
\end{enumerate}
|
||
\end{lemma}
|
||
\begin{proof}
|
||
Per la transitivit\`a degli ordinali, 1) implica 2) (l'inclusione deve essere stretta altrimenti $\alpha\in \alpha$)
|
||
e 2) \`e equivalente a 3). Mostriamo che 3) implica 1). Sia $\alpha$ un
|
||
segmento iniziale proprio di $\beta$. Allora $\alpha$ si pu\`o
|
||
scrivere nella forma $\alpha = \{x \in \beta \mid x < \gamma\}$ per un
|
||
certo $\gamma \in \beta$. Ricordando che $<$ \`e l'appartenenza $\in$,
|
||
abbiamo $\alpha = \{x \in \beta \mid x \in \gamma\} = \gamma$, dove
|
||
l'ultima uguaglianza segue dal fatto che gli elementi di $\gamma$ sono
|
||
automaticamente anche elementi di $\beta$, essendo $\beta$
|
||
transitivo. Abbiamo cos\`{\i} dimostrato che $\alpha = \gamma \in
|
||
\beta$. \end{proof}
|
||
|
||
\begin{lemma} \label{confrontabilita-ord} Se $\alpha$ e $\beta$ sono ordinali, allora $\alpha
|
||
\subseteq \beta$ oppure $\beta \subseteq \alpha$. \end{lemma}
|
||
\begin{proof} Sia $\gamma = \alpha \cap \beta$. Chiaramente $\gamma$
|
||
\`e un ordinale, e $\gamma \subseteq \alpha$, $\gamma \subseteq
|
||
\beta$. Basta mostrare che $\gamma = \alpha$ oppure $\gamma =
|
||
\beta$. Se cos\`{\i} non fosse, $\gamma$ sarebbe incluso strettamente sia
|
||
in $\alpha$ che in $\beta$ e quindi per il lemma precedente
|
||
apparterrebbe sia ad $\alpha$ che a $\beta$: $\gamma \in \alpha$,
|
||
$\gamma \in \beta$. Ma allora $\gamma \in \alpha \cap \beta = \gamma$,
|
||
e quindi $\gamma \in \gamma$ contraddicendo il fatto che $\gamma$ \`e un ordinale. \end{proof}
|
||
|
||
|
||
|
||
\begin{lemma} \label{unicita-ordinali}
|
||
Dati due ordinali $\alpha$ e $\beta$, se $(\alpha,\in)$ \`e isomorfo a
|
||
$(\beta,\in)$ allora $\alpha = \beta$. \end{lemma}
|
||
\begin{proof}
|
||
Se $\alpha\neq \beta$ allora in base ai Lemmi \ref{confrontabilita-ord} e \ref{minore-ord}
|
||
$\alpha$ \`e un segmento iniziale proprio di $\beta$ o viceversa. Ora basta ricordare che, per il Lemma \ref{limitato}, un buon ordine non
|
||
\`e mai isomorfo ad un suo segmento iniziale proprio.
|
||
\end{proof}
|
||
|
||
\begin{definition}
|
||
Se $\alpha$ e $\beta$ sono ordinali scriviamo $\alpha \leq \beta$ se
|
||
$\alpha \subseteq \beta$ e $\alpha < \beta$ se $\alpha \in \beta$.
|
||
\end{definition}
|
||
|
||
Per il Lemma \ref{minore-ord} $x<y$ se e solo se $x\leq y$ e $x\neq y$. Inoltre $\leq$ \`e un ordine totale sulla classe degli ordinali (la totalit\`a \`e data dal Lemma \ref{confrontabilita-ord})
|
||
|
||
\begin{remark} \label{minoredia}
|
||
Ogni ordinale coincide con l'insieme degli ordinali minori di lui. Quindi in particolare
|
||
$\{x \mid x < \alpha\}$ \`e un insieme (in quanto coincide con $\alpha$).
|
||
\end{remark}
|
||
|
||
%\section{La classe degli ordinali \`e bene ordinata}
|
||
|
||
\begin{theorem}
|
||
(Principio del minimo per gli ordinali) Ogni classe non vuota $X$ di ordinali ha un minimo elemento.
|
||
\end{theorem}
|
||
\begin{proof} Fissiamo un elemento $\alpha$ di $X$.
|
||
Se $\alpha$ non \`e il minimo di $X$ consideriamo l'insieme $\{\beta < \alpha \mid \beta\in X\}$. Questo \`e
|
||
un sottoinsieme non vuoto dell'insieme bene ordinato $\alpha$ e
|
||
pertanto ha un minimo, che deve coincidere con il minimo di $X$.
|
||
\end{proof}
|
||
|
||
\bc La classe $ON$ degli ordinali non \`e un insieme. \ec
|
||
\bp Poich\'e gli elementi di un ordinale sono ordinali, $ON$ \`e una classe transitiva. Inoltre \`e bene ordinata da $\leq$ per il principio del minimo sopra dimostrato. Se $ON$ fosse un insieme, sarebbe dunque un ordinale, ovvero $ON \in ON$. Ma questo \`e assurdo in quanto un ordinale non appartiene mai a se stesso. \ep
|
||
|
||
%\section{Successore e sup tra gli ordinali}
|
||
|
||
\bl Sia $X$ un insieme transitivo di ordinali. Allora $X$ \`e un ordinale. \el
|
||
\bp Un insieme di ordinali \`e sempre bene ordinato dall'appartenenza. Se \`e anche transitivo, allora per definizione \`e un ordinale. \ep
|
||
|
||
\begin{theorem} \label{unioneON} Consideriamo la classe ordinata $(ON, \leq)$ degli ordinali.
|
||
\begin{enumerate}
|
||
\item $\emptyset$ \`e il minimo ordinale (lo zero).
|
||
\item Se $\alpha$ \`e un ordinale, allora $\alpha \cup \{\alpha\}$ \`e un ordinale, ed \`e il minimo ordinale strettamente maggiore di $\alpha$. Lo chiamiamo $\alpha+1$.
|
||
\item Se $X$ \`e un insieme di ordinali, allora $\bigcup X$ \`e un ordinale, ed \`e il minimo ordinale
|
||
maggiore o uguale a tutti gli ordinali di $X$, cio\`e $\bigcup X = \sup X$.
|
||
\end{enumerate}
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Verifichiamo che $\bigcup X$ \`e un ordinale.
|
||
Poich\'e gli elementi di $X$ sono transitivi (essendo ordinali), $\bigcup X$ \`e transitivo (l'unione di una famiglia di insiemi transitivi \`e transitiva). Poich\`e gli elementi di un ordinale sono ordinali, $\bigcup X$ \`e l'unione di un insieme $X$ i cui elementi sono insiemi di ordinali, e pertanto $\bigcup X$ \`e un insieme di ordinali. Essendo anche transitivo, \`e un ordinale.
|
||
|
||
Similmente si verifica che $\alpha \cup \{\alpha\}$ \`e un ordinale.
|
||
|
||
Gli altri punti seguono facilmente dal fatto che tra ordinali l'inclusione coincide con l'ordine e quindi l'unione coincide con l'estremo superiore.
|
||
\end{proof}
|
||
|
||
Sono dunque ordinali i numeri naturali $0,1,2, \ldots$, il loro sup $\omega = \bigcup \omega$, e poi $\omega+1 = \omega \cup \{\omega\}$, $\omega + 2 = \omega + 1 + 1$, eccetera.
|
||
|
||
\begin{corollary}
|
||
Ogni insieme $X$ di ordinali \`e limitato superiormente.
|
||
\end{corollary}
|
||
\bp Basta prendere $\sup(X) + 1$. \ep
|
||
|
||
\bc Ogni classe di ordinali non limitata superiormente non \`e un insieme. \ec
|
||
|
||
\bexe La classe degli ordinali \`e la pi\`u piccola classe contenente $0$ e chiusa per successore e unione di sottoinsiemi. \eexe
|
||
|
||
|
||
\section{Induzione e ricursione sugli ordinali}
|
||
|
||
\begin{theorem}(Induzione sugli ordinali) Sia $P(x)$ una propriet\`a ben definita sugli ordinali.
|
||
Supponiamo che:
|
||
\begin{enumerate}
|
||
\item valga $P(0)$.
|
||
\item per ogni ordinale $\alpha$ se vale $P(\alpha)$ vale $P(\alpha + 1)$.
|
||
\item per ogni insieme $X$ di ordinali, se per ogni $\beta\in X$ vale $P(\beta)$, allora
|
||
allora vale $P(\sup X)$.
|
||
\end{enumerate}
|
||
Allora tutti gli ordinali $x$ verificano $P(x)$.
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Altrimenti si consideri il minimo ordinale che non verifica $P(x)$
|
||
e si raggiunga una contraddizione distinguendo i casi in cui tale
|
||
ordinale \`e $0$, il successore di un altro ordinale, o il sup degli
|
||
ordinali minori di lui.
|
||
\end{proof}
|
||
|
||
Analogamente si dimostra un teorema di ricursione transfinita per
|
||
definire funzioni su ordinali.
|
||
|
||
\begin{theorem} \label{ricON} (Ricursione su ordinali)
|
||
Sia $H:ON\times V \to V$ una funzione classe. Allora esiste una ed una sola funzione $F:ON\to V$ tale che per ogni $a\in ON$ si ha \[F(a) = H(a, F\rest{{\{x : x<a\}}})\]
|
||
\end{theorem}
|
||
\bp Diciamo che una funzione $g$ \`e buona se esiste $\alpha \in ON$ tale che $\dom(g) = \alpha$ e $g$ verifica l'equazione ricorsiva
|
||
$$g(\beta) = H(n,g\rest{\{i: i<\beta\}})$$
|
||
per ogni $\beta$ nel suo dominio. Per induzione \`e facile vedere che due funzioni buone coincidono sull'intersezione dei loro domini, e quindi ve ne al massimo una su un dato dominio. Definiamo ora $F$ come l'unione di tutte le funzioni buone. L'equazione ricorsiva permette di estendere una funzione buona $g$ con dominio $\beta = \{i: i < \beta\}$ ad una funzione buona $g'$ con dominio $\beta+1= \beta \cup \{\beta\}$, ponendo $g'(\beta) = H(n,g\rest{\{i: i<\beta\}})$. Se $\lambda$ \`e un ordinale limite, e supponendo che per ogni $\beta < \lambda$ esista una funzione buona $g_\beta$ con dominio $\beta$ (necessariamente unica), possiamo ottenere una funzione buona $g_\lambda$ con dominio $\lambda$ ponendo $g_\lambda = \bigcup_{\beta<\lambda} g_\beta$ (qui dobbiamo usare l'assioma di rimpiazzamento per assicurarci che la classe $\{g_\beta: \beta < \lambda\}$ di cui prendiamo l'unione sia un insieme). Per induzione ne segue che per ogni ordinale $\alpha$ esiste una funzione buona con dominio $\alpha$. Ne segue che l'unione $F$ di tutte le funzioni buone \`e una funzione da $ON$ ad $V$ che verifica l'equazione ricorsiva.
|
||
\ep
|
||
|
||
Applicando il teorema di ricursione possiamo definire la somma tra ordinali nel modo seguente.
|
||
|
||
\begin{definition} Definiamo la somma di due numeri ordinali per ricursione sul secondo argomento:
|
||
\begin{enumerate}
|
||
\item $\alpha + 0 = \alpha$,
|
||
\item $\alpha + S(\beta) = S(\alpha + \beta)$, dove $S(x) = x+1$,
|
||
\item $\alpha + \lambda = \sup_{\beta<\lambda} \alpha+ \beta$ se $\lambda$ \`e un ordinale limite.
|
||
\end{enumerate}
|
||
\end{definition}
|
||
|
||
\begin{definition} Definiamo il prodotto di due numeri ordinali per induzione sul secondo argomento:
|
||
\begin{enumerate}
|
||
\item $\alpha \cdot 0 = 0$,
|
||
\item $\alpha \cdot S(\beta) = \alpha \cdot \beta + \alpha$,
|
||
\item $\alpha \cdot \lambda = \sup_{\beta<\lambda} \alpha \cdot \beta$, se $\lambda$ \`e un ordinale limite.
|
||
\end{enumerate}
|
||
\end{definition}
|
||
|
||
\begin{definition} Definiamo l'esponenziazione di due numero ordinali per induzione sul secondo argomento:
|
||
\begin{enumerate}
|
||
\item $\alpha^0 = 1$,
|
||
\item $\alpha^{\beta+ 1} = \alpha^{\beta}\cdot \alpha$,
|
||
\item $\alpha^{\lambda} = \sup_{\beta<\lambda} \alpha^{\beta}$, se $\lambda$ \`e un ordinale limite.
|
||
\end{enumerate}
|
||
\end{definition}
|
||
|
||
\br \label{sup}
|
||
Se $(\beta_i: i \in I)$ \`e una famiglia di ordinali, allora $$\alpha + \sup_{i\in I}\beta_i = \sup_{i\in I}(\alpha+ \beta_i).$$ Per dimostrarlo si distinguono due casi. Se la famiglia ha un massimo elemento $\beta_j$, allora entrambi i membri dell'uguaglianza da dimostrare coincidono con $\alpha + \beta_j$ (dopo aver verificato che $\alpha + x$ \`e una funzione crescente di $x$). Se invece la famiglia non ha un massimo allora il sup \`e un ordinale limite e possiamo applicare la terza clausola nella definizione di somma. Analogamente $\alpha \cdot \sup_{i\in I}\beta_i = \sup_{i\in I}(\alpha\cdot \beta_i)$ e $\alpha^{\sup_{i\in I}\beta_i} = \sup_{i\in I}\alpha^{\beta_i}$. \er
|
||
|
||
|
||
\bexe Se $\alpha$ e $\beta$ sono ordinali numerabili, anche $\alpha^\beta$ lo \`e. \eexe
|
||
|
||
\bexe Valgono le leggi associative del $+$ e del $\cdot$, e la legge distributiva a destra $x \cdot (y+ z) = x\cdot y + x \cdot z$. Non valgono le leggi commutative, e neppure la distributivit\`a a sinistra. \eexe
|
||
%Attenzione: nonostante si usino le stesse notazioni, le operazioni sugli ordinali sono diverse dalle omologhe operazioni sui cardinali. Ad esempio se $\beta$ \`e un cardinale infinito, $2^{\beta}$ (esponenziazione cardinale) non \`e numerabile: l'esponenziazione tra cardinali fa uscire dal numerabile.
|
||
|
||
\bexe Abbiamo:
|
||
\begin{enumerate}
|
||
\item (Sottrazione) Se $\alpha$ e $\beta$ sono ordinali, ed $\alpha \leq \beta$, allora esiste un unico ordinale $\gamma$ con $\alpha + \gamma = \beta$.
|
||
\item (Divisione con resto) Se $\alpha$ e $\beta$ sono ordinali, con $\beta \neq 0$, allora esiste una unica coppia di ordinali $\xi$ e $\rho$ tale che $\alpha = \beta \xi + \rho$, con $\rho < \beta$.
|
||
\item (Rappresentazione in base $\gamma$) Dato un ordinale $\gamma \neq 0$ possiamo rappresentare ogni ordinale $\alpha \neq 0$ in modo unico nella forma $\alpha = \gamma^{\alpha_1} t_1 + \ldots + \gamma^{\alpha_k} t_k$ con $k \in \omega$, $t_1, \ldots, t_k < \gamma$, $\alpha_1 > \ldots > \alpha_k$.
|
||
\item (Forma normale di Cantor) In particolare se $\alpha$ \`e un ordinale diverso da zero, allora esiste un'unica scrittura della forma $\alpha = \omega^{\alpha_1} n_1 + \ldots + \omega^{\alpha_k} n_k$ con $k \in \omega$, $n_1, \ldots, n_k < \omega$, $\alpha_1 > \ldots > \alpha_k$.
|
||
\end{enumerate}
|
||
\eexe
|
||
\bp (1) Procedo per induzione su $\beta$. Per $\beta < \alpha$ non c'\`e nulla da dimostrare e per $\beta = \alpha$ l'unico possibile $\gamma$ \`e zero. Se $\alpha + \gamma=\beta$, allora $\alpha + \gamma + 1 = \beta + 1$ (dando per buona l'associativit\`a). Rimane da trattare il caso in cui $\beta$ \`e limite. Per ipotesi induttiva possiamo supporre che per ogni $x<\beta$ con $\alpha \leq x$ esiste un unico ordinale $\gamma_x$ tale che $\alpha + \gamma_x = x$. Sia $\gamma = \sup_{x<\beta} \gamma_x$. Allora $\alpha + \gamma = \alpha + \sup_{x<\beta} \gamma_x = \sup_{x<\beta} (\alpha + \gamma_x) = \sup_{x<\beta} x = \beta$.
|
||
|
||
(2) Considero il massimo ordinale $\xi$ tale che $\beta \cdot \xi \leq \alpha$ e prendo come $\rho$ la differenza tra $\alpha$ e $\beta \cdot \xi$, ovvero l'unico ordinale tale che $\alpha = \beta \cdot \xi + \rho$. Dobbiamo per\`o dimostrare che il massimo esiste e che $\rho < \beta$. Per mostrare che il massimo esiste osserviamo che la classe $C$ degli ordinali $x$ tali che $\beta \cdot x \leq \alpha$ \`e un insieme (essendo ciascun $x$ necessariamente $< \alpha+1$). Posto $\xi$ l'estremo superiore di $C$, dobbiamo avere $\beta \cdot \xi \leq \alpha$ in quanto la moltiplicazione \`e continua nel secondo argomento (nel senso che commuta con i sup). Abbiamo cos\`{\i} dimostrato che $\xi$ \`e in effetti un massimo. Ora se per assurdo $\rho$ fosse maggiore di $\beta$, potremmo sostituire $\rho$ con $\rho-\beta$ e $\xi$ con $\xi+1$, ottenendo $\alpha = \beta \cdot (\xi + 1) + (\rho - \beta)$, e contraddicendo la massimalit\`a di $\xi$.
|
||
|
||
(3) Considero il massimo ordinale $\alpha_1$ tale che $\gamma^{\alpha_1} \leq \alpha$ (dimostrate che esiste). Ora per il teorema di divisione con resto scrivo $\alpha = \gamma^{\alpha_1} t_1 + \rho$ con $\rho< \gamma^{\alpha_1}$. Osservo che $t_1<\gamma$ altrimenti avrei $\gamma^{\alpha_1} \leq \alpha$ contraddicendo la massimalit\`a di $\alpha_1$. Per induzione posso supporre che $\rho$, se non \`e zero, si scriva nella forma $\gamma^{\alpha_2} t_2 + \ldots + \gamma^{\alpha_k} t_k$ con $\alpha_2 > \ldots > \alpha_k$ e $t_i< \gamma$ per ogni $i$, e concludo osservando che $\alpha_1 > \alpha_2$ altrimenti riarrangiando i termini contraddirei la massimalit\`a di $\alpha_1$.
|
||
\ep
|
||
|
||
|
||
\bexe Se $\alpha$ e $\beta$ sono ordinali, $\alpha+\beta$ \`e isomorfo a $\alpha \times\{0\} \cup \beta \times\{1\}$ con l'unico ordine in cui tutti gli elementi di $\alpha\times\{0\}$ sono minori di quelli di $\beta\times\{1\}$ e in ciascuno di questi due insiemi si segue l'ordine delle prime componenti in $\alpha$ e $\beta$ rispettivamente.
|
||
\eexe
|
||
\bp L'isomorfismo $f: \alpha + \beta \to \alpha \times\{0\} \cup \beta \times\{1\}$ \`e il seguente. Dato $x< \alpha+\beta$, distinguiamo due casi. Se $x<\alpha$, poniamo $f(x) = x\times \{0\}$. Se invece $\alpha \leq x$ possiamo scrivere $x= \alpha + y$ e poniamo $f(x) = y\times \{1\}$. \ep
|
||
|
||
\bexe Se $\alpha$ e $\beta$ sono ordinali, $\alpha\cdot \beta$ \`e isomorfo a $\alpha \times\beta$ con l'ordine lessicografico: prima si confrontano le seconde componenti delle coppie, poi a parit\`a si confrontano le prime.
|
||
\eexe
|
||
\bp Dato $u < \alpha \cdot \beta$, posso usare il teorema di divisione con resto per scrivere $u = \alpha y + x$ con $x< \alpha$. L'isomorfismo cercato manda $u$ nella coppia $(x,y)$ (osserviamo che $y$ \`e necessariamente $<\beta$). L'isomorfismo inverso manda $(x,y)$ in $\alpha y + x$. \ep
|
||
|
||
\bexe Se $\alpha$ e $\beta$ sono ordinali, $\alpha^\beta$ \`e il tipo d'ordine dell'insieme bene ordinato $(S,<)$ cos\`{\i} definito: $S$ \`e l'insieme delle funzioni $f: \beta \to \alpha$ con supporto finito, ovvero con $f(x) = 0$ per tutti gli $x\in \beta$ al di fuori di un insieme finito; date $f_1 \neq f_2$ in $S$, poniamo $f_1<f_2$ se per il massimo $x$ tale che $f_1(x)\neq f_2(x)$, si ha $f_1(x) < f_2(x)$. Si noti che il massimo esiste perch\'e i supporti sono finiti.
|
||
\eexe
|
||
\bp (Cenno) Data $f: \beta \to \alpha$ con supporto finito $\textrm{supp}(f) \subseteq \beta$, associamo ad $f$ l'ordinale $\alpha^{x_1} \cdot f(x_1) + \ldots + \alpha^{x_k} \cdot f(x_k)$ dove $x_1>\ldots > x_k$ sono gli elementi del supporto di $f$ (conveniamo che se il supporto \`e vuoto associamo ad $f$ l'ordinale $0$). Questa corrispondenza definisce l'isomorfismo cercato.
|
||
\ep
|
||
|
||
|
||
\bl Sia $f: ON \to ON$ una funzione crescente e continua, dove continua significa che $f(\lambda) = \sup_{\alpha<\lambda} f(\alpha)$ per ogni ordinale limite $\lambda$. Allora esistono ordinali $x$ arbitrariamente grandi tali che $f(x) = x$. \el
|
||
\bp (Cenno) Dato $x_0\in ON$ definiamo induttivamente $x_{n+1} = f(x_n)$ e poniamo $x = \sup_{n\in \omega} x_n$. Allora $f(x) = x$ ed $x\geq x_0$. \ep
|
||
|
||
\bexe Si dimostri che esistono ordinali $\alpha$ arbitrariamente grandi tali che $\alpha = \omega^\alpha$.
|
||
Sia $\varepsilon_0$ il minimo ordinale tale che $\varepsilon_0 = \omega^{\varepsilon_0}$. Si dimostri che $\varepsilon_0$ \`e numerabile. \eexe
|
||
|
||
|
||
\section{Relazioni ben fondate}
|
||
|
||
\bd Una relazione binaria $R$ su un insieme (o una classe) $A$ si dice ben fondata se ogni sottoinsieme non vuoto $X$ di $A$ ha un elemento $a\in X$ tale che non esiste alcun $x \in A$ con $xRa$. Tale $a$ si dice un elemento $R$-minimale di $X$. Si noti che in generale pu\`o esistere pi\`u di un elemento $R$-minimale di $X$.
|
||
\ed
|
||
|
||
\bexe Sia $R$ la relazione binaria su $\N$ cos\`{\i} definita: $xRy$ se $S(x) = y$. Si dimostri che $R$ \`e ben fondata. \eexe
|
||
|
||
La relazione $\leq$ sui numeri naturali non \`e ben fondata in quanto vale la propriet\`a riflessiva $x\leq x$ e una relazione riflessiva non \`e mai ben fondata. Tuttavia abbiamo:
|
||
|
||
\bexe La relazione di ordine stretto $<$ su $\N$ \`e ben fondata. \eexe
|
||
|
||
\bexa La relazione di inclusione stretta $\subset$ tra sottoinsiemi di $\omega$ non \`e ben fondata. Infatti sebbene vi sia un sottoinsieme di $\omega$ minimale rispetto all'inclusione (l'insieme vuoto) esistono famiglie di sottoinsiemi di $\omega$ all'interno delle quali non vi sono elementi minimali. Un esempio \`e dato dalla famiglia di tutte le semirette $\{x: x \geq n\}$ al variare di $n$ in $\omega$.
|
||
\eexa
|
||
|
||
\bprop Una relazione $R$ su $A$ \`e ben fondata se e solo se non esistono successioni $(a_n\mid n\in \N)$ con $a_{n+1}Ra_n$ per ogni $n\in \N$. \eprop
|
||
\bp Se esiste $(a_n\mid n\in \N)$ come sopra, allora $\{a_n \mid n \in \N\}$ non ha elementi $R$-minimali, e quindi $R$ non \`e ben fondata. Viceversa supponiamo che $R$ non sia ben fondata. Esiste dunque un insieme non vuoto $B\subseteq A$ senza elementi $R$-minimali. Definiamo ricorsivamente $a_n$ prendendo come $a_0$ un arbitrario elemento di $B$ e come $a_{n+1}$ un qualsiasi elemento $x$ di $B$ tale che $xRa_n$. Pi\`u formalmente, usando l'assioma della scelta, fissiamo una funzione $f$ che, dato $b\in B$, restituisce un elemento $f(b)\in B$ con $f(b)Rb$ (tale elemento esiste visto che $B$ non ha elementi $R$-minimali), e definiamo induttivamente $a_{n+1} = f(a_n)$.
|
||
\ep
|
||
|
||
\bexe Un ordine totale $(A,\leq)$ \`e un buon ordine se e solo se la corrispondente relazione di ordine stretto $<$ \`e ben fondata. \eexe
|
||
|
||
\section{Induzione e ricursione su relazioni ben fondate}
|
||
|
||
\bprop (Induzione ben fondata) Se $R$ \`e una relazione ben fondata su un insieme $X$ e sia $P$ una propriet\`a ben definita. Supponiamo che, dato un qualsiasi $x\in X$, sia possibile dimostrare $P(x)$ assumendo ``come ipotesi induttiva'', che $P(y)$ valga per ogni $y\in X$ con $yRx$. Detto pi\`u formalmente supponiamo che valga l'enunciato $$(\forall x \in X)\big((\forall y\in X)(yRx \to P(y)) \to P(x)\big)$$ (detto ``passo induttivo''). Allora, per ogni $x\in X$, vale $P(x)$. \eprop
|
||
\bp Se vi fosse un $a\in X$ tale che $\lnot P(a)$, consideriamo un elemento $R$-minimale $a$ tale che $\lnot P(a)$. Allora per tutti gli $y\in X$ con $yRa$ vale $P(y)$, e dunque per il passo induttivo vale anche $P(a)$. Assurdo. \ep
|
||
|
||
\br
|
||
Nel caso in cui $R$ sia la relazione $<$ sui numeri naturali $\N$, l'induzione ben fondata coincide con ``induzione forte''. Si noti che non abbiamo bisogno di un ``caso base'' dell'induzione, in quanto il ``passo induttivo''
|
||
$$(\forall x \in \N) \big((\forall y\in \N)(y<x \to P(y)) \to P(x)\big)$$ gi\`a include il caso base, come gi\`a visto nel caso dell'induzione forte sui numeri naturali.
|
||
%Ad esempio supponiamo di voler dimostrare $P(0)$. Per il passo induttivo (prendendo $x=0$) abbiamo $$(\forall y\in \N)(y<0 \to P(y)) \to P(0).$$
|
||
%D'altra parte l'implicazione $y<0 \to P(y)$ vale ``a vuoto'' per ogni $y$ (in quanto la premessa $y<0$ \`e sempre falsa) e dunque dal passo induttivo otteniamo $P(0)$.
|
||
\er
|
||
|
||
%\section{Ricursione su relazioni ben fondate}
|
||
Diamo qui sotto una versione molto generale del teorema di ricursione, che permette definizioni ricorsive non solo sui numeri naturali, ma su qualunque insieme dotato di una relazione ben fondata $R$.
|
||
|
||
\begin{theorem} \label{ricBN} (Teorema di ricursione per relazioni ben fondate)
|
||
Sia $R$ una relazione ben fondata su un insieme $A$. Sia $H:A\times V \to V$ una funzione.
|
||
Esiste una ed una sola funzione $F:A\to V$ tale che per ogni $a\in A$ si ha
|
||
$$
|
||
F(a) = H(a, F\rest{{\{x : xRa\}}})
|
||
$$
|
||
L'ipotesi che $A$ sia un insieme pu\`o essere rilassata. Possiamo permettere ad $A$ di essere una classe, ma in questo caso abbiamo bisogno di una ipotesi in pi\`u su $R$, ovvero che per ogni $a\in A$ la classe $\{x: xRa\}$ sia un insieme (altrimenti $F\rest{{\{x : xRa\}}}$ sarebbe una classe e non potrebbe essere fornita in input ad $H$).
|
||
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
(Unicit\`a) Supponiamo che $G$ sia una funzione che verifica la stessa equazione di $F$, ovvero per ogni $a\in A$ si abbia \[G(a) = H(a, G\rest{\{x : xRa\}}).\]
|
||
Vogliamo dimostrare che $G(a) = F(a)$ per ogni $a\in A$. Se per assurdo cos\`{\i} non fosse, consideriamo un elemento $R$-minimale $a\in A$ tale che $G(a) \neq F(a)$. Per tale $a$ dobbiamo allora avere $F\rest{\{x: xRa\}} = G\rest{\{x: xRa\}}$. Ci\`o \`e assurdo in quanto $F(a) = H(a, F\rest{\{x: xRa\}} ) = G(a, G\rest{\{x: xRa\}} ) = G(a)$.
|
||
|
||
(Esistenza)
|
||
Dato un sottoinsieme $B$ di $A$ diciamo che $B$ \`e buono
|
||
se esiste una funzione $g$ con $\dom(g)=B$ e tale che
|
||
$\forall a\in B$ si abbia $\{x : xRa\} \subseteq B$ e
|
||
\[g(a) = H(a, g\rest{ { \{x \mid xRa\} } } ).\]
|
||
La restrizione di $R$ a $B$ \`e ben fondata, e quindi per la prima parte
|
||
del teorema se una tale $g$ esiste essa \`e unica.
|
||
Ad ogni $B$ buono possiamo quindi associare un'unica funzione $g=g_B$ (tramite una funzione classe che manda $B$ in $g_B$).
|
||
Lo stesso ragionamento mostra che se $B$ e $B'$ sono entrambi buoni allora $B\cap B'$ \`e buono e $g_B$ coincide con $g_{B'}$ su $B\cap B'$. Consideriamo la classe $\{g_B \mid B \mbox{ \`e
|
||
buono}\}$ e la sua unione
|
||
\[F= \bigcup_{B \mbox{ buono}} g_B.\]
|
||
Tale $F$ \`e una funzione classe (in quanto unione di una classe di funzioni che coincidono a due a due sul dominio comune) e ha come dominio l'unione di tutti i sottoinsiemi buoni.
|
||
Inoltre $F$ estende ogni $g_B$ e
|
||
pertanto verifica ancora l'equazione ricorsiva $F(b) = H(b, F\rest{\{x \mid
|
||
xRb\}})$ per ogni $b\in \dom(F)$. (Basta infatti, dato $b\in \dom(F)$,
|
||
considerare un $B$ buono con $b\in B$ ed usare la condizione per $g_B$.)
|
||
|
||
Resta da dimostrare che $\dom(F) = A$. Consideriamo per assurdo un elemento $R$-minimale $a\in A$ tale che $a\nin \dom(F)$. Per ogni $b$ con $bRa$ esiste dunque una funzione $g$ con dominio buono tale che $b\in \dom(g)$. Di tali funzioni ne possono esistere pi\`u di una, ma possiamo prendere quella con il dominio pi\`u piccolo possibile, chiamiamola $g_b$, che sicuramente esiste perch\'e basta prendere l'intersezione di tutti gli insiemi buoni che contengono $b$. Siccome $\{b: bRa\}$ \`e un insieme per le nostre ipotesi, la classe $\{g_b: bRa\}$ \`e un insieme per l'assioma di rimpiazzamento, e pertanto l'unione $g = \bigcup \{g_b : bRa\}$ \`e ancora un insieme. Poich\`e le $g_b$ coincidono a due a due sul dominio comune (per la parte sull'unicit\`a), $g$ \`e una funzione, e verifica ancora l'equazione ricorsiva. Pertanto il dominio di $g$ \`e buono, ed include $\{b: bRa\}$. Possiamo estendere $g$ ad una funzione $f$ il cui dominio include anche $a$ definendo $f(a) = H(a, g\rest{\{b: bRa\}})$ e ponendo $f=g$ sugli elementi del dominio di $g$. Siccome anche $f$ verifica l'equazione ricorsiva, abbiamo dimostrato che $a$ appartiene ad un insieme buono, e dunque $a\in \dom(F)$, contro l'ipotesi. Questo assurdo mostra che $\dom(F) = A$.
|
||
\end{proof}
|
||
|
||
\bexe (Funzione di Ackermann) Si dimostri che esiste una e una sola funzione $f: \N\times \N \to \N$ tale che:
|
||
$$f(m, n) =
|
||
\begin{cases}
|
||
n+1 & \mbox{se } m = 0 \\
|
||
f(m-1, 1) & \mbox{se } m > 0 \mbox{ and } n = 0 \\
|
||
f(m-1, f(m, n-1)) & \mbox{se} m > 0 \mbox{ and } n > 0.
|
||
\end{cases}
|
||
$$
|
||
\eexe
|
||
|
||
La funzione di Ackermann cresce molto velocemente: si provi a calcolarne alcuni valori, come ad esempio $f(2,2)$ o $f(3,2)$.
|
||
\bp (Suggerimento) Si definisca una relazione ben fondata $R$ su $\N\times \N$ nel modo seguente: $(x,y) R (x',y')$ se $x<x'$ oppure $x=x'$ e $y<y'$. Si applichi il teorema di ricursione con questa relazione ben fondata. \ep
|
||
|
||
\section{Rango di una relazione ben fondata}
|
||
|
||
\bt Una relazione binaria $R$ su un insieme $A$ \`e ben fondata se e solo se esiste una funzione $\rho: A \to ON$ tale che per ogni $x,y\in A$ con $xRy$ si ha $\rho(x) < \rho(y)$.
|
||
\et
|
||
\bp Se $\rho$ esiste, $R$ deve essere ben fondata, altrimenti esisterebbe una successione infinita decrescente $a_{n+1}Ra_n$ di elementi $a_n\in A$ che darebbe luogo ad una successione infinita descrescente $\rho(a_n)$ di ordinali (cosa impossibile).
|
||
|
||
Viceversa, supponendo $R$ ben fondata, definiamo per ricursione transfinita una funzione $\rho: A \to V$ ponendo, per ogni $a\in A$, $$\rho(a) = \bigcup \{\rho(b)+1: bRa\},$$ dove $x+1 = x\cup \{x\}$. Verifichiamo che $\rho$ fa il lavoro richiesto.
|
||
Innanzitutto mostriamo che per ogni $a\in A$ $\rho(a)$ \`e un ordinale. Dato $a\in A$, per induzione ben fondata possiamo supporre che per ogni $b$ con $bRa$ l'insieme $\rho(b)$ sia un ordinale. Ma allora lo \`e anche $\rho(b)+1$ e pertanto anche $\rho(a)$, essendo un'unione di un insieme di ordinali.
|
||
Il resto \`e chiaro: $\rho(a) = \sup \{\rho(b)+1: bRa\}$, e quindi $\rho(a) > \rho(b)$ per ogni $bRa$.
|
||
\ep
|
||
|
||
\bexe Sia $R$ la relazione su $\N$ definita da $xRy$ se e solo se $x$ divide $y$ ed $x\neq y$. Si definisca $\rho$ come sopra e si calcoli $\rho(72)$. \eexe
|
||
|
||
\bexe L'immagine della funzione $\rho$ sopra definita \`e un insieme transitivo di ordinali, e pertanto \`e un ordinale. \eexe
|
||
\bp Sia $a\in A$ e sia $\beta<\rho(a)$ un ordinale. Dobbiamo mostrare che esiste $c\in A$ con $\rho(c) = \beta$. Lo dimostriamo per induzione ben fondata su $a$. Siccome $\beta < \rho(a) = \sup \{\rho(b)+1: bRa\}$, esiste un $b$ con $bRa$ tale che $\beta < \rho(b)+1$. Se $\beta = \rho(b)$ abbiamo concluso. Nel caso contrario $\beta < \rho(b)$ e visto che $bRa$ per induzione esiste $c\in A$ con $\rho(c) = \beta$.
|
||
\ep
|
||
|
||
\bd La funzione $\rho$ sopra definita si dice funzione rango associata a $(A,R)$. La sua immagine \`e un ordinale, detto il rango di $(A,R)$. \ed
|
||
|
||
\bexe Se $(A,R)$ \`e un buon ordine, la $\rho$ \`e iniettiva. \eexe
|
||
|
||
\bexe Sia $R$ la relazione binaria su $\omega \times \omega$ definita come segue. $(x,y)R(x',y')$ se $x\leq x', y\leq y'$ e almeno una delle due disuguaglianze \`e stretta. Si dimostri che $R$ \`e ben fondata e si calcoli il rango di $(\omega\times \omega, R)$. \eexe
|
||
|
||
|
||
\section{Ordinale associato ad un buon ordine}
|
||
|
||
\bt
|
||
Dato un buon ordine $\leq_A$ su un insieme $A$, esiste uno ed uno solo ordinale $\alpha$ tale che $(A,<_A)$ \`e isomorfo ad $(\alpha, \in)$. Tale $\alpha$ viene chiamato il tipo d'ordine di $(A,\leq_A)$ (secondo von Neumann). \et
|
||
\bp L'unicit\`a segue dal Lemma \ref{unicita-ordinali}. Mostriamo l'esistenza.
|
||
Definiamo $F: A \to V$ per ricursione transfinita come segue:
|
||
$$F(a) = \{F(b) : b<_A a\}.$$
|
||
Sia $\alpha = \im(F)$. Dobbiamo verificare che $\alpha$ \`e un ordinale e che $F: (A,<_A) \to (\alpha, \in)$ \`e un isomorfismo.
|
||
|
||
Mostriamo che $\alpha$ \`e transitivo: se $x\in y\in \alpha$, allora $y = F(a)$ per qualche $a\in A$, e siccome tutti gli elementi di $F(a)$ sono della forma $F(b)$ per qualche $b\in A$, abbiamo $x\in \im(F) = \alpha$.
|
||
|
||
Un ragionamento simile mostra che, per ogni $a\in A$, $F(a)$ \`e transitivo. Infatti se $x\in y \in F(a)$, abbiamo $y=F(b)$ per qualche $b<_A a$ e quindi $x = F(c)$ per qualche $c<_A b$. Ma essendo $<_A$ transitiva otteniamo $c<_A a$ e quindi $x\in F(a)$.
|
||
|
||
Per induzione su $a$ mostriamo ora che $F(a)$ \`e un ordinale. Per ipotesi induttiva se $bRa$ allora $F(b)$ \`e un ordinale. Ne segue che $F(a) = \{F(b) : b<_A a\}$ \`e un insieme transitivo di ordinali, e pertanto \`e un ordinale.
|
||
|
||
Osserviamo ora che se vale $b<_A a$, per definizione di $F$ deve valere $F(b) \in F(a)$, ovvero $F(b) < F(a)$ come ordinali. Abbiamo quindi dimostrato che $F$ \`e una funzione crescente da $(A,<_A)$ ad $\alpha = \im(F)$, e pertanto \`e un isomorfismo d'ordine.
|
||
\ep
|
||
|
||
\bexe La $F$ nella dimostrazione appena data non \`e altro che la funzione rango: $F(a) = \sup\{F(b)+1: b<_A a\}$. \eexe
|
||
|
||
\bexe Dati due buoni ordini $(A, \leq_A)$ e $(B,\leq_B)$ con tipi d'ordine $\alpha$ e $\beta$ rispettivamente, si ha che $(A,\leq_A)$ \`e isomorfo ad un segmento iniziale di $(B,\leq_B)$ se e solo se $\alpha \leq \beta$. \eexe
|
||
|
||
\bc Dati due buoni ordini, uno dei due \`e isomorfo ad un segmento iniziale dell'altro. \ec
|
||
\bp Siccome ogni buon ordine \`e isomorfo ad un ordinale, possiamo ricondurci al caso in cui i due buoni ordini siano due ordinali. Ma gi\`a sappiamo che dati due ordinali uno dei due \`e uguale (non solo isomorfo) ad un segmento iniziale dell'altro. \ep
|
||
|
||
\bexe Dato un buon ordine $(X,\leq)$ indichiamo con $\tipo(X,<)\in ON$ il tipo d'ordine di $(X,<)$, ovvero l'unico ordinale isomorfo a $(X,<)$. Si dimostri che se $X = \bigcup_{i\in I}X_i$ e gli $X_i$ sono segmenti iniziali di $X$, allora $\tipo(X,<) = \sup_{i\in I} \tipo(X_i,<)$. \eexe
|
||
|
||
\section{Funzione di Hartogs}
|
||
|
||
\bd Dato un insieme $X$ sia $H(X)$ la classe degli ordinali $\alpha$ di cardinalit\`a $\leq |X|$, ovvero tali che esiste una funzione iniettiva da $\alpha$ ad $X$. \ed
|
||
|
||
Ad esempio $H(\omega)$ \`e la classe degli ordinali numerabili (o finiti). Faremo vedere che $H(\omega)$ \`e pi\`u che numerabile.
|
||
|
||
\bprop $H(X)$ <20> un insieme. \eprop
|
||
\bp Consideriamo la classe $Z$ consistente delle coppie $(B,<_B)$ tali che $B\subseteq X$ e $<_B$ \`e un buon ordine su $B$. Ciascuna coppia $(B,<_B)$ della classe appartiene all'insieme $\parti(X)\times \parti(X\times X)$ e pertanto $Z$ stesso \`e un insieme per lo schema di assiomi di comprensione. Chiaramente un ordinale $\alpha$ appartiene a $H(X)$ se e solo se \`e il tipo d'ordine di qualche $(B,<_B)\in Z$ (in quanto data una funzione iniettiva $f$ da $\alpha$ ad $X$ possiamo usare $f$ per definire un buon ordine sull'immagine $B$ di $f$ copiando l'ordine che abbiamo su $\alpha$). Ne segue che $H(X)$ \`e l'immagine di $Z$ tramite la funzione-classe ``tipo d'ordine'', e pertanto \`e un insieme per lo schema di assiomi di rimpiazzamento. \ep
|
||
|
||
\bprop $H(X)$ \`e un ordinale. \eprop
|
||
\bp Chiaramente $H(X)\subseteq ON$, quindi basta mostrare che $H(X)$ \`e transitivo. Se $\alpha<\beta<H(X)$, allora $|\alpha|\leq |\beta|\leq |X|$ e quindi $\alpha \in H(X)$. \ep
|
||
|
||
\bt (Hartogs) $|H(X)|\not\leq |X|$. \et
|
||
\bp Altrimenti $H(X)\in H(X)$, il che \`e impossibile essendo $H(X)$ un ordinale. \ep
|
||
|
||
Ancora non abbiamo dimostrato che dati due insiemi uno dei due ha cardinalit\`a maggiore o uguale all'altro, quindi dalla proposizione precedente non possiamo ancora concludere che $|H(X)|>|X|$. Tuttavia visto che due ordinali sono sempre uno incluso nell'altro, le cardinalitl\`a degli ordinali sono sempre confrontabili e otteniamo:
|
||
|
||
\bc Se $X$ \`e un ordinale, allora $|H(X)|>|X|$. \ec
|
||
|
||
In particolare $H(\omega)$ ha cardinalit\`a $>|\omega|$, ovvero esiste una quantit\`a pi\`u che numerabile di ordinali numerabili. In generale dato un ordinale $\alpha$ esiste una quantit\`a pi\`u che numerabile di ordinali di cardinalit\`a $\leq |\alpha|$ (in quanto $|H(\alpha)|>|\alpha|$). Abbiamo anche dimostrato che non esiste un ordinale di cardinalit\`a massima.
|
||
|
||
|
||
\section{Teorema di Zermelo}
|
||
|
||
\bt (Zermelo) Ogni insieme $X$ pu\`o essere bene ordinato. \et
|
||
\bp Basta dimostrare che $X$ pu\`o essere messo in corrispondenza biunivoca con un ordinale. Per l'assioma della scelta esiste una funzione $h$ che associa a ciascun sottoinsieme non vuoto $A$ di $X$ un suo elemento $h(A)\in A$ e chiamiamo $h(A)$ l'elemento selezionato di $A$. Fissiamo un elemento $a\nin X$ e sia $\alpha$ un ordinale tale che non esista una funzione iniettiva da $\alpha$ ad $X\cup \{b\}$. Tale ordinale esiste per il teorema di Hartogs (basta prendere $H(X\cup \{b\})$). Definiamo $F: \alpha \to X \cup \{a\}$ per ricursione sugli ordinali ponendo $F(\alpha)$ come l'elemento selezionato tra gli elementi di $X$ che non appartengono all'immagine di $F$ ristretta agli ordinali minori di $\alpha$, ovvero
|
||
$$F(\alpha) = h(X \setminus \{F(\beta): \beta < \alpha\}),$$
|
||
sempre che l'insieme sia non vuoto.
|
||
Se invece $X \setminus \{F(\beta): \beta < \alpha\}$ \`e vuoto diamo ad $F(\alpha)$ il valore convenzionale $a$. Per definizione di $\alpha$, $F$ non pu\`o essere iniettiva. D'altra parte se $F$ non assumesse mai il valore $a$ sarebbe iniettiva in quanto per definizione $F(\alpha)$ \`e scelto tra gli elementi di $X$ diversi da $F(\beta)$ per ogni $\beta<\alpha$. Quindi esiste un minimo ordinale $\alpha$ tale che $F(\alpha) = a$. Per definizione di $F$ ci\`o pu\`o capitare solo se
|
||
$X \setminus \{F(\beta): \beta < \alpha\}$ \`e vuoto, ovvero $X = \{F(\beta) : \beta < \alpha\} = \im(F \;\rest{\alpha})$. Per la minimalit\`a di $\alpha$, $F \;\rest{\alpha}: \alpha \to X$ \`e iniettiva, e dunque biunivoca. \ep
|
||
|
||
Abbiamo anche dimostrato:
|
||
|
||
\bt Ogni insieme pu\`o essere messo in corrispondenza biunivoca con un ordinale. \et
|
||
|
||
\bc \label{Card-tot} Dati due insiemi $X$ ed $Y$, abbiamo $|X| \leq |Y|$ o $|Y| \leq |X|$. \ec
|
||
\bp Per il teorema precedente e il fatto che due ordinali sono l'uno incluso nell'altro. \ep
|
||
|
||
\section{Lemma di Zorn}
|
||
|
||
\begin{definition} Sia $(A,\leq)$ un ordine
|
||
parziale. Sia $B\subseteq A$. Diciamo che $B$ \`e una catena se per
|
||
ogni coppia di elementi distinti $x,y \in B$ sia ha $x\leq y$ o $y \leq x$. In
|
||
altre parole $B$ \`e una catena se \`e un ordine totale rispetto
|
||
all'ordine indotto da $(P,\leq)$. Un elemento $a\in A$ viene detto un
|
||
maggiorante della catena $B\subseteq A$ se per ogni $b\in B$ sia ha
|
||
$b\leq a$ (tale $a$ pu\`o appartenere o no alla catena). Diciamo che
|
||
$x\in A$ \`e un elemento massimale di $(A,\leq)$ se non esiste alcun
|
||
$y\in A$ con $x<y$.
|
||
\end{definition}
|
||
|
||
Un ordine parziale pu\`o avere o non avere un elemento massimale (ad
|
||
esempio $\N$ non ne ha) e nel caso ne abbia pu\`o averne pi\`u di
|
||
uno. Non bisogna confondere massimale con massimo: un elemento $x$ di
|
||
un insieme ordinato $(A,\leq)$ \`e un massimo se per ogni $y\in A$ si
|
||
ha $y\leq x$. Di elementi massimi ce ne pu\`o essere al pi\`u uno e se
|
||
esiste un massimo esso \`e anche massimale. Se $(A,\leq)$ \`e un
|
||
ordine totale il concetto di massimo e di massimale coincidono.
|
||
|
||
\begin{theorem}(Lemma di Zorn)
|
||
Sia $P$ un insieme e $\leq$ un ordine parziale su $P$ tale che ogni catena ha un maggiorante.
|
||
Allora esiste almeno un elemento $x\in P$ massimale. \end{theorem}
|
||
\bp (Usando l'assioma di Scelta) Supponiamo che non esista alcun elemento massimale e definiamo $x_\alpha\in P$ per ricursione su $\alpha\in ON$ prendendo come $x_0$ un qualsiasi elemento di $P$, come $x_{\alpha+1}$ un elemento maggiore di $x_\alpha$ (esiste perch\'e stiamo assumendo che non vi sia un elemento massimale), e come $x_\lambda$, per $\lambda$ limite, un maggiorante della catena degli $x_\beta$ per $\beta<\lambda$. Per scegliere questi elementi tra le varie possibilit\`a usiamo una funzione di scelta. In tal modo otteniamo una funzione iniettiva da ON a P, il che \`e assurdo in quanto ON \`e una classe propria e P \`e un insieme (considerando la funzione inversa risulta violato l'assioma di rimpiazzamento). \ep
|
||
|
||
|
||
Il lemma di Zorn viene spesso usato nelle dimostrazioni di esistenza non costruttive in matematica. Ad esempio pu\`o essere usato per dimostrare che ogni spazio vettoriale, anche di dimensione infinita, ha una base. In particolare pu\`o essere usato per dimostrare che esiste una base di $\R$ come spazio vettoriale su $\Q$.
|
||
|
||
A partire dal Lemma di Zorn possiamo dare una nuova dimostrazione del teorema di Zermelo.
|
||
|
||
\begin{theorem} Il lemma di Zorn implica il teorema di Zermelo: ogni insieme $X$ pu\`o essere bene ordinato.
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Vogliamo dimostrare l'esistenza di un buon ordinamento su $X$. Sia
|
||
$P$ l'insieme di tutte le coppie della forma $(A,\leq)$ dove $A$ \`e
|
||
un sottoinsieme di $X$ e $\leq$ \`e un buon ordine su $A$. Chiaramente
|
||
$P$ \`e non vuoto in quanto ad esempio ogni sottoinsieme finito di $X$
|
||
pu\`o essere bene ordinato. Mettiamo su $P$ il seguente ordine
|
||
parziale $\preceq$: diciamo che $(A,\leq) \preceq (A', \leq')$ se e
|
||
solo se $(A,\leq)$ \`e un segmento iniziale di $(A',\leq')$ (cio\`e
|
||
$A$ \`e un segmento iniziale di $(A',\leq')$ e $\leq$ coincide con la
|
||
restrizione di $\leq'$ ad $A$). Ogni catena in $(P,\leq)$ ha un maggiorante data dall'unione dei buoni ordini della catena (verificate!), e quindi per il lemma di Zorn esiste un elemento massimale $(M,\leq)$ in $P$. Per finire
|
||
dimostriamo che $M=X$. Nel caso contrario sia $a \in X \setminus M$, e
|
||
definiamo un buon ordinamento $\leq'$ su $M \cup \{a\}$ mantenendo su
|
||
$M$ il precedente ordinamento $\leq$ e stabilendo che $a$ \`e maggiore
|
||
rispetto ad $\leq'$ di ogni elemento di $M$. Evidentemente $(M,\leq)$
|
||
\`e un segmento iniziale di $(M\cup \{a\}, \leq')$, contraddicendo la
|
||
massimalit\`a di $(M,\leq)$ in $P$.
|
||
\end{proof}
|
||
|
||
Per chiudere il cerchio dimostriamo l'assioma della scelta a partire dal teorema di Zermelo.
|
||
|
||
\bt Il teorema di Zermelo implica l'assioma di scelta. \et
|
||
\bp Dato un insieme $X$ per trovare una funzione di scelta $f: \parti(X) \setminus \{\emptyset\} \to X$ basta bene ordinare $X$ e, per ogni sottoinsieme non vuoto $Y$ di $X$, definire $f(Y)$ come il minimo di $Y$. \ep
|
||
|
||
\section{Cardinali come ordinali iniziali}
|
||
|
||
\begin{definition}
|
||
Un buon ordine $(A,\leq)$ si dice iniziale se e solo se ogni suo
|
||
segmento iniziale proprio ha cardinali\`a inferiore a quella di $A$.
|
||
Un ordinale $\alpha$ si dice iniziale se \`e il tipo d'ordine di un
|
||
buon ordine iniziale.
|
||
\end{definition}
|
||
|
||
\begin{example} $0, 1, 2, 3, \ldots$, $\omega$ sono ordinali iniziali. $\omega+1$,
|
||
$\omega+2$, $\omega+\omega$ non lo sono. Attenzione: qui il simbolo $+$ indica
|
||
la somma ordinale, non cardinale.
|
||
\end{example}
|
||
|
||
\begin{exercise}
|
||
Tutti gli ordinali iniziali infiniti sono ordinali limite, ma non \`e
|
||
vero il viceversa: ad esempio $\omega + \omega$ \`e un ordinale limite non iniziale.
|
||
\end{exercise}
|
||
|
||
\bt
|
||
Per ogni insieme $X$ esiste uno ed un solo ordinale iniziale $\alpha$
|
||
della stessa cardinalit\`a di $X$.
|
||
\et
|
||
|
||
\bp
|
||
Bene ordiniamo $X$ e sia $\beta$ il tipo d'ordine di $X$ con il dato buon ordine.
|
||
Ora sia $\alpha$ il minimo ordinale della stessa cardinali\`a di $\beta$.
|
||
\ep
|
||
|
||
Possiamo ora ridefinire $|X|$ come segue.
|
||
|
||
\begin{definition}
|
||
$|X| = $ l'unico ordinale iniziale della stessa cardinalit\`a di $X$.
|
||
Identifichiamo quindi gli ordinali iniziali con i numeri cardinali.
|
||
\end{definition}
|
||
|
||
Abbiamo in questo modo due definizioni di $|X|$. Quella di Frege, secondo cui $|X|$ \`e la classe di equivalenza tutti gli insiemi equipotenti a $X$, e quella di von Neumann secondo cui $|X|$ \`e l'unico ordinale iniziale equipotente ad $X$. Le due definizioni non sono in conflitto. Secondo entrambe le definizioni si ha che $|X|\leq |Y|$ se e solo se esiste una funzioni iniettiva da $X$ ad $Y$, e ci\`o equivale al fatto che $|X|$, visto come ordinale iniziale, \`e minore o uguale (ovvero incluso) a $|Y|$ visto come ordinale iniziale.
|
||
|
||
Il fatto che i cardinali possano essere identificati con una
|
||
una sottoclasse degli ordinali (quelli iniziali) implica che anche per
|
||
i cardinali valga un principio del minimo.
|
||
|
||
\begin{corollary} Ogni classe non vuota di cardinali ha un minimo elemento.
|
||
\end{corollary}
|
||
|
||
Aver identificato i cardinali con gli ordinali iniziali
|
||
non significa per\`o che la somma che abbiamo definito sui
|
||
cardinali coincida con la somma definita sugli ordinali. Ad esempio nonostante il cardinale $\aleph_0$ coincida con l'ordinale iniziale $\omega$, abbiamo $\aleph_0 + 1 = \aleph_0$ (aggiungere un elemento ad un insieme
|
||
numerabile non cambia la cardinalit\`a), ma $\omega + 1 \neq
|
||
\omega$ (aggiungere un elemento in fondo ad un buon ordine ne cambia
|
||
il tipo d'ordine). Il punto \`e che nei due casi il $+$ ha un significato diverso. Quando usiamo la notazione $\aleph_0$ usiamo le operazioni cardinali, quando usiamo la notazione $\omega$ usiamo le operazioni ordinali.
|
||
|
||
\begin{exercise}
|
||
Se $\alpha \in Ord$,
|
||
$|\alpha| \leq \alpha$. Ad esempio $|\omega + \omega| = \omega <
|
||
\omega + \omega$.
|
||
\end{exercise}
|
||
|
||
\section{La funzione aleph}
|
||
|
||
\begin{lemma} Per ogni cardinale $\alpha$ esiste un cardinale $\alpha^+$
|
||
pi\`u grande di $\alpha$ tale che non c\`e nessun cardinale tra $\alpha$ e
|
||
$\alpha^+$. \end{lemma}
|
||
\begin{proof}
|
||
Basta porre $\alpha^+ = H(\alpha)$ dove $H$ \`e la funzione di Hartogs. Sappiamo gi\`a che $|H(\alpha)|>|\alpha|=\alpha$. Se per assurdo esistesse un cardinale $\kappa$ tale che $\alpha<\kappa<H(\alpha)$, allora la cardinalit\`a di $\kappa$ dovrebbe essere sia minore o uguale ad $\alpha$ (essendo $\kappa\in H(\alpha)$) sia maggiore stretto (essendo $\alpha,\kappa$ cardinali con $\alpha<\kappa$).
|
||
\end{proof}
|
||
|
||
Alternativamente avremmo potuto ragionare come segue. Sicuramente esiste un cardinale pi\`u grande di $\alpha$ (ad esempio
|
||
$2^{\alpha}$). Quindi esiste un minimo cardinale pi\`u
|
||
grande di $\alpha$. Questa seconda dimostrazione usa l'assioma della scelta per dimostrare che $2^{\alpha}$ \`e ben definito come ordinale iniziale (occorre trovare un ordinale iniziale in bigezione con l'insieme delle funzioni da $\alpha$ a $2$, e per far ci\`o occorre bene ordinare tale insieme). La prima dimostrazione invece mostra, senza usare la scelta, che per ogni ordinale iniziale $\alpha$ esiste un ordinale iniziale $\alpha^+=H(\alpha)$ di cardinalit\`a immediatamente pi\`u grande.
|
||
|
||
In base al lemma possiamo definire $\aleph_1 = {\aleph_0}^+$, $\aleph_2 =
|
||
{\aleph_1}^+$ e cos\`{\i} via. Si noti che $\aleph_0 < \aleph_1 \leq
|
||
2^{\aleph_0} = |\R|$. Dai lavori di G\"odel (1941) e Cohen (1963) sappiamo che non si pu\`o determinare in base agli assiomi se valga l'uguaglianza $\aleph_1 = 2^{\aleph_0}$.
|
||
|
||
\begin{theorem} Se $X$ \`e un insieme di ordinali iniziali, $\sup
|
||
X$ \`e un ordinale iniziale. \end{theorem}
|
||
|
||
\begin{proof}
|
||
Se $\sup X$ non \`e iniziale esiste un ordinale iniziale $\kappa <
|
||
\sup X$ della stessa cardinalit\`a di $\sup X$. Per definizione di
|
||
$\sup$, esiste $\beta \in X$ con $\kappa < \beta \leq \sup X$. Visto
|
||
che la relazione $\leq$ tra ordinali coincide con l'inclusione $\subseteq$,
|
||
e visto che $\kappa$ e $\sup X$ hanno la stessa cardinalit\`a, ne
|
||
segue che anche $\beta$, essendo compreso tra i due, ha la stessa
|
||
cardinalit\`a. Questo \`e assurdo in quanto $\beta$ \`e iniziale, e
|
||
non pu\`o pertanto avere la stessa cardinalit\`a di un ordinale pi\`u piccolo.
|
||
\end{proof}
|
||
|
||
\bd
|
||
Definiamo per ricursione transfinita:
|
||
\[
|
||
\begin{array}{lcl}
|
||
\aleph_0 & = & |\N|,\\
|
||
\aleph_{\alpha+1} & = & \aleph_\alpha^+, \\
|
||
\aleph_\alpha & = & \sup \{\aleph_\beta \mid \beta < \alpha\} \mbox{ se $\alpha$
|
||
\`e un ordinale limite }.
|
||
\end{array}
|
||
\]
|
||
\ed
|
||
|
||
\bexe Se $\alpha < \beta$, allora $\aleph_\alpha < \aleph_\beta$. \eexe
|
||
|
||
\bt La funzione $\alpha\mapsto \aleph_\alpha$ \`e una bigezione dalla classe $ON$ degli ordinali verso la classe dei cardinali infiniti. \et
|
||
\bp Sia $\kappa$ un cardinale infinito. Dobbiamo mostrare che esiste un ordinale $\alpha$ tale che $\kappa = \aleph_\alpha$. Sia $\alpha$ l'estremo superiore dell'insieme $X$ degli ordinali $\beta$ tali che $\aleph_\beta \leq \kappa$. In base alle definizioni, distinguendo i due casi in cui $X$ ha un massimo e il caso in cui non lo ha, si deve in ogni caso avere $\aleph_\alpha = \aleph_{\sup(X)} = \sup_{\beta \in X}\aleph_\beta \leq \kappa$. Se fosse $\aleph_\alpha < \kappa$ avremmo $\aleph_{\alpha+1} \leq \kappa$ contraddicendo la definizione di $\alpha$. Ne segue che $\aleph_\alpha = \kappa$.
|
||
\ep
|
||
|
||
\bd L'ordinale iniziale $\aleph_\alpha$ viene anche indicato con la notazione $\omega_\alpha$. Usiamo la prima notazione quanto lo pensiamo come cardinale, e la seconda quanto lo pensiamo come ordinale. Ad esempio se scriviamo $\aleph_\alpha + \aleph_\beta$ intendiamo la somma cardinale (che, come vedremo, fornisce come risultato $\max\{\aleph_\alpha, \aleph_\beta\}$), mentre se scriviamo $\omega_\alpha + \omega_\beta$ intendiamo la somma ordinale, che \`e definita per ricursione sul secondo argomento. Analoghe convenzioni valgono per la moltiplicazione e l'esponenziazione. Se scriviamo $\omega^\omega$ intendiamo l'esponenziazione tra ordinali e otteniamo un ordinale numerabile, mentre se scriviamo $\aleph_0^{\aleph_0}$ otteniamo il cardinale non numerabile $2^{\aleph_0} = |\R|$. Un altro esempio \`e: $\aleph_0 + 1 = \aleph_0$ mentre $\omega_0 + 1 = \omega + 1 > \omega$. \ed
|
||
|
||
\section{Somma e prodotto di alephs}
|
||
|
||
\begin{theorem} Per ogni insieme infinito $X$ si ha $|X\times X| = |X|$.
|
||
\end{theorem}
|
||
\begin{proof} Sia $X$ un insieme di cardinalit\`a $\aleph_\theta$. Dobbiamo
|
||
trovare una corrispondenza biunivoca tra $X\times X$ ed $X$. Possiamo
|
||
supporre per ipotesi induttiva che la tesi $|Y\times Y|=|Y|$ valga per
|
||
insiemi infiniti $Y$ di cardinalit\`a strettamente inferiore a quella
|
||
di $X$. (Se no ci si riduca a questo caso considerando il minimo
|
||
cardinale per cui non valga il teorema.) Fissiamo su $X$ un buon
|
||
ordine $<$ iniziale (ovvero di tipo d'ordine $\aleph_\theta$), in modo
|
||
che i segmenti iniziali propri di $X$ abbiamo cardinalit\`a
|
||
strettamente minore a quella di $X$. L'idea ore \`e quella di cercare
|
||
di definire un buon ordine $\prec$ su $X\times X$ in modo che la
|
||
corrispondenza biunivoca cercata sia un isomorfismo
|
||
d'ordine. Ordiniamo le coppie $(\alpha, \beta) \in X\times X$ nel modo
|
||
seguente: $(\alpha, \beta) \prec (\gamma, \delta)$ se e solo se $\max
|
||
(\alpha, \beta) < \max (\gamma, \delta)$ oppure a parit\`a di massimi
|
||
$\alpha <\gamma$, oppure a parit\`a di massimi e prime componenti
|
||
$\beta < \delta$ (i massimi sono presi rispetto all'ordine
|
||
$<$). Chiaramente $\prec$ \`e un buon ordine, e per il teorema di
|
||
confrontabilit\`a dei buoni ordini abbiamo che o $(X\times X, \prec)$
|
||
e $(X, <)$ sono isomorfi oppure uno dei due \`e un segmento iniziale
|
||
proprio dell'altro. Poich\`e certamente $|X\times X|\geq |X|$, e i
|
||
segmenti iniziali propri di $X$ hanno cardinalit\`a minore di $|X|$,
|
||
una delle tre alternative si esclude subito: $X\times X$ non pu\`o
|
||
essere isomorfo ad un segmento iniziale di $X$. Resta quindi da
|
||
escludere che $X$ sia isomorfo ad un segmento proprio $J$ di $X\times
|
||
X$, e a tal fine \`e sufficiente dimostrare che ogni tale $J$ ha
|
||
cardinalit\`a $<|X|$. Per verificare quest'ultima affermazione notiamo
|
||
prendiamo un elemento $(u,v)$ in $X\times X \setminus J$. Poich\'e $J$ \`e un segmento iniziale, $(u,v)$ \`e maggiore o uguale a tutti gli elementi di $J$. Ne segue che
|
||
$J\subseteq Y\times Y$, dove $Y = \{x\in X \mid x \leq \max(u,v)\}$, e dunque $|J|\leq |Y\times Y|$. Ma $Y$ \`e un segmento iniziale proprio di $X$ (non
|
||
pu\`o essere uguale ad $X$ in quanto un buon ordine iniziale infinito
|
||
non pu\`o avere un massimo elemento), e pertanto per le nostre ipotesi
|
||
$|Y\times Y|=|Y|<|X|$, da cui la tesi. \end{proof}
|
||
|
||
\begin{theorem}
|
||
Dati due cardinali infiniti $\alpha, \beta$ si ha $\alpha + \beta =
|
||
\alpha \cdot \beta = \max \{\alpha, \beta\}$. \end{theorem}
|
||
\begin{proof}
|
||
Sia $\alpha \leq \beta$. Abbiamo $\beta \leq \alpha + \beta \leq \beta
|
||
+ \beta = \beta \cdot 2 \leq \beta \cdot \beta = \beta$. \end{proof}
|
||
|
||
\section{Teorema di K\"{o}nig}
|
||
|
||
\bd Per $i\in I$, sia $\alpha_i$ un cardinale. Definiamo la somma $\Sigma_{i\in I}\alpha_i$ come la cardinalit\`a di $\bigcup_{i\in I}A_i$ dove gli $A_i$ sono insiemi disgiunti con $|A_i| = \alpha_i$. Equivalentemente, senza assumere che gli $A_i$ siano disgiunti, $\Sigma_{i\in I} |A_i| = |\bigcup_{i\in I} A_i\times \{i\}|$. \ed
|
||
|
||
\bl Data una famiglia $(A_i: i \in I)$ di insiemi $A_i$, non necessariamente disgiunti, abbiamo $\sup_{i\in I} |A_i| \leq |\bigcup_{i\in I}A_i| \leq \Sigma_{i\in I}|A_i|$. \el
|
||
\bp La prima disuguaglianza \`e ovvia. Per la seconda basta considerare la funzione surgettiva da $\bigcup_{i\in I}A_i\!\times\! \{i\}$ in $\bigcup_{i\in I}A_i$ che manda $(x,i)$ in $x$. \ep
|
||
|
||
\bd Per $i\in I$, sia $\beta_i$ un cardinale. Definiamo il prodotto $\Pi_{i\in I}\beta_i$ come la cardinalit\`a del prodotto cartesiano infinito $ \Pi_{i\in I}B_i$ dove i $B_i$ sono insiemi con $|B_i| = \kappa_i$. \ed
|
||
|
||
|
||
\bt[Teorema di K\"{o}nig] Per ogni $i\in I$ siano $\alpha_i$ e $\beta_i$ cardinali tali che $\alpha_i<\beta_i$.
|
||
Allora $\Sigma_{i\in I}\alpha_i < \Pi_{i\in I} \beta_i$. \et
|
||
|
||
\bp
|
||
Per ogni $i\in I$ fissiamo degli insiemi $A_i \subset B_i$ con $|A_i| = \alpha_i$ e $|B_i| = \beta_i$, e definiamo $A'_i := A_i\times \{i\}$. Basta mostrare che non esistono funzioni surgettive $g$ da $\bigcup_{i\in I}A'_i$ a $\Pi_{i\in I}B_i$ (quindi in particolare non esistono funzioni biunivoche). Data $g \colon \bigcup_{i\in I}A'_i \to \Pi_{i\in I}B_i$, occorre dunque trovare un elemento $(c_i\mid i\in I)$ di $\Pi_{i\in I} B_i$ che non \`e nell'immagine di $g$. Per $j\in I$, consideriamo la funzione $g_j\colon A_j \to B_j$ ottenuta come composizione delle funzioni $A_j \stackrel{\iota_j}\to \bigcup_{i\in I}A'_i \stackrel{g}\to \Pi_{i\in I}B_i \stackrel{\pi_j}\to B_j$, dove $\iota_j(a) = (a,j)$ e $\pi_j((c_i\mid i\in I)) = c_j$. Poich\'e $|A_j|< |B_j|$, la $g_j$ non \`e surgettiva. Possiamo dunque scegliere $(c_i\mid i\in I)\in \Pi_{i\in I}B_i$ in modo che per ogni $j\in I$ $c_j\nin \im (g_j)$. Se per assurdo $(c_i\mid i\in I) = g(x)$ per qualche $x \in \bigcup_{i\in I}A'_i$, sia $j\in I$ tale che $x \in A'_j$, e scriviamo $x$ nella forma $(a,j)$ con $a\in A_j$. Per definizione di $g_j$ dobbiamo avere $g_j(a) = c_j$, ma questo \`e assurdo in quanto $c_j$ era stato scelto fuori dall'immagine di $g_j$.
|
||
\ep
|
||
|
||
Come corollario otteniamo una seconda dimostrazione del teorema di Cantor:
|
||
|
||
\bc Per ogni cardinale $\kappa$ abbiamo $\kappa < 2^\kappa$. \ec
|
||
\bp $\kappa = \Sigma_{i \in \kappa} 1 < \Pi_{i\in \kappa} 2 = 2^\kappa$. \ep
|
||
|
||
In base agli assiomi di GB non riusciamo a stabilire se $|\R|$ sia $\aleph_1$, tuttavia abbiamo:
|
||
|
||
\bc $|\R| \neq \aleph_\omega$. \ec
|
||
\bp Supponiamo per assurdo che $|\R| = \aleph_\omega$. Ne segue che, per ogni $n\in \omega$, $\aleph_n \leq \aleph_\omega = |\R| = 2^{\aleph_0}$ e quindi per il teorema di K\"onig $\Sigma_{n<\omega}\aleph_n < \Pi_{n<\omega}2^{\aleph_0}$. Questo \`e assurdo in quanto $\Pi_{n<\omega}2^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0} = |\R|$, e d'altra parte $|\R| = \aleph_\omega = \sup_{n<\omega}\aleph_n \leq \Sigma_{n<\omega}\aleph_n$.
|
||
\ep
|
||
|
||
\section{Cofinalit\`a}
|
||
|
||
\bd Siano $(A,\leq_A)$ e $(B,\leq_B)$ due insiemi ordinati. Una funzione $f: A\to B$ si dice cofinale o illimitata se l'immagine di $f$ non ha maggioranti stretti in $B$.
|
||
La cofinalit\`a di $(B,\leq_B)$ \`e il minimo ordinale $\alpha$ tale che esiste una funzione cofinale $f\colon \alpha\to (B,\leq_B)$.
|
||
\ed
|
||
|
||
\bexa L'inclusione di $\N$ in $\R$ \`e cofinale (rispetto all'usuale ordine di $\R$).
|
||
Siccome $\N$ ha tipo d'ordine $\omega$, ne segue che la cofinalit\`a di $\R$ \`e minore o uguale ad $\omega$, e visto che un insieme finito non pu\`o essere cofinale in $\R$ essa \`e esattamente $\omega$.
|
||
\eexa
|
||
|
||
\bexe La cofinalit\`a di $(A,\leq_A)$ \`e uguale ad $1$ se e solo se $(A,\leq_A)$ ha un massimo. Se la cofinalit\`a di un ordine totale \`e maggiore di $1$ essa deve essere almeno $\omega$ (ad esempio non pu\`o essere $2$). \eexe
|
||
|
||
\bd Identificando un ordinale con l'insieme ordinato degli ordinali minori di lui,
|
||
abbiamo che una funzione tra due ordinali $f\colon \alpha\to
|
||
\beta$ \`e cofinale se per ogni $\gamma < \beta$ esiste $\delta <
|
||
\alpha$ tale che $f(\delta) \geq \gamma$. La cofinalit\`a $cf(\beta)$ di $\beta$
|
||
\`e il minimo ordinale $\alpha$ tale che esiste una funzione cofinale $f\colon \alpha\to
|
||
\beta$.
|
||
\ed
|
||
|
||
|
||
\bexe
|
||
\begin{enumerate}
|
||
\item Se $\beta$ \`e un ordinale successore, $cf(\beta)=1$.
|
||
\item $cf(\omega + \omega) = \omega$ (dove $+$ indica la somma
|
||
ordinale).
|
||
\end{enumerate}
|
||
\eexe
|
||
|
||
|
||
\bl $\alpha \leq cf(\beta)$ se e solo se esiste una funzione cofinale da $\beta$ ad $\alpha$. \el
|
||
\bp Se esiste una funzione cofinale da $\beta$ ad $\alpha$, allora il minimo ordinale $\delta$ per cui esiste una funzione cofinale da $\delta$ ad $\alpha$ \`e ovviamente minore o uguale a $\beta$, ovvero $cf(\alpha) \leq \beta$. Viceversa supponiamo che $cf(\alpha) \leq \beta$ e sia $f: cf(\alpha) \to \alpha$ cofinale. Estendiamo $f$ in modo arbitrario ad una funzione $g:\beta\to \alpha$. Visto che $g$ estende $f$, \`e ancora cofinale. \ep
|
||
|
||
\bl Per ogni ordinale $\alpha$ abbiamo $cf(\alpha) \leq |\alpha| \leq \alpha$. \el
|
||
\bp Per definizione $|\alpha|$ \`e il minimo ordinale tale che esiste una funzione biunivoca da $|\alpha|$ ad $\alpha$. Ora basta osservare che ogni funzione biunivoca (o anche solamente surgettiva) \`e ovviamente cofinale. \ep
|
||
|
||
\bd
|
||
Un ordinale $\beta$ si dice regolare se $cf(\beta) = \beta$.
|
||
\ed
|
||
|
||
\bl Ogni ordinale regolare \`e un cardinale (ordinale iniziale). \el
|
||
\bp Ovvio dalle disuguaglianze $cf(\alpha) \leq |\alpha| \leq \alpha$ e dal fatto che $\alpha$ \`e un cardinale se e solo se $|\alpha| = \alpha$. \ep
|
||
|
||
\bd Un cardinale successore \`e un cardinale della forma della forma $\kappa^+$ dove $\kappa^+$ \`e il minimo cardinale maggiore di $\kappa$. Equivalentemente i cardinali successori sono i cardinali finiti e i cardinali della forma $\aleph_{\alpha+1}$ per qualche ordinale $\alpha$. \ed
|
||
|
||
\bl Ogni cardinale successore $\kappa^+$ \`e regolare. In particolare $\aleph_1$ \`e regolare. \el
|
||
\bp Supponiamo per assurdo che $cf(\kappa^+) < \kappa^+$. Ogni cardinale strettamente minore di $\kappa^+$ \`e minore o uguale a $\kappa$, e visto che $cf(\kappa^+)$ \`e un cardinale otteniamo $cf(\kappa^+) \leq \kappa$, ovvero esiste una funzione cofinale $f: \kappa \to \kappa^+$. Ci\`o ci permette di scrivere $\kappa^+ = \sup_{\alpha<\kappa}f(\alpha) = \bigcup_{\alpha<\kappa} f(\alpha)$, dove $\alpha$ varia tra gli ordinali minori di $\kappa$ (non necessariamente iniziali). Per ogni $\alpha<\kappa$, $f(\alpha) \in \kappa^+$, e visto che $\kappa^+$ \`e iniziale, $|f(\alpha)| < \kappa^+$, ovvero $|f(\alpha)| \leq \kappa$ (sebbene possa accadere che $f(\alpha) > \kappa$). Poich\'e la cardinalit\`a dell'unione \`e minore o uguale alla somma delle cardinalit\`a, abbiamo $\kappa^+ \leq \Sigma_{\alpha<\kappa}|f(\alpha)| \leq \kappa \cdot \kappa = \kappa$, il che \`e assurdo. \ep
|
||
|
||
\bexa $\aleph_\omega$ e $\aleph_{\omega+\omega}$ hanno cofinalit\`a $\omega$, quindi non sono regolari. \eexa
|
||
\bp Basta considerare le funzioni cofinali $n\mapsto \aleph_n$ e $n \mapsto \aleph_{\omega+n}$. \ep
|
||
|
||
\bexe Un cardinale $\kappa$ \`e regolare se e solo se per ogni famiglia $(A_i \mid i\in
|
||
I)$ di insiemi $A_i$ tali che $|A_i|<\kappa$ e $|I|<\kappa$, si ha
|
||
$|\bigcup_{i\in I}A_i| < \kappa$.
|
||
\eexe
|
||
|
||
\bt Per ogni ordinale $\alpha$, $cf(2^{\aleph_\alpha}) > \aleph_\alpha$. \et
|
||
\bp Sia $\theta = cf(2^{\aleph_\alpha})$. Possiamo allora scrivere $2^{\aleph_\alpha} = \Sigma_{\nu < \theta} \kappa_\nu$ dove $\kappa_
|
||
\nu$ \`e un cardinale minore di $2^{\aleph_\alpha}$. Per il teorema di K\"onig $\Sigma_{\nu < \theta} \kappa_
|
||
u < \Pi_{\nu < \theta} 2^{\aleph_\alpha}= {(2^{\aleph_\alpha})}^\theta$. Se fosse $\theta \leq \aleph_\alpha$, avremmo l'assurdo $2^{\aleph_\alpha} < {(2^{\aleph_\alpha})}^\theta=2^{\aleph_\alpha \cdot \theta}= 2^{\aleph_\alpha}$.
|
||
\ep
|
||
|
||
\bc La cofinalit\`a di $2^{\aleph_0}$ \`e diversa da $\omega$. Quindi in particolare $2^{\aleph_0}$ \`e diverso sia da $\aleph_\omega$ (gi\`a lo sapevamo) che da $\aleph_{\omega+\omega}$ (ma non si pu\`o stabilire, in base agli assiomi, se sia pi\`u grande o pi\`u piccolo). \ec
|
||
|
||
\section{Gerarchia di von Neumann}
|
||
|
||
\begin{axiom} L'assioma di fondazione dice che ogni insieme non vuoto $X$ contiene un elemento $a$ che \`e disgiunto da $X$ (ricordiamo che stiamo assumendo che non vi siano urelementi, ovvero ogni oggetto \`e un insieme). \end{axiom}
|
||
|
||
\bexe L'assioma di fondazione equivale al fatto che la relazione di appartenenza su $V$ sia ben fondata. \eexe
|
||
\bp Assumiamo la fondazione. Se per assurdo $\in$ non \`e ben fondata su $V$ esiste un sottoinsieme non vuoto $X$ di $V$ senza elementi $\in$-minimali, ovvero per ogni $a\in X$ esiste $b\in X$ con $b\in a$. Questo significa in particolare che $a\cap X \neq \emptyset$ (in quanto $b$ vi appartiene) e quindi $X$ non ha elementi disgiunti da $X$ stesso, contraddicendo l'assioma di fondazione.
|
||
|
||
Viceversa, se $\in$ \`e ben fondata su $V$, dato un insieme non vuoto $X$ e considerato un suo elemento $a\in V$ che sia $\in$-minimale, dobbiamo necessariamente avere $a\cap X = \emptyset$, altrimenti un eventuale elemento $b\in a \cap X$ contraddirrebbe la minimalit\`a di $a$.
|
||
\ep
|
||
|
||
|
||
|
||
\bd La gerarchia di von Neumann \`e definita per ricursione transfinita nel modo seguente:
|
||
|
||
$
|
||
\begin{array}{lll}
|
||
V_0 & = & \emptyset \\
|
||
V_{\alpha+1} & = & \parti(V_\alpha) \\
|
||
V_\lambda & = & \bigcup_{\alpha<\lambda} V_\alpha \; \mbox{
|
||
per $\lambda$ ordinale limite.}
|
||
\end{array}
|
||
$
|
||
%Un insieme \`e ben fondato se appartiene a $V_\alpha$ per qualche $\alpha$.
|
||
\ed
|
||
|
||
\bexe Ogni $V_\alpha$ \`e transitivo e per $\beta < \alpha$ si ha $V_\beta \subseteq V_\alpha$. \eexe
|
||
\bp Per induzione su $\alpha$. Se $\alpha$ \`e limite $V_\alpha$ include ogni $V_\beta$ con $\beta<\alpha$ essendo l'unione di tali insiemi. Inoltre $V_\alpha$ \`e transitivo essendo l'unione di insiemi che per ipotesi induttiva sono transitivi. Se $\alpha = \gamma + 1$ per ipotesi induttiva $V_\gamma$ \`e transitivo, e quindi $x \in V_\gamma \to x \subseteq V_\gamma$, ovvero $V_\gamma \subseteq \parti(V_\gamma) = V_{\gamma+1}$. Rimane da dimostrare la transitivit\`a di $V_{\gamma+1}$. Se $x\in y\in V_{\gamma+1}$, allora $x\in y \subseteq V_\gamma$, e quindi $x\in V_\gamma$. Ma sappiamo che $V_\gamma \subseteq V_{\gamma+1}$ e pertanto $x\in V_{\gamma+1}$. \ep
|
||
|
||
Assumendo l'assioma di fondazione possiamo definire il rango di un insieme per ricursione sulla relazione ben fondata $\in$.
|
||
|
||
\bd Il rango $\rho(x)$ di un insieme $x$ \`e definito da $$\rho(x) = \sup\{\rho(y)+1: y\in x\}.$$
|
||
\ed
|
||
|
||
\bl $x\in V_\alpha$ se e solo se $\rho(x)<\alpha$. \el
|
||
\bp Per induzione su $\alpha$. Assumiamo $x\in V_\alpha$ e dimostriamo $\rho(x) < \alpha$. Se $\alpha$ \`e limite allora $x\in V_\beta$ per qualche $\beta<\alpha$, e per ipotesi induttiva $\rho(x)<\beta<\alpha$. Se $\alpha = \gamma+1$, allora $V_\alpha = \parti(V_\gamma)$ e $x\subseteq V_\gamma$. Per ipotesi induttiva gli elementi $y\in x$ hanno $\rho(y)<\gamma$, e quindi $\rho(y)+1 \leq \gamma$. Per definizione di $\rho(x)$ ne segue che $\rho(x) \leq \gamma < \alpha$.
|
||
|
||
Viceversa assumiamo $\rho(x)<\alpha$ e dimostriamo $x\in V_\alpha$. Se $\alpha$ \`e limite $\rho(x)<\beta$ per qualche $\beta<\alpha$ per ipotesi induttiva $x\in V_\beta \subseteq V_\alpha$. Supponiamo allora $\alpha = \gamma+1$. Per ogni $y\in x$ si ha $\rho(y) < \rho(x) < \gamma+1$ e pertanto $\rho(y)<\gamma$. Per ipotesi induttiva $y \in V_\gamma$, e visto che ci\`o vale per tutti gli elementi di $x$ ne segue che $x\in \parti (V_\gamma) = V_{\alpha}$.
|
||
\ep
|
||
|
||
\br Anche senza assumere l'assioma di fondazione, per ogni $\alpha$ la relazione di appartenenza ristretta a $V_\alpha$ \`e ben fondata e per ogni $x\in V_\alpha$ $\rho(x) < \alpha$. La dimostrazione \`e analoga alla precedente. \er
|
||
|
||
\bc L'assioma di fondazione equivale all'affermazione che ogni insieme $x$ appartiene a qualche $V_\alpha$, ovvero $V = \bigcup_{\alpha \in ON} V_\alpha$. \ec
|
||
\bp Dato $x\in V$, se vale la fondazione $\alpha = \rho(x)$ \`e ben definito e abbiamo $x\in V_\alpha$. Viceversa se $V = \bigcup_{\alpha \in ON} V_\alpha$ non possono esserci successioni decrescenti infinite $x_{n+1} \in x_n$ altrimenti, supponendo $x_0\in V_\alpha$, per la transitivit\`a di $V_\alpha$ l'intera successione apparterrebbe a $V_\alpha$, contraddicendone la ben fondatezza. \ep
|
||
|
||
\bc Se $x\subseteq y \in V_\alpha$, allora $x\in V_\alpha$. \ec
|
||
\bp Se $x \subseteq y$, in base alla definizione di $\rho$ si ha immediatamente $\rho(x) \leq \rho(y)$, e la tesi segue dal risultato precedente. \ep
|
||
|
||
Assumendo l'assioma di fondazione abbiamo un semplice criterio per distinguere gli insiemi dalle classi proprie.
|
||
|
||
\bl Una classe $X\subseteq V$ \`e un insieme se e solo se appartiene a $V_\alpha$ per qualche $\alpha\in ON$. \el
|
||
\bp Se $X$ \`e un insieme, possiamo definire $\alpha = \rho(X)$ e abbiamo $X\in V_\alpha$. Viceversa se $X\in V_\alpha$ allora ovviamente $X$ \`e un insieme. \ep
|
||
|
||
\bd Definiamo $\beth_0 = \aleph_0$, $\beth_{\alpha+1} = 2^{\beth_\alpha}$ e $\beth_\lambda = \sup_{\alpha<\lambda} \beth_\alpha$ per $\lambda$ limite. \ed
|
||
|
||
\bexe Per ogni $\alpha$, $|V_{\omega+\alpha}| = \beth_\alpha \geq \aleph_\alpha$. \eexe
|
||
|
||
\end{document}
|
||
|
||
\section{Cenno ai risultati di indipendenza}
|
||
|
||
Nel parlare di insiemi abbiamo introdotto molti simboli (per il vuoto $\emptyset$, l'unione $\bigcup X$, le parti $\parti X$, la coppia $\{a,b\}$, la coppia ordinata $(a,b)$, il prodotto cartesiano $X\times Y$, eccetera). Tutti questi simboli sono tuttavia stati definiti a partire dai soli simboli logici e dal simbolo di appartenenza $\in$. Ad esempio $x = (a,b)$ pu\`o essere inteso come abbreviazione per $\forall z (z \in x \liff z = \{a\} \lor z = \{a,b\})$, dove a sua volta $z = \{a,b\}$ \`e una abbreviazione per $\forall t (t \in z \liff t = a \lor t = b)$ e $z = \{a\}$ \`e una abbreviazione per $\forall t (t \in z \liff t = a)$. Infine $A = X\times Y$ \`e una abbreviazione per $\forall u (u \in A \liff (\exists a \in X)(\exists b\in Y) \; x = (a,b))$. Sciogliendo le definizioni tutto si lascia esprimere attraverso i soli simboli $\in, =, \forall, \exists, \lnot, \land, \lor, \to, \liff$ le variabili e le parentesi. Non abbiamo bisogno nemmeno della notazione $\{x: P(x)\}$, in quanto anch'essa fa capo ad una definizione: dire $a\in \{x: P(x)\}$ equivale a dire $P(a)$, e dire $A= \{x:P(x)\}$ equivale a dire $\forall t(t\in A \liff P(t))$, dove $P(t)$ avr\`a a sua volta una definizione.
|
||
|
||
L'appartenenza e i simboli logici forniscono dunque un linguaggio universale per la matematica, che gioca in qualche modo lo stesso ruolo che ha il pentagramma per la musica. Questa \`e solo una possibilit\`a di principio e non bisogna abusarne: la lingua italiana, se bene usata, \`e pi\`u efficace di qualunque simbolismo. Tuttavia \`e bene sapere che, cambiando il significato del simbolo $\in$, si cambia il significato di tutta la matematica, cosicch\'e dobbiamo sperare che gli assiomi che abbiamo dato non consentano interpretazioni troppo strane del simbolo di appartenenza.
|
||
Se ad esempio interpretassimo $x\in y$ come la relazione ``$x$ ed $y$ sono numeri naturali e $x$ \`e il predecessore di $y$'' l'assioma di estensionalit\`a risulterebbe ancora verificato (due numeri naturali sono uguali se hanno lo stesso predecessore), ma gli altri assiomi no (ad esempio l'assioma della coppia), e quindi per lo meno siamo sicuri del fatto che $x\in y$ non significa che $x$ \`e il predecessore di $y$.
|
||
|
||
Ragionare in modo rigoroso, evitando l'intuizione geometrica, significa ragionare senza presupporre che $\in$ abbia altri significati o propriet\`a che stanno solo nella nostra testa (magari suggeriti da una figura) e che non sono tra quelle esplicitate dagli assiomi. Le figure e i diagrammi possono essere utili come strumenti euristici per trovare dimostrazioni, ma non sostituiscono le dimostrazioni. Tuttavia, dopo un po' di esperienza, ci si rende conto che certe figure si lasciano facilmente tradurre in dimostrazioni (ad esempio i ben noti diagrammi di Venn per studiare le possibili intersezioni tra vari insiemi), e allora vanno bene anche quelle, se intese come promesse che a richiesta si \`e in grado di fornire una dimostrazione.
|
||
|
||
Rimane per\`o il problema: esistono modelli non-standard degli assiomi? Ovvero \`e possibile immaginare due diverse intepretazioni di $V$ e del simbolo di appartenenza $\in$, entrambe compatibili con gli assiomi, e tali che in una delle due un certo enunciato matematico risulti vero e nell'altra falso?
|
||
Purtroppo si, e l'ipotesi del continuo \`e uno di essi. Inoltre G\"odel ci insegna che, anche se si aggiungono altri assiomi per restringere le possibili interpretazioni, saltano fuori nuovi enunciati indecidibili (oltre al fatto che bisognerebbe sapere come sceglierli se vogliamo che la matematica non si riduca ad un gioco). Quando abbiamo dimostrato che i numeri naturali, cos\`{\i} come vengono descritti dagli assiomi di Peano, sono unici a meno di isomorfismo, si trattava in effetti di un'unicit\`a relativa ad un fissato universo di insiemi. Entro un dato universo $V$, con una data $\in$, i numeri naturali sono unici a meno di isomorfismo. Se si cambia l'intepretazione di $V$ e $\in$ cambia ovviamente anche tutto ci\`o che si definisce al suo interno.
|
||
Se ci\`o voglia dire che la matematica \`e in ultima analisi un'opinione, lo lascio giudicare a voi.
|
||
|
||
|
||
|
||
\bexe Se $x\in V_{\omega+\omega}$ anche $\parti(x)\in V_{\omega+\omega}$. In altre parole
|
||
gli insiemi di $V_{\omega+\omega}$ verificano l'assioma delle parti. In modo analogo si verifica che tutti gli assiomi di GB meno il rimpiazzamento risultano verificati se rileggiamo gli assiomi intendendo come ``insiemi'' quelli di $V_{\omega+\omega}$ e come ``classi'' gli elementi di $V_{\omega+\omega+1}$.\eexe
|
||
|
||
Visto che una teoria \`e coerente (nel senso che dai suoi assiomi non si deduce un teorema e la sua negazione) se e solo se ha un modello, abbiamo (pi\`u o meno) dimostrato che GB meno il rimpiazzamento \`e coerente (usando come modello $V_{\omega+\omega}$ e le sue parti). Tuttavia per definire $V_{\omega+\omega}$ (o anche solamente $\omega+\omega$) serve l'assioma di rimpiazzamento, quindi non \`e un grosso progresso. Un'altro esempio dello stesso fenomeno \`e il seguente: se rileggiamo gli assiomi intendendo come ``insiemi'' quelli di $V_{\omega+\omega}$ e come ``classi'' gli elementi di $V_{\omega+1}$, tutti gli assiomi di GB meno l'assioma dell'infinito risultano verificati. Sfortunatamente per definire $V_\omega$ serve l'assioma dell'infinito. In generale, per i teoremi di G\"odel, per dimostrare che una teoria \`e coerente serve una teoria pi\`u forte, mentre Hilbert sperava si potesse fare il contrario con una sorta di ``bootstrapping'', ovvero dimostrare la coerenza della teoria degli insiemi usando la teoria degli insiemi finiti (di cui evidentemente si fidava di pi\`u visti i paradossi che imperversavano all'epoca). Se se ne vuole sapere di pi\`u si deve studiare la logica matematica (inclusi i teoremi di G\"odel), e dopo eventualmente un corso avanzato di teoria degli insiemi (dove G\"odel avr\`a di nuovo di che dire la sua).
|
||
|
||
|