3
$\begingroup$

A version of this question got a couple of comments but no answer on stackexchange.

I learned the concept of forcing in logic from Boolos & Jeffrey's book Computability and Logic (second edition, before the later editions in which Burgess was one of the authors). They did forcing in arithmetic, not in set theory. So they treated generic sets of natural numbers. A set chosen in any simple random fashion has probability $0$ of being generic in the sense in which they defined it. Now I'm wondering: is there an easily definable situation in which a set chosen via a simple random process would have probability $1$ of being generic?

Imagine that $n$ is some sort of infinitely large integer, and thus so are $n\pm1, n\pm2, n\pm3,\ldots$. For each (finite!) prime number $p$ and each finite positive integer $k$, we would randomly decide which congruence class modulo $p^k$ to put $n$ into, and consequently which prime powers each member of $\{n, n\pm1, n\pm2, n\pm3,\ldots\}$ is divisible by. This implies that with probability $1$, every member of $\{n, n\pm1, n\pm2, n\pm3,\ldots\}$ has infinitely many prime factors. This follows from the fact that the expected number of prime factors of each such "number" is the sum of the reciprocals of all primes.

Boolos and Jeffrey consider conditions like $\{G(3), \lnot G(5), G(20) \}$, which give a finite amount of information about membership or non-membership in a set $\{x : G(x)\} \subseteq\{0,1,2,3,\ldots\}$. A "generic" set is defined roughly as a set about which nothing is true except what can be "forced" by such finite "conditions". If one randomly picks $G(x)$ or $\lnot G(x)$ for each $x$ by tossing a coin, then with probability $1$ one does not get a generic set. That is because no finite condition can force a set to have a density (the proof includes some work showing that the property of having a density is actually expressible in the "language of arithmetic", which includes the usual arithmetic relations and operations and also logical connectives and quantifiers). So generic sets are ill-behaved things that are not typical of what you get from ordinary random processes.

So let's go back to our infinite integers and let our conditions be things like $\lbrace(2^3 \mid n),\ (7^2 \nmid n+1),\ (13 \mid n-1),\ (3\mid n-1),\ 19 \mid n+2 \rbrace$, etc. As before, let a generic "set" (but "set" is no longer literally the right word) be one about which nothing is true but what is forced by some finite condition, and as before we will say that a condition forces the sentence "$\alpha\text{ or }\beta$" iff either it forces $\alpha$ or it forces $\beta$; it forces $\exists x\ \alpha(x)$ iff there is some $x$ for which it forces $\alpha(x)$, and it forces $\lnot\alpha$ iff no more extensive condition forces $\alpha$.

It seems plausible to me that, in contrast to the previous situation, such randomly chosen "sets" could be generic. In particular, each of these "numbers" would be forced to have infinitely many prime factors since no finite condition could force it not to. And each would be divisible by a prime $p$ only finitely many times, i.e. by $p^k$ but not by $p^{k+1}$, for some $k$, since, for example, if $2^5\mid m$ then $2^2\nmid m+2$.

Is that true?

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you producing a random list of $p$-adic numbers for each $p$ or a random set? $\endgroup$
    – Will Sawin
    Commented Dec 6, 2011 at 5:55
  • $\begingroup$ or, rather, a random number. $\endgroup$
    – Will Sawin
    Commented Dec 6, 2011 at 6:05
  • 1
    $\begingroup$ I have the distinct feeling that unless you do something extreme, the only partial orders for which you can produce true generic object will be trivial from the perspective of forcing. In particular, the notion of generic (should it agree with the notion you are using) will guarantee the answer is always: no matter what type of generic you pick or can describe; the probability of it being truely generic is 0. $\endgroup$
    – Not Mike
    Commented Dec 6, 2011 at 8:08

1 Answer 1

Reset to default
2
$\begingroup$

The same argument that you gave for why the coin-flipping random sets are not generic can be used to show that your new concept of random sets (as far as I understand it) also cannot be generic. Namely, if one chooses randomly to add $p|n$ or $p\not|n$ to the type you are building up, independenty for each prime $p$, then the resulting type will have the property that there is a density on the set of primes dividing $n$. That is, about half the primes will divide $n$ and half will not, converging to $\frac12$ as the number of primes gets large.

But such a type cannot be generic, since it is dense for there to be very long stretches of primes none of which divide $n$ and then again very long stretches of primes that do.

Your strategy seems merely to move the issue from the bits of the set coded by the generic number to the set of primes that divide it.

Meanwhile, it is true that genericity provides a kind of randomness, and different notions of genericity provide different incompatible notions of randomness. Much of this is explored in the theory of algorithmic randomness. For example, Downey and Hirschfeldt's book Algorithmic randomness and complexity provides a rich comparison of various notions of randomness, many of which arise from genericity considerations.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I suspect that Michael didn't intend that each prime $p$ has probability 1/2 of dividing $n$ but rather that the congruence class of $n$ mod $p$ is chosen uniformly at random, so the probability of divisibility is $1/p$. Because this interpretation makes the probability depend on $p$, Joel's argument doesn't trivially carry over, but a minor modification still works. $\endgroup$
    – Andreas Blass
    Commented Dec 6, 2011 at 15:22
  • $\begingroup$ Yes, Andreas, your interpretation seems reasonable. In this case, the random type will put the residue of $n$ modulo $p$ into the "lower half" of $p$ with an asymptotic density of $\frac12$, but generically this feature will not converge, since it is dense for it to have very long periods in the upper half, and then in the lower half, in a way that prevents convergence. $\endgroup$
    – Joel David Hamkins
    Commented Dec 6, 2011 at 15:49
  • $\begingroup$ No one needs to merely suspect that I meant is what Andreas Blass wrote; rather is is implied by what I wrote about the sum of the reciprocals of the primes. The "number" $n$ was not supposed to be singled out for special treatment; rather the probability distribution of its prime factors should be the same as that of $n+j$, for each $j$. Similarly with $p^k$: the probability that $n$ is divisible by it would be $1/p^k$. $\endgroup$
    – Michael Hardy
    Commented Dec 6, 2011 at 18:13
  • $\begingroup$ @Joel I am not convinced that your objection was fatal, but rather I think it shows in what direction we should refine the question. I was quite imprecise about which 1st-order language should contain the statements to be forced; part of the question should necessarily be how best to make things like that precise. Apparently we should deprive the language of the ability to say much of anything about the multiset of prime factors of a "number", but allow it to speak of the number of times any particular prime divides the "number". $\endgroup$
    – Michael Hardy
    Commented Dec 6, 2011 at 20:10
  • $\begingroup$ Michael, I am convinced my objection is fatal. Whatever language you decide on, once one imposes a probabilistic way to deciding what parts of it will be included in the filter or not, then you will get an asymptotic density for that feature. But genericity will instead enforce nonconvergence for the density of that feature. $\endgroup$
    – Joel David Hamkins
    Commented Dec 7, 2011 at 20:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .