# Propositional logic: Minimal set of formulas, which is consistent and complete

## Hello together,

I have a rather basic issue on propositional logic: first, consider an arbitrary set of formulas $$T$$ that is consistent and complete, i.e., for every propositional formula $$\varphi$$, either there holds $$T\vdash\varphi$$ or $$T\vdash\neg\varphi$$.

My Question is: Is there a minimal consistent and complete subset $$T^\prime\subseteq T$$, i.e., $$T^\prime$$ is still complete, but no proper subset $$T^{\prime\prime}$$ of $$T^\prime$$ is?

I know some examples where that is the case, namely e.g. the set of propositional variables $$T_1=\{A_0,A_1,\dots\}$$. One can also vary this example by considering any subset $$T_2$$ of the literals (i.e., variables or negations of them) such that for any $$i\geq0$$, either $$A_i\in T$$ or $$\neg A_i\in T$$. In these cases, both $$T_1$$ and $$T_2$$ are already minimal in the above sense.

However, my attempts to prove the question above failed so far. My first approach was it to successively eliminate formulas $$\varphi$$ that can be proven from the rest, i.e. such that $$T\setminus\{\varphi\}\vdash\varphi$$. More detailed: let $$T=\{\varphi_0,\varphi_1,\dots\}$$. Then we define a sequence $$(T_i)_{i\geq0}$$ of subsets of formulas of $$T$$ as follows:

1. $$T_0:=T$$

2. If $$T_i$$ is defined, then search if there is an index $$j\geq0$$ such that $$T_i\setminus\{\varphi_j\}\vdash\varphi_j$$. If yes, pick the least such $$j$$ and define $$T_{i+1}:=T_i\setminus\{\varphi_j\}$$. Otherwise, set $$T_{i+1}=T_i$$

Now if the construction stops at some point, i.e. if there is an $$i\geq0$$ such that $$T_i=T_{i+1}$$, then for least such $$i$$, $$T_i$$ is minimal by construction. However, if the construction runs forever, then we cannot argue that the intersection $$\bigcap_{i\geq0}T_i$$ is still complete because the notion of proof is finite.

I have made now several other attempts, including infinite proofs and axiom of choice, but still nothing seemed to helped. Maybe I have overseen something. Still, I think that the answer to the question is Yes. Does somebody have an idea (or have a counterexample) for this question.

Yours sincerely,

Martin

• It seems to me that you are assuming that $T$ is countable.
– user40023
Feb 2, 2015 at 11:20
• Yes, I consider only propositional formulas built up from a countable set of variables, i.e., w.l.o.g. let $\{A_0,A_1,\dots\}$ be the set of propositional variables. Feb 2, 2015 at 11:29
• A related fact: every theory $T$ in classical propositional or first-order logic has an independent axiomatization, i.e., a set of formulas $T'$ such that $T$ and $T'$ generate the same theory, but no proper subset of $T'$ does. For countable $T$, the argument is quite simple: we enumerate $T=\{A_n:n<\omega\}$, and let $I$ be the set of $n$ such that $A_0,\dots,A_{n-1}\nvdash A_n$. Then one easily checks that $T'=\{A_0\land\dots\land A_{n-1}\to A_n:n\in I\}$ works. The uncountable case is a nontrivial theorem due to Reznikoff; see arxiv.org/abs/1108.5171 for an English translation. Feb 2, 2015 at 21:55

Let $\varphi_n=A_0\wedge A_1\wedge\cdots\wedge A_{n-1}$ be the assertion that the first $n$ many propositional variables are true. The theory $T=\{\varphi_n\mid n\in\mathbb{N}\}$ consisting of all these assertions is complete and consistent, but there is no minimal complete consistent subset of $T$, since $\varphi_k\to\varphi_n$ is a tautology when $n\leq k$, and so any particular formula can be omitted without loss from any infinite subcollection; but no finite set of the $\varphi_n$ is complete.