%% FIRST RENAME THIS FILE <yoursurname>.tex. 
%% BEFORE COMPLETING THIS TEMPLATE, SEE THE "READ ME" SECTION 
%% BELOW FOR INSTRUCTIONS. 
%% TO PROCESS THIS FILE YOU WILL NEED TO DOWNLOAD asl.cls from 
%% http://aslonline.org/abstractresources.html. 


\documentclass[bsl,meeting]{asl}
%\usepackage{url}  % added by David Pierce

\AbstractsOn

\pagestyle{plain}

\def\urladdr#1{\endgraf\noindent{\it URL Address}: {\tt #1}.}


\newcommand{\NP}{}
%\usepackage{verbatim}

\begin{document}
\thispagestyle{empty}

%% BEGIN INSERTING YOUR ABSTRACT DIRECTLY BELOW; 
%% SEE INSTRUCTIONS (1), (2), (3), and (4) FOR PROPER FORMATS

\NP  
\absauth{David Pierce}
\meettitle{Induction and recursion}
\affil{Mathematics Department, Middle East Technical University,
%  Eski\c sehir Yolu, 
Ankara 06531, Turkey}  
\meetemail{dpierce@metu.edu.tr}

%% INSERT TEXT OF ABSTRACT DIRECTLY BELOW

Dedekind \cite[II.130]{MR0159773} makes an observation overlooked by
Peano \cite{Peano} and others:  A set with an initial element and a
successor-operation may admit proof by induction without
admitting inductive or rather \emph{recursive} definition of
functions.  

Landau \cite[Preface for the Teacher]{MR12:397m} confesses
to having confused induction with recursion.  
Henkin \cite{MR0120156} works out the distinction.
Yet the confusion
continues to be made, even in textbooks intended for students of
mathematics and computer science who ought to be able to understand
the distinction.  Textbooks also perpetuate related confusions, such
as suggestions
that induction and `strong' induction (or else the `well-ordering
principle') are logically equivalent, and that either one is sufficient
to axiomatize the natural numbers.

In an exercise in one noteworthy textbook \cite[II.1,
  p.~38]{MR0214415}, the reader is invited
to show the logical independence of the three
axioms introduced by Dedekind, but commonly called by the name of
Peano: ($\alpha$) the initial element is not a successor, ($\beta$) the
successor-operation is injective, and ($\gamma$) proof by induction works.
  But first, just after the introduction of these as axioms for the
natural numbers, these numbers are used to
index iterates of functions.  This indexing is used later (II.2)
to define addition and
multiplication.  But this indexing strictly requires all three of the
axioms, normally in the equivalent form introduced only later still
(II.11) and called the Peano--Lawvere Axiom.  (Mention of this is absent
from later editions, as \cite{MR941522}; it is called the
  Dedekind--Peano Axiom in \cite[9.1, p.~156]{MR1965482}.)

Landau implicitly (and Henkin explicitly) shows that addition and
multiplication can be 
defined by induction alone.  But the argument takes some work.
(Strictly, the argument requires that these operations are being
defined on a \emph{set.}  However, with more work, one can avoid this
assumption.)  If one thinks
that the recursive definitions of addition and
multiplication---$n+0=n$, $n+(k+1)=(n+k)+1$, $n\cdot0=0$, 
$n\cdot(k+1)=n\cdot k+n$---are \emph{obviously} justified by induction 
alone, then one may think the same for exponentation, with 
$n^0=1,\ n^{k+1}=n^k\cdot n$.
However, while addition and multiplication are
well-defined on $\mathbb Z/(n)$ (which admits induction),
exponentiation is
not; rather, we have
$(x,y)\mapsto x^y\colon\mathbb Z/(n)\times\mathbb Z/\phi(n)\to\mathbb Z/(n)$.
This is one example to suggest that getting things 
straight may make a pedagogical difference.



%\bibliographystyle{amsplain}
%\bibliography{../../../TeX/references}


\begin{thebibliography}{10}

%% INSERT YOUR BIBLIOGRAPHIC ENTRIES HERE; 
%% SEE (4) BELOW FOR PROPER FORMAT.
%% EACH ENTRY MUST BEGIN WITH \bibitem{citation key}
%%
%% IF THERE ARE NO ENTRIES  
%% DELETE THE LINE ABOVE (\begin{thebibliography}{20}) 
%% AND THE LINE BELOW (\end{thebibliography})

\bibitem{MR0159773}
{\scshape Richard Dedekind}, 
{\bfseries\itshape
Essays on the theory of numbers. {I}: {C}ontinuity and
  irrational numbers. {II}: {T}he nature and meaning of numbers}, 
Dover,
  1963

\bibitem{MR0120156}
{\scshape Leon Henkin},
{\itshape On mathematical induction},
{\bfseries\itshape The American Mathematical Monthly},
vol.~67 (1960), no.~4, pp.~323--338

\bibitem{MR12:397m}
{\scshape Edmund Landau}, 
{\bfseries\itshape Foundations of {A}nalysis},
Chelsea, 
1966

\bibitem{MR1965482}
{\scshape F.~William Lawvere and Robert Rosebrugh}, 
{\bfseries\itshape Sets for mathematics}, 
Cambridge,
2003

\bibitem{MR0214415}
{\scshape Saunders Mac~Lane and Garrett Birkhoff}, 
{\bfseries\itshape Algebra}, 
Macmillan, 1967

\bibitem{MR941522}
\bysame, 
{\bfseries\itshape Algebra}, 
third ed., Chelsea, 1988

\bibitem{Peano}
{\scshape Guiseppe Peano}, 
{\itshape The principles of arithmetic, presented by a new method},
{\bfseries\itshape From {F}rege to {G}{\"o}del},
 (Jean van Heijenoort, editor), 
Harvard, 
1967

\end{thebibliography}


\vspace*{-0.5\baselineskip}
% this space adjustment is usually necessary after a bibliography

\end{document}


%% READ ME
%% READ ME
%% READ ME

INSTRUCTIONS FOR SUPPLYING INFORMATION IN THE CORRECT FORMAT: 

1. Author names are listed as First Last, First Last, and First Last.

\absauth{FirstName1 LastName1, FirstName2 LastName2, and FirstName3 LastName3}


2. Titles of abstracts have ONLY the first letter capitalized,
except for Proper Nouns.

\meettitle{Title of abstract with initial capital letter only, except for
Proper Nouns} 


3. Affiliations and email addresses for authors of abstracts are
  listed separately.

% First author's affiliation
\affil{Department, University, Street Address, Country}
\meetemail{First author's email}
%%% NOTE: email required for at least one author
\urladdr{OPTIONAL}
%
% Second author's affiliation
\affil{Department, University, Street Address, Country}
\meetemail{Second author's email}
\urladdr{OPTIONAL}
%
% Third author's affiliation
\affil{Department, University, Street Address, Country}
% Second author's email
\meetemail{Third author's email}
\urladdr{OPTIONAL}


4. Bibliographic Entries

%%%% IF references are submitted with abstract,
%%%% please use the following formats

%%% For a Journal article
\bibitem{cite1}
{\scshape Author's Name},
{\itshape Title of article},
{\bfseries\itshape Journal name spelled out, no abbreviations},
vol.~XX (XXXX), no.~X, pp.~XXX--XXX.

%%% For a Journal article by the same authors as above,
%%% i.e., authors in cite1 are the same for cite2
\bibitem{cite2}
\bysame
{\itshape Title of article},
{\bfseries\itshape Journal},
vol.~XX (XXXX), no.~X, pp.~XX--XXX.

%%% For a book
\bibitem{cite3}
{\scshape Author's Name},
{\bfseries\itshape Title of book},
Name of series,
Publisher,
Year.

%%% For an article in proceedings
\bibitem{cite4}
{\scshape Author's Name},
{\itshape Title of article},
{\bfseries\itshape Name of proceedings}
(Address of meeting),
(First Last and First2 Last2, editors),
vol.~X,
Publisher,
Year,
pp.~X--XX.

%%% For an article in a collection
\bibitem{cite5}
{\scshape Author's Name},
{\itshape Title of article},
{\bfseries\itshape Book title}
(First Last and First2 Last2, editors),
Publisher,
Publisher's address,
Year,
pp.~X--XX.

%%% An edited book
\bibitem{cite6}
Author's name, editor. % No special font used here
{\bfseries\itshape Title of book},
Publisher,
Publisher's address,
Year.