# Proof that $\bigcup_{i \epsilon I} A_{i}$ is an elementary substructure of $\mathfrak{U}$

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?

• Welcome to MSE. I suggest that you add the solution-verification tag to your question. – José Carlos Santos Feb 19 at 7:14
• Sorry about that @JoséCarlosSantos , just edited the tag. – Vagoltof Feb 19 at 7:17
• 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$. – Alex Kruckman Feb 20 at 19:56
• 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"! – Vagoltof Feb 20 at 20:41

## 1 Answer

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$$?

• 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? – Vagoltof Feb 21 at 4:38
• 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. – Vagoltof Feb 21 at 4:41
• @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"? – Alex Kruckman Feb 21 at 4:56
• 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. – Alex Kruckman Feb 21 at 5:00
• 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$). – Vagoltof Feb 21 at 5:12