edits
authorChris <chris.barker@nyu.edu>
Sun, 22 Feb 2015 14:03:42 +0000 (09:03 -0500)
committerChris <chris.barker@nyu.edu>
Sun, 22 Feb 2015 14:03:42 +0000 (09:03 -0500)
topics/_week5_simply_typed_lambda.mdwn

index c3b1cf8..cee3f91 100644 (file)
@@ -166,8 +166,31 @@ functions; but a simply-types identity function can never apply to itself.
 
 #Typing numerals#
 
 
 #Typing numerals#
 
-The Church numerals are well behaved with respect to types.  They can
-all be given the type (&sigma; --> &sigma;) --> &sigma; --> &sigma;.
+The Church numerals are well behaved with respect to types.  
+To see this, consider the first three Church numerals (starting with zero):
+
+    \s z . z
+    \s z . s z
+    \s z . s (s z)
+
+Given the internal structure of the term we are using to represent
+zero, its type must have the form &rho; --> &sigma; --> $sigma; for
+some &rho; and &sigma;.  This type is consistent with term for one,
+but the structure of the definition of one is more restrictive:
+because the first argument `s` must apply to the second argument `z`,
+the type of the first argument must describe a function from
+expressions of type &sigma; to some other type.  So we can refine &rho;
+by replacing it with the more specific type &sigma; --> &tau;.  At
+this point, the overall type is (&sigma; --> &tau;) --> &sigma; -->
+&sigma;.  Note that this refined type remains compatible with the
+definition of zero.  Finally, by examinine the definition of two, we
+see that expressions of type &tau; must be suitable to serve as
+arguments to functions of type &sigma; --> &tau;.  The most general
+way for that to be true is if &tau; &equiv; &sigma;.  So at this
+point, we have the overall type of (&sigma; --> &sigma;) --> &sigma; -->
+&sigma;.
+
+
 
 ## Predecessor and lists are not representable in simply typed lambda-calculus ##
 
 
 ## Predecessor and lists are not representable in simply typed lambda-calculus ##