If every truth assignment satisfies some wff, some finite disjunction is a tautology

218 Views Asked by At

Let $X_1,X_2,X_3,...$ be well formed formulas. If for every truth assignment $v$ there exists $n$ with $X_n$ satisfied by $v$, show there exists $n$ with $X_1\lor...\lor X_n$ a tautology.

We can assume there are an infinite number of sentence symbols, as a finite number would imply a finite number of truth assignments, so we could take $n$ to be the maximum of the first satisfying indices of the truth assignments. I think it's important that the number of sentence symbols is countable. For all $n$, let $Y_n=X_1\lor...\lor X_n$ and $S_n$ be the set of truth assignments satisfying $Y_n$. Note that $S_1\subseteq S_2\subseteq S_3\subseteq...$. Since the number of sentence symbols is countable and every truth assignment sends every sentence symbol to $0$ or $1$, the truth assignments are in bijection with countable binary sequences, which are in bijection with the real numbers between $0$ and $1$. I was hoping to get a contradiction out of this, but we could just make $S_n\setminus S_{n-1}$ the binary numbers from $0$ to $1$ with $n$ leading $0$s. Compactness of well formed formulas might be relevant, but I can't think of a way to apply it.

1

There are 1 best solutions below

1
On BEST ANSWER

In general we do not need countability, as it boils down to a compactness argument. Let $X_1, X_2, \ldots$ be as you described. Then consider $\neg X_1, \neg X_2, \ldots$ instead. By assumption, for every truth assignment there will be $n$ such that $\neg X_n$ is false. That means that there is no truth assignment such that $\neg X_1, \neg X_2, \ldots$ are all true. Now we can apply compactness to find a finite subset $\neg X_{i_1}, \ldots, \neg X_{i_k}$ such that $\neg X_{i_1} \wedge \ldots \wedge \neg X_{i_k}$ will be false in every truth assignment (so, a tautology). In other words, $\neg(\neg X_{i_1} \wedge \ldots \wedge \neg X_{i_k})$ will be true in every truth assignment and this is equivalent to $X_{i_1} \vee\ldots \vee X_{i_k}$.

To get the exact formulation of your problem we do need to assume that $\neg X_1, \neg X_2, \ldots$ is countable. Then we can take $n = \max \{i_1, \ldots, i_k\}$, and then clearly $X_1 \vee \ldots \vee X_n$ is true in every in truth assignment.