Intereting Posts

The Hexagonal Property of Pascal's Triangle
Find a point position on a rotated rectangle
To find all odd integers $n>1$ such that $2n \choose r$ , where $1 \le r \le n$ , is odd only for $r=2$
Classification of general fibre bundles
Is this local martingale a true martingale?
On the general form of the family $\sum_{n=1}^\infty \frac{n^{k}}{e^{2n\pi}-1} $
Metric on n-sphere in terms of stereographic projection coordinates
Infinite Sum without using $\sin\pi$
ACF universal is the theory of integral domains
Finding integers of the form $3x^2 + xy – 5y^2$ where $x$ and $y$ are integers, using diagram via arithmetic progression
Hartshorne Theorem 8.17
Is there a category theory notion of the image of an axiom or predicate under a functor?
$\operatorname{height} \mathfrak{p} + \dim A / \mathfrak{p} = \dim A$
Understanding direct sum of matrices
Kostrikin's Definition of Tensor Product

This is (a translation of) an excerpt from a model theory textbook that shows that $2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S, <)$, where $S$ is the successor function.

Suppose $2\mathbb Z$ is defined by a formula $\phi(x)$. Then let $\mathcal M \succ (\mathbb Z, 0, S, <)$ be a proper elementary extension and $D$ be the set defined by $\phi(x)$ in $\mathcal M$. In $\mathbb Z$, odd numbers and even numbers appears in turn. A similar property holds in $\mathcal M$, thus (1): $a\in D \Rightarrow S(a) \not \in D$. Let $\sigma : \mathcal M \rightarrow \mathcal M$ be a map defined by $a \mapsto a\ (a \in \mathbb Z)$ and $a \mapsto S(a)\ (a \not \in \mathbb Z)$. Then $\sigma$ is an isomorphism on $\mathcal M$. By (1), $\sigma$ does not preserve $D$. Thus $2\mathbb Z$ is not definable in $\mathbb Z$.

This uses the following proposition:

- Can equinumerosity by defined in monadic second-order logic?
- Finding Expressively Adequate truth Functions
- How can I get the negation of $\exists!$ (unique existential quantification)?
- Proof by contradiction vs Prove the contrapositive
- How does predicate logic handle contradictory statements about something that does not exist?
- Understanding the definition of completeness of formal theorys(and Godel's famous theorem)

Suppose $A\subset |\mathcal M|^n$ is definable. Then for every isomorphism $\sigma$ on $\mathcal M$, $\sigma(A) = A $.

What I don’t understand is the argument that $\sigma$ does not preserve $D$. I suppose this argument assumes $D\setminus\mathbb Z\neq\emptyset$. This intuitively holds, because the language is not expressive enough to exclude non-integers from $D$ (I’m thinking of $\mathbb R$ as $\mathcal M$). But I am unable to show this.

How can you prove that $D\setminus\mathbb Z\neq\emptyset$?

- How to find the logical formula for a given truth table?
- Proving a property of a Logic Formal Language
- Show that $ \{\lnot,\leftrightarrow\} $ is not functional complete
- How can some statements be consistent with intuitionistic logic but not classical logic, when intuitionistic logic proves not not LEM?
- Some hints for “If a prime $p = n^2+5$, then $p\equiv 1\mod 10$ or $p\equiv 9\mod 10$”
- Recommendation on a rigorous and deep introductory logic textbook
- Is the formal semantics of first-order logic ambiguous?
- First-order logic without equality
- How is second-order ZFC defined?
- Entailment relations that are not partial orders

Note that if $\phi (x)$ defines $2 \mathbb{Z}$ in $\mathcal{Z} = ( \mathbb{Z} , 0 , S , < )$ then as $\mathcal{Z} \models ( \forall x ) ( \phi (x) \vee \phi ( S(x) )$, every elementary extension of $\mathcal{Z}$ must also satisfy this sentence. From this it follows that $D \setminus \mathbb{Z}$ is nonempty.

**Added for clarity:**

If $\phi (x)$ defines $2 \mathbb{Z}$ in the model $\mathcal{Z}$, then it must be that $$\mathcal{Z} \models ( \forall x ) ( \phi (x) \leftrightarrow \neg \phi ( S(x) )$$ (and this is probably much better than my original). As an elementary extension, $\mathcal{M}$ must also satisfy this sentence. From here we may conclude that there is an $a \in M \setminus \mathbb{Z}$ (where $M$ denotes the universe of $\mathcal{M}$) such that $\mathcal{M} \models \phi ( a )$. (Taking any $a \in M \setminus \mathbb{Z}$ either it or $S^{\mathcal{M}} (a)$ will be as required.)

Using the automorphism $\sigma$ of $\mathcal{M}$ given in the question, and taking any $a \in M \setminus \mathbb{Z}$ such that $\mathcal{M} \models \phi (a)$, we then have the following:

- As $\mathcal{M} \models ( \forall x ) ( \phi (x) \leftrightarrow \neg \phi ( S(x) )$ it follows that $\mathcal{M} \models \neg \phi ( S(a) )$.
- As $\sigma$ is an automorphism it follows that $\mathcal{M} \models \phi ( \sigma(a) )$, but as $\sigma (a) = \mathcal{S}^\mathcal{M}$ we get $\mathcal{M} \models \phi ( S(a) )$.

These conclusions are clearly contradictory!

- Union of Cartesian products: $X \times (Y \cup Z)= (X \times Y) \cup(X\times Z)$
- Finite ring of sets
- Principal period of $\sin\frac{3x}{4}+\cos\frac{2x}{5}$
- The meaning of notation $\subset\subset$ in complex analysis
- Modulo operations over Gaussian Integers
- How many values does the expression $1 \pm 2 \pm 3 \pm \cdots \pm n$ take?
- Prove that any shape 1 unit area can be placed on a tiled surface
- Example of non-flat modules
- positive linear functionals are bounded in $C^*$-algebras
- Proving $rank(\wp(x)) = rank(x)^+$
- Free cocompact action of discrete group gives a covering map
- Solving $(f(x))^2 = f(\sqrt{2}x)$
- Solving a recurrence of polynomials
- Is there a simple group of any (infinite) size?
- Centralizer/Normalizer of abelian subgroup of a finite simple group