Notes - Logic MT24, Isomorphisms and equivalences of structures

Created: November 22, 2024
Updated: January 07, 2025

Flashcards

Isomorphic structures

Suppose:

  • $\mathcal L$ is a first-order language
  • $\mathcal A = \langle A; \ldots \rangle$ and $\mathcal B = \langle B; \ldots \rangle$ are $\mathcal L$-structures

@Define what it means for $\mathcal A$ and $\mathcal B$ to be isomorphic, written $A \cong B$.

There exists a bijection $\theta : A \to B$ such that:

  • $\theta(c^\mathcal A) = c^\mathcal B$ for $c$ constant symbol
  • $\theta(f^\mathcal A(a _ 1, \ldots, a _ k)) = f^\mathcal B(\theta(a _ 1), \ldots, \theta(a _ k))$ for a $k$-ary function symbol and $a _ i \in A$
  • $(a _ 1, \ldots, a _ k) \in P^\mathcal A$ iff $(\theta(a _ 1), \ldots, \theta(a _ k)) \in P^\mathcal B$ for $P$ a $k$-ary relation symbol and $a _ i \in A$

@State a criterion for completeness of a theory in terms of isomorphisms.

Suppose:

  • $\Sigma \subseteq \text{Sent}(\mathcal L)$ has a unique countable model up to isomorphism.
  • (i.e. if $\Sigma$ is consistent and if $\mathcal A \models \Sigma$ and $\mathcal B \models \Sigma$ are countable, then $A \cong B$).

Then:

  • $\Sigma$ is complete.

(The key is that a unique countable model up to isomorphism is enough to prove elementary equivalence of all models, not just countable models).

Elementarily equivalent structures

Suppose:

  • $\mathcal L$ is a first-order language
  • $\mathcal A, \mathcal B$ are $\mathcal L$-structures

@Define what it means for $\mathcal A$ and $\mathcal B$ to be elementarily equivalent, written $A \equiv B$?
\[\text{Th}(\mathcal A) = \text{Th}(\mathcal B)\]

Suppose:

  • $\mathcal L$ is a first-order language
  • $\Sigma \subseteq \text{Sent}(\mathcal L)$ is a $\mathcal L$-theory

@State a criterion for completeness in terms of elementary equivalence.

$\Sigma$ has a model and $\mathcal A \equiv \mathcal B$ for any two models $\mathcal A$ and $\mathcal B$ of $\Sigma$.

Relationship between isomorphic and elementarily equivalent structures

Suppose:

  • $\mathcal L$ is a first-order language
  • $\mathcal A = \langle A; \ldots \rangle$ and $\mathcal B = \langle B; \ldots \rangle$ are $\mathcal L$-structures

@State a relationship between $\mathcal A$ and $\mathcal B$ being isomorphic and $\mathcal A$ and $\mathcal B$ being elementarily equivalent.
  • $\mathcal A \cong \mathcal B \implies \mathcal A \equiv \mathcal B$ (non-trivial)
  • $\mathcal A \cong \mathcal B \not\Longleftarrow \mathcal A \equiv \mathcal B$ (e.g. by Löwenheim-Skolem there might be two elementarily equivalent structures, one of which is countable and the other uncountable)

@Prove that if:

  • $\mathcal L$ is a first-order language
  • $\mathcal A = \langle A; \ldots \rangle$ and $\mathcal B = \langle B; \ldots \rangle$ are $\mathcal L$-structures
  • $\mathcal A \cong \mathcal B$

Then:

  • $\mathcal A \equiv \mathcal B$

@todo.

@Prove that if:

  • $\Sigma \subseteq \text{Sent}(\mathcal L)$ has a unique countable model up to isomorphism.
  • (i.e. $\Sigma$ is consistent and for any two countable models $\mathcal A \models \Sigma$ and $\mathcal B \models \Sigma$, it follows $A \cong B$).

then:

  • $\Sigma$ is complete.

(The key is that a unique countable model up to isomorphism is enough to prove elementary equivalence of all models, not just countable models).

Suppose $\mathcal A$ and $\mathcal B$ are two arbitrary models of $\Sigma$, i.e. $\mathcal A \models \Sigma$ and $\mathcal B \models \Sigma$ (not necessarily countable). We want to show that then $A \equiv B$, since then all models satisfy the same sentences and $\Sigma$ is complete.

Since $\text{Th}(\mathcal A)$ and $\text{Th}(\mathcal B$) are both consistent, then by the Weak Downward Löwenheim-Skolem theorem, there are countable models $\mathcal A’$ and $\mathcal B’$ such that $\mathcal A’ \equiv A$ and $\mathcal B’ \equiv B$.

Then $\mathcal A’ \models \Sigma$ and $\mathcal B’ \models \Sigma$ (since $\text{Th}(\mathcal A)$ and $\text{Th}(\mathcal B)$ are supersets of $\Sigma$).

But then by assumption, $\mathcal A’ \cong \mathcal B’$. Since isomorphic structures are elementarily equivalent, $\mathcal A’ \equiv \mathcal B’$. Hence

\[\mathcal A \equiv \mathcal A' \equiv \mathcal B' \equiv \mathcal B\]

and so $\mathcal A \equiv \mathcal B$.



Related posts