(Updated) I am trying to solve the following problem, any help would be much appreciated!
Let Γ be the theory in the language containing just the binary relational symbol ≤, and Γ says ``the relation ≤ is a linear ordering, and every element has an immediate successor in ≤’’.
(a) Write Γ down precisely in the language of first order logic.
(b) Show that there is a sentence in the language, which cannot be decided from the axioms of Γ.
This is what I have so far:
a) Γ = { ∀x ∀y ∀z ((x ≤ y ∧ y ≤ z) → x ≤ z), ∀x (x ≤ x), ∀x ∀y ((x ≤ y ∧ y ≤ x) → x = y), ∀x ∀y (x ≤ y ∨ y ≤ x), ∀x ∃y ∀z (x ≤ z → (y ≤ z ∧ x ≤ y)}
I think this is correct.
b) I am a little confused on (b). What I am thinking is, I just need to show there exists a sentence which is undecidable. So, based on the hint from Max(Thank you.), I came up with the following sentence:
∀x ∃y ∀z (z ≤ x → (z ≤ y ∧ y ≤ x) .
This is undecidable, because there is no sentence in Γ which proves this sentence.
I've already answered in the comments about how to express that every element has an immediate successor and I think you understood that so I won't linger on it here (unless you want me to)
For the second part, the idea is to use what some call the correction theorem, which is just a theorem that says that the way we do proofs is fine. It asserts "For any language $L$, theory $T$ and formula $\phi$, if $T\vdash \phi$, then any model $M$ of $T$ has $M\models \phi$". Intuitively it says that if you can prove something, then it's "always true".
Here since we want to show that $\Gamma$ does not prove a certain formula we want to use the contrapositive : if there is some model $M$ of $\Gamma$ such that $\neg(M\models \phi)$, then there is no proof of $\phi$ in $\Gamma$. Moreover if we also find a model $N$ of $\Gamma$ such that $N\models \phi$, we will have that there is no proof of $\neg \phi$ in $\Gamma$.
Thus what we want to do is find a formula $\phi$, and models of $\Gamma$ $M,N$ such that $M\models \phi$, and $N\models \neg \phi$. A model of $\Gamma$ is simply a totally ordered set in which any element has an immediate successor. What are the simplest ones ? I guess they are $\mathbb{N}$ and $\mathbb{Z}$ with the usual ordering. They are obviously not isomorphic (as ordered sets) since $\mathbb{N}$ is well-ordered and $\mathbb{Z}$ isn't.
This fact makes us think (unrightfully though because elementary equivalence and isomorphism are different concepts) that there ought to be some formula that holds in one and not the other.
Such a formula would be "every element has an immediate predecessor" (I'll let you write it down properly, it's a good exercise - I'll call it $\phi$), which holds in $\mathbb{Z}$ but not in $\mathbb{N}$ ($0$ doesn't have any predecessor).
So we have found a formula $\phi$ such that $\mathbb{Z}\models \phi$, $\mathbb{N}\models \neg\phi$. Therefore, from what I've shown earlier, there is no proof in $\Gamma$ of $\phi$, or $\neg\phi$: $\phi$ is undecidable in $\Gamma$