Two of the properties satisfied by 1st order logic which make it so useful for describing mathematical structures are the Lowenheim-Skolem property and Compactness. These properties allow us to use 1st order logic to study infinite structures without concern for the underlying universe in which these structures occur. As these two properties are so important, we might ask what other abstract logics satisfy these properties? And is it possible to find a logic with more expressive power than 1st order logic which also has these properties? In one of the most significant results in the study of abstract logics, Lindstrom showed that among all abstract logics which satisfy Compactness, the Lowenheim-Skolem property, and are closed under negation and conjugation, 1st order logic is maximal. In this talk we will introduce the notions of abstract logic, compactness, and the Lowenheim-Skolem property, and then we will prove Lindstrom's Theorem.
Logic and Computation Seminar
Monday, October 2, 2006 - 4:30pm
Nate Ackerman
University of Pennsylvania