%(If you can read TeX fluently, you may wish to fast-forward to a line
%beginning %file starts here or \frfilename
%if one of these is present.)
%TeXfiles with this heading are designed for processing with AmSTeX,
%accessed through TeXfiles amstex.tex (with amssym.tex and
% amsppt.sty and possibly amsppt.sti) during compilation.
%If these are unavailable, a readable
%version can (I hope) be produced by deleting the % before
% \amstexsupportedfalse below.
%Some special difficulties arise with the importation of .ps files
%in diagrams. Look for \picture below for notes on these.
%The following \count registers are used for special purposes:
% \count1=\stylenumber to specify style
% \count2=\footnotenumber to count footnotes
%AmSTeX declaration
\newif\ifamstexsupported
\amstexsupportedtrue
% \amstexsupportedfalse %use when AMSTeX unavailable
\newif\ifDHFamstexloaded %for detection of a non-standard AMSTeX
\DHFamstexloadedfalse
\newif\ifDHFamspptloaded
\DHFamspptloadedfalse
\newif\iffourteensavailable
\fourteensavailabletrue
\fourteensavailablefalse
\newif\ifathome
\athometrue %to cope with a quirk of my son's Ghostscript
\athomefalse
\newif\iffirstpage
\firstpagetrue
%Style assignments
\countdef\stylenumber=1
\countdef\footnotenumber=2
\def\fullsize{\magnification=\magstep1
\def\pagewidth{390pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=1}
\def\smallprint{\magnification=\magstep0
\overfullrule0pt
\def\pagewidth{468pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=2}
\def\printersize{\magnification=\magstep1
\baselineskip24pt
\overfullrule0pt
\def\pagewidth{330pt}
\def\pageheight{8.5truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=3}
\def\refsize{\magnification=\magstep1
\overfullrule0pt
\def\pagewidth{390pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=4}
\def\rrversion{\magnification=\magstep1
\overfullrule0pt
\def\pagewidth{330pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=5}
\def\bigsize{\magnification=\magstep2
\overfullrule0pt
\def\pagewidth{325pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=6}
\def\bbigsize{\magnification=\magstep3
\overfullrule0pt
\def\pagewidth{271pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=7}
\def\USsmallprint{\magnification=\magstep0
\overfullrule0pt
\def\pagewidth{482pt}
\def\pageheight{8.7truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=8}
\def\halfmagsize{\magnification=\magstephalf
\def\pagewidth{427pt}
\def\pageheight{9truein}
\hsize\pagewidth
\vsize\pageheight
\stylenumber=9}
% register stylenumber is used to control the output format
%addresses, letterheads
\def\deptaddress{\hskip 3truein Department of Mathematical Sciences\par
\noindent e-mail: {\tt fremdh}\hskip 2.9truein\today\par
\medskip}
\long\def\univaddress#1{\hskip 3truein Department of Mathematical Sciences\par
\hskip 3truein University of Essex\par
\hskip 3truein Colchester CO4 3SQ\par
\hskip 3truein England\par
%\hskip 3truein van Vleck Hall\par
%\hskip 3truein 480 Lincoln Drive\par
%\hskip 3truein Madison\par
%\hskip 3truein WI 53706-1388, U.S.A.\par
\hskip 3.2truein#1\par
\noindent e-mail: {\tt fremdh\@essex.ac.uk}
%{\tt fremlin\@math.wisc.edu}
\bigskip}
\long\def\letterhead#1#2#3{\univaddress{#1}
{\parindent=0pt
#2
}
\medskip
\noindent Dear #3,
}
\def\shortaddress{\noindent Departmentof Mathematical Sciences, University of Essex,
Colchester CO4 3SQ, England\par
\noindent e-mail: fremdh\@essex.ac.uk}
\def\valediction#1#2{\bigskip
\hskip 3truein #1,
\vskip 1truein
\hskip 3.3truein #2
\bigskip}
%picture importation
%It is clear that there is no general standard. The syntax I
%use when calling for a .ps file is
% \def\Caption{<...>}
% \picture{}{}
%which is supposed to import .ps at height ,
%centered, and adding a one-line centered caption <...> .
%The basic macro listed in \def\picture is that which
%used to work at Essex. We now use the macro in
% \def\picturewithpsfig , which requires a previous input
% psfig.tex or psfig.sty ;
%if you interpolate \atUEssex early in your file it will
%give you the latter.
% I find that psfig is erratic in its centering, especially
%under magnification, so I have written a routine
% \centerpicturewithpsfig (which may be called from
% \centerpicture ) with the syntax
% \centerpicture{}{}{}
%the first dimension being width and the second height.
\def\picture#1#2{\bigskip
\bigskip
\immediate\write0{importing diagram #1.ps at height #2
with dvitops}
\vbox{\vskip #2
\special{dvitops: import #1.ps \pagewidth #2}
\Centerline{\Caption}
}
\medskip
\def\Caption{}}
%an alternative version, without caption
\def\centerpicture#1#2#3{\bigskip
\bigskip
\immediate\write0{importing diagram #1.ps at width #2
and height #3 with dvitops}
\vbox{\vskip #3
\special{dvitops: import #1.ps \pagewidth #3}
}}
%to put pictures on same line
\def\sideshiftedpicture#1#2#3#4{\bigskip
\bigskip
\immediate\write0{importing diagram #1.ps at height #4
and width #3 with dvitops}
\vbox{\special{dvitops: import #1.ps #3 #4}}
\hskip #2 plus 0pt minus 0pt
}
\def\startsideshiftedpicture{}
\newcount\scaleup
\newcount\scaledown
\scaleup=1
\scaledown=1
\def\scalesideshiftedpicture#1#2#3#4{
\dimen4=#4
\dimen3=#3
\multiply\dimen4 by\scaleup
\divide\dimen4 by \scaledown
\multiply\dimen3 by\scaleup
\divide\dimen3 by \scaledown
\sideshiftedpicture{#1}{#2}{\dimen3}{\dimen4}}
%alternative picture importation code
\def\atUEssex{
\input psfig.sty
\def\picture##1##2{\picturewithpsfig{##1}{##2}}
\def\sideshiftedpicture##1##2##3##4{
\sideshiftedpicturewithpsfig{##1}{##2}{##3}{##4}}
\def\centerpicture##1##2##3{
\centerpicturewithpsfig{##1}{##2}{##3}}
\def\startsideshiftedpicture{
\sideshiftedpicture{empty}{1pt}{1pt}{1pt}}
}
\def\athome{
\input psfig.sty
\def\picture##1##2{\picturewithpsfig{##1}{##2}}
\def\sideshiftedpicture##1##2##3##4{
\sideshiftedpicturewithpsfig{##1}{##2}{##3}{##4}}
\def\centerpicture##1##2##3{
\centerpicturewithpsfig{##1}{##2}{##3}}
\def\startsideshiftedpicture{
\sideshiftedpicture{empty}{1pt}{1pt}{1pt}}
\voffset=1cm}
\def\atUWMadison{
\fourteensavailablefalse
\input psfig
\def\picture##1##2{\picturewithpsfig{##1}{##2}}
}
\def\picturewithpsfig#1#2{\bigskip
\immediate\write0{importing diagram #1.ps at height #2 with psfig}
\vbox{\hsize\pagewidth
%\centerline{\discrversionA{\hskip1truein}{}\psfig{figure=#1.ps,height=#2
\centerline{\psfig{figure=#1.ps,height=#2
}}
\medskip
\centerline{\Caption}}
\medskip
\def\Caption{}}
\def\centerpicturewithpsfig#1#2#3{
\immediate\write0{importing diagram #1.ps at width #2
and height #3 with psfig}
\dimen 3 = #2
\dimen 4 = #3
\dimen 2 = \pagewidth
\advance\dimen2 by -\dimen3
\divide\dimen2 by 2
\discrversionB{\shrinkonestep}{}
\discrversionH{\shrinkonestep}{}
\discrversionF{\enlargeonestep}{}
\discrversionG{\enlargeonestep\enlargeonestep}{}
\dimen 6 = \dimen4
\divide\dimen6 by 3
\vskip\dimen6
\ifdim\dimen2>0\hskip\dimen2\fi
\vbox{\psfig{file=#1.ps,width=\dimen3,height=\dimen4}}
\discrversionG{\vskip-\dimen6}{}
}
\def\enlargeonestep{\dimen5 = 5truein
\dimen6 = 7truein
\ifdim\dimen3<\dimen5
\ifdim\dimen4<\dimen6
\divide\dimen3 by 5
\multiply\dimen3 by 6
\divide\dimen4 by 5
\multiply\dimen4 by 6
\fi\fi}
\def\shrinkonestep{\divide\dimen3 by 6
\multiply\dimen3 by 5
\divide\dimen4 by 6
\multiply\dimen4 by 5}
\def\sideshiftedpicturewithpsfig#1#2#3#4{
\immediate\write0{importing diagram #1.ps at height #4
and width #3 with psfig}
\dimen 4 = #4
\dimen 3 = #3
\discrversionB{\shrinkonestep}{}
\discrversionH{\shrinkonestep}{}
\discrversionF{\enlargeonestep}{}
\discrversionG{\enlargeonestep\enlargeonestep}{}
% \vbox{\psfig{figure=#1.ps,height=\dimen4,width=\dimen3}}
\psfig{figure=#1.ps,height=\dimen4,width=\dimen3}
\hskip #2 plus 0pt minus 0pt}
%alternative picture importation code; I've been told about this
%but have not used it successfully myself
%\def\Caption{}
%\input epsf
%\epsfverbosetrue
%\def\picture#1#2{\bigskip
% \bigskip
% \immediate\write0{importing diagram #1.ps at height #2 with epsf}
% \epsfysize=#2
% \centerline{\epsffile{#1.ps}}
% \medskip
% \Centerline{\Caption}
% \medskip
% }
%in addition it may be necessary to amend the imported .ps file
%by replacing the %%BoundingBox header by %%BoundingBox:
%special fonts
\def\biggerscriptfonts{\scriptfont0=\eightrm
\scriptfont1=\eighti
\scriptfont2=\eightsy
\scriptfont3=\eightex
\scriptfont\bffam=\eightbf
\scriptfont\msbfam=\eightmsb
\scriptfont\eufmfam=\eighteufm
}
\def\Loadcyrillic{\ifamstexsupported
\input cyracc.def
\font\tencyr=wncyr10
\def\cyr{\tencyr\cyracc} \def\itcyr{\tenitcyr\cyracc}
\else\def\cyr{\smc}\def\cdprime{u\i}\def\Cdprime{UI}\fi}
%http://wkweb3.cableinet.co.uk/linux/LDP/HOWTO/Cyrillic-HOWTO-7.html
%cyrillic.tex
\def\Loadfourteens{\iffourteensavailable
\font\fourteenrm=cmr14
\font\fourteenbf=cmbx14
\font\fourteenit=cmsl14
\else\font\fourteenrm=cmr10 scaled \magstep2
\font\fourteenbf=cmbx10 scaled \magstep2
\font\fourteenit=cmsl10 scaled \magstep2
\fi}
\def\smallerfonts{\eightpoint
\textfont\msbfam=\eightmsb
\textfont\eufmfam=\eighteufm
\textfont\bffam=\eightbf
\textfont\eurmfam=\eighteurm
\textfont\eusmfam=\eighteusm
}
\font\twelveex=cmex10 scaled \magstep1
%Copyright declarations
\newcount\oldcopyrightdate
\newcount\newcopyrightdate
\oldcopyrightdate=0
\def\copyrightdate#1{\newcopyrightdate=#1
\ifnum\newcopyrightdate=\oldcopyrightdate\else
\oldcopyrightdate=#1
\oldfootnote{}{\eightrm \copyright\ #1 D.~H.~Fremlin}
\immediate\write0{Copyright #1}
\fi}
%hyphenation
\hyphenation{equi-ver-id-ical}
%miscellaneous definitions
\def\Aut{\mathop{\text{Aut}}}
\def\backstep#1{\hskip -0.#1em plus 0 pt minus 0 pt}
\def\Bang{\vthsp\hbox{\bf X\hskip0.07em\llap X\hskip0.07em\llap X\rm}}
\def\BanG{\Bang{\hskip 1.111pt plus 3.333pt minus 0pt}}
%\def\BbbN{\mathchoice{\hbox{$\Bbb N$\hskip0.02em}}
% {\hbox{$\Bbb N$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb N$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb N$\hskip0.04em}}}
%\def\BbbQ{\mathchoice{\hbox{$\Bbb Q$\hskip0.02em}}
% {\hbox{$\Bbb Q$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb Q$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb Q$\hskip0.04em}}}
%\def\BbbR{\mathchoice{\hbox{$\Bbb R$\hskip0.02em}}
% {\hbox{$\Bbb R$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb R$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb R$\hskip0.04em}}}
% %do not use with $\Bbb R^X$
%\def\BbbZ{\mathchoice{\hbox{$\Bbb Z$\hskip0.02em}}
% {\hbox{$\Bbb Z$\hskip0.02em}}
% {\hbox{$\scriptstyle\Bbb Z$\hskip0.04em}}
% {\hbox{$\scriptscriptstyle\Bbb Z$\hskip0.04em}}}
\def\BbbN{\openBbb{N}}
\def\BbbQ{\openBbb{Q}}
\def\BbbR{\openBbb{R}}
%do not use with $\Bbb R^X$ do not use in $_{\Bbb R^r}$
\def\BbbZ{\openBbb{Z}}
\def\Bbbone{\hbox{1\hskip0.13em\llap{1}}}
\def\biggerint{\textfont3=\twelveex\intop\nolimits}
\def\biggeriint{\textfont3=\twelveex\iint}
% remarkable fact: this seems to infect all \int within a given
% $..$ ; but $\biggerint$$\int$ seems to leave the $\int$ normal
% really \textfont3=\twelveex is more reliable, since \biggerint
% as written gets turned off rather easily (e.g. by \comment,
% or by an extra {...})
\def\bover#1#2{{{#1}\over{#2}}}
\def\Bover#1#2{\backstep4\hbox{
\biggerscriptfonts${\shortstrut#1}\over{\shortstrut#2}$}}
% when there are superscripts in the denominator, as in \Bover1{2^m}
% or \Bover1{\sqrt{2\pi}^r} , these can sometimes come out with better
% horizontal alignment if you use \Bover1{{\sshortstrut 2}^m} or
% \Bover1{{\sqrt{2\pi}}^r}
\def\bsp{/\penalty-100}
\def\Caption{}
\def\Center#1{
\Centerline{#1}
\noindent}
\def\Centerline#1{\vskip 5pt
{\def\int{\text{}$$\textfont3=\twelveex\intop\nolimits}
\def\dashint{\text{}$$\textfont3=\twelveex
\mskip2mu\vrule height2.6pt width4.5pt depth-2.4pt\mskip-11mu
\intop\nolimits\mskip-2mu}
\def\idashint{\text{}$$\int\mskip-7mu\dashint}
\def\dashiint{\text{}$$\dashint\mskip-6mu\int}
\def\dashidashint{\text{}$$\dashint\mskip-6mu\dashint}
\def\underlineint{
\text{}$$\textfont3=\twelveex\underline{\intop\nolimits}}
\def\overlineint{
\text{}$$\textfont3=\twelveex\overline{\intop\nolimits}}
\def\iint{\text{}$$\textfont3=\twelveex
\intop\nolimits\hskip-0.5em\intop\nolimits}
\def\sum{\text{}$$\sumop}
\def\prod{\text{}$$\prodop}
\def\bigcap{\text{}$$\bigcapop}
\def\bigcup{\text{}$$\bigcupop}
\centerline{#1}}\vskip 5pt}
\mathchardef\bigcapop="1354
\mathchardef\bigcupop="1353
\mathchardef\prodop="1351
\mathchardef\sumop="1350
%in \Centerline{$\overline{}$, $\cmmnt{}$} must use \sumop etc
\def\cf{\mathop{\text{cf}}}
\def\circumflex#1{{\accent"5E #1}}
\def\closeplus{\hbox{+}}
\def\coint#1{\left[#1\right[}
\def\curl{\mathop{\text{curl}}}
\def\dashint{\mathchoice{-\mskip-20mu\intop\nolimits}
{{\vrule height2.7pt width4.5pt depth-2.5pt\mskip-10mu\intop\nolimits}}
{-\mskip-16.5mu\intop\nolimits} %not yet used
{-\mskip-16.5mu\intop\nolimits}} %not yet used
\def\idashint{\mathchoice{\int\mskip-6mu\dashint}
{\int\mskip-5mu\dashint}
{\int\mskip-5mu\dashint} %not yet used
{\int\mskip-5mu\dashint}} %not yet used
\def\dashiint{\mathchoice{\dashint\mskip-10mu\int}
{\dashint\mskip-6mu\int}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\dashidashint{\mathchoice{\dashint\mskip-10mu\dashint}
{\dashint\mskip-6mu\dashint}
{\dashint\mskip-6mu\dashint} %not yet used
{\dashint\mskip-6mu\dashint}} %not yet used
\def\dashidashiint{\mathchoice{\dashint\mskip-8mu\dashint\mskip-10mu\int}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\dashiidashint{\mathchoice{\dashint\mskip-10mu\int\mskip-8mu\dashint}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\idashidashint{\mathchoice{\int\mskip-8mu\dashint\mskip-8mu\dashint}
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int} %not yet used
{\dashint\mskip-6mu\int}} %not yet used
\def\diam{\mathop{\text{diam}}}
\def\discrpage{\ifnum\stylenumber=1{\frnewpage} %redefined in mt.tex
\else\ifnum\stylenumber=3{\frnewpage}
\else\ifnum\stylenumber=5{\frnewpage}
\else\bigskip\fi\fi\fi}
\long\def\discrversionA#1#2{\ifnum\stylenumber=1#1\else#2\fi}
\long\def\discrversionB#1#2{\ifnum\stylenumber=2#1\else#2\fi}
\long\def\discrversionC#1#2{\ifnum\stylenumber=3#1\else#2\fi}
\long\def\discrversionD#1#2{\ifnum\stylenumber=4#1\else#2\fi}
\long\def\discrversionE#1#2{\ifnum\stylenumber=5#1\else#2\fi}
\long\def\discrversionF#1#2{\ifnum\stylenumber=6#1\else#2\fi}
\long\def\discrversionG#1#2{\ifnum\stylenumber=7#1\else#2\fi}
\long\def\discrversionH#1#2{\ifnum\stylenumber=8#1\else#2\fi}
% facility for special interpolations in particular output
% versions
\def\displaycause#1{\noalign{\noindent (#1)}}
\def\displayeqn#1{$$\eqalignno{#1}$$}
\def\diverg{\mathop{\text{div}}}
\def\dom{\mathop{\text{dom}}}
\def\eae{=_{\text{a.e.}}}
\def\esssup{\mathop{\text{ess sup}}}
\mathchardef\Exists="3239
\def\family#1#2#3{\langle#3\rangle_{#1\in#2}}
\def\familyi#1#2{\family{i}{#1}{#2}}
\def\familyiI#1{\familyi{I}{#1}}
\def\frfilename#1{\ifnum\stylenumber=1{\noindent filename #1}
\else\ifnum\stylenumber=6{\noindent{\fiverm filename #1}}
\else\ifnum\stylenumber=7{\noindent{\fiverm filename #1}}
\else\fi\fi\fi}
\def\Footnote#1#2{\footnote"#1"{#2}}
\mathchardef\Forall="3238
\def\frakc{\frak c\phantom{.}}
\def\frnewpage{\vskip \pageheight plus 0pt minus\pageheight
\eject
\gdef\topparagraph{}
\gdef\bottomparagraph{}
}
\def\frsmallcirc{{\hskip 1pt plus 0pt minus 0pt}
{\raise 1pt\hbox{$\smallcirc$}}{\hskip 1pt plus 0pt minus 0pt}}
\def\geae{\ge_{\text{a.e.}}}
\def\grad{\mathop{\text{grad}}}
\def\grheada{{\bf ($\pmb{\alpha}$)}}
\def\grheadb{{\bf ($\pmb{\beta}$)}}
\def\grheadc{{\bf ($\pmb{\gamma}$)}}
\def\grheadd{{\bf ($\pmb{\delta}$)}}
\def\grheade{{\bf ($\pmb{\epsilon}$)}}
\def\grheadz{{\bf ($\pmb{\zeta}$)}}
\def\grv#1{{\accent"12 #1}}
\def\hfillall{\hskip\pagewidth plus0pt minus\pagewidth}
\def\Imag{\mathop{\Cal I\text{m}}}
\long\def\inset#1{{\narrower\narrower{\vskip 1pt plus 1pt minus 0pt}
#1
{\vskip 1pt plus 1pt minus 0pt}}}
\def\Int#1#2{\displaystyle{\int_{#1}^{#2}}}
\def\interior{\mathop{\text{int}}}
\def\leae{\le_{\text{a.e.}}}
\long\def\leaveitout#1{}
\def\LLcorner{\mathchoice{\,\hbox{\vrule height7pt width0.5pt depth0pt
\vrule height0.5pt width5pt depth0pt}\,}
{\,\hbox{\vrule height7pt width0.5pt depth0pt
\vrule height0.5pt width5pt depth0pt}\,}
{\,\hbox{\vrule height5pt width0.3pt depth0pt
\vrule height0.3pt width4pt depth0pt}\,}
{\,\hbox{\vrule height4pt width0.25pt depth0pt
\vrule height0.25pt width3pt depth0pt}\,}
}
\def\Ln{\mathop{\text{Ln}}}
\def\Loadfont#1{\font#1}
\def\loibr{\hbox{\hskip0.1em]\hskip0.05em}}
\def\Matrix#1{\pmatrix#1\endpmatrix}
\def\Mu{\text{M}}
\def\noamslogo{\def\amslogo{}}
\def\normalsubgroup{\vartriangleleft}
\def\Nu{\text{N}}
\def\ocint#1{\left]#1\right]}
\def\ofamily#1#2#3{\langle#3\rangle_{#1<#2}}
\let\oldcases=\cases
\let\oldfootnote=\footnote
\def\On{\mathop{\text{On}}}
\def\ooint#1{\left]#1\right[}
\def\openBbb#1{\Bbb#1\mskip1mu}
\def\pd#1#2{\bover{\partial#1}{\partial#2}}
\def\Pd#1#2{\Bover{\partial#1}{\partial#2}}
\def\pdd#1#2{{{\partial^2#1}\over{\partial#2^2}}}
\def\Pdd#1#2{\Bover{\partial^2#1}{\partial#2^2}}
\def\pde#1#2#3{{{\partial^2#1}\over{\partial#2\partial#3}}}
\def\Pde#1#2#3{\Bover{\partial^2#1}{\partial#2\partial#3}}
\def\Prf{\vthsp\hbox{\bf P\hskip0.07em\llap P\hskip0.07em\llap P\rm}}
\def\pushbottom#1{\hbox{\vrule height0pt depth#1 width0pt}}
\def\Qed{\vthsp\hbox{\bf Q\hskip0.07em\llap Q\hskip0.07em\llap Q\rm}}
\def\QeD{\Qed{\hskip 1.111pt plus 3.333pt minus 0pt}}
\def\Quer{\vthsp\hbox{\bf ?\hskip0.05em\llap ?\hskip0.05em\llap
?\thinspace\rm}}
\def\query{\discrversionA{\immediate\write0{query}
\global\advance\footnotenumber by 1
\oldfootnote{$^{\the\footnotenumber}$}{query}}{}}
\def\Real{\mathop{\Cal R\text{e}}}
\def\restr{\mathchoice
{\hbox{$\restriction$}\mskip 1mu}
{\hbox{$\restriction$}\mskip 1mu}
{\hbox{$\scriptstyle\restriction$}\mskip 1mu}
{\hbox{$\scriptscriptstyle\restriction$}\mskip 1mu}}
\def\restrp{\mathchoice
{\hbox{$\restriction$}\mskip 2mu}
{\hbox{$\restriction$}\mskip 2mu}
{\mskip-1mu\hbox{$\scriptstyle\restriction$}\mskip 2mu}
{\mskip-1mu\hbox{$\scriptscriptstyle\restriction$}\mskip 1mu}}
%use in \restrp V \restrp W \restrp Y
% \restrp\Cal P \restrp\Bbb R \restrp\frak
% \restrp\Omega \restrp\Tau \restrp\Upsilon
% \restrp[ \restrp\widehat{}
\def\Rho{\text{P}}
\def\roibr{\hbox{\hskip0.05em[\hskip0.1em}}
\def\RoverC{\hbox{\biggerscriptfonts${{\Bbb R}\atop{\Bbb C}}$}}
\def\sequence#1#2{\family{#1}{\Bbb N}{#2}}
\def\sequencen#1{\sequence{n}{#1}}
\def\setover#1#2{\overset{#1}\to{#2}}
\def\shortstrut{\hbox{\vrule height7.5pt depth2.5pt width0pt}}
\def\sshortstrut{\hbox{\vrule height5.8pt depth2.5pt width0pt}}
\def\smallcirc{{\scriptstyle\circ}}
\def\ssbullet{{\scriptscriptstyle\bullet}}
\def\symmdiff{\triangle}
\def\thicken#1{#1\hskip0.03em\llap #1\hskip0.03em\llap
#1\hskip0.03em\llap #1}
\def\Tau{{\text{T}}}
\def\tbf#1{\text{\bf #1}}
\def\terror#1#2#3{#1: `#2' for `#3'}
\def\today{\number\day.\number\month.\number\year}
\def\UEMDRR{University of Essex Mathematics Department Research Report}
\def\UEMDWP{University of Essex Mathematics Department Working Paper}
\def\versiondate#1{
\immediate\write0{Version of #1}
\def\vsdate{#1}
\ifnum\stylenumber=1\hfill Version of #1
\medskip
\else\ifnum\stylenumber=2\hfill Version of #1
\medskip
\else\ifnum\stylenumber=6\hfill{\fiverm Version of #1}
\medskip
\else\ifnum\stylenumber=7\hfill{\fiverm Version of #1}
\medskip
\else\ifnum\stylenumber=8\hfill Version of #1
\medskip
\else\fi\fi\fi\fi\fi}
\def\versionhead{\ifnum\stylenumber=3 \hfill PRINTER'S VERSION
\bigskip
\else\ifnum\stylenumber=4 \hfill REFEREE'S VERSION
\bigskip
\else \fi\fi}
\def\versionref{\ifnum\stylenumber=1\workingref
\else\ifnum\stylenumber=2\workingref
\else\ifnum\stylenumber=8\workingref
\else\printerref\fi\fi\fi}
\def\vthsp{\hskip0.001em}
%Missing AmSTeX can be coped with by using the following lines:
\ifamstexsupported\else
\immediate\write0{AmSTeX-unsupported version of fremtex.tex }
\fourteensavailablefalse
\def\@{@}
\def\\{\cr}
\def\AmSTeX{AmS\TeX}
\def\Bbb#1{\underline{\hbox{\bf #1}}}
\def\biggerscriptfonts{}
\def\bumpeq{=_{\text{approx}}}
\def\Cal#1{{\cal#1}}
\def\curlyeqprec{\preceq}
\def\eightit{\it}
\def\eightrm{\rm}
\def\eightsmc{\smc}
\def\eurm#1{\underline{\cal#1}}
\def\Footnote#1#2{\footnote#1#2}
\def\frac#1#2{{#1}\over{#2}}
\def\frak#1{{\hbox{\bf #1\hskip0.1em\llap #1}}}
\def\frnewpage{\vfill\eject}
\def\iint{\int\!\!\!\int}
\def\iiint{\int\!\!\!\int\!\!\!\int}
\def\iiiint{\int\!\!\!\int\!\!\!\int\!\!\!\int}
\def\llcorner{\lfloor}
\def\loadeurm{}
\def\loadeusm{}
% \def\loadeusmx#1{\def\eusm#1{\underline{\cal#1}}}
\def\ltimes{|\hskip-0.5em\times}
\def\eusm#1{\underline{\cal#1}}
\def\ltimes{|\times}
\def\Loadfont#1{}
\def\Matrix#1{\pmatrix{#1}}
\def\noamslogo{}
\def\nrightarrow{\not\rightarrow}
\def\preccurlyeq{\preceq}
\def\query{\discrversionA{\immediate\write0{query}
\footnote{$^*$}{query}}{}}
\def\restriction{|}
\def\rtimes{\times|}
\def\setover#1#2{#2^{#1}}
\def\shortstrut{\strut}
\def\smallerfonts{\eightrm}
\def\smallfrown{\wedge}
\def\smc{}
\def\spcheck{\check{\phantom{x}}}
\def\sphat{\hat{\phantom{x}}}
\def\square{\mathchoice\sqr64\sqr64\sqr43\sqr33}
\def\sqr#1#2{{\vcenter{\vbox{\hrule height.#2pt
\hbox{\vrule width.#2pt height#1pt \kern#1pt
\vrule width.#2pt}
\hrule height.#2pt}}}}
\def\pmb#1{\underline{#1}}
\def\text#1{\hbox{#1}}
\def\therefore{\ssbullet\raise.9ex\hbox{$\ssbullet$}\ssbullet}
\def\twelvebf{\bf}
\def\vartriangleleft{\triangleleft}
\def\Vdash{|\vdash}
\def\vDash{|=}
\fi
%End of lines for missing AmSTeX
\ifamstexsupported\input amstex
% \documentstyle{amsppt}
\input amsppt.sty
\PSAMSFonts
\tenpoint
%\font\eightmsb=msym8
\font\eightmsb=msbm10
\font\eighteufm=eufm10 at 8 pt
\font\eighteurm=eurm8
\font\eighteusm=eusm8
\font\varseveneufm=eufm10 at 7 pt
\scriptfont\eufmfam=\varseveneufm
\def\=#1{{\accent"16 #1}}
\gdef\nopagenumbers{\NoPageNumbers}
\else\fi
\newcount\footmarkcount
\ifDHFamstexloaded
\loadmsBm
\def\eightBbb#1{{\fam\msBfam#1}}
\loadmsFm
\def\eightfrak#1{{\fam\msFfam#1}}
\else
\def\eightBbb#1{{\scriptstyle\Bbb#1}}
\def\eightfrak#1{{\scriptstyle\frak#1}}
\fi
\ifathome\athome\fi
%interword glue (\tenrm standard):
% (space) 3.333 + 1.667 - 1.111
% (,) 3.333 + 2.083 - 0.889
% (.) 4.444 + 5. - 0.370
%very odd fact: \discrversionA{2.}{} doesn't work,
% \discrversionA{ 2.}{} does
%The false line feed introduced by my Fortran programs, leading to
%a surplus ae at the top of the next page, seems to be associated
%with Fk(\032)3081 or something similar in the PostScript file.
\smallprint
\frfilename{n11706.tex}
\versiondate{14.7.11}
\def\dotproduct{\hskip.1em\tbf{.}\hskip.1em}
\long\def\doubleinset#1{\inset{\inset{\parindent=-20pt #1}}}
\def\Gr{\mathop{\text{Gr}}\nolimits}
\def\innerprod#1#2{(#1|#2)}
\def\proof{\medskip\noindent{\bf proof} }
\def\zz{}
\Centerline{\bf Kirszbraun's theorem}
\Centerline{\smc D.H.Fremlin}
\Centerline{\it University of Essex, Colchester, England}
\medskip
\inset{\noindent Wikipedia gives a statement of this theorem and an outline
of its history, but no online source for the proof.
It's so pretty that I write one out here.}
\bigskip
\noindent{\bf\zz1 The essential ideas}
\medskip
{\bf\zz1A The context} I'll come to the actual statement of the theorem,
taken from
{\tt http:/{\bsp}en.wikipedia.org{\bsp}wiki/Kirszbraun\_theorem},
in \zz1G below. This will be in the standard full-generality form
concerning Lipschitz maps between (real) Hilbert spaces $H_1$ and $H_2$.
If you aren't familiar with `Hilbert spaces'
({\tt http://en.wikipedia.org/wiki{\bsp}Hilbert\_space}),
then you will probably prefer to start by taking both $H_1$ and $H_2$ to be
a Euclidean space $\BbbR^n$, with the inner product
\Centerline{$\innerprod{x}{y}=x\dotproduct y=\sum_{i=1}^n\xi_i\eta_i$}
\noindent if $x=(\xi_1,\ldots,\xi_n)$ and $y=(\eta_1,\ldots,\eta_n)$ belong
to $\BbbR^n$, and the norm
\Centerline{$\|x\|=\sqrt{\innerprod{x}{x}}=\sqrt{\sumop_{i=1}^n\xi_i^2}$,}
\noindent so that
\Centerline{$\|x-y\|=\sqrt{\sumop_{i=1}^n(\xi_i-\eta_i)^2}$}
\noindent is the Euclidean distance from $x$ to $y$ calculated with
the $n$-dimensional version of Pythagoras' theorem. In fact all the
really interesting ideas of the proof, in \zz1B-\zz1F below, are
needed for the two-dimensional case $n=2$. (The case $n=1$ is much
easier, as noted in Wikipedia.) I do have to warn you, however, that
ordinary proofs of Kirszbraun's theorem involve `Tychonoff's theorem'
(see \zz2B below), and unless the words `topology', `compact set' and
`continuous function' mean something to you, you are going to have a good
deal of work to do to understand the `first proof' offered in \S\zz2.
There is an alternative method using `filters' which I will describe in
\S\zz3, but this also demands some highly abstract reasoning on top of
basic real analysis.
\bigskip
{\bf\zz1B The miraculous bit: Lemma} Let $H_1$ and $H_2$ be Hilbert
spaces. Suppose that $J$ is
a non-empty finite subset of $H_1$, and $g:J\to H_2$ a function such
that $\|g(x)-g(y)\|\le\|x-y\|$ and $\|g(x)\|>\|x\|$ for all
$x$, $y\in J$. Then $0$ does not belong to the convex hull $\Gamma(f[J])$
of $f[J]=\{g(x):x\in J\}$.
\proof Note first that, for any $x$, $y\in J$,
$$\eqalign{\innerprod{x}{y}
&=\Bover12(\|x\|^2+\|y\|^2-\|x-y\|^2)\cr
&<\Bover12(\|g(x)\|^2+\|g(y)\|^2-\|g(x)-g(y)\|^2)
=\innerprod{g(x)}{g(y)}\cr}$$
\noindent because $\|x\|<\|g(x)\|$, $\|y\|<\|g(y)\|$ and
$\|x-y\|\ge\|g(x)-g(y)\|$. Now
suppose that $w\in\Gamma(f[J])$. Then there is a family
$\family{x}{J}{\lambda_x}$ of non-negative real numbers such that
$\sum_{x\in J}\lambda_x=1$ and $w=\sum_{x\in J}\lambda_xg(x)$. So
$$\eqalignno{\|w\|^2
&=\innerprod{w}{w}
=\innerprod{\sum_{x\in J}\lambda_xg(x)}{\sum_{y\in J}\lambda_yg(y)}
=\sum_{x,y\in J}\lambda_x\lambda_y\innerprod{g(x)}{g(y)}\cr
&>\sum_{x,y\in J}\lambda_x\lambda_y\innerprod{x}{y}\cr
\displaycause{because $\innerprod{g(x)}{g(y)}>\innerprod{x}{y}$, therefore
$\lambda_x\lambda_y\innerprod{g(x)}{g(y)}
\ge\lambda_x\lambda_y\innerprod{x}{y}$, for all $x$, $y\in J$, and there is
at least one $x\in J$ such that $\lambda_x>0$, so that
$\lambda_x\lambda_x\innerprod{g(x)}{g(x)}
>\lambda_x\lambda_x\innerprod{x}{x}$}
&=\innerprod{\sum_{x\in J}\lambda_xx}{\sum_{y\in J}\lambda_yy}
=\|\sum_{x\in J}\lambda_xx\|^2
\ge 0,\cr}$$
\noindent and $w\ne 0$.
\bigskip
{\bf\zz1C Basic facts about Hilbert spaces: Lemma} Let $H$ be a
Hilbert space.
(a)(i) For any $x$, $y\in H$,
$|\innerprod{x}{y}|\le\|x\|\|y\|$.
\quad(ii) For any $x\in H$,
$\|x\|=\max\{\innerprod{x}{c}:c\in H$, $\|c\|\le 1\}$.
(b) For any $x$, $y\in H$,
$\|x+y\|^2+\|x-y\|^2=2\|x\|^2+2\|y\|^2$.
(c) If $C\subseteq H$ is a non-empty closed convex set,
and $b\in H$, then
there is a $b'\in C$ such that $\innerprod{z-b}{b'-b}\ge\|b'-b\|^2$
for every $z\in C$.
(d) If $f:H\to\Bbb R$ is a linear functional and
$\gamma=\sup\{|f(x)|:x\in H$, $\|x\|\le 1\}$ is finite, there is a
unique $c\in H$ such that
$f(x)=\innerprod{x}{c}$ for every $x\in H$.
(e) If $I\subseteq H$ is finite, then $\Gamma(I)$ is compact for the norm
topology on $H$.
\medskip
\noindent{\bf Remark} As I said in \zz1A, if you don't know what a Hilbert
space is, just take $H$ to be $\BbbR^n$ for some $n$ -- in fact, the case
$n=2$ is already enough to use every idea here.
\proof{\bf (a)(i)} (This is the `Cauchy-Schwarz inequality'.)
If either $x$ or $y$ is zero then we have $0$ on both sides.
Otherwise, set $\alpha=\|x\|$ and $\beta=\|y\|$ and consider
$$\eqalign{0&\le\|\beta x-\alpha y\|^2
=\innerprod{\beta x-\alpha y}{\beta x-\alpha y}\cr
&=\beta^2\|x\|^2-2\alpha\beta\innerprod{x}{y}
+\alpha^2\|y\|^2
=2\alpha^2\beta^2-2\alpha\beta\innerprod{x}{y};\cr}$$
\noindent dividing by $2\alpha\beta>0$,
$0\le\alpha\beta-\innerprod{x}{y}$ and
$\innerprod{x}{y}\le\alpha\beta=\|x\|\|y\|$.
Similarly,
\Centerline{$-\innerprod{x}{y}=\innerprod{-x}{y}
\le\|-x\|\|y\|=\|x\|\|y\|$,}
\noindent so $|\innerprod{x}{y}|\le\|x\|\|y\|$.
\medskip
\quad{\bf (ii)}
In particular, if $\|c\|\le 1$, then $\innerprod{x}{c}\le\|x\|$.
In the other direction, if $x=0$ then $\|x\|=0=\innerprod{x}{0}$, while
otherwise we can set $c=\Bover1{\|x\|}x$ and see that
$\|c\|=1$ and $\innerprod{x}{c}=\Bover1{\|x\|}\|x\|^2=\|x\|$.
\medskip
{\bf (b)}
$$\eqalign{\|x+y\|^2+\|x-y\|^2
&=\innerprod{x+y}{x+y}+\innerprod{x-y}{x-y}\cr
&=\|x\|^2+2\innerprod{x}{y}+\|y\|^2+\|x\|^2-2\innerprod{x}{y}+\|y\|^2
=2\|x\|^2+2\|y\|^2.\cr}$$
{\bf (c)(i)} The set $\{\|z-b\|:z\in C\}\subseteq\Bbb R$
is non-empty and has a lower bound, so it has a greatest lower bound
$\alpha$ say. For each $n\in\Bbb N$, set
$C_n=\{z:z\in C$, $\|z-b\|\le\alpha+4^{-n}\}$.
Then $\|z-z'\|\le 2^{-n}\sqrt{8\alpha+4}$ for all $z$, $z'\in C_n$.
To see this, note
that because $C$ is convex, $w=\bover12(z+z')$ belongs to $C$, so
$\|w-b\|\ge\alpha$. Now
$$\eqalignno{4\alpha^2
&=\|2w-2b\|^2
=\|(z_1-b)+(z_2-b)\|^2\cr
&=2\|z_1-b\|^2+2\|z_2-b\|^2-\|(z_1-b)-(z_2-b)\|^2\cr
\displaycause{by (b) just above}
&\le 4(\alpha+4^{-n})^2-\|z_1-z_2\|^2,\cr}$$
\noindent so
\Centerline{$\|z_1-z_2\|^2
\le 4((\alpha+4^{-n})^2-\alpha^2)
=8\alpha\cdot 4^{-n}+4\cdot 4^{-2n}
\le 4^{-n}(8\alpha+4)$}
\noindent and $\|z_1-z_2\|\le 2^{-n}\sqrt{8\alpha+4}$.
\medskip
\quad{\bf (ii)} Since every $C_n$ is non-empty, we can choose a sequence
$\sequencen{z_n}$ in $H$ such that $z_n\in C_n$ for every $n\in\Bbb N$.
In this case, $\|z_m-z_n\|\le 2^{-m}\sqrt{8\alpha+4}$ whenever $m\le n$,
because in this case both $z_m$ and $z_n$ belong to $C_m$. So
$\sequencen{z_n}$ is a Cauchy sequence and has a limit $b'$ in
$H$.\footnote{This is where we need to know that $H$ is a Hilbert space,
rather than just an inner product space.}
Because every $z_n$ belongs to $C$, and $C$ is closed, $b'\in C$; and
now
\Centerline{$\alpha\le\|b'-b\|=\lim_{n\to\infty}\|z_n-b\|\le\alpha$,}
\noindent so $\|b'-b\|=\alpha$.
\medskip
\quad{\bf (iii)} Next, for $z\in C$,
we know that $\delta z+(1-\delta)b'\in C$
for every $\delta\in\ocint{0,1}$, because $C$ is convex.
But this means that
$$\eqalign{\|b'-b\|^2
&\le\|\delta z+(1-\delta)b'-b\|^2
=\|\delta(z-b)+(1-\delta)(b'-b)\|^2\cr
&=\delta^2\|z-b\|^2+2\delta(1-\delta)\innerprod{z-b}{b'-b}
+(1-\delta)^2\|b'-b\|^2;\cr}$$
\noindent subtracting $\|b'-b\|^2$ from both sides,
\Centerline{$0
\le\delta^2\|z-b\|^2+2\delta(1-\delta)\innerprod{z-b}{b'-b}
-2\delta\|b'-b\|^2+\delta^2\|b'-b\|^2$;}
\noindent dividing by $2\delta>0$,
\Centerline{$0
\le\Bover12\delta\|z-b\|^2+(1-\delta)\innerprod{z-b}{b'-b}
-\|b'-b\|^2+\Bover12\delta\|b'-b\|^2$;}
\noindent rearranging the terms,
\Centerline{$\|b'-b\|^2-\innerprod{z-b}{b'-b}
\le\Bover12\delta(\Bover12\|z-b\|^2-2\innerprod{z-b}{b'-b}
+\|b'-b\|^2)$;}
\noindent letting $\delta\downarrow 0$,
\Centerline{$\|b'-b\|^2-\innerprod{z-b}{b'-b}\le 0$,}
\noindent that is,
\Centerline{$\innerprod{z-b}{b'-b}\ge\|b'-b\|^2$.}
\medskip
{\bf (d)(i)} I'll start by checking that there can be at most one $c$ with
this property. If $f(x)=\innerprod{x}{c}=\innerprod{x}{c'}$ for every
$x\in H$, then
\Centerline{$\|c-c'\|^2
=\innerprod{c-c'}{c-c'}
=\innerprod{c-c'}{c}-\innerprod{c-c'}{c'}
=f(c-c')-f(c-c')
=0$,}
\noindent and $c-c'=0$, that is, $c=c'$.
So I just have to show that there is some $c$ which will serve.
\medskip
\quad{\bf (ii)} If $f(x)=0$ for every $x\in H$, we can, and must,
take $c=0$. So from now on I will suppose that we have a $b\in H$ such
that $f(b)\ne 0$.
\medskip
\quad{\bf (iii)} Set $C=\{x:f(x)=0\}$. Then $C$ is
a linear subspace of $H$ (because $f(0)=0$, so $0\in C$, and if
$x$, $y\in C$ and $\alpha$, $\beta\in\Bbb R$ then
$f(\alpha x+\beta y)=\alpha f(x)+\beta f(y)=0$, so
$\alpha x+\beta y\in C$). In particular, $C$ is a non-empty convex set.
It will help to know that $|f(x)|\le\gamma\|x\|$ for every $x\in H$; this
is certainly true if $x=0$, since then $|f(x)|=0=\gamma\|x\|$; and for
non-zero $x$ we have $\|\Bover1{\|x\|}x\|=1$, so that
$\Bover1{\|x\|}|f(x)|=|f(\Bover1{\|x\|}x)|\le\gamma$ and
$|f(x)|\le\gamma\|x\|$. In particular, $\gamma\|b\|\ge|f(b)|>0$
and $\gamma>0$.
\medskip
\quad{\bf (iv)} Next, $C$ is closed. For if $x$ is any point of
$H\setminus C$, and $\|y-x\|\le\Bover1{2\gamma}|f(x)|$, then
\Centerline{$|f(y)-f(x)|
=|f(y-x)|\le\gamma\|y-x\|\le\Bover12|f(x)|<|f(x)|$}
\noindent and $f(y)\ne 0$, that is, $y\notin C$. Thus any point of
$H\setminus C$ is the centre of a non-trivial ball included in
$H\setminus C$, and $H\setminus C$ is open, that is, $C$ is closed.
\medskip
\quad{\bf (v)} We can therefore appeal to (c) just above to find a
$b'\in C$ such that $\innerprod{z-b}{b'-b}\ge\|b'-b\|^2$ for every
$z\in C$. In this case
$$\eqalign{\innerprod{z-b'}{b'-b}
&=\innerprod{(z-b)-(b'-b)}{b'-b}
=\innerprod{z-b}{b'-b}-\innerprod{b'-b}{b'-b}\cr
&=\innerprod{z-b}{b'-b}-\|b'-b\|^2
\ge 0\cr}$$
\noindent for every $z\in C$. In fact, if $z\in C$, then
\Centerline{$\innerprod{z}{b'-b}
=\innerprod{(z+b')-b'}{b'-b}
\ge 0$}
\noindent because $z+b'\in C$. Consequently we also have
\Centerline{$-\innerprod{z}{b'-b}
=\innerprod{-z}{b'-b}
\ge 0$}
\noindent for every $z\in C$, because then $-z$ also belongs to $C$.
Thus $\innerprod{z}{b'-b}=0$ for every $z\in C$. In particular,
$\innerprod{b'}{b'-b}=0$, so
\Centerline{$\innerprod{b}{b'-b}=\innerprod{b-b'}{b'-b}
=-\innerprod{b'-b}{b'-b}=-\|b'-b\|^2$.}
\medskip
\quad{\bf (vi)} Since $f(b)\ne 0$, $b\ne b'$, $\|b'-b\|>0$,
$\beta=-\Bover{f(b)}{\|b'-b\|^2}$ is defined and we can try
$c=\beta(b'-b)$. In this case,
\Centerline{$\innerprod{b}{c}
=\beta\innerprod{b}{b'-b}
=-\beta\|b'-b\|^2
=f(b)$,}
\noindent while
\Centerline{$\innerprod{z}{c}
=\beta\innerprod{z}{b'-b}
=0$}
\noindent whenever $z\in C$.
\medskip
\quad{\bf (vii)} Finally, given $x\in H$, consider
$x'=x-\Bover{f(x)}{f(b)}b$. We have
\Centerline{$f(x')=f(x)-\Bover{f(x)}{f(b)}f(b)=0$,}
\noindent so $x'\in C$ and
\Centerline{$\innerprod{x}{c}
=\innerprod{x-x'}{c}+\innerprod{x'}{c}
=\innerprod{\Bover{f(x)}{f(b)}b}{c}+0
=\Bover{f(x)}{f(b)}\innerprod{b}{c}
=f(x)$.}
\noindent Thus we have found a suitable $c$.
\medskip
{\bf (e)} The hypercube $[0,1]^I$ is compact, and the simplex
\Centerline{$S=\{\family{x}{I}{\lambda_x}:\lambda_x\ge 0$ for every
$x\in I$, $\sum_{x\in I}\lambda_x=1\}$,}
\noindent being a closed subset of $[0,1]^I$, is also compact; now
the function $\family{x}{I}{\lambda_x}\mapsto\sum_{x\in I}\lambda_xx$ is a
continuous surjection from $S$ onto $K$, so $K$ also is compact.
\medskip
{\bf\zz1D The key to the door: Lemma} Let $H_1$ and $H_2$ be Hilbert
spaces, $I\subseteq H_1$ a finite
set, $f:I\to H_2$ a function such that $\|f(x)-f(y)\|\le\|x-y\|$ for all
$x$, $y\in I$, and $a$ any point of $H_1$. Then there is a
$b\in H_2$ such that $\|b-f(x)\|\le\|a-x\|$ for every $x\in I$.
\proof{\bf (a)} If $I=\emptyset$ we can set $b=0$;
if $a\in I$ we can set $b=f(a)$. So let us suppose from
now on that $I$ is not empty and $a\notin I$.
\medskip
{\bf (b)}
Set $K=\Gamma(f[I])$. Then $K$ is a non-empty convex
subset of $H_2$. Also
$K$ is compact for the norm topology of $H_2$, by Lemma \zz1Ca.
For each $x\in I$, the functions $z\mapsto\|z-f(x)\|$ and
$z\mapsto\Bover{\|z-f(x)\|}{\|a-x\|}$ from $K$ to $\coint{0,\infty}$
are continuous.
Again because $I$ is finite, the function $h:K\to\coint{0,\infty}$
defined by saying
that $h(z)=\max_{x\in I}\Bover{\|z-f(x)\|}{\|a-x\|}$ is continuous.
So $h$ attains its infimum; let $b\in K$ be such that $h(b)\le h(z)$ for
every $z\in K$. Set
\Centerline{$\gamma=h(b)$,
\quad$J=\{x:x\in I$, $\Bover{\|b-f(x)\|}{\|a-x\|}=\gamma\}$.}
\noindent Of course $J$ is a non-empty subset of $I$.
\medskip
{\bf (c)} We find that $b$ has to belong to $\Gamma(f[J])$. To see this,
argue by contradiction: suppose that $b\notin\Gamma(f[J])$. Now
$\Gamma(f[J])$ is a compact convex subset of $H_2$, by Lemma \zz1Ca again.
By Lemma \zz1Cb, there is a $b'\in\Gamma(f[J])$ such that
$\innerprod{z-b}{b'-b}\ge\|b'-b\|^2$ for
every $z\in\Gamma(f[J])$; in particular,
$\innerprod{f(x)-b}{b'-b}\ge\|b'-b\|^2$ for every $x\in J$.
Now consider $b_{\delta}=(1-\delta)b+\delta b'=b+\delta(b'-b)$ for small
$\delta>0$. We always have $b_{\delta}\in K$ because $b$ and $b'$ belong
to the convex set $K$. If $x\in J$, then
\Centerline{$\innerprod{f(x)-b}{b_{\delta}-b}
=\delta{f(x)-b}{b'-b}\ge\delta\|b'-b\|^2$,}
\noindent so
$$\eqalign{\|f(x)-b_{\delta}\|^2
&=\|(f(x)-b)-(b_{\delta}-b)\|^2
=\|f(x)-b\|^2-2\innerprod{f(x)-b}{b_{\delta}-b}+\|b_{\delta}-b\|^2\cr
&\le\|f(x)-b\|^2-2\delta\|b'-b\|^2+\delta^2\|b'-b\|^2
<\|f(x)-b\|^2\cr}$$
\noindent whenever $0<\delta\le 1$. So
\Centerline{$\Bover{\|f(x)-b_{\delta}\|}{\|a-x\|}
<\Bover{\|f(x)-b\|}{\|x-a\|}=\gamma$}
\noindent whenever $0<\delta\le 1$. On the other hand, for
$x\in I\setminus J$, we know that
\Centerline{$\lim_{\delta\downarrow 0}\Bover{\|f(x)-b_{\delta}\|}{\|x-a\|}
=\Bover{\|f(x)-b\|}{\|x-a\|}<\gamma$,}
\noindent so there is a $\delta_x>0$ such that
$\Bover{\|f(x)-b_{\delta}\|}{\|x-a\|}<\gamma$ whenever
$0<\delta\le\delta_x$. Because $I\setminus J$ is finite, we can now find
a $\delta>0$ such that $\delta\le\delta_x$ for every $x\in I\setminus J$.
But we shall now have
\Centerline{$\Bover{\|f(x)-b_{\delta}\|}{\|x-a\|}<\gamma$}
\noindent for every $x\in I$, so that $h(b_{\delta})<\gamma=h(b)$. And we
chose $b$ to minimise $h$, so this ought to be impossible.
\medskip
{\bf (d)} Thus $b\in\Gamma(f[J])$. We can therefore apply Lemma \zz1B, as
follows. Set $J'=\{x-a:x\in J\}$.
Define $g:J'\to H_2$ by setting $g(x)=f(x+a)-b$ for $x\in J'$.
Note that if $x$, $y\in J'$, then
$$\eqalign{\|g(x)-g(y)\|
&=\|(f(x+a)-b)-(f(y+a)-b)\|
=\|f(x+a)-f(y+a)\|\cr
&\le\|(x+a)-(y+a)\|
=\|x-y\|.\cr}$$
\Centerline{$\|g(x)\|=\|f(x+a)-b\|=\|b-f(x+a)\|=\gamma\|x\|$.}
\noindent Because $b$ belongs to $\Gamma(f[J])$, we can express it as
$\sum_{x\in J}\lambda_xf(x)$ where $\lambda_x\ge 0$ for every $x\in J$ and
$\sum_{x\in J}\lambda_x=1$. In this case
$$\eqalign{\sum_{x\in J'}\lambda_{x+a}g(x)
&=\sum_{x\in J'}\lambda_{x+a}(f(x+a)-b)
=\sum_{x\in J}\lambda_x(f(x)-b)\cr
&=\sum_{x\in J}\lambda_xf(x)-\sum_{x\in J}\lambda_xb
=b-b
=0,\cr}$$
\noindent while of course $\lambda_{x+a}\ge 0$ for every $x\in J'$ and
$\sum_{x\in J'}\lambda_{x+a}=\sum_{x\in J}\lambda_x=1$. So
$0\in\Gamma(g[J'])$. By Lemma \zz1B, there must be an $x\in J'$ such that
$\|x\|\ge\|g(x)\|=\gamma\|x\|$; that is, there is an $x\in J$ sucy that
$\|x-a\|\ge\gamma\|x-a\|$. But we decided long ago, in (a) above, that we
were looking only at the case in which $a\notin I$, so that $x-a\ne 0$ and
$\gamma\le 1$.
\medskip
{\bf (e)} Finally, returning to the definition of $\gamma$ in (b), we see
that $h(b)\le 1$, that is, $\|f(x)-b\|\le\|x-a\|$ for every $x\in I$,
so that we have the point we need.
\bigskip
{\bf\zz1E Corollary} Let $H_1$ and $H_2$ be Hilbert spaces,
$I\subseteq H_1$ a finite
set, $\gamma\in\coint{0,\infty}$ a non-negative real number,
$f:I\to H_2$ a function such that $\|f(x)-f(y)\|\le\gamma\|x-y\|$ for all
$x$, $y\in I$, and $a$ any point of $H_1$. Then there is a
$b\in H_2$ such that $\|b-f(x)\|\le\gamma\|a-x\|$ for every $x\in I$.
\medskip
\proof If $\gamma=0$ then $f$ must be constant and we can take $b$ to be
the constant value of $f$ (or $0$ if $I$ is empty). Otherwise, set
$g(x)=\Bover1{\gamma}f(x)$ for $x\in I$. Then
\Centerline{$\|g(x)-g(y)\|=\Bover1{\gamma}\|f(x)-f(y)\|\le\|x-y\|$}
\noindent for $x\in I$. By Lemma \zz1E, there is a $b_1\in H_2$ such that
$\|b_1-g(x)\|\le\|a-x\|$ for every $x\in I$. Set $b=\gamma b_1$; then
$\|b-f(x)\|=\gamma\|b_1-g(x)\|\le\gamma\|a-x\|$ for every $x\in I$.
\bigskip
{\bf\zz1F Corollary} Let $H_1$ and $H_2$ be Hilbert spaces,
$I$, $J\subseteq H_1$ finite sets, $\gamma\in\coint{0,\infty}$ and
$f:I\to H_2$ a function such that $\|f(x)-f(y)\|\le\gamma\|x-y\|$ for all
$x$, $y\in I$. Then there is a function $g:I\cup J\to H_2$ such that
$g(x)=f(x)$ for every $x\in I$ and
$\|g(x)-g(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in I\cup J$.
\proof Induce on the number $\#(J)$ of elements of $J$. For the base
step, when $\#(J)=0$, we have $J=\emptyset$ and we can take $g=f$.
For the inductive step to $\#(J)=n+1$ where $n\in\Bbb N$, take any
$a\in J$, and set $J'=J\setminus\{a\}$. Then $\#(J')=n$, so the inductive
hypothesis tells us that there is a function $f_1:I\cup J'\to H_2$ such
that $f_1(x)=f(x)$ for every $x\in I$ and
$\|f_1(x)-f_1(y)\|\le\gamma\|x-y\|$
whenever $x$, $y\in I\cup J'$. If $a\in I\cup J'$ then $I\cup J=I\cup J'$
and we can take $g=f_1$. Otherwise,
Lemma \zz1E, applied to $f_1$, tells us that
there is a $b\in H_2$ such that $\|f_1(x)-b\|\le\gamma\|x-a\|$ for every
$x\in I\cup J'$. So if we define $g:I\cup J\to H_2$ by setting
$$\eqalign{g(x)
&=f_1(x)\text{ if }x\in I\cup J',\cr
&=b\text{ if }x=a,\cr}$$
\noindent then we shall have
\Centerline{$g(x)=f_1(x)=f(x)$ for every $x\in I$,}
$$\eqalign{\|g(x)-g(y)\|
&=\|f_1(x)-f_1(y)\|\le\gamma\|x-y\|\text{ if }x,\,y\in I\cup J',\cr
&=\|f_1(x)-b\|\le\gamma\|x-a\|=\gamma\|x-y\|\text{ if }x\in I\cup J'
\text{ and }y=a,\cr
&=\|b-f_1(y)\|=\|f_1(y)-b\|\le\gamma\|y-a\|=\gamma\|x-y\|\cr
&\mskip100mu
\text{ if }x=a\text{ and }y\in I\cup J',\cr
&=\|b-b\|=0=\gamma\|x-x\|\text{ if }x=a\text{ and }y=a.\cr}$$
\noindent So $g$ has the required property and the induction continues.
\bigskip
{\bf\zz1G Kirszbraun's Theorem} Let $H_1$ and $H_2$ be Hilbert spaces,
$A\subseteq H_1$ a set and
$f:A\to H_2$ a function. Suppose that $\gamma\ge 0$ is such that
$\|f(x)-f(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in A$. Then there is a
function $g:H_1\to H_2$ such that $g(x)=f(x)$ for every $x\in A$ and
$\|g(x)-g(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in H_1$.
\bigskip
{\bf\zz1H Miracles and keys} I'll come to actual proofs of this theorem in
\S\S\zz2-\zz3 below. But I ought to explain why I've labelled the
paragraphs in the way that I have. \zz1G is a `theorem' because it's the
target of this whole note; it's a striking, useful and non-obvious fact,
which makes it a prize to grasp and hold. \zz1C is a list of `basic
facts' because if you have done anything with Hilbert spaces you should
know most of them, and if you hope to do anything with Hilbert spaces (even
the finite-dimensional ones) you should put them all in your tool-box.
\zz1E and \zz1F are `corollaries' because I think there is a chance that
they will be pretty well
obvious; \zz1E is just a re-scaling of \zz1D, and \zz1F is a natural
induction. (Of course when I say `natural', I don't mean that anyone is
born with an instinct to do this sort of thing,
in the way that a baby is born with
instincts to grasp and suckle. I mean that after you have had
a bit of training, the
word `finite set' will trigger an impulse to look in succession at the
cases of sets with $0$, $1$ and $2$ elements, and try to see if one will
help with the next.)
Now between \zz1B and \zz1D I make a further distinction. When I say that
\zz1D is the `key', what I mean is, that an experienced
pure mathematician (for whom at least one of \S\zz2 or \S\zz3
below should be essentially obvious) will see at once that it has got to be
true (if the target theorem is true at all) and that with this established,
the rest ought to be mopping up. Furthermore, the idea in part (a) of the
proof, picking $b$ to minimize $\max_{x\in I}\Bover{\|b-f(x)\|}{\|a-x\|}$,
may not come instantly to mind, but is easy to remember and
is the kind of trick which often works. But even with these hints,
the proof of Lemma \zz1D can present real difficulties if you do not have a
friend or a book to point you to a version of the idea in \zz1B. And
\zz1B doesn't remind me of anything I have seen anywhere else.
That is why I call it a `miracle'. Of course it is no more miraculous
than Pythagoras' theorem. But it does stand by itself; it is a
fact about the geometry of Euclidean space for which I do not have a
picture to show me why it works.
\bigskip
\noindent{\bf\zz2 First proof}
\medskip
In \zz1H, I said that with Lemma \zz1D and its corollary \zz1F in hand the
rest of the proof of Kirszbraun's theorem is mopping up. Essentially
there is just one way of doing this, but it can be expressed in more than
one way. If you have done a conventional first course in functional
analysis, with Tychonoff's theorem and the Banach-Alaoglu theorem, the
following is likely to be the most natural approach. If not, you may find
that the technique in \S\zz3 below is more directly accessible,
\bigskip
{\bf\zz2A Weak topologies} Let $H$ be a Hilbert space.
Then $H$ has a {\bf weak topology}
for which all the functionals $x\mapsto\innerprod{x}{y}$, for $y\in H$, are
continuous, and every ball $B=\{x:\|x\|\le\alpha\}$, for
$\alpha\ge 0$, is compact.
\medskip
\noindent{\bf Remark} This is really a special case of
the Banach-Alaoglu theorem, because if
we identify $H$ with its own dual space (using Lemma \zz1Cd)
then its weak topology is just its
weak* topology. If this remark doesn't make much sense to you, then note
that if $H=\BbbR^n$, as considered in \zz1A above, then you just have to
know that the functionals $x\mapsto\innerprod{x}{y}=x\dotproduct y$ are
continuous in the usual sense, and the balls $\{x:\|x-b\|\le\alpha\}$
are compact in the sense of the $n$-dimensional Heine-Borel and
Bolzano-Weierstrass theorems.
\bigskip
{\bf\zz2B Tychonoff's
theorem} ({\tt http://en.wikipedia.org/wiki/Tychonoff's\_theorem})
Suppose that we are given any family $\familyiI{X_i}$ of compact
spaces. Let $X=\prod_{i\in I}X_i$ be the set of
functions $g$ defined on $I$ such that $g(i)\in X_i$ for every $i\in I$.
Then $X$ has a {\bf product topology} for which all the functions
$g\mapsto g(i):X\to X_i$ are continuous and $X$ is compact.
I'm afraid that we are going to want this theorem with $I=H_1$. So
there are no real short cuts, and even if you are willing to take the
theorem on trust for the moment, you are going to have to think about
continuous functions and compact sets in non-trivial topological spaces.
\bigskip
{\bf\zz2C Proof of \zz1G} I repeat the target:
\medskip
\noindent{\bf Kirszbraun's Theorem} Let $H_1$ and $H_2$ be Hilbert spaces,
$A\subseteq H_1$ a set and
$f:A\to H_2$ a function. Suppose that $\gamma\ge 0$ is such that
$\|f(x)-f(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in A$. Then there is a
function $g:H_1\to H_2$ such that $g(x)=f(x)$ for every $x\in A$ and
$\|g(x)-g(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in H_1$.
\proof{\bf (a)} If $A=\emptyset$ then we can
just set $g(x)=0$ for every $x\in H_1$. So let us suppose from now on that
$A$ has at least one member; fix $a\in A$.
\medskip
{\bf (b)} For each $x\in H_1$, let $B_x\subseteq H_2$ be the ball
\Centerline{$\{y:\|y\|\le\|f(a)\|+\gamma\|x-a\|\}$}
\noindent so that $B_x$ is a compact subset of $H_2$ when given its weak
topology. By Tychonoff's theorem, $X=\prod_{x\in H_1}B_x$ is compact in
its product topology. Now, for any finite set $I\subseteq H_1$, set
$$\eqalign{F_I
&=\{g:g\in X,\,g(x)=f(x)\text{ for every }x\in I\cap A,\cr
&\mskip100mu\|g(x)-g(y)\|\le\gamma\|x-y\|
\text{ for every }x,\,y\in I\}.\cr}$$
\medskip
{\bf (c)} We have to check that all these sets $F_I$ are non-empty.
To see this, note that by Corollary \zz1F there is a function
$g_0:I\to H_2$ such that $g_0(x)=f(x)$ for every
$x\in (I\cup\{a\})\cap A$ and
$\|g_0(x)-g_0(y)\|\le\gamma\|x-y\|$ for every $x$, $y\in I\cup\{a\}$.
Now
$$\eqalign{\|g_0(x)\|
&=\|f(a)+(g(x)-f(a))\|
\le\|f(a)\|+\|g(x)-f(a)\|\cr
&=\|f(a)\|+\|g_0(x)-g_0(a)\|
\le\|f(a)\|+\gamma\|x-a\|,\cr}$$
\noindent so $g_0(x)\in B_x$, for every $x\in I$. If we now set
$$\eqalign{g(x)
&=g_0(x)\text{ for }x\in I,\cr
&=0\text{ for other }x\in H_1,\cr}$$
\noindent we shall have $g\in X$ and therefore $g\in F_I$.
\medskip
{\bf (d)} We have to check that all the sets $F_I$ are closed.
To see this, note that for each $x\in I\cap A$ the map
$g\mapsto g(x):X\to B_x$ is continuous and the set $\{f(x)\}$ is a closed
set, so $\{g:g\in X$, $g(x)=f(x)\}$ is closed. At the same time, for
$x$, $y\in I$, the maps $g\mapsto g(x)$ and $g\mapsto g(y)$
from $X$ to $H_2$ are continuous when $H_2$ is given its weak topology;
while the function $z\mapsto\innerprod{z}{c}:H_2\to\Bbb R$ is
continuous for every $c\in H_2$. So $g\mapsto\innerprod{g(x)}{c}$,
$g\mapsto\innerprod{g(y)}{c}$ and $g\mapsto\innerprod{g(x)-g(y)}{c}$ from
$X$ to $\Bbb R$ are all continuous; consequently
$\{g:\innerprod{g(x)-g(y)}{c}\le\gamma\|x-y\|\}$ is closed in $X$.
Now by Lemma \zz1Ca,
\Centerline{$\{g:\|g(x)-g(y)\|\le\gamma\|x-y\|\}
=\bigcap_{\|c\|\le 1}\{g:\innerprod{g(x)-g(y)}{c}\le\gamma\|x-y\|\}$}
\noindent is an intersection of closed subsets of $X$, so is closed.
Finally,
\Centerline{$F_I
=\bigcap_{x\in I\cap A}\{g:g(x)=f(x)\}\cap\bigcap_{x,y\in I}
\{g:\|g(x)-g(y)\|\le\gamma\|x-y\|\}$}
\noindent is in turn an intersection of closed sets, so is closed.
\medskip
{\bf (e)} Set $\Cal E=\{F_I:I\subseteq H_1$ is finite$\}$. Then
we have just seen that $\Cal E$ is a family of closed sets. Also it has
the finite intersection property. For if
$I_0,\ldots,I_n\subseteq H_1$ are finite sets containing $a$, then
$I=\bigcup_{i\le n}I_i$ is finite, and
\Centerline{$\bigcap_{i\le n}F_{I_i}\supseteq F_I\ne\emptyset$.}
\medskip
{\bf (f)} Thus we have a compact space $X$ and a family $\Cal E$ of closed
subsets of $X$ with the finite intersection property. There is therefore
a $g\in X$ which belongs to every member of $\Cal E$, that is,
$g\in F_I$ whenever $I\subseteq H_1$ is finite and contains $a$.
In particular, if $x\in A$, then $g\in F_{\{a,x\}}$ so $g(x)=f(x)$, while
if $x$, $y\in H_1$, then $g\in F_{\{a,x,y\}}$ so
$\|g(x)-g(y)\|\le\gamma\|x-y\|$. But this means that $g$ is a function
with the properties we need.
\bigskip
\noindent{\bf\zz3 Second proof}
\medskip
The argument in \zz2C above took a variety of topological concepts and
manipulations for granted. Even if you are interested only in the case
$H_1=H_2=\BbbR^2$ (so that all the sets $B_x$ are just disks),
and have some idea of what a compact set in the plane
looks like, and are willing to take Tychonoff's theorem on trust,
the proof may have gone rather briskly. I will therefore describe an
alternative route. It will take longer because I will not call explicitly
on either the Banach-Alaoglu theorem or Tychonoff's theorem, and in fact I
will incorporate what amount to proofs of these theorems. In a sense,
therefore, this is a more `elementary' proof, and may be more accessible if
you have done no functional analysis. Even if you have done enough to
make \S\zz2 reasonably straightforward, the techniques here are an
essential part of general topology, and are worth studying for that reason.
\medskip
{\bf\zz3A Filters: three definitions (a)} If $X$ is a set, a
{\bf filter} on $X$ is a family $\Cal F$ of subsets of $X$ such that
\inset{$X\in\Cal F$;
$\emptyset\notin\Cal F$;
if $A\in\Cal F$ and $A\subseteq B\subseteq X$ then $B\in\Cal F$;
if $A$, $B\in\Cal F$ then $A\cap B\in\Cal F$.}
\medskip
{\bf (b)} If $X$ is a set, an {\bf ultrafilter} on $X$ is a
filter $\Cal G$ on $X$ such that
\inset{for every $A\subseteq X$, either $A\in\Cal G$ or
$X\setminus A\in\Cal G$.}
\medskip
{\bf (c)} If $X$ is a set, a {\bf filter base} on $X$ is a family
$\Cal E$ of subsets of $X$ such that
\inset{$\Cal E$ is not empty;
$\emptyset\notin\Cal E$;
if $A$, $B\in\Cal E$ there is a $C\in\Cal E$ such that
$C\subseteq A\cap B$.}
\medskip
{\bf (d)} If you have never seen these words before, don't worry; I will
try to explain everything fully. But you will need to watch very closely,
because we shall be completely dependent on the logic of set theory, and
every word of the definitions above is vital. Perhaps I should point out
at once that if $\Cal F$ is a filter on $X$ then $X$ cannot be empty,
because $X\in\Cal F$ and $\emptyset\notin\Cal F$.
\medskip
{\bf (e)} We can get a bit more practice with the following:
if $X$ is a
set and $\Cal E$ is a filter base on $X$, there is a filter $\Cal F$ on $X$
which includes $\Cal E$. In fact there is an easy formula for one. Try
\Centerline{$\Cal F=\{A:A\subseteq X$ and there is some $E\in\Cal E$ such
that $E\subseteq A\}$.}
\noindent Working through the definition of `filter', we have
\inset{----- every member of $\Cal F$ is a subset of $X$ because that's
written into the formula for $\Cal F$;
----- $\emptyset\notin\Cal F$ because the only subset of $\emptyset$ is
itself, and $\emptyset\notin\Cal E$;
----- $X\in\Cal F$ because $\Cal E$ is not empty, and if $A\in\Cal E$ then
$A\subseteq X\subseteq X$;
----- if $A\in\Cal F$ and $A\subseteq B\subseteq X$, there is an
$E\in\Cal E$ such that $E\subseteq A$, and now $E\subseteq B$, so
$B\in\Cal F$;
----- if $A$, $B\in\Cal F$ then there are $E$, $F\in\Cal E$ such that
$E\subseteq A$ and $F\subseteq B$; now there is a $C\in\Cal E$ such that
$C\subseteq E\cap F$, so we have $C\subseteq A\cap B\subseteq X$ and
$A\cap B\in\Cal F$.}
\noindent So all the clauses of the definition in (a) are satisfied, mostly
because they match the clauses of the definition in (c).
\bigskip
{\bf\zz3B Limits along filters} The most important reason for thinking
about filters is the following. Suppose that $X$ is a set, $\Cal F$ is a
filter on $X$, $\phi:X\to\Bbb R$ is a function, and $\alpha\in\Bbb R$.
Then we say that {\bf $\phi$ converges to $\alpha$ along $\Cal F$} if for
every $\epsilon>0$ the set $\{t:t\in X$, $|\phi(t)-\alpha|\le\epsilon\}$
belongs to $\Cal F$.
I think this is the first $\epsilon$ in this note. We got through the
whole of the first proof of Kirszbraun's theorem without a single
$\epsilon$, though I have a limit in part (c-iii) of the proof of Lemma
\zz1C, and all the ideas on continuity in \zz2A-\zz2C depend, at bottom, on
$\epsilon$s and $\delta$s.
We now have some more practice on elementary properties of filters. These
ought to remind you of limits of sequences.
\bigskip
{\bf\zz3C Proposition} Let $X$ be a set and $\Cal F$ a filter on
$X$.
(a) If
$\phi:X\to\Bbb R$ is a function, there can be at most one $\alpha\in\Bbb R$
such that $\phi$ converges to $\alpha$ along $\Cal F$. We can therefore
write
\Centerline{$\lim_{t\to\Cal F}\phi(t)=\alpha$}
\noindent to mean that this happens.
(b) Suppose that $\phi:X\to\Bbb R$ is a function and
$\lim_{t\to\Cal F}\phi(t)=\alpha$. Then
$\lim_{t\to\Cal F}\beta\phi(t)=\beta\alpha$ for every $\beta\in\Bbb R$.
(c) If $\phi:X\to\Bbb R$ and $\psi:X\to\Bbb R$ are such that
$\lim_{t\to\Cal F}\phi(t)=\alpha$ and $\lim_{t\to\Cal F}\psi(t)=\beta$,
then $\lim_{t\to\Cal F}\phi(t)+\psi(t)=\alpha+\beta$.
\proof{\bf (a)} If $\phi$ converges along $\Cal F$ to both $\alpha$ and
$\alpha'$, then for any $\epsilon>0$ the sets
\Centerline{$A=\{t:t\in X$, $|\phi(t)-\alpha|\le\Bover12\epsilon\}$,
\quad$A'=\{t:t\in X$, $|\phi(t)-\alpha'|\le\Bover12\epsilon\}$}
\noindent both belong to $\Cal F$. So $A\cap A'\in\Cal F$ and
$A\cap A'$ is not empty, by the fourth and second clauses in the definition
of `filter'. Take any $t\in A\cap A'$; then
\Centerline{$|\alpha-\alpha'|\le\|\alpha-\phi(t)|+|\phi(t)-\alpha'|
\le\Bover12\epsilon+\Bover12\epsilon=\epsilon$.}
\noindent So $|\alpha-\alpha'|\le\epsilon$ for every $\epsilon>0$ and
$\alpha=\alpha'$.
\medskip
{\bf (b)} Let $\epsilon>0$. Then the set
\Centerline{$A=\{t:t\in X$,
$|\phi(t)-\alpha|\le\Bover{\epsilon}{1+|\beta|}\}$}
\noindent belongs to $\Cal F$. Now if $t\in A$,
\Centerline{$|\beta\phi(t)-\beta\alpha|=|\beta||\phi(t)-\alpha|
\le\Bover{\epsilon|\beta|}{1+|\beta|}\le\epsilon$.}
\noindent So $\{t:t\in X$, $|\beta\phi(t)-\beta\alpha|\le\epsilon\}$
includes $A$ and belongs to $\Cal F$. As $\epsilon$ is arbitrary,
$\lim_{t\to\Cal F}\beta\phi(t)=\beta\alpha$.
\medskip
{\bf (c)} Let $\epsilon>0$. Then the sets
\Centerline{$A=\{t:t\in X$,
$|\phi(t)-\alpha|\le\Bover{\epsilon}2$,
\quad$A=\{t:t\in X$,
$|\psi(t)-\beta|\le\Bover{\epsilon}2\}$}
\noindent belong to $\Cal F$. Now if $t\in A\cap B$,
\Centerline{$|\phi(t)+\psi(t))-\alpha-\beta|
\le|\phi(t)-\alpha|+|\psi(t)-\beta|
\le\Bover{\epsilon}2+\Bover{\epsilon}2=\epsilon$.}
\noindent So $\{t:t\in X$,
$|(\phi(t)+\psi(t))-(\alpha+\beta)|\le\epsilon\}$
includes $A\cap B$ and belongs to $\Cal F$. As $\epsilon$ is arbitrary,
$\lim_{t\to\Cal F}\phi(t)+\psi(t)=\alpha+\beta$.
\medskip
\noindent{\bf Remark} You will see that the definition of `filter' is
almost exactly what is needed to make this proposition work. (I haven't
used the clause `$X\in\Cal F$', but everything else is called on.)
Not everyone who teaches the elementary theory of convergence of sequences
is careful to point out that a sequence can have at most one limit. But I
hope you can see that the grammar of the sentences
`$\lim_{n\to\infty}t_n=\alpha$', `$\lim_{t\to\Cal F}\phi(t)=\alpha$'
insists on this being true. Of course not all sequences have limits, and
to have a limit along a filter is also the exception rather than the rule
-- any appearance to the contrary is because we don't trouble to mention
the cases when there is no limit.
\bigskip
{\bf\zz3D} Now for something which doesn't correspond directly to anything
you will have seen for limits of sequences.
\medskip
\noindent{\bf Proposition} Let $X$ be a set, $\Cal G$ an ultrafilter on $X$
and $\phi:X\to\Bbb R$ a function such that
$B=\{t:t\in X$, $|\phi(t)|\le\gamma\}$ belongs to $\Cal G$ for some
$\gamma\ge 0$. Then $\lim_{t\to\Cal G}\phi(t)$ is defined and
belongs to $[-\gamma,\gamma]$.
\proof For $\alpha\in\Bbb R$, set
\Centerline{$A_{\alpha}=\{t:t\in X$, $\phi(t)\ge\alpha\}$.}
\noindent Consider $C=\{\alpha:\alpha\in\Bbb R$, $A_{\alpha}\in\Cal G\}$.
We have
\Centerline{$A_{-\gamma}\supseteq B\in\Cal G$,}
\noindent so $-\gamma\in C$.
If $\alpha\in C$ then $A_{\alpha}\cap B\in\Cal G$ and
$A_{\alpha}\cap B\ne\emptyset$. There is therefore a $t\in X$ such that
$\phi(t)\ge\alpha$ and $|\phi(t)|\le\gamma$; in which case
$\alpha\le\phi(t)\le\gamma$. Thus $\gamma$ is an upper bound for $C$.
Putting these together, $C$ is a non-empty subset of $\Bbb R$ with an upper
bound in $\Bbb R$, and has a supremum $\beta$ say, with
$-\gamma\le\beta\le\gamma$.
If $\epsilon>0$, then $\beta+\epsilon\notin C$, so that
$A_{\beta+\epsilon}\notin\Cal G$. But $\Cal G$ is supposed to be an
ultrafilter, so $X\setminus A_{\beta+\epsilon}\in\Cal G$. At the same
time, $\beta-\epsilon$ is not an upper bound for $C$, so there is an
$\alpha\in C$ such that $\beta-\epsilon\le\alpha$,
and $A_{\alpha}\in\Cal G$. Putting these together,
\Centerline{$A_{\alpha}\setminus A_{\beta+\epsilon}
=A_{\alpha}\cap(X\setminus A_{\beta+\epsilon})\in\Cal G$.}
\noindent But if $t\in A_{\alpha}\setminus A_{\beta+\epsilon}$, then
\Centerline{$\beta-\epsilon\le\alpha\le\phi(t)\le\beta+\epsilon$}
\noindent and $|\phi(t)-\beta|\le\epsilon$. Thus
$\{t:t\in X$, $|\phi(t)-\beta|\le\epsilon\}$ includes
$A_{\alpha}\setminus A_{\beta+\epsilon}$ and must belong to $\Cal G$.
As $\epsilon$ is arbitrary, $\lim_{t\to\Cal G}\phi(t)=\beta$ is defined and
belongs to $[-\gamma,\gamma]$.
\bigskip
{\bf\zz3E The Ultrafilter Lemma} Whenever $\Cal F$ is a filter on a set
$X$, there is an ultrafilter $\Cal G$ on $X$ including $\Cal F$.
\medskip
\noindent{\bf Remark} I will make no attempt to prove this, for
reasons which I will try to explain in \S\zz4. For the moment, I will ask
you to take it as a theorem of more or less the same kind as Tychonoff's
theorem (\zz2B above). See {\tt
http://en.wikipedia.org/wiki{\bsp}Ultrafilter\_lemma}.
\bigskip
{\bf\zz3F Proof of \zz1G} Once again, I repeat the target:
\medskip
\noindent{\bf Kirszbraun's Theorem} Let $H_1$ and $H_2$ be Hilbert spaces,
$A\subseteq H_1$ a set and
$f:A\to H_2$ a function. Suppose that $\gamma\ge 0$ is such that
$\|f(x)-f(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in A$. Then there is a
function $g^*:H_1\to H_2$ such that $g^*(x)=f(x)$ for every $x\in A$ and
$\|g^*(x)-g^*(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in H_1$.
\proof I begin by setting up just the same structure as that used in \zz2C.
\medskip
{\bf (a)} If $A=\emptyset$ then we can
set $g(x)=0$ for every $x\in H_1$. So let us suppose from now on that
$A$ has at least one member; fix $a\in A$.
For each $x\in H_1$, let $B_x\subseteq H_2$ be the ball
\Centerline{$\{y:\|y\|\le\|f(a)\|+\gamma\|x-a\|\}$.}
\noindent Now, for any finite set $I\subseteq H_1$, set
$$\eqalign{F_I
&=\{g:g\in X,\,g(x)=f(x)\text{ for every }x\in I\cap A,\cr
&\mskip100mu\|g(x)-g(y)\|\le\gamma\|x-y\|
\text{ for every }x,\,y\in I\}.\cr}$$
\medskip
{\bf (b)} We have to check that all these sets $F_I$ are non-empty.
To see this, note that by Corollary \zz1F there is a function
$g_0:I\to H_2$ such that $g_0(x)=f(x)$ for every
$x\in (I\cup\{a\})\cap A$ and
$\|g_0(x)-g_0(y)\|\le\gamma\|x-y\|$ for every $x$, $y\in I\cup\{a\}$.
Now
$$\eqalign{\|g_0(x)\|
&=\|f(a)+(g(x)-f(a))\|
\le\|f(a)\|+\|g(x)-f(a)\|\cr
&=\|f(a)\|+\|g_0(x)-g_0(a)\|
\le\|f(a)\|+\gamma\|x-a\|,\cr}$$
\noindent so $g_0(x)\in B_x$, for every $x\in I$. If we now set
$$\eqalign{g(x)
&=g_0(x)\text{ for }x\in I,\cr
&=0\text{ for other }x\in H_1,\cr}$$
\noindent we shall have $g\in X$ and therefore $g\in F_I$.
\medskip
{\bf (c)} Now we start to diverge from the line in \zz2C.
If $I$, $J\subseteq H_1$ are finite sets then $I\cup J$ is a
finite subset of $H_1$ and $F_{I\cup J}\subseteq F_I\cap F_J$. So
$\Cal E=\{F_I:I\subseteq H_1$ is finite$\}$ is a filter base on $X$.
There are therefore a filter $\Cal F$ on $X$ including $\Cal E$, by \zz3Ae
above, and an ultrafilter $\Cal G$ on $X$ including $\Cal F$, by
the Ultrafilter Lemma.
\medskip
{\bf (d)} Suppose that $x\in H_1$ and $z\in H_2$. Then
$$\eqalignno{|\innerprod{f(x)}{z}|
&\le\|f(x)\|\|z\|\cr
\displaycause{Lemma \zz3(a-i)}
&\le(\|f(a)\|+\gamma\|x-a\|)\|z\|\cr}$$
\noindent for every $f\in X$. By Proposition \zz3D,
$\lim_{f\to\Cal G}\innerprod{f(x)}{z}$ is defined; call it
$\phi_x(z)$. We also have
$|\phi_x(z)|\le(\|f(a)\|+\gamma\|x-a\|)\|z\|$.
\medskip
{\bf (e)} Fix $x\in H_1$ for the moment. Then we have a
functional $\phi_x:H_2\to\Bbb R$. This is
linear, because by Lemma \zz3Cc and \zz3Cd,
$$\eqalign{\phi_x(\alpha z)
&=\lim_{f\to\Cal G}\innerprod{f(x)}{\alpha z}
=\lim_{f\to\Cal G}\alpha\innerprod{f(x)}{z}\cr
&=\alpha\lim_{f\to\Cal G}\innerprod{f(x)}{z}
=\alpha\phi_x(z),\cr}$$
$$\eqalign{\phi_x(w+z)
&=\lim_{f\to\Cal G}\innerprod{f(x)}{w+z}
=\lim_{f\to\Cal G}\innerprod{f(x)}{w}+\innerprod{f(x)}{z}\cr
&=\lim_{f\to\Cal G}\innerprod{f(x)}{w}
+\lim_{f\to\Cal G}\innerprod{f(x)}{z}
=\phi_x(w)+\phi_x(z)\cr}$$
\noindent for all $w$, $z\in H_2$ and $\alpha\in\Bbb R$. We have already
seen, at the end of (d) just above,
that for any $x\in H_1$ there is a constant
$\gamma_x=\|f(a)\|+\gamma\|x-a\|$ such that $|\phi_x(z)|\le\gamma_x$
whenever $z\in H_2$ and $\|z\|\le 1$. So Lemma \zz1Cd tells us that there
is a unique member of $H_2$, which we can call $g^*(x)$, such that
$\phi_x(z)=\innerprod{g^*(x)}{z}$ for every $z\in H_2$.
\medskip
{\bf (f)} This defines a function $g^*$ from $H_1$ to $H_2$. Now consider
its properties. Suppose that $x\in A$. Then
$F_{\{x\}}\in\Cal E\subseteq\Cal F\subseteq\Cal G$, and $g(x)=f(x)$ for
every $g\in F_{\{x\}}$. If $z\in H_2$ and $\epsilon>0$, then
$\{g:|\innerprod{g(x)}{z}-\phi_x(z)|\le\epsilon\}\in\Cal G$, so
$F_{\{x\}}\cap\{g:|\innerprod{g(x)}{z}-\phi_x(z)|\le\epsilon\}$ belongs to
$\Cal G$ and is not empty; take $g\in F_{\{x\}}$ such that
$|\innerprod{g(x)}{z}-\phi_x(z)|\le\epsilon$. Then
\Centerline{$|\innerprod{f(x)-g^*(x)}{z}|
=|\innerprod{f(x)}{z}-\innerprod{g^*(x)}{z}|
=|\innerprod{g(x)}{z}-\phi_x(z)|
\le\epsilon$.}
\noindent As $\epsilon$ is arbitrary, $\innerprod{f(x)-g^*(x)}{z}=0$.
This is true for every $z\in H_2$, so $f(x)=g^*(x)$.
\medskip
{\bf (g)} Now suppose that $x$, $y\in H_1$. Then
$F_{\{x,y\}}\in\Cal E\subseteq\Cal G$, and $\|g(x)-g(y)\|\le\gamma\|x-y\|$
for every $g\in F_{\{x,y\}}$. Again, take any $z\in H_2$ and
$\epsilon>0$. We know that
\Centerline{$\lim_{g\to\Cal G}\innerprod{g(x)}{z}=\phi_x(z)$,
\quad$\lim_{g\to\Cal G}\innerprod{g(y)}{z}=\phi_y(z)$,}
\noindent so
$$\eqalignno{\lim_{g\to\Cal G}\innerprod{g(x)-g(y)}{z}
&=\lim_{g\to\Cal G}\innerprod{g(x)}{z}-\innerprod{g(y)}{z}
=\lim_{g\to\Cal G}\innerprod{g(x)}{z}-\lim_{g\to\Cal G}\innerprod{g(y)}{z}
\cr
\displaycause{using \zz3Cb and \zz3Cc again}
&=\phi_x(z)-\phi_y(z)
=\innerprod{g^*(x)}{z}-\innerprod{g^*(y)}{z}
=\innerprod{g^*(x)-g^*(y)}{z}.\cr}$$
\noindent Accordingly
\Centerline{$\{g:
|\innerprod{g(x)-g(y)}{z}-\innerprod{g^*(x)-g^*(y)}{z}|\le\epsilon\}$}
\noindent belongs to $\Cal G$ and must meet $F_{\{x,y\}}$. Take
$g\in F_{\{x,y\}}$ such that
$|\innerprod{g(x)-g(y)}{z}-\innerprod{g^*(x)-g^*(y)}{z}|\le\epsilon$;
then
$$\eqalignno{|\innerprod{g^*(x)-g^*(y)}{z}|
&\le\epsilon+|\innerprod{g(x)-g(y)}{z}|
\le\epsilon+\|g(x)-g(y)\|\|z\|\cr
\displaycause{\zz1C(a-i) again}
&\le\epsilon+\gamma\|x-y\|\|z\|.\cr}$$
\noindent As $\epsilon$ is arbitrary,
$|\innerprod{g^*(x)-g^*(y)}{z}|\le\gamma\|x-y\|\|z\|$; as
$z$ is arbitrary, $\|g^*(x)-g^*(y)\|\le\gamma\|x-y\|$, by
\zz1C(a-ii).
\medskip
{\bf (h)} Putting (f) and (g) together, we see that $g^*$ has the required
properties, and the proof is complete.
\bigskip
\noindent{\bf\zz4 The magic of choice}
\medskip
In the proofs above, I have mentioned three major results: a special case
of the Banach-Alaoglu theorem (\zz2A), Tychonoff's theorem (\zz2B) and the
Ultrafilter Lemma (\zz3E).
All three can be proved if we are willing
to use the Axiom of Choice ({\tt
http://en.wikipedia.org{\bsp}wiki/Axiom\_of\_choice}).
Here I should like to offer some thoughts on
what we should make of this.
\medskip
{\bf\zz4A Miracles and magic (a)} I called \zz1B a `miracle'. This is
pitching it strong, but conveys the notion that there is something singular
about it. In distinction to this, I would call the Ultrafilter Lemma
`magic'. We intone the spell `let $\Cal G$ be an ultrafilter including
$\Cal F$' and a door opens. But $\Cal G$ is indescribable and
uncontrolled. I didn't offer any actual examples
of ultrafilters because {\it without} a special axiom of some kind there
are very few of them, and all those which can be described
explicitly in the ordinary language of mathematics are quite useless.
An ultrafilter is generally
a jinn which we have called into our service. If we call at the right
moment, we can get very good service. But is this black magic or white
magic?
\medskip
{\bf (b)} The Axiom of Choice can be
stated in various ways, but the one which seems most natural in the context
here is
\doubleinset{(AC) If $\familyiI{X_i}$ is any family of non-empty sets, then
$\prod_{i\in I}X_i$ is not empty, that is, there is a function $g$ defined
on the set $I$ such that $g(i)\in X_i$ for every $i\in I$.}
\noindent Put like this, AC seems an entirely natural principle. For
finite sets $I$, in fact, it is easily proved by induction on $\#(I)$.
I actually used a simple version of it in the proof of Lemma \zz1C above.
In part (c-ii) of that proof, I wrote `since every $C_n$ is non-empty, we
can choose a sequence $\sequencen{z_n}$ such that $z_n\in C_n$ for every
$n$', that is, $\sequencen{z_n}\in\prod_{n\in\Bbb N}C_n$. I do not think
I have ever had a student who noticed that anything special was being done
in such cases (I am sure I did not notice myself, until it was pointed out
to me).
The proofs that AC implies the Ultrafilter Lemma and Tychonoff's theorem
are not natural in the way that choosing a sequence is, but are undoubtedly
part of ordinary abstract pure mathematics.
It is fair to say that the great majority of pure
mathematicians use AC and its consequences without scruple
whenever they come in handy.
\medskip
{\bf (c)} I myself believe that it is better to be
conscious of the occasions on which one is relying on it. Partly I think
that one of the things mathematics is for is to raise our consciousness of
what we are really doing. Partly I feel that proofs
not using choice (when available) are more illuminating than the
alternatives, even when they are longer and more effort.
And partly I believe that
there are rival axioms, actually contradicting AC, which are well
worth exploring (the most interesting, at the moment, being the `Axiom of
Determinacy',
{\tt http:/{\bsp}en.wikipedia.org/wiki/Axiom\_of\_determinacy}).
You will be quite unable to join in this exploration if you are not
aware which of your favourite theorems may have vanished in the new
landscape.
\medskip
{\bf (d)} So we are led naturally to the question: do we really need AC
to prove Kirszbraun's theorem? Especially we should ask: do we really
need AC to prove Kirszbraun's theorem when both Hilbert spaces are
finite-dimensional Euclidean spaces, starting with $\BbbR^2$? because such
strong magic, whether black or white, should not be needed if we can see
what we are doing.
\bigskip
{\bf\zz4B First things first (a)}
As I noted in \zz4Ab, I did use AC, in a very
simple form, during the proof of \zz1Cc. In fact it is not really
necessary here. The key to avoiding it is to use the correct definition
of `Hilbert space'. Now everyone agrees that a Hilbert space is a
complete inner product space
({\tt http://en.wikipedia.org/wiki/Hilbert\_space}). But not everyone
uses the correct definition of `complete'. The standard definition
({\tt http://en.wikipedia.org/wiki/Complete\_metric\_space}) declares that
a metric space $(X,\rho)$ is complete if every Cauchy sequence in $X$ is
convergent. Working from this, you won't be able to prove further
properties of $X$ without getting hold of a Cauchy sequence, which is what
I do in part (c-ii) of the proof of \zz1C. And to get an actual sequence
you are likely to have to choose all its terms simultaneously -- or, what
demands a slightly stronger use of AC, one at a time in an inductive
process. So I myself use a different definition of `complete metric
space'. I say that a metric space $(X,\rho)$ is complete if every Cauchy
{\it filter} converges. I see that I have to give you two more
definitions. First, if $(X,\rho)$ is a metric space,
a filter $\Cal F$ on $X$ {\bf converges} to a point $x\in X$ if
$\{y:y\in X$, $\rho(x,y)\le\epsilon\}$ belongs to $\Cal F$ for every
$\epsilon>0$. (This is like \zz3B, but without the function $\phi$ -- or,
if you like, replacing $\phi$ with the identity function from $X$ to
itself.) Second, a filter $\Cal F$ on $X$ is a {\bf Cauchy} filter if for
every $\epsilon>0$ there is a set $A\in\Cal F$ with diameter at most
$\epsilon$, that is, such that $\rho(x,y)\le\epsilon$ for all $x$,
$y\in A$.
\medskip
{\bf (b)} If you will follow me this far, and agree that a Hilbert space is
an inner product space in which every Cauchy filter converges, then
the proof of \zz1Cc can be rewritten with no choosing of sequences.
For the sets $C_n=\{z:z\in C$, $\|z-b\|\le\alpha+4^{-n}\}$ are defined by a
formula. I'm not asking a jinn to tell me what to do here. Next,
$C_m\cap C_n=C_n$ whenever $m\le n$, so $\Cal E=\{C_n:n\in\Bbb N\}$ is a
filter base. There is therefore a filter $\Cal F$ on $H$ including
$\Cal E$, by \zz3Ae (which also gives an explicit formula for $\Cal F$).
Next, the diameter of $C_n$ is at most $2^{-n}\sqrt{8\alpha+4}$ (part (c-i)
of the proof of \zz1C). Since
$\lim_{n\to\infty}2^{-n}\sqrt{8\alpha+4}=0$, and every $C_n$ belongs to
$\Cal F$, $\Cal F$ is a Cauchy filter. $\Cal F$ therefore converges to
some $b'\in H$. Of course we need to check that because $C\in\Cal F$ and
$C$ is closed, $b'\in C$, and also that $\|b'-b\|\le\alpha$, which takes a
little manoeuvre of the same kind as those in parts (f) and (g) of the
proof in \zz3F. But now we can repeat the argument of part (c-iii) of the
proof of \zz1C.
\medskip
{\bf (c)} Obviously this won't do unless the Hilbert spaces we know and
love, and also those which turn up in other parts of mathematics (either
pure or applied), are complete in the Cauchy-filter sense. But they all
are. For instance, there is a proof that a Cauchy filter on $\Bbb R$ is
convergent which essentially follows the line of Proposition \zz3D above.
We just have to find a different reason for concluding that if
$A_{\beta+\epsilon}\notin\Cal F$ then
$X\setminus A_{\beta+2\epsilon}\in\Cal F$. (Look at where a
set of diameter at most $\epsilon$ which belongs to $\Cal F$ must be.)
And now we can get to finite-dimensional Euclidean spaces, and even
$\ell^2$, by looking at coordinates in the same way as we do for
Cauchy-sequence completeness. We need slightly more refined techniques,
but the hardest part of the exercise is getting used to handling filters at
all. It is trickier to get one's mind around the idea of filter than the
idea of sequence. But, in return, we can write down our own formulae
for filters in contexts where we have
to ask for magical help in building sequences.
\bigskip
{\bf\zz4C The heavy lifting} All the rest of \S\zz1 goes through with no
call for AC. By the time we have reached \zz1F, we are a little short of
explicit formulae, but we are claiming the existence of only one function
$g$ at a time, and that function defined only on a finite set $I\cup J$.
(If we wanted to talk about a whole family
$\langle g_{IJ}\rangle_{I,J\subseteq H_1\text{ are finite}}$, of course, we
should then need some form of AC.) Moreover, if (as I have repeatedly
said) we care mostly about the finite-dimensional case, then there is no
problem in \zz2A; when $H=\BbbR^n$, the weak topology is actually the norm
topology, and we have direct proofs to show that
closed balls are compact. (I must say I think these are easier and
cleaner if you use filters, but you don't have to. You're allowed to
induce on $n$, if you find it helps.
Just make sure that you aren't choosing sequences without
giving formulae for them.)
However, even if $H_1=\Bbb R$ and $H_2=\BbbR^2$, the argument of
\zz2C demands that we look at an uncountably infinite product
$X=\prod_{x\in H_1}B_x$. And this really does seem to involve us with
Tychonoff's theorem, by no means in its full strength (because all the
compact sets $B_x$ are simple ones, by the standards of general topology),
but certainly in a form which isn't consistent with the Axiom of
Determinacy, for instance.
I have not yet figured out just how much of the Ultrafilter Lemma we need
for Kirzsbraun's theorem in the full generality stated. (We don't need
the whole of AC; it's known that it's possible for AC to be false but the
Ultrafilter Lemma true -- see {\smc Halpern \& Levy 71}.) However, for
{\it separable} $H_1$ and $H_2$ (including Euclidean spaces and $\ell^2$,
and the great majority of Hilbert spaces required in ordinary
applications), there is a way round, necessarily harder work with no jinn
to help us, but a good example of technique.
\bigskip
{\bf\zz4D Clearing the way} I had better make it clear what I mean by
saying that a Hilbert space $H$ is `separable';
I mean that there is a countable set which is dense for the norm. Since a
countable set is, by definition, either finite or equipollent with
$\Bbb N$, and since $H$ is not empty, there will be a sequence
$\sequencen{x_n}$ in $H$ such that $\{x_n:n\in\Bbb N\}$ is dense.
\bigskip
{\bf\zz4E} Next, it will be helpful to have the notion of `limit superior'
along filters.
\medskip
\noindent{\bf Definition} If $X$ is a set, $\Cal F$ is a filter on $X$ and
$\phi:X\to\Bbb R$ is a function, then I will write
\Centerline{$\limsup_{t\to\Cal F}\phi(t)
=\inf_{A\in\Cal F}\sup_{t\in A}\phi(t)$.}
\noindent In this formula, I am willing to allow
$\sup_{t\in A}\phi(t)=\infty$ if $\phi$ is not bounded above on $A$,
$\limsup_{t\to\Cal F}\phi(t)=\infty$ if $\phi$ is unbounded above on every
$A\in\Cal F$, and $\limsup_{t\to\Cal F}\phi(t)=-\infty$ if
$\{\sup_{t\in A}\phi(t):A\in\Cal F\}$ is unbounded below.
\bigskip
{\bf\zz4F Proposition} Let $X$ be a set and $\Cal F$ a filter on $X$.
Suppose that $\phi:X\to\Bbb R$ is a function such that for every
$\epsilon>0$ there is a function $\psi:X\to\Bbb R$ such that
($\alpha$) $\lim_{t\to\Cal F}\psi(t)$ is defined in $\Bbb R$ ($\beta$)
there is an $A\in\Cal F$ such that $|\phi(t)-\psi(t)|\le\epsilon$ for every
$t\in A$. Then $\lim_{t\to\Cal F}\phi(t)$ is defined in $\Bbb R$.
\proof{\bf (a)} There are a $B_0\in\Cal F$ and a $\psi_0:X\to\Bbb R$ such
that $\beta_0=\lim_{t\to\Cal F}\psi_0(t)$ is defined and
$|\phi(t)-\psi_0(t)|\le 1$ for every $t\in B_0$. Next, there is a
$B_1\in\Cal F$ such that $|\psi_0(t)-\beta_0|\le 1$ for every
$t\in B_1$. In this case, $B_0\cap B_1\in\Cal F$ and
$|\phi(t)-\beta_0|\le 2$ for every $t\in B_0\cap B_1$. It follows at
once that
\Centerline{$\limsup_{t\to\Cal F}\phi(t)\le\sup_{t\in B_0\cap B_1}\phi(t)
\le\beta_0+2$;}
\noindent at the same time, if $A$ is any member of $\Cal F$, there is a
$t_0\in A\cap B_0\cap B_1$, so
\Centerline{$\sup_{t\in A}\phi(t)\ge\phi(t_0)\ge\beta_0-2$;}
\noindent putting these together, $\alpha=\limsup_{t\to\Cal F}\phi(t)$ lies
between $\beta_0-2$ and $\beta_0+2$, and is finite.
\medskip
{\bf (b)} Let $\epsilon>0$. Then there is an $A_0\in\Cal F$ such that
$\sup_{t\in A_0}\phi(t)\le\alpha+\epsilon$;
there are a $\psi:X\to\Bbb R$ and an $A_1\in\Cal F$ such that
$\beta=\lim_{t\to\Cal F}\psi(t)$ is defined and
$|\phi(t)-\psi(t)|\le\bover15\epsilon$ for every $t\in A_1$; and there is
an $A_2\in\Cal F$ such that $|\psi(t)-\beta|\le\bover15\epsilon$ for every
$t\in A_2$. As $A=A_0\cap A_1\cap A_2$ belongs to $\Cal F$,
$\sup_{t\in A}\phi(t)\ge\alpha$, and there is a $t_1\in A$ such that
$\phi(t_1)\ge\alpha-\bover15\epsilon$; in which case
\Centerline{$\beta\ge\psi(t_1)-\Bover15\epsilon
\ge\phi(t_1)-\Bover25\epsilon\ge\alpha-\Bover35\epsilon$.}
\noindent Now, for any $t\in A$,
\Centerline{$\alpha+\epsilon\ge\phi(t)\ge\psi(t)-\Bover15\epsilon
\ge\beta-\Bover25\epsilon\ge\alpha-\epsilon$,}
\noindent that is, $|\phi(t)-\alpha|\le\epsilon$. As $\epsilon$ is
arbitrary, $\lim_{t\to\Cal F}\phi(t)=\alpha$ is defined.
\bigskip
{\bf\zz4G Lemma} (a) Let $(X,\rho)$ be a complete
separable metric space, and
$F\subseteq X$ a closed subset. Then $F$ is separable.
(b) Let $(X,\rho)$ be a metric space, $(Y,\sigma)$ a complete
metric space, $A$ a subset of $X$,
and $f:A\to Y$ a function such that $\sigma(f(x),f(x'))\le\gamma\rho(x,x')$
for all $x$, $x'\in A$. Then there is a unique function
$g:\overline{A}\to Y$ such that $g(x)=f(x)$ for every $x\in A$ and
$\sigma(g(x),g(x'))\le\gamma\rho(x,x')$
for all $x$, $x'\in\overline{A}$.
\proof{\bf (a)} If $X$ is empty, this is trivial. Otherwise, let $D$ be a
countable dense subset of $X$ and
$\sequencen{x_n}$ a sequence running over $D$.
Set $K=\{(n,k):n$, $k\in\Bbb N$, $U(x_n,2^{-k})\cap F\ne\emptyset\}$, where
$U(x,\epsilon)=\{x':\rho(x',x)<\epsilon\}$ for $x\in X$ and $\epsilon>0$.
For $(n,k)\in K$, define $\sequence{i}{z_{nki}}$ inductively by saying
that
\inset{$z_{nk0}=x_n$,
given that $U(z_{nki},2^{-k-i})\cap F\ne\emptyset$, $z_{n,k,i+1}=x_m$ where
$m$ is the least member of $\Bbb N$ such that
$U(z_{nki},2^{-k-i})\cap U(x_m,2^{-k-i-1})\cap F\ne\emptyset$.}
\noindent(To see that there always is such an $m$, note that there is an
$x'\in F\cap U(z_{nki},2^{-k-i})$, and now there must be an $m$ such that
$\rho(x',x_m)<2^{-k-i-1}$.) In this case,
$\rho(z_{n,k,i+1},z_{nki})\le 2^{-k-i}+2^{-k-i-1}$ for every $i$, so
$\sequence{i}{z_{nki}}$ is a Cauchy sequence and has a limit $x'_{nk}$ in
$X$, because $X$ is complete. Now $\rho(x'_{nk},z_{nki})\le 2^{-k-i+1}$
for every $i$, so $U(x'_{nk},2^{-k-i+2})\supseteq U(z_{nki},2^{-k-i})$
meets $F$, for every $i$; because $F$ is closed, $x'_{nk}\in F$.
Now $D'=\{x'_{nk}:(n,k)\in K\}$ is a countable subset of $F$. To see that
it is dense in $F$, take any $x'\in F$ and $k\in\Bbb N$. Then there is an
$n\in\Bbb N$ such that $\rho(x_n,x')<2^{-k}$ and $(n,k)\in K$.
Next, $\rho(x'_{nk},x_n)=\rho(x'_{nk},z_{nk0})\le 2^{-k+1}$, so
$\rho(x',x'_{nk})\le 2^{-k+2}$. As $x'$ and $k$ are arbitrary,
$D'$ is dense in $F$ and $F$ is separable.
\medskip
{\bf (b)} If $A$ is empty, so is $\overline{A}$, and $g=f$ is the empty
function. Otherwise, for each $x\in\overline{A}$,
\Centerline{$\Cal F_x=\{B:B\subseteq Y$, there is a $\delta>0$ such that
$B\supseteq f[A\cap U(x,\delta)]\}$}
\noindent is a Cauchy filter on $Y$, because
$\diam(f[A\cap U(x,\delta)])\le 2\gamma\delta$ for every $\delta>0$.
If $x\in A$ then $f(x)$ belongs to every member of $\Cal F_x$ so
$g(x)=f(x)$. Next,
if $x$, $x'\in\overline{A}$ and $\epsilon>0$, there are
$x_1$, $x'_1\in A$ such that $\rho(x,x_1)$, $\rho(x',x'_1)$,
$\sigma(g(x),f(x_1))$ and $\sigma(g(x'),f(x'_1))$ are all at most
$\epsilon$; now
\Centerline{$\sigma(g(x),g(x'))\le 2\epsilon+\sigma(f(x_1),f(x'_1))
\le 2\epsilon+\gamma\rho(x_1,x'_1)
\le 2\epsilon+\gamma(2\epsilon+\rho(x,x'))$.}
\noindent This shows that
$\sigma(g(x),g(x'))\le\gamma\rho(x,x')$
for all $x$, $x'\in\overline{A}$.
Of course $g$ is unique because it is continuous and agrees with
$f$ on a dense subset of $\overline{A}$.
\medskip
\noindent{\bf Remark} In the hypothesis of part (a), when I wrote that
`$X$ is complete', of course I meant that every
Cauchy filter on $X$ is convergent; but it follows easily that every
Cauchy sequence converges.
The filters $\Cal F_x$ in part (b) of the proof belong to the standard
proof that a uniformly continuous function into a complete Hausdorff
uniform space has a uniformly continuous extension; but if you have seen
this result only for metric spaces, then it may have been done with Cauchy
sequences instead, which are problematic here.
\bigskip
{\bf\zz4H Kirszbraun's theorem without AC} We now have the following.
\medskip
\noindent{\bf Kirszbraun's Theorem} Let $H_1$ be a
separable Hilbert space, $H_2$ a Hilbert space, $A\subseteq H_1$ a set and
$f:A\to H_2$ a function. Suppose that $\gamma\ge 0$ is such that
$\|f(x)-f(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in A$. Then there is a
function $g^*:H_1\to H_2$ such that $g^*(x)=f(x)$ for every $x\in A$ and
$\|g^*(x)-g^*(y)\|\le\gamma\|x-y\|$ for all $x$, $y\in H_1$.
\proof{\bf (a)} For most of the proof (down to the end of
(e) below) I will suppose that $H_2$ also is separable. In this case,
we can follow the argument of \zz3F down to the last
sentence of part (c) there. We suppose that $a\in A$, that
$B_x=\{y:y\in H_2$, $\|y\|\le\|f(a)\|+\gamma\|x-a\|\}$ for every
$x\in H_2$, that $X=\prod_{x\in H_1}B_x$, and that $\Cal F$ is a filter on
$X$ containing
$$\eqalign{F_I
&=\{g:g\in X,\,g(x)=f(x)\text{ for every }x\in I\cap A,\cr
&\mskip100mu\|g(x)-g(y)\|\le\gamma\|x-y\|
\text{ for every }x,\,y\in I\}\cr}$$
\noindent for every finite set $I\subseteq H_1$. Note that the constant
function with value $0$ belongs to $X$, so $X$ is not empty. (Of course
this is included in the
demonstration, in part (b) of the proof in \zz3F, that
$F_{\emptyset}\ne\emptyset$.)
\medskip
{\bf (b)} We no longer expect there to be an ultrafilter including
$\Cal F$. But we can build something good enough for our purposes,
as follows. Let
$D_1\subseteq H_1$, $D_2\subseteq H_2$ be countable dense sets. Then
$D_1\times D_2$ is countable, so there is a sequence
$\sequencen{(x_n,z_n)}$ running over $D_1\times D_2$.
Now define a sequence $\sequencen{\Cal G_n}$ of filters on $X$, as follows.
Start with $\Cal G_0=\Cal F$. Given $\Cal G_n$, note that
\Centerline{$|\innerprod{g(x_n)}{z_n}|\le\|g(x_n)\|\|z_n\|
\le\|f(a)\|+\gamma\|x_n-a\|\|z_n\|$}
\noindent for every $g\in X$, so
\Centerline{$\alpha_n=\limsup_{g\to\Cal G_n}\innerprod{g(x_n)}{z_n}$}
\noindent is finite. Set
\Centerline{$\Cal G_{n+1}
=\bigcup_{C\in\Cal G_n,\epsilon>0}\{B:B\subseteq X$,
$C\cap\{g:|\alpha_n-\innerprod{g(x_n)}{z_n}|\le\epsilon\}
\subseteq B\}$.}
\noindent It is easy to see that $B\cap B'\in\Cal G_{n+1}$ whenever $B$,
$B'\in\Cal G_{n+1}$ and that $\emptyset\notin\Cal G_{n+1}$, so that
$\Cal G_{n+1}$ is a filter on $X$ including $\Cal G_n$. Continue.
At the end of the induction, set $\Cal G=\bigcup_{n\in\Bbb N}\Cal G_n$;
then $\Cal G$ also is a filter on $X$.
\medskip
{\bf (c)} The formula for $\Cal G_{n+1}$ ensures that
$\lim_{g\to\Cal G_{n+1}}\innerprod{g(x_n)}{z_n}=\alpha_n$; it follows that
$\lim_{g\to\Cal G}\innerprod{g(x_n)}{z_n}=\alpha_n$ for every $n$, and
$\lim_{g\to\Cal G}\innerprod{g(x)}{z}$ is defined for every
$x\in D_1$ and $z\in D_2$.
\medskip
{\bf (d)} It follows that $\lim_{g\to\Cal G}\innerprod{g(x)}{z}$ is defined
for every $x\in H_1$ and $z\in H_2$. To see this, I appeal to Proposition
\zz4F. Take any $\epsilon>0$. Set
\Centerline{$\delta
=\min(1,\Bover{\epsilon}{\|f(a)\|+\gamma(\|x-a\|+\|z\|+1)})>0$.}
\noindent Then
there are $x'\in D_1$, $z'\in D_2$ such that $\|x-x'\|\le\delta$ and
$\|z-z'\|\le\delta$. In this case, for any $g\in F_{\{x,x'\}}$,
$$\eqalign{|\innerprod{g(x)}{z}-\innerprod{g(x')}{z'}|
&\le|\innerprod{g(x)}{z}-\innerprod{g(x)}{z'}|
+|\innerprod{g(x)}{z'}-\innerprod{g(x')}{z'}|\cr
&=|\innerprod{g(x)}{z-z'}|
+|\innerprod{g(x)-g(x')}{z'}|\cr
&\le\|g(x)\|\|z-z'\|
+\|g(x)-g(x')\|\|z'\|\cr
&\le(\|f(a)\|+\gamma\|x-a\|)\delta
+\gamma\|x-x'\|(\|z\|+\|z'-z\|)\cr
&\le(\|f(a)\|+\gamma\|x-a\|)\delta
+\gamma\delta(\|z\|+1)
\le\epsilon.\cr}$$
\noindent But $F_{\{x,x'\}}\in\Cal G$ and
$\lim_{g\to\Cal G}\innerprod{g(x')}{z'}$ is defined. Thus the condition
of \zz4F is satisfied and we have a limit
$\lim_{g\to\Cal G}\innerprod{g(x)}{z}$.
\medskip
{\bf (e)} We have reached the same position as at the beginning of
part (e) of the proof in \zz3F, and can find an extension of $f$ as
before.
\medskip
{\bf (f)} This proves the theorem when $H_2$ is separable. For the
general case, I use Lemma \zz4G, as follows. First, by \zz4Gb, we have an
extension of $f$ to a function $f_1:\overline{A}\to H_2$ such that
$\|f_1(x)-f_1(x')\|\le\gamma\|x-x'\|$ for all $x$, $x'\in\overline{A}$.
Next, by \zz4Ga, $\overline{A}$ has a countable dense subset $D_0$ say.
In this case, the set $D_2$ of rational linear combinations of elements of
$f[D_0]$ is countable, and $\overline{D}_2$ is a closed linear subspace of
$H_2$, so is a Hilbert space in its own right. Now (a)-(e) tell us that
there is a suitable extension of $f_1$ to a function from $H_1$ to
$\overline{D}_2\subseteq H_2$.
\bigskip
{\bf\zz4I Remarks (a)} The method in \zz4H
will work whenever $H_1$ is
provided with a `well-orderable' dense set $D_1$, rather than just a
countable one; here I say that $D$ is well-orderable if there is
a well-ordering on $D$, that is, if there is an ordinal
equipollent with $D$. The point is that (having well-ordered
$D_1$) we can use this in the argument of
\zz1Ib to get a well-ordered dense subset $D_0$ of $\overline{A}$, from
which we can build well-orderings of $D_2$ and
$D_1\times D_2$. The last of these will give us an order in
which to take pairs $(x,z)$ in an inductive construction of $\Cal G$, as in
part (b) of the proof above.
\medskip
{\bf (b)} Note that the argument there includes a useful general fact:
\inset{\noindent If $X$ is a set, $\Cal G_0$ is a filter on $X$, and
$\phi:X\to\Bbb R$ is a function such that
$\limsup_{t\to\Cal G_0}\phi(t)$ is finite, then there is a filter
$\Cal G_1$ on $X$, including $\Cal G_0$, such that
$\lim_{t\to\Cal G_1}\phi(t)$ is defined in $\Bbb R$.}
\noindent But it would have done us no good to write this out as a
preparatory lemma. For it is not enough, in \zz4H, just to know that
we shall always be able to extend a filter $\Cal G_n$ suitably. We have
to have a definite recipe for the extension, so that we nowhere have to
make infinitely many choices.
\bigskip
\noindent{\bf Acknowledgement} Conversation with B.Kirchheim.
\bigskip
\noindent{\bf References}
%Banaschewski B.\ [83] `The power of the ultrafilter theorem', J.\
%London Math.\ Soc.\ (2) 27 (1983) 193-202.
%Halpern J.D.\ [64] `The independence of the axiom of choice from the
%Boolean prime ideal theorem', Fund.\ Math.\ 55 (1964) 57-66.
Halpern J.D.\ \& Levy A.\ [71] `The Boolean prime ideal theorem does not
imply the axiom of choice', pp.\ 83-134 in {\smc Scott 71}.
Kirszbraun M.D.\ [34] `\"Uber die zusammenziehenden und Lipschitzian
Transformationen', Fundamenta Math.\ 22 (1934) 77-108
({\tt http://matwbn.icm.edu.pl/ksiazki/fm{\bsp}fm22/fm22112.pdf}).
Scott D.S.\ [71] (ed.) {\it Axiomatic Set Theory.}
Amer.\ Math.\ Soc., 1971
(Proceedings of Symposia in Pure Mathematics XIII, vol.\ 1;
{\tt http://www.mediafire.com/??el9sb0onr41r7h5}).
Jech T.\ [73] {\it The Axiom of Choice.} North-Holland, 1973.
%QA 248.J4 store A 7440 1749 1
\end