Global Logic and Undecidability

Michael Heather1, David Livingstone2 and Nick Rossiter2
1 Ambrose, St Bede’s Chambers, Jarrow NE32 5JB, UK,
michael.heather@cantab.net
2 School of Computing, Engineering and Information Sciences, Northumbria
University, NE1 8ST, UK
{david.livingstone,nick.rossiter}@unn.ac.uk
WWW home page: http://computing.unn.ac.uk/staff/CGNR1/

Current world problems require clear thinking not only at the level of systems as a whole but also at a level higher because globalisation difficulties most often lie at the interoperating interface between systems [8]. This is the current subject matter of applied universal logic where fundamental questions about foundations need to be raised to provide a rigorous conceptual understanding of the interstitial logic necessary for the stability of interoperating systems.  Universal logic provides a study of logical structures and here we are concerned with its dynamic face at its highest level. 

The classical logic that dominated the twentieth century was in the main local and could therefore be very adequately built on the premises of Whitehead and Russell's  Principia Mathematica. There were of course very many developments in higher order and non-classical logic in the last century but they almost without exception all implicitly relied on the Principia. Franzén [2] argues that Gödel's theorems make undecidable any such axiomatic system based on number or its set analogue. Furthermore Gödel went further in showing that while first order predicate logic is complete, the same does not extend to first order intuitionistic logic.  Interoperating systems however are by their very nature not closed and therefore need the open semantics of intuitionistic logic. 

Computer science has greatly boosted both the depth and breadth of applied logic. Two branches in particular have been prolific in the use of reasoning applied to real world activity. These are the study of artificial intelligence and the use of database technology for information systems. While artificial intelligence has been launched using programming methods with a formal basis like list programming and functional languages, these are essentially from the same stable as the  Principia  and therefore subject to the vagaries of   Gödel undecidability [3]. Databases on the other hand have been derived from real world data applications in commercial information systems, often built on the quite formal basis of the relational model of Codd [1]. Its use is so widespread that Halpern and his co-authors have cited [4] the relational model as evidence 'on the unusual effectiveness of logic in computer science'. 

In fact this is a long way form the real picture and this paper sets out some of the detail of how in practice Codd's relational model as currently implemented is very much subject to Gödel undecidability. This proves a very salutary reminder of the limitations to applied universal logic when treated classically [5]. Null data values are undecidable, multiple occurrence data in bags rely on natural numbers and are therefore undecidable according to Franzén’s criteria; closed world assumption is a reductionist view of data and consequently results in loss of information, normal forms apply a standardised typing to simplify update operations; vendor variety is symptomatic of Gödel undecidability. Not invalidly chosen with different ways of dealing with problems. 

Thus universal logic needs to escape Gödel’s clutches which constrain any approach based on models. A move to a metaphysical representation such as in category theory [7] is able to provide interpretational logic as can be found in defeasance [6]. 

References:

[1] Codd, E F, The Relational Model for Database Management Addison-Wesley (1990).

[2] Franzén, Torkel, Gödel's Theorem, An Incomplete Guide to its Use and Abuse, Wellesley, Mass, A K Peters 172pp (2005).

[3] Gödel, Kurt, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38 173-198 (1931): translated in Jean van Heijenoort, From Frege to Gödel: A Source Book on Mathematical Logic Harvard 596-616 (1967).

[4] Halpern, Joseph Y, Harper, Robert, Immerman, Neil, Kolaitis, Phokion G, Vardi, Moshe Y, Vianu, Victor, On the unusual effectiveness of logic in computer science, Bulletin of Symbolic Logic 7(2) 213-236 (2001).

[5] Heather, Michael, Livingstone, David, & Rossiter, Nick, Higher Order Logic and Interoperability in Global Enterprise, AREIN, I-ESA, Madeira, 26-30 March 12pp (2007).

[6] Heather, Michael, & Rossiter, Nick, Logical Monism: The Global Identity of Applicable Logic, Advanced Studies in Mathematics and Logic 2 39-52 (2005).

[7] Heather, Michael, & Rossiter, Nick, Universal Logic applied to a Defeasible World, Perspectives on Universal Logic, Jean-Yves Béziau & Alexandre Costa-Leite (edd), Polimetrica, 279-295 (2007).

[8] Rossiter, Nick, & Heather, Michael, Free and Open Systems Theory, EMCSR-2006, Cybernetics and Systems, 18th European Meeting on Cybernetics and Systems Research, University of Vienna, 18-21 April 2006, Trappl, R, (ed) 1 27-32 (2006).