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



Propositional logic: Minimal set of formulas, which is consistent and complete
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. 


The same idea works even when there are uncountably many variables. Just divide them into groups of countably infinitely many and do the same trick within each group.


