DIMACS TR: 97-03
Trees and Ehrenfeucht-Fraisse games
Authors: Stevo Todorcevic, Jouko Vaananen
ABSTRACT
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