2
$\begingroup$

I was thinking about some problem involving quantifiers (the existencial and universal quantifiers) and I noticed how it might resemble probability in a sense. They both assume a variable and its domain, and put restrictions on some predicate of that variable over that domain.

For an example if you didn't get me yet, we can put the following statement involving quantified formula in a probability format:

$ ( \exists x \in X : g(x) ) \equiv ( Pr_{x \in X} [g(x)=1] > 0 ), $

where $g(x) \in \{0,1\}$ is a predicate.

Similarly defined as well for the universal quantifier as $Pr=1$.

However it gets trickier if we nest the quantifiers, for instance I am not sure if the following is correct:

Update: This equation is wrong: $ \exists x \in X : ( \forall y \in Y : g(x,y) ) \equiv Pr[g(X,Y)=1 | Y=y] > 0$.

I propose this one instead: $ \exists x \in X : ( \forall y \in Y : g(x,y) ) \equiv Pr_{x\in X} \left[ Pr_{y\in Y}[g(x,y)=1 | X=x] = 1 \right] > 0$.

-end update

If that line of intuition was correct as I hope, I was wondering if such relationship has been explored before and if not I was hoping to know if it would be possible or not to put a general framework for converting a quantified formula of any alternation depth into a probability equivalent.

  • 0
    @Qiaochu The solution is to ignore sets of measure zero when discussing the "circumstances" in which some statement holds.2010-12-11

1 Answers 1

2

There's a recent book on the subject by Jan Krajicek, draft here.

Instead of defining the probabilities directly, the truth value should be the corresponding event itself, i.e. the points in which the statement is true. So for a proposition $P(x)$, the truth value is the points in which $x$ is true. The Boolean connectives correspond to set operations: negation to complementation, and to intersection, or to union. Quantifiers correspond to supremum (exists) and infimum (forall). Having defined the truth values, you can calculate the probability at the end. You then get that a statement is tautological iff it holds with probability $1$.

The preceding has assumed that the probability space is finite; for infinite spaces the picture is more complicated, and you can consult the draft to see how to do it with non-standard models of the naturals (endowed with the Loeb measure, which is an extension of the counting measure).