First note that there exists a natural measure $\mu$ on $P(\omega \times \omega)$, inherited from the Lebesgue measure on the reals (by identifying the reals with $P(\omega)$ and $\omega$ with $\omega \times \omega$ in the natural ways)

Let us consider models of $ZFC$ of the form $(\omega, E),$ where $E \subseteq \omega \times \omega$ is interpreted as the $\in$-relation.

Given a theory $T \supseteq ZFC,$ let us consider the set $M_T=\{E \subseteq \omega \times \omega:(\omega, E)$ is a model of $T\}$

Question 1. Is the set $M_{ZFC}$ measurable? If so, what is its measure?

In the case that the answer to the above question is yes, and the measure is positive, then one may ask questions like the following which can measure the truth or falsity of statements like $CH$.

Question 2 What is the measure of $M_{ZFC+CH}?$ What about $M_{ZFC+\neg CH}?$

If the answer to question 1 is negative, then one may ask the following:

Question 3. What about questions 1 and 2 if we replace the measure with the outer measure of the required sets?


Edit: By the answer given by Wojowu, and his suggestion, I would also like to ask the following:

Question 4. What happens if we replace $ZFC$ with $ZFC -$foundation?

  • 3
    Pretty sure the sets are measurable - it should be possible to turn the quantifiers into countable unions and intersections. My guess is that they all have measure zero. – Wojowu May 19 at 10:45
  • 2
    Isn't this somehow related to Sacks probabilistic methods for proving independence? – Asaf Karagila May 19 at 10:54
  • 1
    @FedericoPoloni The natural measure is normalized – Wojowu May 19 at 10:59
  • 1
    @FedericoPoloni In fact this is true. The measure I am considering on $P(\omega)$ is essentially the one induced by the natural product measure on $2^\omega$ (by identifying these spaces in the natural way). – Mohammad Golshani May 19 at 11:00
  • 16
    You're essentially taking the random directed graph, interpreting its edge-relation as membership, and hoping to thereby get a model of ZF minus foundation. But what you actually get (with probability 1) is well-known properties of random graphs, like "every two sets have an element in common" (in fact, every two sets have infinitely many elements in common) that makes it look very unlike any reasonable set theory. – Andreas Blass May 19 at 12:49
up vote 30 down vote accepted

For any $E$ modelling ZFC and for each $n\in\omega$, we must have $(n,n)\not\in E$. Therefore $M_{ZFC}$ is contained in the cylinder set defined by $(0,0)\not\in E,\dots,(n,n)\not\in E$ which has measure $2^{-n-1}$. Therefore $M_{ZFC}$ has outer measure zero, thus is measurable and has measure zero.

Had we excluded the diagonal from $\omega\times\omega$, we can't have both $(n,m)\in E,(m,n)\in E$ for $n\neq m$, so we get infinitely many independent conditions each of measure $3/4$, so again we get outer measure zero.

Excluding foundation from ZFC makes this method not work, so it can make for a more interesting question, but perhaps we can use a similar trick.

Edit: Without foundation, let $M_n$ be the set of those models of ZFC-Foundation for which $n$ represents the empty set. We get infinitely many conditions $(m,n)\not\in E$, so $M_n$ has outer measure zero. Since $M_{ZFC-Foundation}$ is a countable union of $M_n$, it has measure zero too. Since I don't know of a reasonable variant of ZFC which doesn't prove existence of the empty set, I think that closes the case.

  • Thanks for your answer. I edited to question to ask for the case we don't have foundation. – Mohammad Golshani May 19 at 11:27
  • 7
    It is actually much worse than that. Any non-trivial statement about finitely many sets of the type "for all tuples of sets $\omega_1,\dots,\omega_n$ there exist a set $\omega$ such that $P(\omega_1,\dots,\omega_n,\omega)$" creates a problem because the probability that a given tuple satisfies it is $0$ for nearly all reasonable predicates $P$ one can think of. – fedja May 19 at 11:34
  • 5
    @fedja: Could you have picked any worse letter to denote arbitrary sets? How about $\aleph$? Similarly, do you called your integration variable $\rm d$? :) – Asaf Karagila May 20 at 7:11
  • 2
    @AsafKaragila I certainly could. Just wait until the next time! :-) I guess I had to write a quadruple integral with respect to $da\,db\,dc\,dd$ at least once in my life, so "Yes" to the second question too :lol: – fedja May 20 at 12:16
  • 1
    @fedja Having once had an opportunity to do that, I've decided to skip $d$ and use $de$... I guess I was lucky certain constant did not come up in the answer! – Wojowu May 20 at 14:18

This answer is really just an extensive elaboration of the comments of Andreas Blass and fedja.

For any relational language $L$, let $X_L$ be the space of all $L$-structures with domain $\omega$. To determine an $L$-structure with domain $\omega$, we just need to decide, for each relation symbol $R\in L$ of arity $\text{ar}(R)$ and each tuple $a_1,\dots,a_{\text{ar}(R)}$ from $\omega$, whether or not $R(a_1,\dots,a_{\text{ar}(R)})$ holds. So $X_L$ is in bijection with the Cantor space $\prod_{R\in L}2^{\omega^{\text{ar}(R)}}$ (and the topology on $X_L$ is defined so that this bijection is a homeomorphism). Let's denote by $\mu$ the measure on $X_L$ inherited from the natural measure on the Cantor space.

