Applying the compactness theorem

Question

Using a Hilbert system:

L is a FOL (First order language) with R, where R is a single binary predicate symbol. Suppse A = ⟨V,E⟩ is a structure for this language domain V = |A|. Suppose also that E = RA, is the interpretation of the symbol R in A.

So ⟨V, E⟩ can be viewed as a directed graph; i.e., a (possibly infinite) set of vertices in V connected by edges in E.

Note that A Hamiltonian cycle in a graph is a finite sequence of vertices a1, a2,. . . , an such that the following 3 conditions are met:

• a1, a2,. . . , an are distinct,
• V = {a1,...,an}
• ⟨a1,a2⟩ ∈ E, ⟨a2,a3⟩ ∈ E,...⟨an−1,an⟩ ∈ E, ⟨an,a1⟩ ∈ E.

Also note that if ⟨V,E⟩ has Hamiltonian cycle then V is finite.

How do you describe a sentence σn in the language L that has the property ⟨V,E⟩ |= σn if and only if ⟨V,E⟩ has a Hamiltonian cycle with n vertices. The question requires to give σn explicitly in the case that n = 4.

Could you provide a hint or suggestion as to how I can begin to go about this!

Many thanks!

Answer 1

For a given $n$, can you express "$\langle V, E\rangle$ has a Hamiltonian cycle with exactly $n$ vertices" as a first order sentence? Once you've managed to do this, call this sentence $H_n$.

Now suppose we had such a $\sigma$. Is the theory $\{\sigma\}\cup\{\lnot H_n\,|\,n\in\mathbb{N}\}$ consistent?

---

Edit: The question has been edited significantly since I wrote the answer above. It used to ask why a sentence expressing "there is a Hamiltonian cycle of some size" does not exist (the compactness theorem is relevant here), and now it asks why a sentence expressing "there is a Hamiltonian cycles of size $n$" exists (the compactness theorem is irrelevant here). Are you sure you're asking what you mean to ask?

Answer 2

Let $\varphi(x_1,x_2,x_3)$ be

$$x_1\ne x_2\land x_1\ne x_3\land x_2\ne x_3\;;$$

it says that $x_1,x_2$, and $x_3$ are distinct objects. Let $\psi(x_1,x_2,x_3)$ be

$$\forall y(y=x_1\lor y=x_2\lor y=x_3)\;;$$

it says that everything is one of these three objects. Let $\chi(x_1,x_2,x_3)$ be

$$E(x_1,x_2)\land E(x_2,x_3)\land E(x_3,x_1)\;;$$

It says that the three objects are properly ‘chained’ by $E$. Then $\sigma_3$ is

$$\exists x_1,x_2,x_3\Big(\varphi(x_1,x_2,x_3)\land\psi(x_1,x_2,x_3)\land\chi(x_1,x_2,x_3)\Big)\;.$$

Now generalize this.