I am trying to solve these problems :

(a) Define a $V_G$-sentence $\phi$ such that $\phi$ has arbitrarily large finite models, and for any model $G$, $G$ is a connected graph.

(b) Find a connected graph that does not model the sentence $\phi$ you found in (a).

Any ideas?


closed as off-topic by TheGeekGreek, Namaste, Stefan Mesken, Davide Giraudo, Leucippus Jun 1 '17 at 0:04

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – TheGeekGreek, Namaste, Stefan Mesken, Davide Giraudo, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Can you clarify what $V$ is? $\endgroup$ – Hanul Jeon May 1 '17 at 18:08
  • $\begingroup$ $V$ is the vocabulary over $G$, so actually we are looking for a $V_{G}$-sentence. $\endgroup$ – Angela May 1 '17 at 22:48

The proof that graph connectedness is not expressible in the first-order language of graphs is a classic application of compactness. The purpose of this exercise is to show that a first-order sentence in the language of graphs may only have connected models, as long as it excludes some connected graphs as well.

This observation suggests how to proceed. A sentence about graphs that has connected models of arbitrary size is one that characterizes complete (simple) graphs. If $E$ is the edge relation, then

$$ \forall x \,.\, \neg E(x,x) \wedge \forall y \,.\, x=y \vee E(x,y) \enspace.$$

Every connected but incomplete graph is not a model of this sentence.

  • $\begingroup$ Thank you for your response. Just one last question to be sure, what this symbol, $.$, mean in your sentence. Is it multiplication? $\endgroup$ – Angela May 30 '17 at 12:59
  • $\begingroup$ No, the dot, borrowed from lambda calculus, separates the quantifier (e.g., $\forall x$) from the expression that is its scope. There's plenty of different notations in use for quantification formulae. An alternative to the one above would be $(\forall x)(\neg E(x,x) \wedge (\forall y)(x=y \vee E(x,y)))$. Once you get used to the dots, it's a less cluttered notation. $\endgroup$ – Fabio Somenzi May 30 '17 at 14:19
  • $\begingroup$ Yes that is true!Thank you so much for your help! :-) $\endgroup$ – Angela May 30 '17 at 14:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.