DIMACS TR: 97-03

Trees and Ehrenfeucht-Fraisse games

Authors: Stevo Todorcevic, Jouko Vaananen


We study trees T of height at most omega-1 with no uncountable branches, and their applications in the study of pairs (A,B) of non-isomorphic structures over a fixed vocabulary. There is a natural quasi-ordering of such trees in terms of the existence of a strictly increasing mapping from one tree to another. We investigate in depth the structure of this quasi-ordering and relate its properties to properties of pairs (A,B) of structures. Many new constructions of pairs of highly equivalent non-isomorphic structures are given.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-03.ps.gz
DIMACS Home Page