The space $X_L$ also comes with an action (called the logic action) of $S_\infty$, the permutation group of $\omega$. A permutation $\sigma\in S_\infty$ acts on $X_L$ by permuating the domains of structures. That is, $$\sigma(M)\models R(a_1,\dots,a_{\text{ar}(R)})\text{ iff }M\models R(\sigma^{-1}(a_1),\dots,\sigma^{-1}(a_{\text{ar}(R)})).$$ Then $\sigma$ is an isomorphism $M\cong \sigma(M)$, and the orbit of a point $M\in X_L$ under the action of $S_\infty$ is $$\text{Iso}(M) = \{N\in X_L\mid N\cong M\}.$$ Note that the natural measure on $X_L$ is invariant for the logic action. For more on this setting, see Section 16.C of Kechris's book Classical Descriptive Set Theory.

Now the class of all finite $L$-structures is a Fraïssé class with Fraïssé limit $M_L$. It's a fact that $\mu(\text{Iso}(M_L)) = 1$ and $\text{Iso}(M_L)$ is comeager in $X_L$. So the structure $M_L$ is "generic up to isomorphism" from the point of view of both measure and Baire category.

In your question, the space on which your measure lives is $X_L$ with $L = \{E\}$, and your measure is the natural measure $\mu$. By the fact above, for any $L$-sentence $\varphi$, writing $[\varphi] = \{N\in X_L\mid N\models \varphi\}$, we have $$\mu([\varphi]) = \begin{cases} 1&\text{if } M_L\models \varphi \\ 0&\text{otherwise}\end{cases}$$ Of course, $M_L$ looks nothing like a model of set theory - it should fail to satisfy almost all the axioms, though it does satisfy extensionality.

Ok, so the natural measure $\mu$ gives measure $0$ to the models of ZFC (and the same goes for any first-order theory which is not contained in $\text{Th}(M_L)$. You might ask if there are other measures on $X_L$ which give measure $1$ to the models of ZFC. Of course, you need to impose some restrictions, since you could always pick the Dirac measure concentrating on a single point (well, assuming ZFC is consistent!).

A natural idea is to find such a measure which is still invariant for the logic action. But this is impossible, for the reason pointed out by fedja. Explicitly, suppose $\mu$ is an invariant measure on $X_L$ which gives measure $1$ to models of ZFC. For $n\in \omega$, let $Y_n$ be the set of all structures in $X_L$ such that the "set" $n$ has no elements. By invariance, $\mu(Y_n) = \mu(Y_m)$ for all $m$ and $n$, but $\mu(Y_n\cap Y_m) = 0$ for all $m\neq n$. But by countable additivity, we can't have an infinite family of almost-surely disjoint sets a probability space, all with the same positive measure.

More generally, if $\mu$ is an invariant measure on $X_L$ which gives positive measure to the set of models of a first-order theory $T$, then $T$ must have a completion with trivial definable closure: That is, there should be a model $M\models T$ such that if $\varphi(x,y)$ is a formula, where $x$ is a tuple of variables and $y$ is a singleton, and $a$ is a tuple from $M$ such that there is a unique $b\in M$ such that $M\models \varphi(a,b)$, then already $b$ is an element of the tuple $a$.

Ackerman, Freer, and Patel proved that nontrivial definable closure is actually the only obstruction to the existence of invariant measures on $X_L$ giving positive measure to a given theory. See Theorem 1.2 in this paper.

So one thing you can do is take ZFC and replace equality with an equivalence relation with infinitely many infinite classes (i.e. "blow up" each element of a model to an infinite equivalence class). This is convenient to do in the language of sets, by weakening extensionality to the axiom that if $X$ and $Y$ have exactly the same elements, then they are elements of exactly the same sets. The resulting theory ZFC' does admit invariant measures which give its set of models measure $1$ (again, assuming that ZFC is consistent). But so does (ZFC + CH)' and (ZFC + $\lnot$CH)', and I think it would be hard to make an argument to prefer the measures concentrating on (ZFC + CH)' over those concentrating on (ZFC + $\lnot$CH)' or vice versa. So unfortunately I don't think this path leads to a meaningful way to assign a "probability" to CH.

  • Is it possible that when you replace equality with an equivalence relation that somehow you're 'hiding the measure being trivial'? Could it be that when you take your random models and mod out by the equivalence relation there's only a finite or countable collection of isomorphism types with a positive probability of occurring? – James Hanson May 22 at 22:43
  • @JamesHanson Good question! Every invariant measure on $X_L$ can be decomposed into a mixture (i.e. a weighted average) of ergodic invariant measures. Ergodic measures have the property that they assign measure $0$ or $1$ to every isomorphism type. It's actually kind of tricky to cook up an ergodic measure that doesn't give measure $1$ to a single isomorphism type, but it's possible. In my paper Properly Ergodic Structures with Ackerman, Freer, and Patel, we studied such measures and characterized theories $T$ such that there exists an ergodic measure which gives measure $1$ to the set... – Alex Kruckman May 23 at 2:19
  • ... of models of $T$, without giving measure $1$ to any particular isomorphism type. However, the theory I called ZFC' in my answer is not such a theory (in the terminology of the paper, it has no "rooted" models). So every ergodic measure giving measure $1$ to ZFC' gives measure $1$ to a single isomorphism type, and hence any invariant measure is a weighted average (possibly a continuous average) of these ergodic measures. – Alex Kruckman May 23 at 2:27

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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