No Arabic abstract
We prove field quantifier elimination for valued fields endowed with both an analytic structure and an automorphism that are $sigma$-Henselian. From this result we can deduce various Ax-Kochen-Ersov type results with respect to completeness and the NIP property. The main example we are interested in is the field of Witt vectors on the algebraic closure of $mathbb{F}_{p}$ endowed with its natural analytic structure and the lifting of the Frobenius. It turns out we can give a (reasonable) axiomatization of its first order theory and that this theory is NIP.
This second part of the paper strengthens the descent theory described in the first part to rational maps, arbitrary base fields, and dynamics given by correspondences. We obtain in particular a decomposition of any difference field extension into a tower of finite, field-internal and one-based difference field extensions. This is needed in order to obtain the dynamical Northcott Theorem 1.11 of Part I in sharp form.
When given a class of functions and a finite collection of sets, one might be interested whether the class in question contains any function whose domain is a subset of the union of the sets of the given collection and whose restrictions to all of them belong to this class. The collections with the formulated property are said to be strongly join permitting for the given class (the notion of join permitting collection is defined in the same way, but without the words a subset of). Three theorems concerning certain instances of the problem are proved. A necessary and sufficient condition for being strongly join permitting is given for the case when, for some $n$, the class consists of the potentially partial recursive functions of $n$ variables, and the collection consists of sets of $n$-tuples of natural numbers. The second theorem gives a sufficient condition for the case when the class consists of the continuous partial functions between two given topological spaces, and the collection consists of subsets of the first of them (the condition is also necessary under a weak assumption on the second one). The third theorem is of a similar character but, instead of continuity, it concerns computability in the spirit of the one in effective topological spaces.
We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by this relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a analytic complete equivalence relation. We then investigate the algorithmic properties of this reduction to show that every bi-embeddability spectrum of a graph is the jump spectrum of an elementary bi-embeddability spectrum of a graph.
Strongly Turing determinacy, or $mathrm{sTD}$, says that for any set $A$ of reals, if $forall xexists ygeq_T x (yin A)$, then there is a pointed set $Psubseteq A$. We prove the following consequences of Turing determinacy ($mathrm{TD}$) and $mathrm{sTD}$: (1). $mathrm{ZF+TD}$ implies weakly dependent choice ($mathrm{wDC}$). (2). $mathrm{ZF+sTD}$ implies that every set of reals is measurable and has Baire property. (3). $mathrm{ZF+sTD}$ implies that every uncountable set of reals has a perfect subset. (4). $mathrm{ZF+sTD}$ implies that for any set of reals $A$ and any $epsilon>0$, (a) there is a closed set $Fsubseteq A$ so that $mathrm{Dim_H}(F)geq mathrm{Dim_H}(A)-epsilon$. (b) there is a closed set $Fsubseteq A$ so that $mathrm{Dim_P}(F)geq mathrm{Dim_P}(A)-epsilon$.
We work with symmetric inner models of forcing extensions based on strongly compact Prikry forcing to extend some known results.