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

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.

• Use the rephrasing instead. – user665538 Apr 19 '19 at 4:40
• As @DerekElkins said, usually "infinitely long" expressions make no sense and need a very definite meaning, such as infinitary logic. Notice that as the article says, you will have a different logical system where not all results hold. by reading your question, you seem to be thinking about something related to the compactness theorem. – user657449 Apr 19 '19 at 4:46
• I removed the infinite formula. – user665538 Apr 19 '19 at 4:52
• @SIndigo. "for every truth assignment v there exists n with Xn satisfied by v" is not perfectly clear to me. Shoul I understand " for each assignment, there is some formula that has value true ( but not necessarily the same formula for all valuation)" or should I understand " there is some formula Xn such that this formula has value true for every assignment"? – user654868 Apr 19 '19 at 16:22
• Different $n$ for every assignment. – user665538 Apr 19 '19 at 20:34

## 1 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.

• Thanks. I cannot upvote. – user665538 Apr 19 '19 at 20:35