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 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
10
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 9:23

You must log in to answer this question.

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