Skip to main content
1 of 2
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Forcing and divisibility

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?

Michael Hardy
  • 1
  • 12
  • 85
  • 126