\documentclass[a1,portrait]{a0poster}
\usepackage{amsmath,amssymb}
\usepackage{multicol}
\usepackage{hfoldsty}  % for old-style numerals
\usepackage{pstricks,pst-node,pst-tree}
\usepackage[all]{xy}
\usepackage{paralist}
\usepackage{verbatim} % for the comment environment

\newcommand{\N}{\mathbb N}

\usepackage{upgreek}
\newcommand{\vnn}{\upomega}

\newcommand{\on}{\mathbf{ON}}

\usepackage{mathrsfs}
\newcommand{\sig}{\mathscr S}

\newcommand{\vnns}{\vnn_{\sig}}
\newcommand{\ons}{\ensuremath{\mathbf{ON}_{\sig}}}

\newcommand{\pred}[1]{\operatorname{pred}(#1)}
\newcommand{\predk}[1]{\operatorname{pred}_k(#1)}
\newcommand{\predl}[1]{\operatorname{pred}_{\ell}(#1)}

\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\lu}[1]{\mathbin{#1}}

\newcommand{\bfr}{\\\mbox{}\hfill}

\definecolor{lightgreen}{rgb}{0.8,1,0.8}
\newcommand{\defnbox}[1]{\psframebox*[framesep=2mm,fillstyle=solid,fillcolor=lightgreen]{\vphantom{\ensuremath{1^1_1}}#1}}

\definecolor{lightyellow}{cmyk}{0,0,0.4,0}
\newcommand{\highlightbox}[1]{%
\psframebox*[fillstyle=solid,fillcolor=lightyellow]{\parbox{0.98\columnwidth}{\raggedright#1}}}


\newcommand{\ra}{\psset{linestyle=dashed,linecolor=red}}
\newcommand{\la}{\psset{linestyle=solid,linecolor=blue}}
\newcommand{\mynode}[3][]{#2\TR[#1]{#3}}
\newcommand{\pluscolor}{\psset{linecolor=black,linestyle=solid,linewidth=0.8mm}}
\newcommand{\minuscolor}{\psset{linecolor=blue,linestyle=dashed,dash=4mm 2mm,linewidth=0.8mm}}
\newcommand{\timescolor}{\psset{linecolor=red,linestyle=dotted,linewidth=1.6mm}}

\usepackage{amsthm}

\newtheorem*{theorem}{Theorem}

\theoremstyle{definition}
\newtheorem*{example}{Example}

\renewcommand{\theequation}{\fnsymbol{equation}}

\begin{document}

\title{Numbers and sets}
\author{David Pierce}
\date{May, 2010}
\maketitle
\thispagestyle{empty}
\raggedright
%\flushright
\begin{center}
  \begin{pspicture}(4,-3)(37,0)
\psset{unit=1.2pt,linewidth=0.8mm,linecolor=blue}
\pscircle(10,0)3
 \pscircle(30,0)9
\pscircle(34,0)3
  \pscircle(90,0){27}
\pscircle(82,0)3
 \pscircle(102,0)9
\pscircle(106,0)3
   \pscircle(270,0){81}
\pscircle(226,0)3
 \pscircle(246,0)9
\pscircle(250,0)3
  \pscircle(306,0){27}
\pscircle(298,0)3
 \pscircle(318,0)9
\pscircle(322,0)3
    \psarc(810,0){243}{-20}{200}
\pscircle(658,0)3
 \pscircle(678,0)9
\pscircle(682,0)3
  \pscircle(738,0){27}
\pscircle(730,0)3
 \pscircle(750,0)9
\pscircle(754,0)3
   \pscircle(918,0){81}
\pscircle(874,0)3
 \pscircle(894,0)9
\pscircle(898,0)3
  \pscircle(954,0){27}
\pscircle(946,0)3
 \pscircle(966,0)9
\pscircle(970,0)3
  \end{pspicture}
\end{center}

\begin{multicols}{2}

By an \textbf{iterative algebra,} I mean an ordered triple
\begin{math}
(A,1,S)
\end{math},
or $\str A$, where

\begin{inparaenum}[(1)]
\item
$A$ is a set;\hfill
\item
$1\in A$;\hfill
\item
$S\colon A\to A$.
\end{inparaenum}\hfill\mbox{}

\begin{example}
$A=\defnbox{\N}=\{1,2,3,\dots\}$ and
  $S(n)= n+1$. 
\end{example}

An iterative algebra $\str A$ can be conceived as a \textbf{directed
 graph,} where 

\begin{inparaenum}[(1)]
  \item
$A$ is the set of \textbf{nodes,}\hfill
\item
$1$ is a particular node, and \hfill\mbox{}\\
\item
each pair $(x,S(x))$ is an \textbf{arrow} from $x$ to $S(x)$. 
\end{inparaenum}

The iterative algebra $\str A$ \textbf{admits induction} if it has no
proper subalgebra, so it does \emph{not} look like:
\begin{center}
  \begin{pspicture}(-3,-2.3)(12,0.5)
\psset{xunit=3cm,yunit=2cm,radius=3mm,labelsep=5mm,arrowsize=2mm
  2,linewidth=0.8mm,linecolor=red}
    \Cnode(1,0)1
\uput[u](1,0){$1$}
    \Cnode(2,0)2
\uput[u](2,0){$2$}
\ncline{->}12
    \Cnode(3,0)3
\uput[u](3,0){$3$}
\ncline{->}23
    \pnode(4,0)4
\ncline[linestyle=dashed]{->}34
%%%%%%%%%%%%%%%%%%%%
    \pnode(-1.5,-1){m2}
    \Cnode(-0.5,-1){m1}
\ncline[linestyle=dashed]{->}{m2}{m1}
    \Cnode(0.5,-1){m0}
\ncline{->}{m1}{m0}
    \Cnode(1.5,-1){p1}
\ncline{->}{m0}{p1}
    \Cnode(2.5,-1){p2}
\ncline{->}{p1}{p2}
    \Cnode(3.5,-1){p3}
\ncline{->}{p2}{p3}
    \pnode(4.5,-1){p4}
\ncline[linestyle=dashed]{->}{p3}{p4}
  \end{pspicture}
\end{center}
Then $\str A$ is \textbf{arithmetic} if
\begin{compactenum}[(1)]
\item
it admits induction,
\item
$1\neq S(x)$, so $\str A$ does \emph{not} look like:
  \raisebox{-4.5cm}{\begin{pspicture}(2,-6)(9,-2)
%\psgrid
    \psset{unit=3cm,linewidth=0.8mm,radius=3mm,labelsep=5mm,
      arrowsize=2mm 2,linecolor=blue}
\Cnode(1,0){c1}
\uput[u](1,0){$1$}
\Cnode(2,0){c2}
\uput[u](2,0){$2$}
\ncline{->}{c1}{c2}
\psarc[linestyle=dashed]{<-}(2,-1)1{190}{440}
\Cnode(1,-1){ck}
\uput[l](1,-1){$k$}
\ncline{->}{ck}{c1}
    \end{pspicture}}
\item
$S(x)=S(y)\Rightarrow x=y$, so $\str A$ does not look like:
\raisebox{-4cm}{\begin{pspicture}(1,-1)(9,6)
%\psgrid
    \psset{unit=3cm,linewidth=0.8mm,radius=3mm,labelsep=5mm,
      arrowsize=2mm 2,linecolor=red}
\Cnode(-3,0){d1}
\uput[u](-3,0){$1$}
    \Cnode(-2,0){d2}
\uput[u](-2,0){$2$}
\ncline{->}{d1}{d2}
    \Cnode(1,0){dn}
\uput[d](1,0){$n$}
\ncline[linestyle=dashed]{->}{d2}{dn}
\Cnode(2,0){d3}
\uput[d](2,0){$n+1$}
\ncline{->}{dn}{d3}
\psarc[linestyle=dashed]{->}(2,1)1{-80}{170}
\Cnode(1,1){dk}
\uput[r](1,1){$n+k-1$}
\ncline{->}{dk}{dn}
    \end{pspicture}}
\end{compactenum}
In particular, $(\N,1,S)$ is arithmetic.

In general, $\str A$ \textbf{admits recursion} if, for every iterative
algebra $\str B$, there is a unique homomorphism $h$ from $\str A$ to
$\str B$:
\begin{equation*}
\begin{psmatrix}[colsep=4cm,rowsep=3cm,arrows=->,%
linewidth=0.8mm,arrowsize=2mm 2,nodesep=3mm]
1^{\str A}&A&A\\
1^{\str B}&B&B
\ncline[linecolor=red]{1,1}{1,2}^{\in}
\ncline[linecolor=blue]{1,2}{1,3}^{S^{\str A}}
\ncline[linecolor=red]{2,1}{2,2}_{\in}
\ncline[linecolor=blue]{2,2}{2,3}_{S^{\str B}}
\ncline[linecolor=black]{1,1}{2,1}<{h}
\ncline[linecolor=black]{1,2}{2,2}<{h}
\ncline[linecolor=black]{1,3}{2,3}>{h}
\end{psmatrix}
\end{equation*}

\highlightbox{%
\begin{theorem}[Dedekind]
An iterative algebra admits recursion if and only if\\
it is arithmetic;
in particular, all such iterative algebras are isomorphic.
\end{theorem}}

Also $\N$ is \textbf{well-ordered} by the relation $<$, defined recursively by
\begin{align*}
x&\not<1,&
x<n+1&\Leftrightarrow x\leqslant n.
\end{align*}
Functions can be defined on $\N$ by \textbf{well-ordered
  recursion:} the simplest example is $h$, given by
\begin{equation*}
h(n)=\{h(x)\colon x<n\}.
\end{equation*}
Then $h$ is a bijection from $\N$ onto
\defnbox{$\vnn$}, 
the set of \textbf{von Neumann} natural numbers.  The first five of
these---$0$, $1$, $2$, $3$, and $4$---are illustrated above.

The class \defnbox{$\on$} of von Neumann \textbf{ordinals} comprises
each set that
\begin{compactenum}[(1)]
\item
is well-ordered by membership ($\in$),
 \item
is \textbf{transitive} (its members are also subsets).
\end{compactenum}

 \highlightbox{Then $\on$ itself 
  is well-ordered by membership and is transitive; it is an iterative
  algebra with respect to $\varnothing$ and $x\mapsto x\cup\{x\}$; and
  $\vnn$ is a subalgebra of $\on$ and is a \textbf{free algebra.}}

\emph{All of the foregoing generalizes to an arbitrary algebraic signature,
\defnbox{$\sig$}.}

One free algebra in $\sig$ is the \textbf{term algebra:}  
the smallest set of strings that, for each $n$ in $\vnn$, for each
$n$-ary symbol \defnbox{$F$} in $\sig$, is closed under the concatenation 
\begin{equation*}
(t_0,\dots,t_{n-1})\longmapsto Ft_0\cdots t_{n-1}.
\end{equation*}
Terms can be written as \textbf{labelled trees} or (refinements of)
\textbf{Hasse diagrams:}\columnbreak

  In $\{a,b,-,+,\cdot\}$, the term  
\begin{math}
  \lu+\lu{\cdot}\lu+\lu a\lu b\lu a\lu-\lu+\lu a\lu b
\end{math},
or more conventionally
\begin{equation}\label{*}
  ((a+b)\cdot a)+-(a+b),
\end{equation}
corresponds to either of
\raisebox{-3cm}{\psframebox[framesep=3mm,linecolor=gray]{\begin{pspicture}(0,0)(5.1,6.5)
%\psgrid
\rput[bl](0,0){\psset{treefit=loose}
\psset{linewidth=0.8mm,nodesep=3mm}
  \pstree[treemode=D]{\mynode{\la}{$+$}}
                     {\pstree{\mynode{\la}{$\cdot$}}
                             {\pstree{\mynode{\la}{$+$}}
                                     {\mynode{\la}{$a$}\mynode{\ra}{$b$}}
                              \skiplevel{\mynode{\ra}{$a$}}}
                      \pstree{\mynode{\ra}{$-$}}
                             {\pstree{\mynode{\la}{$+$}}
                                     {\mynode{\la}{$a$}\mynode{\ra}{$b$}}}}}
    \end{pspicture}}}
and
\raisebox{-3cm}{\psframebox[framesep=3mm,linecolor=gray]{%
\begin{pspicture*}(0.3,0)(2.6,6.5)
\psset{linewidth=0.8mm,nodesep=3mm}
\rput[bl](0,0){
  \pstree[treemode=D]{\mynode{\la}{$+$}}
                     {\mynode[name=dot]{\la}{$\cdot$}
                      \Tn
                      \pstree{\mynode{\ra}{$-$}}
                             {\pstree{\mynode[name=plus]{\la}{$+$}}
                                     {\mynode[name=a]{\la}{$a$}
                                      \Tn
                                      \mynode{\ra}{$b$}}
                             \Tn
                             \Tn}}
\la\ncline{dot}{plus}
\ra\ncline{dot}{a}}
\end{pspicture*}}}.
\begin{comment}


Call an $n+1$-tuple
\begin{equation*}
  (X_0,\dots,X_{n-1},F)
\end{equation*}
a set of \textbf{type} $F$ whose 
elements of \textbf{grade} $k$ compose $X_k$.  Define



\end{comment}
%For a von-Neumann style definition, 
Now let
\begin{align*}
\raisebox{-1cm}{\psframebox[framesep=3mm,linecolor=gray]{\begin{pspicture*}(0,0)(2.3,2.5)
%\psgrid
\psset{linewidth=0.8mm,nodesep=3mm}
\rput[bl](0,0){\psset{linewidth=0.8mm,nodesep=3mm}
  \pstree[treemode=D]{\mynode{\la}{$+$}}
                     {\mynode{\la}{$a$}
                      \Tn
                      \mynode{\ra}{$b$}}}
    \end{pspicture*}}}
&=
\bigl(\{a\},\{b\},+\bigr),
&
\raisebox{-2cm}{\psframebox[framesep=3mm,linecolor=gray]{\begin{pspicture*}(0.7,0)(3,4.5)
%\psgrid
\psset{linewidth=0.8mm,nodesep=3mm}
\rput[bl](0,0){\psset{linewidth=0.8mm,nodesep=3mm}
  \pstree[treemode=D]{\mynode[name=dot]{\la}{$\cdot$}}
                     {\Tn
                      \Tn
                      \pstree{\mynode[name=plus]{\la}{$+$}}
                             {\mynode[name=a]{\la}{$a$}
                              \Tn
                              \mynode{\ra}{$b$}}}
\ra\ncline{dot}{a}}
    \end{pspicture*}}}
&=
\biggl(\Bigl\{a,b,\bigl(\{a\},\{b\},+\bigr)\Bigr\},\{a\},\cdot\biggr),
\end{align*}
and so on; then~\eqref{*} is as depicted below.
If $F$ is $n$-ary in $\sig$ as before, $X_k$ is a set when $k<n$, and
$\defnbox X=(X_0,\dots,X_{n-1},F)$, define
\begin{gather*}
\defnbox{\predk {X}}=X_k,\qquad\qquad
\defnbox{\pred{X}}
=X_0\cup\cdots\cup
  X_{n-1},\\ 
\defnbox{Y\in'X}\Leftrightarrow Y\in \pred X
\end{gather*}
(here `pred' is for \emph{predecessor});
say that $X$ is \textbf{$k$-transitive} if
\begin{equation*}
Y\in\predk X\Rightarrow \pred Y\subseteq\predk X.
\end{equation*}
Let \defnbox{$\ons$} comprise those
$X$ such that
\begin{compactenum}[(1)]
  \item
$X=(X_0,\dots,X_{n-1},F)$ for some $n$-ary $F$ in $\sig$, for some $n$
    in $\vnn$; and\bfr each $X_k$ is nonempty;
\item
each element $Y$ of $\pred X$ is $(Y_0,\dots,Y_{m-1},G)$ for some
$m$-ary $G$ in $\sig$,\bfr for some $m$ in $\vnn$; and each $Y_{\ell}$
is nonempty;
\item
$X$ is $k$-transitive for each $k$;
\item
each element of $\pred X$ is $\ell$-transitive for each $\ell$; 
  \item
$\in'$ \textbf{directs} each set $\predk X$ (finite subsets have upper
    bounds);
\item
$\in'$ directs each set $\predl Y$ for each $Y$ in $\pred X$;
\item
$\in'$ is \textbf{well-founded} on $\pred X$ (nonempty subsets have minimal\bfr elements).
\end{compactenum}

Call an element $X$ of $\ons$ a \textbf{limit} if some
$\predk X$ has no maximal element with respect to
$\in'$.    Let \defnbox{$\vnns$}
consist of those $X$ in $\ons$ such that
neither $X$ nor any element of $\pred X$ is a limit.

\highlightbox{\begin{theorem}
The relation $\in'$ is well-founded on $\ons$, and
\begin{equation*}
X\in\ons\Rightarrow\pred X\subseteq\ons.
\end{equation*}
The class $\ons$ is an $\sig$-algebra with respect to the operations
\begin{equation*}
  F(X_0,\dots,X_{n-1})
  =(\pred{X_0}\cup\{X_0\},\dots,\pred{X_{n-1}}\cup\{X_{n-1}\},F);
\end{equation*}
and $\vnns$ is a free subalgebra.
\end{theorem}}

\begin{center}
  \begin{pspicture}(-12.5,-6.25)(12.5,6.25)
\psset{unit=5mm,subgriddiv=0,linewidth=0.8mm}
%\psgrid(-25,-12)(25,12)    
\pluscolor
\psellipse(0,0)(25,12.5)
\psline(0,-12.5)(0,12.5)
\rput(0,12.5){\pscirclebox[fillstyle=solid,fillcolor=white]{$+$}}
\minuscolor
\pscircle(8,3.5){6.5}
\rput(8,10){\pscirclebox[fillstyle=solid,fillcolor=white]{$-$}}
\pluscolor
\psellipse(8,4)(5,2.5)
\psline(8,1.5)(8,6.5)
\rput(8,6.5){\pscirclebox[fillstyle=solid,fillcolor=white]{$+$}}
\rput(5.5,4){$a$}
\rput(10.5,4){$b$}
\rput(5,-0.5){$a$}
\rput(11,-0.5){$b$}
\pluscolor
\psellipse(17,-4)(5,2.5)
\psline(17,-6.5)(17,-1.5)
\rput(17,-1.5){\pscirclebox[fillstyle=solid,fillcolor=white]{$+$}}
\rput(14.5,-4){$a$}
\rput(19.5,-4){$b$}
\rput(3,-9){$a$}
\rput(9,-7){$b$}
\timescolor
\psellipse(-11,4)(10,5)
\psline(-6,-0.3)(-6,8.3)
\rput(-6,8.3){\pscirclebox[fillstyle=solid,fillcolor=white]{$\cdot$}}
\pluscolor
\psellipse(-13,4.5)(5,2.5)
\psline(-13,2)(-13,7)
\rput(-13,7){\pscirclebox[fillstyle=solid,fillcolor=white]{$+$}}
\rput(-15.5,4.5){$a$}
\rput(-10.5,4.5){$b$}
\rput(-11,0.5){$a$}
\rput(-8,1){$b$}
\rput(-3.5,4){$a$}
\pluscolor
\psellipse(-14,-5)(5,2.5)
\psline(-14,-7.5)(-14,-2.5)
\rput(-14,-2.5){\pscirclebox[fillstyle=solid,fillcolor=white]{$+$}}
\rput(-16.5,-5){$a$}
\rput(-11.5,-5){$b$}
\rput(-6,-8){$a$}
\rput(-3,-6){$b$}
  \end{pspicture}
\end{center}

\end{multicols}

\end{document}