2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Use the rephrasing instead. $\endgroup$ – user665538 Apr 19 '19 at 4:40
  • $\begingroup$ 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. $\endgroup$ – user657449 Apr 19 '19 at 4:46
  • $\begingroup$ I removed the infinite formula. $\endgroup$ – user665538 Apr 19 '19 at 4:52
  • $\begingroup$ @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"? $\endgroup$ – user654868 Apr 19 '19 at 16:22
  • 1
    $\begingroup$ Different $n$ for every assignment. $\endgroup$ – user665538 Apr 19 '19 at 20:34
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks. I cannot upvote. $\endgroup$ – user665538 Apr 19 '19 at 20:35

Your Answer

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