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?

  • $\begingroup$ I've just edited to fix many spelling and grammar issues, and a few minor mathematical issues (for example, you wrote $\mathbb{N}^\mathbb{N} = \mathfrak{C}$, but you meant $|\mathbb{N}^\mathbb{N}| = \mathfrak{c}$). If you click on the "edited x min ago" link, you can see all my changes. Please try to avoid making so many typos in your posts! $\endgroup$ – Alex Kruckman Feb 19 '17 at 16:27
  • $\begingroup$ Ok, thanks! :-) $\endgroup$ – user343207 Feb 19 '17 at 16:28
  • $\begingroup$ The most substantial change I made was to clarify the definition of $\mathbb{A}$. It was a bit ambigious whether you meant to fix a set $A$ and then consider all the structures isomorphic to $\langle A^{\mathbb{N}},R\rangle$ or whether you meant to consider all structures isomorphic to a structure of that form, where $A$ is an arbitrary set. $\endgroup$ – Alex Kruckman Feb 19 '17 at 16:28

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$...

  • $\begingroup$ wait. I show that it has model of cardinality $\mathfrak{c}$. Signgature has only one relation so it is finite. So LS theorem should be hold. The aim is to show that there is no model of cardinality $\aleph_0$. For $|A|=0$ we have $0^{\aleph_0} = 0 \neq \aleph_0$. For $|A|=1$ we have $1^{\aleph_0} = 1 \neq \aleph_0$ and for other positive values we have $\mathfrak{c}$. Hmm ? $\endgroup$ – user343207 Feb 19 '17 at 19:26
  • $\begingroup$ Exactly. Well, to be precise, for other values of $|A|$, we have $|A|^{\aleph_0} \geq 2^{\aleph_0} = \mathfrak{c}$, not necessarily equal. $\endgroup$ – Alex Kruckman Feb 19 '17 at 19:55

Your Answer

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