Skip Navigation



Journal of Logic and Computation Advance Access published online on April 23, 2008
Journal of Logic and Computation, doi:10.1093/logcom/exn014
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Cruz-Filipe, L.
Right arrow Articles by Sernadas, C.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Complete Axiomatization of Discrete-Measure Almost-Everywhere Quantification

Luís Cruz-Filipe

Lasige and Dep. Informática, FC, U Lisbon, Portugal E-mail: lcf{at}di.fc.ul.pt

João Rasga, Amílcar Sernadas and Cristina Sernadas

SQIG - Instituto de Telecomunicações and Dep. Matemática, IST, TU Lisbon, Portugal E-mail: jfr{at}math.ist.utl.pt; acs{at}math.ist.utl.pt; css{at}math.ist.utl.pt

Received 9 June 2006.

Following recent developments in the topic of generalized quantifiers, and also having in mind applications in the areas of security and artificial intelligence, a conservative enrichment of (two-sorted) first-order logic (FOL) with almost-everywhere quantification is proposed. The completeness of the axiomatization against the measure-heoretic semantics is carried out using a variant of the Lindenbaum–Henkin technique. The independence of the axioms is analysed, and the almost-everywhere quantifier is compared with related notions of generalized quantification. A suitable fragment of the logic is translated to FOL and validity is shown to be preserved.

Keywords: Generalized quantification; almost-everywhere logic; probabilistic logic; measure-theoretic semantics; complete axiomatization



References

  1. Abadi M, Cortier V. Deciding knowledge in security protocols under equational theories. In: Automata, Languages and Programming (2004) Berlin: Springer. 46–58. Vol. 3142 of Lecture Notes in Computer Science.
  2. Abadi M, Rogaway P. Reconciling two views of cryptography (the computational soundness of formal encryption). Journal of Cryptology (2002) January;15:103–127.[ISI]
  3. Adams EW. The logic of ‘almost all’. Journal of Philosophical Logic (1974) March;3:3–17.[CrossRef][ISI]
  4. Barwise J, Cooper R. Generalized quantifiers and natural language. Linguistics and Philosophy (1981) 4:159–219.[CrossRef][ISI]
  5. Barwise J, Feferman S, eds. Model-theoretic Logics. Perspectives in Mathematical Logic. (1985) New York: Springer-Verlag.
  6. Barwise J, Kaufmann M, Makkai M. Stationary logic. Annals of Mathematical Logic (1978) 13:171–224.[CrossRef]
  7. Billingsley P. Probability and Measure. In: Wiley Series in Probability and Mathematical Statistics (1995) 3rd edn. John Wiley & Sons Inc.
  8. Blackburn P, de Rijke M, Venema Y. Modal Logic. In: Vol. 53 of Lecture Notes in Cambridge Tracts in Theoretical Computer Science (2001) Cambridge: Cambridge University Press.
  9. Carlstrom IF. Truth and entailment for a vague quantifier. Synthese (1975) September;30:461–495.[CrossRef]
  10. Carnielli W, Grácio M. Modulated logics and uncertain reasoning. (2005) Submitted for publication. CLE e-prints vol.5(2), Preprint.
  11. Carnielli WA, Veloso P. A. S. Ultrafilter logic and generic reasoning. In: Computational Logic and Proof Theory (1997) Berlin: Springer. 34–53. Vol. 1289 of Lecture Notes in Computer Science.
  12. Datta A, Derek A, Mitchell JC, Shmatikov V, Turuani M. Probabilistic polynomial-time semantics for a protocol security logic. In: Automata, Languages and Programming (2005) Berlin: Springer. 16–29. Vol. 3580 of Lecture Notes in Computer Science.
  13. Giritli M. Measure logics for spatial reasoning. In: Logics in Artificial Intelligence (2004) Berlin: Springer. 487–499. Vol. 3229 of Lecture Notes in Computer Science.
  14. Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems. SIAM Journal on Computing (1989) 18:186–208.[CrossRef][ISI]
  15. Halmos PR. Measure Theory. (1974) New York: Springer–Verlag.
  16. Halpern JY. An analysis of first-order logics of probability. Artificial Intelligence (1990) 46:311–350.[CrossRef][ISI]
  17. Henkin L. The completeness of the first-order functional calculus. The Journal of Symbolic Logic (1949) 14:159–166.[CrossRef]
  18. Kaufmann M. The quantifier ‘there exist uncountably many’ and some of its relatives. In: Model-theoretic Logic. Perspectives in Mathematical Logic, Barwise and Feferman (1985) New York: Springer-Verlag. 123–176.
  19. Keisler HJ. Logic with the quantifier ‘there exist uncountably many’. Annals of Pure and Applied Logic (1970) 1:1–93.
  20. Keisler HJ. Probability quantifiers. In: Model-theoretic Logic. Perspectives in Mathematical Logic, Barwise and Feferman (1985) New York: Springer-Verlag. 509–556.
  21. Keisler HJ. A completeness proof for adapted probability logic. Annals of Pure and Applied Logic (1986) 31:61–70.[CrossRef][ISI]
  22. Keisler HJ. Hyperfinite models of adapted probability logic. Annals of Pure and Applied Logic (1986) 31:71–86.[CrossRef][ISI]
  23. Mateus P, Pacheco A, Pinto J, Sernadas A, Sernadas C. Probabilistic situation calculus. Annals of Mathematics and Artificial Intelligence (2001) 32:393–431.[CrossRef][ISI]
  24. Mekler AH, Shelah S. Stationary logic and its friends. I. Notre Dame Journal of Formal Logic (1985) 26:129–138.[CrossRef]
  25. Micciancio D, Warinschi B. Completeness theorems for the Abadi-Rogaway logic of encrypted expressions. Journal of Computer Security (2004) 12:99–129.
  26. Mostowski A. On a generalization of quantifiers. Fundamenta Mathematicae (1957) 44:12–36.
  27. Motwani R, Raghavan P. Randomized Algorithms. (1995) Cambridge: Cambridge University Press.
  28. Peterson PL. On the logic of ‘few’, ‘many’, and ‘most’. Notre Dame Journal of Formal Logic (1979) 20:155–179.[CrossRef]
  29. Reiter R. A logic for default reasoning. Artificial Intelligence (1980) 13:81–132. (Special issue on nonmonotonic logic).[CrossRef][ISI]
  30. Shelah S. Generalized quantifiers and compact logic. Transactions of the American Mathematical Society (1975) 204:342–364.[CrossRef][ISI]
  31. van Benthem J, Westerståahl D. Directions in generalized quantifier theory. Studia Logica (1995) 55:389–419.[CrossRef]
  32. Veloso P, Carnielli W. Logics for qualitative reasoning. In: Logic, Epistemology and the Unity of Science (2004) Vol. 1. Dordrecht: Kluwer Academic Publishers. 487–526.
  33. Veloso PAS, Veloso SRM. On ultrafilter logic and special functions. Studia Logica (2004) 78:459–477.[CrossRef]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Cruz-Filipe, L.
Right arrow Articles by Sernadas, C.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?