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?

$\endgroup$
  • 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 '16 at 11:24
  • 1
    $\begingroup$ Yes, I know it. Thanks for reminding it. $\endgroup$ – Mohammad Golshani Nov 17 '16 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 '16 at 18:39
  • $\begingroup$ @Ashutosh Thanks for the references. $\endgroup$ – Mohammad Golshani Nov 24 '16 at 4:52
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$.

$\endgroup$
  • $\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 '16 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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