Substructures
Definition
Over a language L % 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 M % 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 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} }} \mathcal N, and write MN % 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:
MN % 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
cM=cN % 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
fM=fNMnf % 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}}
RM=RNMnR % 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 L % 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 MN % 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 ϕ=ϕ(v) % 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 mM<ω % 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},
Mϕ(m)    Nϕ(m) % 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