7
$\begingroup$

This question is motivated by the work of Ajtai "The complexity of the pigeonhole principle" and similar works. In this paper, the author proves that $PHP_n$, the pigeonhole principle for $n,$ does not have polynomial-size constant-depth Frege proofs. The method of proof is an arithmetical analogue of forcing (of a kind already used by Paris and Wilkie), plus a probabilistic argument to handle the relevant combinatorics.

Now my questions are the following.

Question 1. Are there similar works, which connect set theoretic forcing with probabilistic arguments in an essential way?

Question 2. Are there works, which connect large cardinals and probabilistic arguments?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You know about Sacks' paper, right? (The one mentioned in the comments to this relevant question, mathoverflow.net/questions/121251/…) $\endgroup$
    – Asaf Karagila ♦
    Nov 17, 2016 at 11:24
  • 1
    $\begingroup$ Yes, I know it. Thanks for reminding it. $\endgroup$
    – Mohammad Golshani
    Nov 17, 2016 at 14:10
  • 1
    $\begingroup$ Shelah's 592 + 619 employ quite sophisticated measure-theoretic arguments to prove the consistency of there is a non null set that cannot be partitioned into uncountably many non null sets. $\endgroup$
    – Ashutosh
    Nov 23, 2016 at 18:39
  • $\begingroup$ @Ashutosh Thanks for the references. $\endgroup$
    – Mohammad Golshani
    Nov 24, 2016 at 4:52

2 Answers 2

Reset to default
3
$\begingroup$

Random real forcing is naturally connected with probability and measure theory, in an essential way, since the generic real that is added by the forcing has all the Borel properties that hold with probability one for reals in the ground model.

One recent example is our recent paper on the rearrangement number (with six authors, available soon; I'll update with a link), where we combine probabilistic arguments and forcing. For example, in order to show that the rearrangement number was at least as large as the covering number for measure, we had considered the randomly signed harmonic series as used Rademacher's theorem that a randomly signed series $\sum (-1)^{r(n)}c_n$ converges almost surely just in case the series is square-summable $\sum c_n^2<\infty$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. In general I know connections between forcing and probability. There are some works on probability spaces by Burke and others where forcing appears naturally. But I don't know if probabilistic methods have appeared or not. I'll wait for your mentioned paper which seems very interesting. $\endgroup$
    – Mohammad Golshani
    Nov 17, 2016 at 14:14
2
$\begingroup$

Today I saw the following paper in which probabilistic arguments are used in a forcing argument:

Halfway New Cardinal Characteristics.

See the proof of 3.4. The paper is written by Jörg Brendle, Lorenz Halbeisen, Lukas Daniel Klausner, Marc Lischka and Saharon Shelah.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.