1
$\begingroup$

I am trying to work out the next proof:

Let $\Sigma$ be a set of formulas. Assume $$\Sigma \vDash \bigvee_{i \in I} \varphi_i \ \leftrightarrow \ \bigwedge_{j \in J} \psi_j $$ Where $\varphi_i$ and $\psi_j$ are formulas. This means that for each $M$ and assignment $s$, such that $M \vDash \Sigma(s)$ then $M \vDash \varphi_i(s)$ for all $i \in I$ iff there is some $j\in J$ such that $M \vDash \psi_j(s)$. Apply compactness to show that there are finite subsets $I' \subseteq I$ and $J' \subseteq J$ such that $$\Sigma \vDash \bigvee_{i \in I} \varphi_i \ \leftrightarrow \ \bigvee_{i \in I'} \varphi_i, \ \ \Sigma \vDash \bigvee_{i \in I'} \varphi_i \ \leftrightarrow \ \bigwedge_{j \in J'} \psi_j $$

Now, I know I pretty much have to do for things, the first two is to prove $\Sigma \vDash \bigvee_{i \in I} \varphi_i \ \leftrightarrow \ \bigvee_{i \in I'} \varphi_i$. I think I don't even need compactness yet, the right to left direction is "evident", if I have a model for a finite subset (smaller thing), it means I also have one for the complete one, I would appreciate any ideas on how to say this a bit more formally? Now, when I go to the other direction is that I start having issues, I know that intuitively I need to prove that if I have it for the subset I can have it for the entire set, but I don't know how to procede.

For the second part, $\Sigma \vDash \bigvee_{i \in I'} \varphi_i \ \leftrightarrow \ \bigwedge_{j \in J'} \psi_j$, well, I get that I need to use compactness theorem to assume that there is a finite model for each of the things. And from that finite model, but I have issues formalising it, and getting it in shape. I would very much appreciate anyones input on how to go about this problem.

$\endgroup$
1
$\begingroup$

Hint: Instead of formulas, think about (clopen) subsets of type spaces corresponding to them. Then just apply topological compactness.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the hint, but to be honest, I don't have a background on topology, I don't really know what those concepts are about (or how to go about them). $\endgroup$ – Sara Mar 8 '15 at 9:19
  • $\begingroup$ @Sara: I'd suggest improving on that front, then. Without elementary knowledge of general topology, many important aspects of model theory will be unavailable to you. To avoid topology in this case, you can think about an element satisfying all $\psi_j$ but none of a finite number of $\varphi_i$. $\endgroup$ – tomasz Mar 8 '15 at 9:58
  • $\begingroup$ The topology point of view is interesting, I will definitely look into it. About this one, so I can do something similar to $\Sigma \cup \{\neg \phi_1 :i \in I \} \vDash \psi_j$?? $\endgroup$ – Sara Mar 8 '15 at 10:35
  • $\begingroup$ I'm not sure how that would help. Instead, think about $\Sigma\cup\{\neg\varphi_i,\psi_j\mid i\in I, j\in J\}$. $\endgroup$ – tomasz Mar 8 '15 at 11:17
  • 2
    $\begingroup$ @C-S: Whether it’s helpful depends entirely on whether one is familiar with the notion of a type space. It wasn’t helpful to the OP, but it could be extremely helpful to someone else. $\endgroup$ – Brian M. Scott Mar 9 '15 at 9:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.