# Define a sentence that has arbitrarily large finite models [closed]

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, LeucippusJun 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.

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

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.$$
• Thank you for your response. Just one last question to be sure, what this symbol, $.$, mean in your sentence. Is it multiplication? – Angela May 30 '17 at 12:59
• 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. – Fabio Somenzi May 30 '17 at 14:19