For phi a first order sentence in the signature of directed graphs,
let D_n(phi) be the set of directed graphs with node set {1,...,n}
which satify phi. Show that there are first order sentences phi and
theta in the signature of directed graphs such that lim(n->infinity)
|D_n(phi ^ theta)| / |D_n(phi)| is irrational.

Desired timeframe: 5 days

---

Request for Question Clarification by mathtalk-ga on 07 May 2005 19:22 PDT

Hi, mathdude123-ga:

If you have no further interest in a high-priced Question like this
one, you may take the precaution of "closing" (Expiring) it using the
Close button at upper right, to avoid being charged for an Answer.

If you are still interested, please refer to my Comment from a few
days ago.  The outline of a solution is there, although you may need
some details filled in.

regards, mathtalk-ga

In connection with first-order theories and formal logic, a
"signature" refers to the predicates and function symbols (including
constants) which determine the language of a formal first-order
theory.  For this and more background see:

[First-order Model Theory]
http://plato.stanford.edu/entries/modeltheory-fo/

Hence the signature of "directed graphs" would seem to mean simply
that the language has a single 2-place predicate E(x,y) whose
interpretation for a directed graph is intended to be the existance of
an edge from x to y.

Here one thinks of using the formula phi to impose some structure on
the models which satisfy it, then picking formula theta to guarantee
the irrationality of the limit required in the Question.

Hint:  The fraction of permutations of n things which are derangements
tends, as n goes to infinity, to 1/e.


regards, mathtalk-ga