We present a new proof technique for collapse results for first-order queries on databases which are embedded in N or R{sub}(≥0). Our proofs are by means of an explicitly constructed winning strategy for Duplicator in an Ehrenfeucht-Fra?ssé game, and can deal with certain infinite databases where previous, highly involved methods fail. Our main result is that first-order logic has the natural-generic collapse over 〈N,≤,+〉 for arbitrary (i.e., possibly infinite) databases. Furthermore, a first application of this result shows the natural-generic collapse of first-order logic over 〈R{sub}(≥0),≤,+〉 for a certain kind of databases over R{sub}(≥0) which consist of a possibly infinite number of regions.
展开▼