$$\langle P(N), \subseteq\rangle \prec \langle P(R), \subseteq\rangle $$

Is it an elementary substructure?

A substructure $N$ of structure $M$ is called an elementary substructure of $M$, if for every formula $\varphi$, and for every $$b_1,\ldots,b_n\in N:N \models \varphi(b_1,\ldots,b_n) \Longleftrightarrow M \models \varphi(b_1,\ldots,b_n)$$

How can we show it?


1 Answer 1


No, it is not. Can you think of a property the set $\mathbb{N}$ has as an element of $\mathcal{P}(\mathbb{N})$, which it doesn't have as an element of $\mathcal{P}(\mathbb{R})$?

That said, they are elementarily equivalent - this can be proved easily using Ehrenfeucht-Fraisse games. So this constitutes yet another example of the fact that a substructure which is elementarily equivalent to the whole, need not be an elementary substructure (a simpler counterexample is $[0, 1]$ versus $[0, 2]$ as linear orders).

  • $\begingroup$ I can't. I think that all elements form P(N) are in P(R) too. So there is no idea what property it could be $\endgroup$ May 29, 2017 at 3:06
  • $\begingroup$ @SergeyEsipenko Yes, every element of $\mathcal{P}(\mathbb{N})$ is an element of $\mathcal{P}(\mathbb{R})$. But that doesn't mean they all have the same properties. HINT: Suppose $Y\in\mathcal{P}(X)$. What can you say about $Y$ and $X$, in terms of $\subseteq$? $\endgroup$ May 29, 2017 at 3:08
  • $\begingroup$ You mean something like number of elemets? In Y less or equal elements then in X $\endgroup$ May 29, 2017 at 3:17
  • $\begingroup$ @SergeyEsipenko Not really, but sort of. Is there an expression you can write down involving $X, Y$, and $\subseteq$ which you know is true if $Y\in\mathcal{P}(X)$? Put another way: what does it mean for $Y$ to be an element of $\mathcal{P}(X)$? $\endgroup$ May 29, 2017 at 3:18
  • $\begingroup$ $$\exists x \in P(x) (y \subseteq x)$$ $\endgroup$ May 29, 2017 at 3:33

You must log in to answer this question.

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