8. Find a fixed point `ξ` for the successor function. Prove it's a fixed
point, i.e., demonstrate that `succ ξ <~~> ξ`.
8. Find a fixed point `ξ` for the successor function. Prove it's a fixed
point, i.e., demonstrate that `succ ξ <~~> ξ`.
- We've had surprising success embedding normal arithmetic in the lambda
-calculus, modeling the natural numbers, addition, multiplication, and
+ We've had surprising success embedding normal arithmetic in the Lambda
+Calculus, modeling the natural numbers, addition, multiplication, and
so on. But one thing that some versions of arithmetic supply is a
notion of infinity, which we'll write as `inf`. This object usually
satisfies the following constraints, for any finite natural number `n`:
so on. But one thing that some versions of arithmetic supply is a
notion of infinity, which we'll write as `inf`. This object usually
satisfies the following constraints, for any finite natural number `n`:
- (Note, though, that with some notions of infinite numbers, operations like `+` and `*` are defined in such a way that `inf + n` is different from `n + inf`, and does exceed `inf`.)
+ (Note, though, that with *some* notions of infinite numbers, like [[!wiki ordinal numers]], operations like `+` and `*` are defined in such a way that `inf + n` is different from `n + inf`, and does exceed `inf`.)
-9. Prove that `add 1 ξ <~~> ξ`, where `ξ` is the fixed
-point you found in (1). What about `add 2 ξ <~~> ξ`?
+9. Prove that `add ξ 1 <~~> ξ`, where `ξ` is the fixed
+point you found in (1). What about `add ξ 2 <~~> ξ`?
Comment: a fixed point for the successor function is an object such that it
is unchanged after adding 1 to it. It makes a certain amount of sense
to use this object to model arithmetic infinity. For instance,
depending on implementation details, it might happen that `leq n ξ` is
true for all (finite) natural numbers `n`. However, the fixed point
Comment: a fixed point for the successor function is an object such that it
is unchanged after adding 1 to it. It makes a certain amount of sense
to use this object to model arithmetic infinity. For instance,
depending on implementation details, it might happen that `leq n ξ` is
true for all (finite) natural numbers `n`. However, the fixed point