A Complete Bounded Theory with Unbounded Types

Abstract: Say a first-order theory is bounded if for some finite $n$, it is $\forall_n$-axiomatizable; Similarly for a type. This notion is closely related to descriptive complexity and provides a measure of complexity for theories and types. In an attempt to connect the complexity of theories and that of their types, we show the existence of a bounded (in fact universal) theory which has an unbounded type. The construction uses trees, and one key step of the proof is showing the pseudofiniteness of finite-height trees.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic