Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Graphs and first-order logic.

  1. #1
    Newbie
    Joined
    Oct 2007
    From
    Moldova
    Posts
    15

    Graphs and first-order logic.

    We define the distance d(a,\,b) between two vertices a and b of a graph as the least number of edges in a path from a to b. If no such path exists, then d(a,\,b)=\infty. ... \nu_G is the vocabulary of graphs.
    ...
    (b) Does there exist a \nu_G-formula \delta_{\infty}(a,\,b) so that, for any graph G, G\models\delta_{\infty}(a,\,b) if and only if d(a,\,b)=\infty? Explain your answer.
    I said no, because if there were such a formula, then there would be a formula saying that a graph is connected. What is your opinion?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Graphs and first-order logic.

    I agree. And connectedness is not expressible in first-order logic by compactness argument.
    Thanks from andrei
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complexity of SAT in First-order logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 6th 2011, 09:01 AM
  2. First order logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2011, 08:41 AM
  3. First order logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 10th 2011, 07:10 AM
  4. First order Logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 16th 2011, 04:41 AM
  5. First order Logic!
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: January 3rd 2011, 10:55 AM

Search Tags


/mathhelpforum @mathhelpforum