Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:syntax_and_shorthands_of_hol [2008/05/28 01:04] vkuncak |
sav08:syntax_and_shorthands_of_hol [2008/05/29 17:02] vkuncak |
||
---|---|---|---|
Line 10: | Line 10: | ||
All types are built from i and o using function type constructor $\Rightarrow$. For example, | All types are built from i and o using function type constructor $\Rightarrow$. For example, | ||
- | * binary functions are terms of type $i \Rightarow i \Rightarrow i$ (arrow associates to the right, we use currying to represent functions with multiple arguments) | + | * binary functions are terms of type $i \Rightarrow i \Rightarrow i$ (arrow associates to the right, we use currying to represent functions with multiple arguments) |
* binary predicates are terms of type $i \Rightarrow i \Rightarrow o$ | * binary predicates are terms of type $i \Rightarrow i \Rightarrow o$ | ||
Line 17: | Line 17: | ||
To obtain a logic based on such lambda calculus, we add two family of constants: | To obtain a logic based on such lambda calculus, we add two family of constants: | ||
* equality $=_{t \Rightarrow t \Rightarrow o}$ for each type $t$, denoting equality on elements of type $t$ | * equality $=_{t \Rightarrow t \Rightarrow o}$ for each type $t$, denoting equality on elements of type $t$ | ||
- | * selection operator $\iota_{(i \Rightarrow o) \Rightarrow o}$, denoting 'choice function' that takes a predicate and returns one element satisfying the predicate (if such element exists) | + | * selection operator $\iota_{(i \Rightarrow o) \Rightarrow i}$, denoting 'choice function' that takes a predicate and returns one element satisfying the predicate (if exactly one such element exists) |
Everything else (most of mathematics) can be defined in this logic, and to a large extent has been done in systems such as Isabelle and HOL. | Everything else (most of mathematics) can be defined in this logic, and to a large extent has been done in systems such as Isabelle and HOL. | ||
Line 31: | Line 31: | ||
\lnot F & (F = false) \\ | \lnot F & (F = false) \\ | ||
F_1 \land F_2 & (\lambda g.\ g\ true\ true) = (\lambda g.\ F_1\ F_2) \\ | F_1 \land F_2 & (\lambda g.\ g\ true\ true) = (\lambda g.\ F_1\ F_2) \\ | ||
- | \forall x_{t_1}. F_{t_2} & (\lambda x. F) = (\lambda x. true) \\ | + | \forall x. F & (\lambda x. F) = (\lambda x. true) \\ |
\end{array} | \end{array} | ||
\] | \] | ||
Note that we have defined negation, conjunction, and universal quantification, so all propositional operations and existential quantification are expressible. | Note that we have defined negation, conjunction, and universal quantification, so all propositional operations and existential quantification are expressible. | ||
+ | |||
+ | Note also that we can express | ||
+ | \[ | ||
+ | \mbox{ let } x = E \mbox{ in } F | ||
+ | \] | ||
+ | by $(\lambda x.F)E$. | ||
+ | |||
+ | The selection operator $\iota$ is not essential, but is a useful notation. By writing | ||
+ | \[ | ||
+ | \mbox{ let } y = \iota(\lambda x. P(x)) \mbox{ in } F | ||
+ | \] | ||
+ | we can express the phrase "let y in F denote the unique x such that P(x) holds". | ||