On Logical Independence

There are multiple definitions of logical independence out there in the literature. In this article, we tease out these definitions and investigate their relationships with each other.

The definitions we use are the following:

Definition 1. Let $L$ be a language, $A$ be an axiomatic system in $L$ , and $S$ a statement in $L$ . Assume $A$ is consistent. We say that $S$ is independent of $A$ if both $A \cup \left\{ S \right\}$ and $A \cup \left\{ - S \right\}$ are consistent.

Definition 2. Let $L$ be a language, $A$ be an axiomatic system in $L$ , and $S$ a statement in $L$ . Assume $A$ is consistent. We say that $S$ is independent from $A$ if there exists no sequence of logic from $A$ that can prove or refute $S$ .

Wikipedia lists some definitions as ignoring the possibility of refutation; we consider that to be against the common informal meaning of independence and so we discard such definitions.

If $S$ is independent of $A$ by Def 1, then $A \cup \left\{ S \right\}$ is consistent, so we cannot prove $- S$ in $A$ . But also $A \cup \left\{ - S \right\}$ is consistent, so we cannot prove $- ( - S) = S$ in $A$ . Thus, $S$ is independent of $A$ by Def 2. Thus, Def 1 implies Def 2.

Conversely, if $S$ is not independent of $A$ by Def 1, then either $A \cup \left\{ S \right\}$ or $A \cup \left\{ - S \right\}$ is inconsistent. Assume for the first case that $A \cup \left\{ S \right\}$ is inconsistent. But since $A$ is consistent, this implies that $S$ is (provably) false in $A$ . (In symbols, $A \cup \left\{ S \right\} \rightarrow F$ where $F$ means false, so the contrapositive yields $T \rightarrow \left( \vee_{a \in A}( - a) \right) \vee ( - S)$ , and in $A$ this yields $- S$ .) Similarly, for the second case, $A \cup \left\{ - S \right\}$ being inconsistent implies that $S$ is (provably) true in $A$ . Either way, $S$ is not independent by Def 2. Thus, the negation of Def 1 implies the negation of Def 2, so Def 2 implies Def 1.

Hence, these two meanings are equivalent. Note that this works regardless of proof systems: whatever proof system we choose for the second definition is also taken as the proof system for the first definition. The proof above uses proof by contradiction (which in turn is contrapositive logic) and other propositional logic principles, so any proof system that includes such principles would allow a proof of Def 1 from Def 2 within it. We would not consider a “proof system” to be a valid proof system if it didn’t include propositional logic principles at least — these are obvious and basic principles for human and objectively valid logical reasoning, and they are necessary to begin writing meta-proofs to study proof theory in the first place. We consider such logical principles to always be there regardless of proof system and to be a prerequisite to any mathematical or logical discussion.

Thus, it’s fine to use either definition, as Wikipedia does (see the Wikipedia article on logical independence, Independence (mathematical logic) – Wikipedia.)

Logical Independence of Theories

OK, now let’s tackle another question. There seem to be multiple meanings of a theory itself being independent, in terms of its axioms being independent of each other. What are these meanings?

Definition. An axiomatic system $A$ is independent of 1st kind if every axiom in $A$ is independent of all the others: for every $a \in A$ , $a$ is independent of $A - \left\{ a \right\}$ .

Personally, I don’t know if I would consider that to be “fully” independent; at least as a definition, I would define:

Definition. An axiomatic system $A$ is independent of 2nd kind if every axiom is independent from every other subset of axioms. There are multiple possible formulations I can do of this:

For every subset $S \subseteq A$ and every statement $a \in A - S$ , $a$ is independent of $S$
For every $a \in A$ and every subset $S \subseteq A - \left\{ a \right\}$ , $a$ is independent of $S$

Are these equivalent (just for the second definition)? Is choosing $S \subseteq A$ and $a \in A - S$ equivalent to choosing $a \in A$ and $S \subseteq A - \left\{ a \right\}$ ?

Yes, it is. If $S = A$ , then $a$ can’t exist, so that’s a null condition and can be thrown away. Otherwise, $S$ is a proper subset, and choosing $a \in A - S$ guarantees that both $a \in A$ and $S \subseteq A - \left\{ a \right\}$ . Conversely, if we choose $a \in A$ and $S \subseteq A - \left\{ a \right\}$ , then this also means $S \subseteq A$ and $a \in A - S$ . Thus, these two formulations of the concept of “independent of 2nd kind” are equivalent.

Are these two definitions (1st kind and 2nd kind) equivalent? And how does this relate to Wikipedia’s assertion that though GCH is independent of ZFC, in fact ZF + GCH implies AC? (Here, GCH stands for generalized continuum hypothesis, and the other acronyms stand for their standard meanings.)

Well, would $\left\{ ZF,AC,GCH \right\}$ be independent in either of these definitions? The fact that $ZF + GCH \rightarrow AC$ implies that AC is not independent of the theory minus AC (which is $ZF + GCH$ ); thus, this wouldn’t be independent of the 1st kind, let alone the 2nd. (The 2nd kind is clearly at least stronger than the 1st kind.) Thus, what this really says is: if $S$ is independent of $A$ , that doesn’t mean necessarily that $A \cup \left\{ S \right\}$ is an independent theory. There’s more being asserted for a theory to be independent.

I highly suspect the 1st and 2nd kind definitions to be equivalent, which case we can just talk about a theory being independent regardless and it doesn’t matter. We need to show that the 1st kind implies the 2nd kind, so let’s do that.

First, note that if $S$ is independent of $A$ then $S$ is independent of any subset of $A$ , since if $S$ weren’t independent of some subset of $A$ then it would be provable or refutable from that subset, and therefore provable or refutable from $A$ overall. Now, assume independence of the 1st kind, and take $a \in A$ and a subset $S \subseteq A - \left\{ a \right\}$ . Since $a$ is independent of $A - \left\{ a \right\}$ by assumption of 1st kind independence, $a$ is independent of $S$ . We are done, this proves that both definitions are equivalent.

First written March 31, 2022. When I first wrote this, I thought that the term “undecidable” was also commonly used as a synonym for “independent,” so I viewed the standard terminology as potentially ambiguous. Specifically, I used the term “undecidable” for the second definition of independence (for an individual statement, not a theory.) I later concluded that that was really my “head-canon definition” based on my intuitive understanding of the term “undecidable”; the term “undecidable” in standard usage is only ever applied to the existence of an algorithm to a decision problem, and thus the usage of the term in proof theory is just based on the “most natural” decision problem for proof theory, of whether or not we can generate a proof. Hence, there is no ambiguity, and undecidability is a separate concept from independence.

Share and like (need WordPress account to like):

Leave a comment Cancel reply