1

Let $\Gamma=\Sigma \cup \left\lbrace p_i,i\geq 1 \right\rbrace$ a countable set of propositional formulas. Assume also that for every boolean evaluation $u$ that maps every member of $\Sigma$ to true , there exists an $m$ which depends on $u$ such that $u(p_m)=T$.

It comes as an immediate consequence of compactness lemma that one can expand the set $\Sigma$ with those $p_i$ that are satisfied simultaneously with the members of $\Sigma$ in a disjunction. Meaning : the set $\Sigma \cup\left\lbrace p_1\vee p_2\vee ...\vee p_k \right\rbrace$ is satisfiable.

My question is: Are the members of this disjunction finite?

Saying that there exists an integer $k$ such that $\Sigma\models\left\lbrace p_1\vee p_2\vee ...\vee p_k \right\rbrace$ $(A)$

Or $\Sigma\models \left\lbrace p_1\vee p_2\vee ...\right\rbrace$ $(B)$

Is the statement $(A)$ because of the countability of set $\Gamma$ ?

mort32
  • 13
  • I'm lost. What disjunction? Can you provide a clearer specification of the disjunction you are referring to? What do you mean by "the members of this disjunction"? What does it mean for them to be finite? What does "satisfied along the members of $\Sigma$ in a disjunction" mean? What does it mean to say "one can expand the set $\Sigma$"? Of course one can expand the set $\Sigma$ to get a new set; that's always true of any set. Also I'm not sure what you mean by "Saying that there exists...". Can you edit your question to rephrase and/or elaborate? – D.W. May 18 '15 at 21:18
  • One other question. Is there a strong connection to computer science? This sounds like a pure math question. Generally, we require that questions have a strong connection to computer science, and that they articulate the connection in the question -- pure math questions without such a connection are better suited for Math.SE or Math Overflow. – D.W. May 18 '15 at 21:19
  • "one can expand the set Σ with those $p_i$ that are satisfied along the members of Σ in a disjunction." is the statement (A) in other words: that $\Sigma\cup\left\lbrace p_{1}\vee p_{2}\vee ... \vee p_{k} \right\rbrace$ is satisfiable. This is the disjunction i was referring to. Sorry about this clumsy expression. English is not my native tongue. Maybe you are correct in that it sound more like a pure math question because of the finite/infinite type of the disjunction – mort32 May 18 '15 at 21:49
  • Thanks. I encourage you to edit the question. Comments exist only to help you improve your question: we want people to improve their question, not just leave clarifications in the comments. If you would prefer to see this on another site, you can flag it for moderator attention and ask them to migrate it (don't re-post it on another SE site, as that violates site rules, but you're welcome to ask them to migrate it if you think that's more appropriate -- it's up to you). – D.W. May 18 '15 at 21:56

1 Answers1

0

Suppose that for each $k$ there is a truth assignment for $\Sigma$ which makes all of $p_1,\ldots,p_k$ false. In other words, $\Sigma \cup \{ \lnot p_1, \cdots, \lnot p_k \}$ is satisfiable. This means that every finite subset of $\Sigma \cup \{ \lnot p_i : i \geq 1 \}$ is satisfiable, since for every such finite subset there is a maximal index $k$ such that $p_k$ appears in the subset. By compactness, the infinite set $\Sigma \cup \{ \lnot p_i : i \geq 1 \}$ is satisfiable, contradicting your assumption. We conclude that for some $k$, $\Sigma \vDash p_1 \lor \cdots \lor p_k$.

Yuval Filmus
  • 57,157