5
$\begingroup$

I am trying to answer the following question posed in my logic class: (throughout we work in propositional logic) is there a set $S$ of well-formed-formulas (wffs) satisfied by countable set $V$ of truth assignments such that any truth assignment satisfying $S$ lies in $V$?

My guess is no. My first reaction to this was to do a diagonalization. Present $V$ as an array with $v_{i, j}$ the truth value that assignment $v_i$ gives to the $j$-th propositional letter. Obviously the hard case is when $S$ is infinite; if $S$ is finite, then only finitely many propositional letters occur in the $S$-formulae. Then there is some maximal $k$ for which all $A_n$ with $n \geq k$ do not occur in V. Then the diagonalization is trivial: just diagonalize from the $k$-th letter onward, since changing $A_k$ in this range doesn't affect anything in $S$.

But I have little clue about how to approach the main case when $S$ is infinite. I thought maybe I should try using the fact that $S$ is consistent (since it's satisfiable). If it's maximally consistent, then I think this is simple too, since for every propositional letter $A_n$, either $A_n$ is in $S$ or $(\neg A_n)$ is in $S$, implying that there is only one truth assignment satisfying $S$--since every truth assignment must agree on each propositional letter.

But if $S$ is not maximally consistent, this isn't available to me. Somehow I would like to show that infinitely many propositional letters do not occur in $S$. Then I can apply the trick above and just diagonalize through the superfluous letters.

So, yes, just looking for some hints or corrections if you have any please, though maybe if I don't get anywhere on my own I'll give up and ask for more. Thanks.

(By the way, by referring to letters that "occur in $S$" I mean letters that occur in some formula in $S$).

$\endgroup$
1
  • 1
    $\begingroup$ Algebraically closed field is complete, consistent, and recursively enumerable. $\endgroup$
    – Kenny Lau
    Sep 21, 2017 at 5:30

2 Answers 2

2
$\begingroup$

I think I found my mistake: namely, I believe I was trying to prove a false statement (i.e., "My guess is no".) [Note: This parenthetical clarification now added to pacify certain exceptionally helpful moderators who "reviewed" this post and supplied exceptionally useful feedback.]

$\endgroup$
3
  • 1
    $\begingroup$ Please use the edit link on your question to add additional information. The Post Answer button should be used only for complete answers to the question. - From Review $\endgroup$ Sep 21, 2017 at 6:57
  • $\begingroup$ @Henrik In my question, I asked for a hint. The sentence posted above is a hint. So the sentence posted above is an answer. $\endgroup$ Sep 21, 2017 at 7:12
  • 1
    $\begingroup$ @Leucippus Firstly, I am the author. Secondly, no. $\endgroup$ Sep 21, 2017 at 7:16
1
$\begingroup$

Let $p_0,p_1,p_2,\dots$ be a list of all the propositional variables. Let $S$ consist of the implications $p_n\to p_{n+1}$ for all $n$. What do the satisfying truth assignments look like?

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .