Is it conceivable that Frankl's union closed sets conjecture is undecidable in $\mathsf{ZFC}$, or is this quite implausible, perhaps due to the "finitistic" nature of the statement, or for some other reason?
$\begingroup$
$\endgroup$
asked Dec 5, 2014 at 14:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The statement has complexity $\Pi^0_1$, which means that it has a single universal quantifier, quantifying over the possible union-closed sets, and then making a simple assertion about those objects.
Although this is a very simple level of complexity, it is the same complexity as consistency assertions, and these admit of a robust independence phenomenon. For example, even ZFC, if consistent, admits of independent statements of this level of complexity, such as the statement Con(ZFC), which asserts that ZFC is consistent.
Meanwhile, if we can prove in ZFC (or some other theory) that the union-closed set conjecture was independent of PA, then it would follow that the statement was true in the standard model. The reason is that if a $\Pi^0_1$ statement is independent of PA, then it can admit of no standard counterexample, since PA would prove that this was a counterexample. So, the situation is that if we can prove in ZFC that the union-closed set conjecture is independent of PA, then we would be able to prove in ZFC that it is true.
answered Dec 5, 2014 at 15:10
-
$\begingroup$ Let me attach this post of yours as an explanation for the last paragraph. I think the same argument used in the last paragraph can be used to show, instead of PA, if it is provably independent of ZFC, then it can proven to be true in ZFC+Con(ZFC), right? $\endgroup$– BurakCommented Dec 5, 2014 at 15:22
-
$\begingroup$ Thanks for the link! But your remark isn't quite right, because in general, it depends on the theory that you used to prove the independence. For example, the $\Pi^0_1$ statement Con(ZFC+$\exists$inaccessible cardinal) is provably independent of ZFC in some strong large cardinal theories, but it is not provably true in ZFC+Con(ZFC). $\endgroup$ Commented Dec 5, 2014 at 15:26
-
$\begingroup$ I see, we might have to throw in the theory we prove the independence in. In any case, I think the point I was trying to make is that if we can prove consistency of a $\Pi^0_1$ sentence in some theory, then we can prove it to be true after assuming that that theories in which and from which independence is proven "sufficiently make sense". $\endgroup$– BurakCommented Dec 5, 2014 at 15:34
-
$\begingroup$ Yes, I agree with that. $\endgroup$ Commented Dec 5, 2014 at 15:35