Premium
Simple monadic theories and partition width
Author(s) -
Blumensath Achim
Publication year - 2011
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201010019
Subject(s) - partition (number theory) , mathematics , pairing , bounded function , combinatorics , simple (philosophy) , tree (set theory) , discrete mathematics , mathematical analysis , physics , philosophy , superconductivity , epistemology , quantum mechanics
We study tree‐like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the partition width of models is bounded, or the theory admits definable pairing functions. Our proof rests on structure results concerning indiscernible sequences and finitely satisfiable types for theories without definable pairing functions. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim