3

More precisely, let $T$ be a theory of some first-order language. My question is then the following. What does it mean for two sentences $\sigma_1$ and $\sigma_2$ in the same language to be independent of each other in the theory $T$?

My "hypothesis" is that it means $\neg \, ( \, T \vdash \sigma_1 \leftrightarrow \sigma_2 \,)$. However, I could only come up with this "hypothesis" by looking at some particular examples; also I could not immediately find an online reference where this concept is defined, hence this question. Can somebody confirm this?

Note. I do know what it means for one formula $\sigma$ to be independent from a theory $T$. Namely it means that $\neg \, ( \, T \vdash \sigma\,) \; \wedge \; \neg \, ( T \vdash \neg \sigma)$.

Boda Poldi
  • 31
  • 1

1 Answers1

3

It’s even stronger than that: it means that $T\cup\{\sigma_1\}\not\vdash\sigma_2$ and $T\cup\{\sigma_2\}\not\vdash\sigma_1$. In other words, given $T$, neither of $\sigma_1$ and $\sigma_2$ entails the other. For example, in the context of $\mathsf{ZF}$ set theory the continuum hypothesis and the axiom of choice are independent of each other: assuming that $\mathsf{ZF}$ is consistent, so are $\mathsf{ZF}+\mathsf{CH}+\neg\mathsf{AC}$ and $\mathsf{ZF}+\mathsf{AC}+\neg\mathsf{CH}$.

Brian M. Scott
  • 616,228
  • Are you sure that this is the most "common" way of defining this? Because if this is true then it seems to me that, under this definition, a theorem in Jech's book The Axiom of Choice (Theorem 4.7 on page 51) becomes false: he claims in this theorem that "The Axiom of Choice is independent of the Ordering Principle in set theory with atoms." The Ordering Principle is the statement that any set can be linearly ordered; obviously the Axiom of Choice implies this, because the Axiom of Choice is equivalence with the Well-Ordering Theorem. –  Sep 08 '13 at 02:10
  • 1
    Brian's answer is correct. But there is abuse, as you see. In this particular case, what Jech means is that $\mathsf{ZFA}+$the ordering principle$ does not imply the axiom of choice. – Andrés E. Caicedo Sep 08 '13 at 02:14
  • Ok. It is weird that apparently there is not a fixed "convention" about this. This could cause confusion, especially with people who do not have a lot of experience in these matters. –  Sep 08 '13 at 02:53
  • (But now you know.) It is fairly common, actually, to talk of independence when one really means the restricted sense in which Jech uses the phrase. (Kunen's book is subtitled "Introduction to independence proofs", for example.) – Andrés E. Caicedo Sep 08 '13 at 02:56
  • (And you may want to request the moderators that your two accounts be merged.) – Andrés E. Caicedo Sep 08 '13 at 02:57
  • @Boda Poldi: in your quote from Jech, he does not claim that AC and OP are independent of each other which is what you asked about in the question. Jech states that AC is independent of OP, i.e. ZF + OP neither proves nor disproves AC. "S is independent of T" is not a symmetric relation. – Carl Mummert Sep 08 '13 at 17:11
  • 1
    @Andres Caicedo: Of course ZFA + the ordering principle does not disprove AC either, so Jech's claim that AC is independent of OP does not seem to be a "limited sense". – Carl Mummert Sep 08 '13 at 17:12
  • @BodaPoldi To emphasize Carl's comments: $\phi$ independent of $T$ means $T$ does not prove $\phi$ and does not refute it either, and Jech is saying $\phi$ is independent of $\psi$ in $T$ to mean that $\phi$ is independent of $T\cup{\psi}$. (Still, as I said, it is not uncommon to talk of independence proofs, when we really mean consistency proofs. But Carl is right, and Jech is not used a restricted meaning in the example at hand.) – Andrés E. Caicedo Sep 08 '13 at 17:24