Substructures
Definition
Over a language $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \cl L$, we say that $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \mathcal M$ is a substructure of $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \mathcal N$, and write $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \mathcal M \subseteq \mathcal N$, iff:
$% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} M \subseteq N$
$% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} c^\mathcal M = c^\mathcal N$
$% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} f^\mathcal M = f^\mathcal N \vert_{M^{n_f}}$
$% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} R^\mathcal M = R^\mathcal N \cap M^{n_R}$
Property: Mutual Entailment of qf. formulas
Fix a language $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \cl L$, and take structures $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \cl M \subseteq \cl N$. Then for every quantifier-free formula $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \phi = \phi(\ol v)$ and tuple $% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small {#1} }} \ol m \in \cl M^{<\omega}$,
$% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\tt}[1]{ \texttt{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } % "magnitude" \newcommand{\mag}[1]{ { \lvert {#1} \rvert } } % cardinality \newcommand{\card}{ \t{card} } % disjoint untion \newcommand{\dcup}{ \sqcup } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % tuples \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\iffText}{{ \hspace{20pt}\t{iff}\hspace{20pt} }} \newcommand{\pre}[1]{{ \small `{#1} }} \cl M \vDash \phi(\ol m) \iff \cl N \vDash \phi(\ol m)$
nb. Compare this with the definition of elementary substructure