Results 1 to 2 of 2

Math Help - Applying compactness theorem in First Order Logic

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    Moscow
    Posts
    3

    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!
    Last edited by batchej; March 19th 2013 at 04:18 PM. Reason: More detail
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Corollary of compactness theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 7th 2011, 08:57 AM
  2. [SOLVED] Applying Mean Value Theorem
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 16th 2011, 02:10 AM
  3. Compactness Theorem and partial orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2011, 12:35 PM
  4. compactness theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 27th 2010, 09:46 AM
  5. Applying Cauchys theorem
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: December 3rd 2009, 07:29 AM

Search Tags


/mathhelpforum @mathhelpforum