# Section 2.6: Problem 1 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Show that the following sentences are finitely valid (i.e., that they are true in every finite structure):

(a)

(b)

*Suggestion*: Show that any model of the negation must be infinite.

As suggested, we show that any model of the negation of each sentence must be infinite. We also use the Prenex Normal Form Theorem to transform prenex formulas to a non-prenex form.

(a) Before considering the negation of the formula, we could try to understand its meaning. This says that there is a point
such that either relation
is not “transitive at
” (meaning that there are
such that
but not
) or
or
. This holds in any finite model, because if
is not transitive, then there is a point
such that
is not transitive at
, and if
does not hold for some
, then
for some
, otherwise
is transitive at all points (or, just transitive), and for all points
, so, we can construct a sequence
,
, for
, such that
holds for all
, in particular, by transitivity,
for all
, and, since the universe is finite, there has to be a loop.

Formally, using the negation of the formula, we show that it is true in (some) infinite models only:

If
is a model of this sentence, then we can use the following argument. First,
(A2, MP), and, hence,
(A1, A2, MP), and
. Then,
(A6),
(G),
(A2, MP),
(MP),
(C),
(D), therefore,
. At the same time, by G, A2 and MP,
, so that, by A6, G, A2 and MP,
for all
. Then, arguing as above, by A6, G, A2, MP, C and D,
for all
, hence, for any
,
,
, implying that the underlying structure must be infinite.

(b) Again, before considering the negation of the formula, we try to understand its meaning. In the finite case we can think of it as an edge relation on a graph,
iff there is an edge from
to
. Let us call
the set of vertexes connected with
by incoming edges. So, the truth of the statement follows from the fact that there is a vertex
with the maximum number of incoming edges (which is true in the finite case): for any other vertex
either there is a vertex
such that there is an edge from
to
but no edge from
to
(corresponding to
,
), or, otherwise,
(both are finite), but since
is a vertex with the maximum number of incoming edges,
, meaning, in particular, that if
(
) then
(
).

Formally, using the negation of the formula, we show that it is true in (some) infinite models only:

If
is a model of this sentence, then we can use the following argument. Select any
, and fix
.
iff for all
,
. In particular,
. Now, this is true iff for some
,
iff for some
and for all
,
and
and
. Let
be the set
. Then, if
, then
, and, according to the first of the three expressions,
, i.e.
. And
. At the same time, according to the second and third expressions,
while
. Overall, we have
. Since
was chosen arbitrary, we can find
for
the same way we found
for
such that
, and so on. In particular, for any
, we have
, and
. This shows that the underlying structure must be infinite.