Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision Next revision Both sides next revision | ||
sav08:axioms_of_hol [2008/05/27 17:25] vkuncak created |
sav08:axioms_of_hol [2008/05/28 03:06] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Axioms of Classical HOL ====== | ====== Axioms of Classical HOL ====== | ||
- | Sound, incomplete. | + | Axiom system that is sound (but necessarily incomplete with respect to standard semantics) is the following: |
+ | - $(g\ true\ \land\ g\ false) = (\forall x. g x)$ (domain 'o' has only true,false as elements) | ||
+ | - $(x=y) \rightarrow (fx = fy)$ (congruence) | ||
+ | - $(\lambda x.F_1)F_2 = F_1[x:=F_2]$ (beta reduction) | ||
+ | - $\iota(\lambda y.(x=y)) = x$ (selecting element from $\{x\}$ gives $x$) | ||
+ | |||
+ | Inference rule: | ||
+ | \[ | ||
+ | \frac{C\ \ ; \ \ A=B} | ||
+ | {C[A:=B]} | ||
+ | \] | ||
+ | which replaces one occurrence of $A$ in $C$ with $B$ (we cannot replace variables under $\lambda$) |