Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T13:29:37.551Z Has data issue: false hasContentIssue false

Almost everywhere elimination of probability quantifiers

Published online by Cambridge University Press:  12 March 2014

H. Jerome Keisler
Affiliation:
Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison Wi 53706, USA, E-mail: keisler@math.wisc.edu
Wafik Boulos Lotfallah
Affiliation:
Department of Mathematics, The German University in Cairo, EgyptThe Department of Engineering Mathematics, Faculty of Engineering, Cairo University, Egypt, E-mail: wafik.lotfallah@guc.edu.eg, lotfalla@uwalumni.com

Abstract

We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like ∃≥3/4y which says that “for at least 3/4 of all y”. These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are:

1. We deal with the quantifier ∃≥ry, where y is a tuple of variables.

2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope.

3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities PR for each predicate symbol R.

4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs).

5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers.

6. We allow each PR, as well as each r in the probability quantifier (∃≥ry), to depend on the size of the universe.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2009

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.)

Article purchase

Temporarily unavailable