Applying compactness theorem in First Order Logic

Hey!

Sorry for posting again so quickly, but I also have an issue for a second concept. This one is regarding applying the compactness theorem in first order logic, the framework is 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 a_{1}, a_{2},. . . , a_{n} such that the following 3 conditions are met:

- a_{1}, a_{2},. . . , a_{n} are distinct,

- V = {a_{1},...,a_{n}}

- ⟨a_{1},a_{2}⟩ ∈ E, ⟨a_{2},a_{3}⟩ ∈ E,...⟨a_{n−1},a_{n}⟩ ∈ E, ⟨a_{n},a_{1}⟩ ∈ 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!

Re: Applying compactness theorem in First Order Logic

The formula σ_{n} says the following.

(1) There exist n vertices.

(2) They are distinct.

(3) Every vertex is one of those n.

(4) The n vertices are connected in a cycle.

Compactness theorem is not used in this particular problem. It is probably used to show that there is no single formula σ saying that the graph is Hamiltonian that works for graphs of all sizes.