I'm currently studying model theory with the book "A Course in Model Theory" by Katrin Tent and Martin Ziegler. Currently I have written a proof for Exercise 2.1.1, and I would like to know if it's correct. The problem states:

Exercise 2.1.1. Let $\mathfrak{A}$ be an L-structure and ( $\mathfrak{A}_{i} )_{i \epsilon I}$ a chain of elementary substructures of $\mathfrak{A}$. Show that $\bigcup_{i \epsilon I} A_{i}$ is an elementary substructure of $\mathfrak{A}$.

My solution goes like this:

  1. $\forall i, \forall a, (a \in A_{i} \Rightarrow a \in \bigcup_{i \epsilon I} A_{i})$
  2. $\forall i, \mathfrak{A}_{i} \prec \mathfrak{A}$
  3. $\forall i, \forall \phi, \forall a , ((\mathfrak{A}_{i} \prec \mathfrak{A}) \Leftrightarrow (\mathfrak{A}_{i} \models \phi (a) \Leftrightarrow \mathfrak{A} \models \phi (a) ))$

This first three are basically just definitions, the actual inferences are the following:

  1. The hypothesis: $ \exists i, \exists a \in \bigcup_{i \epsilon I} A_{i}, ( \mathfrak{A} \not\models \phi(a) \Rightarrow \mathfrak{A}_{i} \nprec \mathfrak{A}) $
  2. By Modus Ponens: $\exists i, \mathfrak{A}_{i} \nprec \mathfrak{A}$
  3. $(\forall i, \mathfrak{A}_{i} \prec \mathfrak{A}) \wedge (\exists i, \mathfrak{A}_{i} \nprec \mathfrak{A}) \Rightarrow \bot$ (by 2 and 5)

And finally, by Modus Tollens on the contradictory hypothesis (4):

  1. $\forall i, \forall a \in \bigcup_{i \epsilon I} A_{i}, \mathfrak{A} \models \phi(a)$

Which should satisfy Tarski's Test which according to the book states:

Let $\mathfrak{B}$ be an $L$-structure and $A$ a subset of $B$. Then $A$ is the universe of an elementary substructure if and only if every $L(A)$-forumla $\phi (x)$ which is satisfiable in $\mathfrak{B}$ can be satisfied by an element of $A$.

So again, does the proof seems correct? are there not any inferential jumps or plain just downright wrong inferences?

  • $\begingroup$ Welcome to MSE. I suggest that you add the solution-verification tag to your question. $\endgroup$ – José Carlos Santos Feb 19 at 7:14
  • $\begingroup$ Sorry about that @JoséCarlosSantos , just edited the tag. $\endgroup$ – Vagoltof Feb 19 at 7:17
  • $\begingroup$ I just made a bunch of edits to your question. Most importantly: (1) use $\in$ (\in) instead of $\epsilon$ (\epsilon) for set membership, (2) the symbol $\mathfrak{A}$ is actually a mathfrak A, not a mathfrak U (the U looks like $\mathfrak{U}$). This is why we use $A$ for the domain of $\mathfrak{A}$, not $U$. $\endgroup$ – Alex Kruckman Feb 20 at 19:56
  • $\begingroup$ Sorry about that @AlexKruckman kind of a newbie with the Latex notation, and about te mathfrak A I really never realized it was actually an A, but thanks a lot for taking the bother of correcting my "proof"! $\endgroup$ – Vagoltof Feb 20 at 20:41

I don't understand the proof you've written. (5) does not follow from (4) by Modus Ponens, and (7) is not the negation of the hypothesis (4). Further, your proof concludes that $\phi(x)$ is satisfied by every element of $\bigcup_{i\in I}A_i$, and it should be clear that this is too strong. To apply Tarski's test, you need to consider a formula $\phi(x)$ which is satisfied by some element of $\mathfrak{A}$. But it's quite possible that it's satisfied by only one element!

Anyway, you have the right idea to apply Tarski's test. Let $\varphi(x,\bar{a})$ be an $L$-formula with parameters $\bar{a}$ from $\bigcup_{i\in I}A_i$, such that $\varphi(x,\bar{a})$ is satisfied in $\mathfrak{A}$, i.e., $\mathfrak{A}\models \exists x\, \varphi(x,\bar{a})$. You want to find some $b\in \bigcup_{i\in I} A_i$ such that $\mathfrak{A}\models \varphi(b,\bar{a})$. Then you're done by Tarski's test.

Hint: Use the assumption that $\mathfrak{A}_i\preceq \mathfrak{A}$ to pull satisfaction of $\exists x\, \varphi(x,\bar{a})$ down to $\mathfrak{A}_i$. Careful: not any $i\in I$ works. Why not? How can you pick the right $i$?

  • $\begingroup$ I appreciate your response @AlexKruckman, and certainly, the fact of how "strong" the conclusion was should have been an alert, of which I will now and onwards be aware of, otherwise, I will work heeding your hint. I would like to ask some things regarding steps (4), (5) and (7) though, first regarding (4) if I had stablished the condition " $\exists \phi \in \mathfrak A_{i}$ " even if this is the incorrect route, would this have made the hypothesis valid? $\endgroup$ – Vagoltof Feb 21 at 4:38
  • $\begingroup$ Secondly in (4) I added the material condition (as it seemed intuitively correct given the prior correction) just so I could apply MP in 5, but it felt out of bounds (quite arbitrary), would it be valid to conclude by MP something that is entailed by an hypothesis withou stablishing a material conditional in the hypothesis itself? And regarding (7), I intended just to negate the condition of the conditional as in Modus Tollens, and just inverted the quantifiers and the sentence, isn't that the process of negation? Sorry if I have overstepped with these extra questions. $\endgroup$ – Vagoltof Feb 21 at 4:41
  • 1
    $\begingroup$ @Vagoltof You seem to be trying to give the proof in a very formal style, which actually makes it quite hard to understand the argument. You wrote "if I had stablished the condition `$\exists \phi \in \mathfrak{A}_i$' ... would this have made the hypothesis valid?" This makes no sense at all to me - there must be a typo, since $\phi$ is a formula not an element of $\mathfrak{A}_i$ - and the hypothesis (4) is something you're assuming for contradiction, right? What does it mean for it to be "valid"? $\endgroup$ – Alex Kruckman Feb 21 at 4:56
  • 1
    $\begingroup$ You then write "would it be valid to conclude by MP something that is entailed by an hypothesis without establishing a material conditional in the hypothesis itself". Again, I'm not sure what this means, but you seem to be asking a question about the logical form of the proof itself, not its content. I would strongly recommend that you get some more practice with proof writing and clear up any confusions you have about basic logic before you try to dive into a more advanced and abstract topic like model theory. $\endgroup$ – Alex Kruckman Feb 21 at 5:00
  • $\begingroup$ Well @AlexKruckman, I actually come from a logic-philosophy background, so while I have seen in, for example, Tent and Ziegler book more "informal" proofs, I have a specific need for proofs to be as logically unambiguous as possible, and for each step of an inference be formally stablished. Regarding the typo, yes, as a matter of fact I meant ' $\exists \phi \in Th(\mathfrak A_{i})$' ; by 'valid' in this case I mean, that by adding the correction, what the conditional implies can be correctly inferred ($\mathfrak A_{i} \not \prec \mathfrak A$). $\endgroup$ – Vagoltof Feb 21 at 5:12

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.