ENUMERATION DEGREES · Questions of decidability and definability in the Enumeration degrees
FP6 — Marie Curie Actions (Human Resources and Mobility)
- Duration
- 2006-11-02 → 2008-11-01
- EU contribution
- €145,616
- Participants
- 1
- Scheme
- IIF
Lines connect the coordinator with its partners.
Results in brief
Final Activity Report Summary - ENUMERATION DEGREES (Questions of decidability and definability in the enumeration degrees)
During the course of the 'Questions of decidability and definability in the enumeration degrees' (ENUMERATION DEGREES) project, material for several papers has been produced. Four of these papers have been published, two have been accepted for publication, two are submitted for publication and there are several in various stages of write up. The work initially focused on showing that the Pi_2 theory fo the Sigma_2 enumeration degrees is decidable. Work in this area led the fellow to partially answer an open question by showing that the first order theory of the Delta_2 enumeration degrees is as complicated as that of true arithmetic. There has been significant progress towards showing the same result of the Sigma_2 enumeration degrees. The fellow and Andrea Sorbi were able to answer an open question of Downey by showing that the nonsplitting Sigma_2 enumeration degrees are downwards dense. They did this by introducing a new form of Sigma_2 permitting which allows them to build degrees with specified properties below arbitrary degrees. The fellow was also able answer an open question of Watson by showing that the s-degrees (s-reducibility is a strong form on enumeration reducibility) contained with any nontrivial Sigma_2 enumeration degree contains an infinite independent antichain and is downwards dense. He also showed that there are two Sigma_2 sets A and B such that A is enumeration reducible to B, but A is not s-reducible to any set which is enumeration equivalent to B. This gives us a better understanding of the structure of the s-degrees contained within a single enumeration degree. In work with Maria Affatato and Andrea Sorbi, the fellow was able to show two additional results. For the first result, they showed that the first order theory of the Sigma_2 s-degrees is undecidable. In the second result they strengthened a branching result of Sorbi and Nies by showing that for every incomplete enumeration degree, there is a single pair of degrees which forms a branching pair for every s-degree below the given degree. In work with Andrew Lewis, the fellow was able to show several new results dealing with Pi^0_1-classes. In particular they examined the degree spectra of a Pi^0_1-classes under inclusion and showed that this structure is a countable lattice, has minimal covers, etc. In more applied project with Jonathan Baer and Stephen Anderson, the fellow was able to use his analytic and computing skills to study and analyse soil desiccation cracking patterns in Missouri clay loam topsoil. In other work with Andrew Lewis and Andrea Sorbi, the fellow is studying Strong Minimal covers in both the Pi^0_2 enumeration degree and Sigma_2 and Pi_2 s-degrees. They have shown that in each of these structures strong minimal covers exist, strengthening and expanding previous work by Slaman and Calhoun. He is also engaged in research with Wu and Yang in looking at elementary differences between the Sigma_2 and Delta_2 s-degrees. Their current project is to construct a minimal pair of s-degrees contained within the same enumeration degree. Finally, the fellow is working with Soskova examining high-nonsplitting degrees.
Data: CORDIS, © European Union
Project objective
We propose to ascertain if there is an effective procedure that determines the validity of an arbitrary first order $\forall\exists$-sentence in the upper semi-lattice of the $\Sigma^0_2$ enumeration degrees. It is known that the $\forall$-fragment of the first order theory of the $\Sigma^0_2$ enumeration degrees is decidable. Slaman and Woodin (1996) proved that first order theory of the $\Sigma^0_2$ enumeration degrees is un-decidable and more recently, Kent (unpublished) proved that the $\forall\exists\forall$-fragment of this theory is un-decidable.This left open the question of whether the $\forall\exists$-fragment is decidable. Answering this question is equivalent to finding an effective procedure that determines, when we are given an arbitrary finite lattice $P$ and finite lattices $Q_0$, ..., $Q_n$ which extend $P$, if there is an embedding of $P$ into the $\Sigma^0_2$ enumeration degrees which cannot be extended to an embedding of any of the $Q_i$. Lempp, Slaman and Sorbi (to appear) have shown that the sub-problem where $n = 0$ is decidable.In order to fully answer the question, we propose to answer the above problem in the following three sub-cases:Case 1: Let $P$ be an arbitrary finite anti-chain and each $Q_i$ a one point extension of $P$.Case 2: Let $P$ be an arbitrary finite lattice and each $Q_i$ a one point extension of $P$.Case 3: Let $P$ be an arbitrary finite anti-chain and each $Q_i$ an arbitrary extension of $P$.To answer the first case, more research needs to be performed on the properties of Ahmad pairs. In particular, we propose to determine the maximal size of an anti-chain where each two distinct elements form an Ahmad pair. Also, we propose to determine if the join of an Ahmad pair is non-trivially bounded from above. Cases 2 and 3 are extensions of case 1. It is believed that answering these questions will lead to an affirmative solution of the question of whether the $\forall\exists$-fragment is decidable.
Original text from CORDIS.
Participants
- UNIVERSITÀ DEGLI STUDI DI SIENA · SIENACoordinatorItaly
Links
Data: CORDIS, © European Union