Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-02T22:27:53.116Z Has data issue: false hasContentIssue false
  • English
  • Français

Completeness and Herbrand theorems for nominal logic

Published online by Cambridge University Press:  12 March 2014

James Cheney
James Cheney*
Affiliation:
University of Edinburgh, Laboratory for Foundations of Computer Science, Edinburgh, Eh8 9Le, United Kingdom. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Nominal logic is a variant of first-order logic in which abstract syntax with names and binding is formalized in terms of two basic operations: name-swapping andfreshness. It relies on two important principles: equivariance (validity is preserved by name-swapping), and fresh name generation (“new” or fresh names can always be chosen). It is inspired by a particular class of models for abstract syntax trees involving names and binding, drawing on ideas from Fraenkel-Mostowski set theory: finite-support models in which each value can depend on only finitely many names.

Although nominal logic is sound with respect to such models, it is not complete. In this paper we review nominal logic and show why finite-support models are insufficient both in theory and practice. We then identify (up to isomorphism) the class of models with respect to which nominal logic is complete: ideal-supported models in which the supports of values are elements of a proper ideal on the set of names.

We also investigate an appropriate generalization of Herbrand models to nominal logic. After adjusting the syntax of nominal logic to include constants denoting names, we generalize universal theories to nominal-universal theories and prove that each such theory has an Herbrand model.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 71 , Issue 1 , March 2006 , pp. 299 - 320
Copyright
Copyright © Association for Symbolic Logic 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Abiteboul, Serge, Hull, Richard, and Vianu, Victor, Foundations of Databases, Addison-Wesley, 1995.Google Scholar
[2]Barendregt, H. P., The Lambda Calculus, North-Holland, 1984.Google Scholar
[3]de Bruijn, N. G., Lambda-calculus notation with nameless dummies, a tool for automatic formula manipulation, Indagationes Mathematicae, vol. 34 (1972), no. 5, pp. 381–392.CrossRefGoogle Scholar
[4]Brunner, Norbert, The Fraenkel-Mostowski method, revisited, Notre Dame Journal of Formal Logic, vol. 31 (1990), no. 1, pp. 64–75.Google Scholar
[5]Cheney, James, The complexity of equivariant unification, Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 3142, Springer-Verlag, 2004, pp. 332–344.CrossRefGoogle Scholar
[6]Cheney, James, Nominal logic programming, Ph.D. thesis, Cornell University, Ithaca, NY, 08 2004.Google Scholar
[7]Cheney, James, Equivariant unification. Proceedings of the Conference on Rewriting Techniques and Applications (RTA), Lecture Notes in Computer Science, vol. 3467, Springer-Verlag, 2005, pp. 74–89.Google Scholar
[8]Cheney, James, A simpler proof theory for nominal logic, Proceedings of the Conference on Foundations of Software Science and Computation Structures (FOSSACS), Lecture Notes in Computer Science, vol. 3441, Springer-Verlag, 2005, pp. 379–394.Google Scholar
[9]Cheney, James and Urban, Christian, Alpha-Prolog: A logic programming language with names, binding and alpha-equivalence, Proceedings of the 20th International Conference on Logic Programming (ICLP), Lecture Notes in Computer Science, vol. 3132, Springer-Verlag, 2004, pp. 269–283.Google Scholar
[10]Church, Alonzo, A formulation of the simple theory of types, this Journal, vol. 5 (1940), pp. 56–68.Google Scholar
[11]Curry, H. B. and Feys, R., Combinatory Logic, North-Holland, 1958.Google Scholar
[12]Felgner, Ulrich, Models of ZF-Set Theory, Lecture Notes in Mathematics, vol. 223, Springer-Verlag, 1970.Google Scholar
[13]Fraenkel, A., The concept “definite” and the indepedence of the Auswahlsaxiom, From Frege to Gödel (van Heijenoort, J., editor), Harvard University Press, 1967, pp. 284–289.Google Scholar
[14]Frege, G., Begriffsschrift: A formula language, modeled upon that of arithmetic, for pure thought, From Frege to Gödel (van Heijenoort, J., editor), Harvard University Press, 1967, pp. 1–82.Google Scholar
[15]Gabbay, Murdoch, A theory of inductive definitions with alpha-equivalence, Ph.D. thesis, University of Cambridge, 2001.Google Scholar
[16]Gabbay, Murdoch, FM-HOL, a higher-order theory of names, Workshop on Thirty Five Years of Automath (Heriot Watt, UK) (Kamareddine, F., editor), 04 2002.Google Scholar
[17]Gabbay, Murdoch, Fresh logic: A logic of FM, 2003, preprint.Google Scholar
[18]Gabbay, Murdoch, A general mathematics of names in syntax, preprint, 03 2004.Google Scholar
[19]Gabbay, Murdoch and Cheney, James, A sequent calculus for nominal logic, Proceedings of the Annual IEEE Symposium on Logic in Computer Science (LICS) (Turku, Finland), 2004, pp. 139–148.Google Scholar
[20]Gabbay, Murdoch and Pitts, Andrew, A new approach to abstract syntax with variable binding, Formal Aspects of Computing, vol. 13 (2002), pp. 341–363.CrossRefGoogle Scholar
[21]Gunter, C. A. and Mitchell, J. C. (editors), Theoretical Aspects of Object-Oriented Programming: Types, Semantics, and Language Design, The MIT Press, 1994.Google Scholar
[22]Harper, Robert, Honsell, Furio, and Plotkin, Gordon, A framework for defining logics, Journal of the ACM, vol. 40 (1993), no. 1, pp. 143–184.CrossRefGoogle Scholar
[23]Henkin, Leon, The completeness of the first-order functional calculus, this Journal, vol. 14 (1949), no. 3, pp. 159–166.Google Scholar
[24]Hopcroft, John E. and Ullmann, Jeffrey D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.Google Scholar
[25]Jech, Thomas J., About the axiom of choice, Handbook of Mathematical Logic (Barwise, J., editor), North-Holland, 1977, pp. 345–370.CrossRefGoogle Scholar
[26]Kamarredine, Fairouz, Laan, Twan, and Nederpelt, Rob, Types in logic and mathematics before 1940, The Bulletin of Symbolic Logic, vol. 8 (2002), no. 2, pp. 185–245.CrossRefGoogle Scholar
[27]Kennaway, J. R., Klop, J. W., Sleep, M. R., and de Vries, F. J., Infinitary lambda calculus, Theoretical Computer Science, vol. 175 (1997), no. 1, pp. 93–125.CrossRefGoogle Scholar
[28]Lowe, Gavin, An attack on the Needham-Schroeder public-key authentication protocol, Information Processing Letters, vol. 56 (1995), no. 3, pp. 131–133.CrossRefGoogle Scholar
[29]Lane, Saunders Mac and Moerdijk, Ieke, Sheaves in Geometry and Logic: A First Introduction to Topos Theory, Springer-Verlag, 1992.Google Scholar
[30]Miller, Dale and Tiu, Alwen, A proof theory for generic judgments (extended abstract), Proceedings of the 18th Symposium on Logic in Computer Science (LICS), IEEE Press, 2003, pp. 118–127.Google Scholar
[31]Milner, Robin, Parrow, Joachim, and Walker, David, A calculus of mobile processes, I-II, Information and Computation, vol. 100 (1992), no. 1, pp. 1–77.CrossRefGoogle Scholar
[32]Milner, Robin, Tofte, Mads, Harper, Robert, and MacQueen, David, The Definition of Standard ML - Revised, MIT Press, 1997.CrossRefGoogle Scholar
[33]Morrisett, G. and Harper, R., Semantics of memory management for polymorphic languages, Higher Order Operational Techniques in Semantics, Publications of the Newton Institute, Cambridge University Press, 1997.Google Scholar
[34]Needham, Roger M. and Schroeder, Michael D., Using encryption for authentication in large networks of computers, Communications of the ACM, vol. 21 (1978), no. 12, pp. 993–999.CrossRefGoogle Scholar
[35]Nielson, Flemming, Nielson, Hanne Riis, and Hankin, Chris, Principles of Program Analysis, 2nd ed., Springer, 2005.Google Scholar
[36]O'Hearn, P. and Pym, D. J., The logic of bunched implications, The Bulletin of Symbolic Logic, vol. 5 (1999), no. 2, pp. 215–244.CrossRefGoogle Scholar
[37]Pfenning, Frank and Elliott, Conal, Higher-order abstract syntax, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), ACM Press, 1989, pp. 199–208.Google Scholar
[38]Pitts, A. M., Nominal logic, A first order theory of names and binding, Information and Computation, vol. 183 (2003), pp. 165–193.CrossRefGoogle Scholar
[39]Prawitz, Dag, Natural Deduction: A Proof-Theoretical Study, Almquist and Wiksell, 1965.Google Scholar
[40]Priest, Graham, An Introduction to Non-Classical Logic, Cambridge University Press, 2001.Google Scholar
[41]Schönfinkel, M., On the building blocks of mathematical logic, From Frege to Gödel (van Heijenoort, J., editor), Harvard University Press, 1967, pp. 355–366.Google Scholar
[42]Schöpp, Ulrich and Stark, Ian, A dependent type theory with names and binding, Proceedings of the Computer Science Logic Conference (Karpacz, Poland), Lecture Notes in Computer Science, vol. 3210, Springer-Verlag, 2004, pp. 235–249.CrossRefGoogle Scholar
[43]Stoy, Joseph E., Denotational Semantics: The Scott-Strachey Aapproach to Programming Language Ttheory, Series in Computer Systems, vol. 1, MIT Press, 1981.Google Scholar
[44]Truss, J. K., Permutations and the axiom of choice, Automorphisms of First-Order Structures (Kaye, Richard and Macpherson, Dugald, editors), Oxford, 1994, pp. 131–152.CrossRefGoogle Scholar
[45]Vestergaard, René and Brotherston, James, >A formalised first-order confluence proof for the λ-calculus using one-sorted variable names, Information and Computation, vol. 183 (2003), pp. 212–244.CrossRefGoogle Scholar
[46]Viganó, Luca, Labelled Non-Classical Logics, Kluwer Academic Publishers, 2000.CrossRefGoogle Scholar