1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ It seems to me that you are assuming that $T$ is countable. $\endgroup$
    – user40023
    Feb 2, 2015 at 11:20
  • $\begingroup$ 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. $\endgroup$ Feb 2, 2015 at 11:29
  • $\begingroup$ 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. $\endgroup$ Feb 2, 2015 at 21:55

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.