1
$\begingroup$

Lets consider class $\mathbb{A}$ os structures, which are isomorphic to structure $\langle A^{\mathbb{N}}, R\rangle$ where $A$ is any non-empty set and $A^{\mathbb{N}}$ is set of all infinite sequences over $A$. When it comes to $R$: $xRy$ if only and only if set of position on $x$ and $y$ are different is finite.

Prove that there is not exists such set of first-order logic sentences that is express class $\mathbb{A}$.

This one is difficult, from my point of view. You know, we have not-directed graph, in vertex we have one infinite sequence over non-empty set. We have an edge in case of two sequences are different in finite positions, in other words are almost the same. I was solving similar problem using compactness theorem or gamse, however this one seems to be undoable. Can you help me, please ?

$\endgroup$
6
$\begingroup$

If $A$ has exactly one element, then so does $A^{\mathbb N}$. On the other hand, if $A$ has at least two elements, then $A^{\mathbb N}$ is uncountable. So every structure in $\mathbb A$ has either one element or uncountably many.

Now suppose there is a set $T$ that axiomatizes $\mathbb A$. Then in particular $T$ is satisfied by $\left<\{0,1\}^{\mathbb N},R\right>$, but by the downward Löwenheim-Skolem theorem, $\left<\{0,1\}^{\mathbb N},R\right>$ is elementarily equivalent to some countable substructure, which therefore also satisfies $T$. But there are no countable structures in $\mathbb A$, so $T$ didn't express $\mathbb A$ after all.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy