Re: basic first-order model theory question.

From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 06/20/04 

Date: 20 Jun 2004 17:29:33 -0400

Yarden Katz <yarden@umd.edu> writes:

 : Hi,
 :
 : I'm having trouble understanding how one gets an infinite model from
 : a finite sentence in FOL. Consider the example:
 :
 : AxEyRxy & AxAy~(Rxy & Ryx) & AxAxAz((Rxy & Ryz) -> Rxz)
 :
 : Where we interpret R to mean strict less-than relation.

DON'T interpret R.
The whole point is it doesn't MATTER how you interpret R.
No matter WHAT R is interpreted to, it will STILL be the case
that IF it is interpreted as satisfying these axioms, the
domain of the model will be infinite.

If your domain is finite then there is an n such that you COULD
call the things in your domain {1,2,...,n} (so call them that).

Next, note that the AxAy~(Rxy & Ryx) axiom implies that R is irreflexive,
i.e., you can't ever have Rxx, because substituting x for y in
AxAy~(Rxy & Ryx) yields Ax~[ Rxx & Rxx ] which is Ax~Rxx.
So you know ~1R1, ~2R2, ~3R3, etc.
NOW you have some feel for why they suggested you interpret
R as < (so do that). < clearly satisfies the first 2 axioms,
but what happens if you invoke transitivity over a finite domain? 

-- 
 --- The history of our nation has demonstrated that separate is seldom, if ever, equal.
 --- (Feb.3,2004) Supreme Judicial Court of Massachusetts (4-3), adv.Sen.#2175