Title page for ETD etd-09082012-040214
|Type of Document
||Pemmaraju, Sriram V.
||Modal logics of provability
||Master of Science
||Computer Science and Applications
|Roach, John W.
|Cuda, Thomas V.
|Heath, Lenwood S.
- Symbolic and mathematical.
|Date of Defense
Gödel proved his Incompleteness theorems for any theory 'strong' enough to represent recursive
functions. In the process he showed that the provability predicate can be represented
in such theories. Modal logics of provability are modal logics which attempt to express the
concept of 'provability' and 'consistency' using the modal operators '' and '<>' respectively.
This is achieved by forcing '' to behave like the provability predicate. GL is a
modal logic which has been shown to be complete and sound with respect to arithmetic
theories (theories which can represent all recursive functions), hence results about concepts
such as 'consistency,' 'provability' and 'decidabi1ity' in arithmetic theories can be stated and
proved in GL. It has also been proved that GL is complete with respect to the class of finite,
transitive, reversely well—founded models. This essentially means that the set of theorems of
GL is recursive and hence there exists an effective procedure to determine whether a given
wff is a theorem of GL or not. We investigate a weaker version of GL called GH and show
that GH is not complete with respect to arithmetic theories. We show this by first showing
that GH is a proper subset of GL and then showing that the theorems missing from GH are properties of the provability predicate. We finally, show that GH is not complete with respect to the class of transitive, reversely well-founded models and hence not sound and complete with respect to any frame.
|| Approximate Download Time
| 28.8 Modem
|| 56K Modem
|| ISDN (64 Kb)
|| ISDN (128 Kb)
|| Higher-speed Access
next to an author's name indicates that all
files or directories associated with their ETD
are accessible from the Virginia Tech campus network only.
If you have questions or technical
problems, please Contact DLA.