Daniel Zavala-Svensson: Quantifier elimination and decidability of infinitary theories of the real line

Tid: 10:00-11:00

Sammanfattning: In this thesis, we extend logic language to infinitary languages, where we allow for con- and disjunctions of infinite sets of formulas, and quantifiers can bind infinite sets of variables. The cardinalities of those sets are bounded however, and based on those bounds we investigate the existence of quantifier elimination and decision methods for infinitary theories on the ordered field of reals. With analytic sets from descriptive set theory as a counterexample we prove the main result: The countably infinite theory of the ordered field of reals does not have quantifier elimination.

Markus Sandell: Borsuk's Conjecture and Erdos Distance Problem

Tid: 11:00-12:00

Sammanfattning: This paper concerns two conjectures that was stated in the 30's and 40's and was not solved for about 60 years. The first one is the conjecture stated by Karol Borsuk in 1933 which says that any bounded subset in Rn can be divided into n + 1 subsets of smaller diameter. This was by many mathematicians considered true until 1993, when Kahn and Kalai [18] came up with a counterexample in the 1325th dimension. In 2013 Andriy Bondarenko came up with a counterexample in the 65th dimension using the theory of
strongly regular graphs. We will explain the disproof by Bondarenko in this
paper.

The second conjecture was given in 1946 when Paul Erdos said the following: if you have n points in the plane, then these points determine at least cn/ log n distinct distances, for some constant c. Erdos himself proved that the number of distances is at least more than c*sqrt(n), which we will also show in this paper together with greater lower bounds by Moser [20] and Székely [24].

This paper is divided into three sections. The first one introduces some basic theory that will be needed for the rest of the paper, while the second and the third one is about Borsuk's conjecture and Erdos distance problem. At the end of the last section we mention even greater lower bounds and how Erdos conjecture finally was proved by Katz and Guth in 2010 [14].