Geodesic
Pseudofinite Homogeneity, Isolation, and Reducibility
Matematičeskie zametki, Tome 81 (2007) no. 4, pp. 515-527.

Voir la notice de l'article provenant de la source Math-Net.Ru

It has been proved (by S. M. Dudakov and M. A. Taitslin) that the reducibility of some models of a theory implies the second pseudofinite homogeneity property for this theory. We prove the converse, namely, that any theory with the first or the second pseudofinite homogeneity property has a reducible model and, therefore, possesses the second isolation property. This also proves the equivalence of the second isolation property and the second pseudofinite homogeneity property, in contrast to the first pseudofinite homogeneity property, which is more general than the first isolation property (this was established by O. V. Belegradek, A. P. Stolboushin, and M. A. Taitslin).
Keywords: reducible model, first and second pseudofinite homogeneity properties, second isolation property, query language, order collapse property, relational database. 
@article{MZM_2007_81_4_a4,
     author = {S. M. Dudakov},
     title = {Pseudofinite {Homogeneity,} {Isolation,} and {Reducibility}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {515--527},
     publisher = {mathdoc},
     volume = {81},
     number = {4},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2007_81_4_a4/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - Pseudofinite Homogeneity, Isolation, and Reducibility
JO  - Matematičeskie zametki
PY  - 2007
SP  - 515
EP  - 527
VL  - 81
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2007_81_4_a4/
LA  - ru
ID  - MZM_2007_81_4_a4
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T Pseudofinite Homogeneity, Isolation, and Reducibility
%J Matematičeskie zametki
%D 2007
%P 515-527
%V 81
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2007_81_4_a4/
%G ru
%F MZM_2007_81_4_a4
S. M. Dudakov. Pseudofinite Homogeneity, Isolation, and Reducibility. Matematičeskie zametki, Tome 81 (2007) no. 4, pp. 515-527. http://geodesic.mathdoc.fr/item/MZM_2007_81_4_a4/

[1] E. F. Codd, “A relational model for large shared data banks”, Comm. of ACM, 13 (1970), 377–387 | DOI | Zbl

[2] E. F. Codd, “Relational completeness of database sublanguages”, Database Systems, ed. R. Rustin, Prentice-Hall, 1972, 33–64

[3] A. V. Aho, J. D. Ullman, “Universality of data retrieval languages”, Proc. of 6th Symp. on Principles of Programming Languages (San Antonio, Tex., 1979), 1979, 110–120 | MR | Zbl

[4] A. Chandra, D. Harel, “Computable queries for relational databases”, J. Compuer System Sci., 21:2 (1980), 156–178 | DOI | MR | Zbl

[5] P. Kanellakis, G. Kuper, P. Revesz, “Constraint query languages”, J. Compuer System Sci., 51:1 (1995), 26–52 | DOI | MR

[6] O. V. Belegradek, A. P. Stolboushkin, M. A. Taitslin, “Extended order-generic queries”, Ann. Pure Appl. Logic, 97:1–3 (1999), 85–125 | DOI | MR | Zbl

[7] S. M. Dudakov, “Translyatsionnyi rezultat dlya rasshirenii arifmetiki Presburgera odnomestnoi funktsiei, soglasovannoi so slozheniem”, Matem. zametki, 76:3 (2004), 362–371 | MR | Zbl

[8] J. Baldwin, M. Benedikt, “Stability theory, permutations of indiscernibles, and embedded finite models”, Trans. Amer. Math. Soc., 352:11 (2000), 4937–4969 | DOI | MR | Zbl

[9] M. A. Taitslin, “A general condition for collapse results”, Ann. Pure Appl. Logic, 113:1–3 (2001), 323–330 | DOI | MR | Zbl

[10] S. M. Dudakov, “Translyatsionnaya teorema dlya teorii $I$-svodimykh algebraicheskikh sistem”, Izv. RAN. Ser. matem., 68:5 (2004), 67–90 | MR | Zbl

[11] G. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, M., 1997 | MR | Zbl

[12] M. A. Taitslin, “Ogranichennye psevdokonechnaya odnorodnost i izolirovannost”, Vestn. Tverskogo gos. un-ta, ser. Prikladnaya matem., 2:1 (2003), 5–15

[13] S. M. Dudakov, M. A. Taitslin, “Translyatsionnye rezultaty dlya yazykov zaprosov v teorii baz dannykh”, UMN, 61:2(368) (2006), 3–66 | MR | Zbl