%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 $x0$ 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 |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 \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\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 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 \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)$ è 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|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|\alpha|=\alpha$. Se per assurdo esistesse un cardinale $\kappa$ tale che $\alpha<\kappa \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).