# Thread: Applying compactness theorem in First Order Logic

1. ## 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 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!

2. ## 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.