Show that class of infinite sequences with relation $R$ is not axiomatizable

156 Views Asked by At

Lets consider the class $\mathbb{A}$ of all structures which are isomorphic to a structure of the form $⟨A^{\mathbb{N}},R⟩$, where $A$ is any nonempty set, $A^{\mathbb{N}}$ is set of all infinite sequences over $A$, and $xRy$ iff the set of positions on which $x$ and $y$ are different is finite.

Prove that this class is not axiomatizable.

My approach is the following.
The signature (language) is finite. There is an infinite model of this class:
$A=\mathbb{N}$, then $|\mathbb{N}^\mathbb{N}|=\mathfrak{c}$.

Hence, from the Löwenheim-Skolem theorem, there also exist models of any infinite cardinality. However, sequences can differ only on finite number of positions, then the number of these sequences is: $|A|^{\aleph_0}\ge\mathfrak{c}$

This is a contradiction with the Löwenheim-Skolem theorem, because there is no model with cardinality $\aleph_0$.

Am I ok?

1

There are 1 best solutions below

2
On BEST ANSWER

Your argument is on the right track, and you're almost there. But I don't understand the sentence "However, sequences can differ only on finite number of positions, then the number of these sequences is:$|A|^{\aleph_0}\ge\mathfrak{c}$".

When you're looking for a contradiction with Löwenheim-Skolem, what's relevant is the cardinality of the structure, not the relation $R$. But you refer to sequences differing on a finite number of positions, which has to do with the definition of $R$.

Instead, you need to argue that for any set $A$, $|A^{\mathbb{N}}|\neq \aleph_0$. Think about the cases when $|A| = 0$, $|A| = 1$, and $|A|\geq 2$...