Skip to main content

Revisiting two-variable logic

Tony Tan ( Department of Computer Science and Information Engineering, College of Electrical Engineering and Computer Science, National Taiwan University )

In this talk we will present another proof for the well-known "small model property" of two-variable logic.
As far as we know, existing proofs of this property rely heavily on model theoretic concepts.
In contrast, we will present a proof that is essentially a very simple counting argument.
Matching lower bounds will also be considered.

Share this: