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
    I think in a sense, that's what fuzzy logic is about. I've always wondered why fuzzy logic is considered so special when in fact, it is equivalent to probability theory. It's just the interpretation that differs.2010-12-10
  • 0
    You need to be able to put a probability measure on the domain such that each event happens with positive probability, so the domain can be at most countable.2010-12-10
  • 0
    @Qiaochu Yuan: I am not following you, continuous probability distributions such as the normal distribution has the domain as $\mathbb{R}$, which is uncountable. Or there is something I don't know ?2010-12-10
  • 0
    @M. Alaggan: you say that the existence of x such that g(x) is true is equivalent to P(g(x) = 1) > 0. This is only true if every element of the domain has positive measure, which is generally false on an uncountable measure space; any singleton in R has measure 0 (typically).2010-12-10
  • 0
    The problem is eliminated though if he chooses the right probability measure. Since you want the end result to be independent of the choice of the measure, you might want to try to define a kind of supremum or something like that.2010-12-10
  • 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).