Re: deductive databases
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Wed, 25 May 2005 23:11:50 GMT
Message-ID: <WC7le.101230$Pg5.6146163_at_phobos.telenet-ops.be>
>
> The compactness theorem states that if every finite subset of a set
> K of sentences has a model, K has a model. The theorem presupposes
> infinite models. It is not the case that if every finite subset of K
> has a finite model, K has a finite model. So it's not clear to me
> what you have in mind.
Date: Wed, 25 May 2005 23:11:50 GMT
Message-ID: <WC7le.101230$Pg5.6146163_at_phobos.telenet-ops.be>
Torkel Franzen wrote:
> Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be> writes:
>
>>I don't understand how compactness applies if all models that we >>consider are infinite. Can you explain this?
>
> The compactness theorem states that if every finite subset of a set
> K of sentences has a model, K has a model. The theorem presupposes
> infinite models. It is not the case that if every finite subset of K
> has a finite model, K has a finite model. So it's not clear to me
> what you have in mind.
Ok. I had to go back and do some reading and I think I understand now. What I still not understand is how compactness shows in this case (or even in the normal case) proves that you cannot express the transitive closure. The proof for inexpressibility of TC I know works with Ehrenfeucht-Fraisse games, so I'm surprised that there is apparently a much simpeler way to prove it.
- Jan Hidders