2

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

Michael Hardy
  • 1
just a student
  • 179

1 Answers1

3

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).

Noah Schweber
  • 245,398
  • 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 – just a student May 29 '17 at 03:06
  • @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$? – Noah Schweber May 29 '17 at 03:08
  • You mean something like number of elemets? In Y less or equal elements then in X – just a student May 29 '17 at 03:17
  • @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)$? – Noah Schweber May 29 '17 at 03:18
  • $$\exists x \in P(x) (y \subseteq x)$$ – just a student May 29 '17 at 03:33
  • The sentence I was looking for was "$Y\subseteq X$" - if $Y$ is an element of the powerset of $X$, then $Y\subseteq X$ by definition. What you've written sort of looks like this, but doesn't really parse (do you see why? the "$\exists x\in P(x)$" is really not supposed to be there). OK, now think about the formula $\varphi(a)=$"$\forall x(x\subseteq a)$." In $\mathcal{P}(\mathbb{N}),$ do we have $\varphi(\mathbb{N})$? What about in $\mathcal{P}(\mathbb{R})$? – Noah Schweber May 29 '17 at 03:36
  • Hm So, if we chose $a=P(N)$, then every $x\subseteq a$ But if $P(R)$ there are elements $\notin P(N)$ and this is not an elementary elementary substructure ?? – just a student May 29 '17 at 04:14