Abstracts.
Subspaces of
Computable Vector Spaces. With R. G. Downey, D. R. Hirschfeldt,
A. M. Kach, S. Lempp, and J. R. Mileti. Submittted for publication.
Abstract: We show that the
existence of a proper subspace of a vector space of dimension greater
than one (over an infinite field) is equivalent to~\WKL\ over~\RCA, and
that the existence of a finite-dimensional proper subspace of such a
vector space is equivalent to~\ACA\ over~\RCA.
Countably complementable linear
orderings. Submittted for publication.
Abstract: We say that a
countable linear ordering $\L$ is countably complementable if there
exists a linear ordering $\Lba$, possibly uncountable, such that for
any countable linear ordering $\B$, $\L$ does not embed into $\B$ if
and only if $\B$ embeds into $\Lba$. We characterize the linear
orderings which are countably complementable. We also show that this
property is equivalent to the countable version of the finitely
faithful extension property introduced by Hagendorf.
Using similar methods and introducing the notion of weakly
countably complementable linear orderings, we answer a question posed
by Rosenstein and prove the countable case of a conjecture of
Hagendorf, namely, that every countable linear ordering satisfies the
countable version of the totally faithful extension property.
Computable linearizations of
well-partial-orderings. Submittted for publication.
Abstract. We analyze results
on well-partial-orderings from the viewpoint of computability theory,
and we answer two questions posed by Diana Schmidt. We obtain the
following results. De Jongh and Parikh showed that every
well-partial-order has a linearization of maximal order type. We show
that such a linearization can be found computably. We also show that
the process of finding such a linearization is not computably uniform,
not even hyperarithmetically. A similar behavior occurs with minimal
linearizations. Schimdt also asked whether there was any relationship
between the rank (also known as hight) and the maximal order type of a
well-partial-ordering. We characterize the pairs of ordinals which can
be obtained as rank and maximal order type of a well-partial-ordering.
Ranked
Structures and Arithmetic Transfinite Recursion. With
Noam Greenberg. In preparation.
Abstract. ATR0
is the natural subsystem of second order arithmetic in which one can
develop a decent theory of ordinals ([Simpson 1999]). We investigate
classes of structures which are in a sense the “well-founded part” of a
larger, simpler class, for example, superatomic Boolean algebras
(within the class of all Boolean algebras). The other classes we study
are: well-founded trees, reduced Abelian p-groups, and countable,
compact topological spaces. Using computable reductions between these
classes, we show that Arithmetic Transfinite Recursion is the natural
system for working with them: natural statements (such as comparability
of structures in the class) are equivalent to ATR0.
The reductions themselves are also objects of interest.
Indecomposable
linear orderings and
Theories of Hyperarithmetic
Analysis.
Submitted for publication.
Abstract. A statement of
hyperarithmetic analysis is a sentence of second order arithmetic S
such that for every Y ⊆ ω,
the minimum ω-model containing Y
of RCA0+S is HYP(Y), the ω-model
consisting of the sets hyperarithmetic in Y . We provide an example of a
mathematical theorem which is a statement of hyperarithmetic analysis.
This statement, that we call INDEC, is due to Jullien [1969]. To the
author’s knowledge, no other already published, purely mathematical
statement has been found with this property until now. We also prove
that, over RCA0, INDEC is implied by
∆-1-1-CA0 and implies ACA0,
but of course, neither ACA0, nor ACA0+
imply it. We introduce five other statements of hyperarithmetic
analysis and study the relations among them. Four of them are related
to finitely-terminating games. The fifth one, related to iterations of
the Turing jump, is strictly weaker than all the other statements that
we study in this paper, as we prove using Steel’s method of forcing
with tagged trees.
Equimorphism
Invariants for Scattered Linear Orderings. To appear in Fundamenta Mathmaticae.
Abstract. Two linear
ordering are equimorphic if they can be embedded in each other. We
define invariants for scattered linear orderings which classify them up
to equimorphism. Essentially, these invariants are finite sequences of
finite trees with ordinal labels. Also, for each ordinal α, we
explicitly describe the finite set of minimal scattered equimorphism
types of Hausdorff rank α. We compute the invariants of each of these
minimal types.
A
minimal pair of K-degrees. With Barbara F. Csima. To appear in the Proceedings of the AMS.
Abstract. We construct a minimal
pair of K-degrees. We do this
by showing the
existence of an unbounded nondecreasing function f which forces K-triviality
in the sense that γ ∈ 2^ω is K-trivial
if and only if for all n, K(γ up to n) ≤ K(n)
+ f(n) + O(1).
Boolean
Algebras, Tarski
Invariants, and Index Sets.
With Barbara F.
Csima and Richard A.
Shore. To appear in the Notre Dame
Journal of Formal Logic.
Abstract. Tarski
defined a way of assigning to each boolean algebra, B, an invariant inv(B)∈In, where In is a set of triples from
N,
such that two boolean algebras have the same invariant if and only if
they
are elementarily equivalent. Moreover, given the invariant of a boolean
algebra, there is a computable procedure that decides its elementary
theory.
If we restrict our attention to dense Boolean algebras, these
invariants
determine the algebra up to isomorphism. In this paper we analyze the
complexity
of the question ``Does B have
invariant x?''. For each x∈ In
we define a complexity class Gamma_x,
that could be either Sigma_n,
Pi_n, Sigma_n & Pi_n, or Pi_ω+1
depending on x, and prove
that the set of indices for computable boolean algebras
with invariant x is complete
for the class Gamma_x. Analogs
of
many
of these results for computably enumerable Boolean algebras were proven
in Selivanov [1990] and [1991]. According to Selivanov [2003] similar
methods
can be used to obtain the results for computable ones. Our methods are
quite different and give new results as well. As the algebras we
construct
to witness hardness are all dense, we establish new similar results for
the complexity of various isomorphism problems for dense Boolean
algebras.
Equivalence
between Fraïssé's
conjecture and Jullien's theorem.
To appear in the Annals
of Pure and Applied Logic.
Abstract.
We
say that a linear ordering L
is extendible if
every partial ordering
that does not embed L can be
extended to a linear ordering which does
not embed L either. Jullien's
theorem is a complete classification of
the countable extendible linear orderings. Fraïssé's
conjecture,
which is actually a theorem, is the statement that says that the class
of countable linear ordering is well quasiordered under embeddablity.
In
this paper we study the strength of these two theorems from the
viewpoint
of Reverse Mathematics. As a result of our analysis we get that they
are
equivalent over the basic system of RCA0
+ Sigma-1-1-induction.
We also prove that Fraïssé's
conjecture is equivalent, over RCA0, to
two other interesting statements. One that says that the class
of well founded labeled tree, with labels from {+,-}, with very a
natural
order relation, is well quasiordered.
The other statement says that every linear ordering which does not
contain a copy of the rationals is equimorphic to a finite sum of
indecomposable
linear orderings.
While studying the proof theoretic strength of Jullien's
thorem, we
prove the extendibility of many linear orderings, including $\omega^2$
and $\eta$, using just ATR0
+ Sigma-1-1-induction.
Moreover,
for all these linear orderings, L, we
prove that any partial ordering, P,
which does not embed L has a
linearization, hyperarithmetic (or
equivalently Delta-1-1) in P
join L, which does not embed L.
There
is no order in the Generalized High/Low HIerarchy. To appear in the
Archive of Mathematical Logic.
Abstract. We
prove that the existential theory of the Turing degrees, in the
language
with Turing reduction and relations for the classes in the generalized
high/low hierarchy, is decidable. This answers a question that Lerman
asked
in [1985].
Up
to equimorphism, hyperarithmetic is recursive. Journal
of
Symbolic Logic, 70 (2), 2005, 360-378
Abstract. Two linear orderings are equimorphic if
each can be embedded into the other. We prove that every
hyperarithmetic
linear ordering is equimorphic to a recursive one. This extends a
result
of Spector [1955] that says that every hypearithmetic well-ordering is
isomorphic to a computable one.
On the way to our main result we prove
that a
linear ordering has Hausdorff rank less than omega-1-CK if and only if
it is equimorphic to a recursive one. As a corollary of our proof we
prove
that given a recursive ordinal α, the partial ordering of
equimorphism
types of linear orderings of Hausdorff rank at most α ordered by
embeddablity, is recursively presentable.
Teoria
de Conjuntos Segun Von Newman(On Set
theory in the sense of Von Newman).
Publicaciones
Matemáticas del Uruguay,
10, 2005,
91-110.
(Extracted
from my undergrad monograph.)
Abstract. Probamos
que, dentro de la teoría de von Neumann (VN), hay un
modelo
natural de la teoría de Zermelo-Fraenkel (ZF) sin el
axioma
de fundación y vemos que ni el axioma de fundación ni su
negación son teoremas en ese modelo.Por último obtenemos
que la consistencia de VN está implicada por la
consistencia
de ZF+ AC + existe un cardinal inaccesible.
Generalized
High degrees have the complementation property. With Noam Greenberg
and Richard Shore. Journal
of Symbolic Logic, 69(4), 2004, 1200-1220.
Abstract. We
show that if
d is in GH_1 then D(≤ d) has the complementation
property, i.e. that for all a<d there is some b<d
such that a \meet b = 0 and a \join b
= d.
Embedding
and coding below a 1-generic degree.With Noam Greenberg. Notre
Dame Journal of Formal Logic, 44 (4), 2003, 200-216.
Abstract. We
prove that the theory of $\D(≤ \bg)$ is computably equivalent to
first
order true arithmetic for 1-generic degree $\bg$.
For this we show that 1-genericity
is enough
to find the parameters needed to code a set of degrees using the Slaman
and Woodin forcing. We also prove that any recursive lattice can be
embedded
below a 1-generic degree preserving top and bottom.
Embedding
Jump Upper Semilattices into the Turing Degrees. Journal
of Symbolic Logic, 68 (3), 2003, 989-1014.
Abstract.
We prove
that every countable jump upper semilattice can be embedded in D.
Where
a jump upper semilattice (jusl) is an upper semilattice endowed with a
strictly increasing and monotone unary operator that we call jump, and D is the jusl of Turing degrees. As a corollary we get
that
the
existential theory of D(≤T,\vee,') is
decidable. We also prove
that
this result is not true about jusls with 0, by proving that not every
quantifier
free 1-type of jusl with 0 is realized in D. On the other hand, we
show
that every quantifier free 1-type of jump partial ordering (jpo) with 0
is realized in D. Moreover, we show that if every quantifier free
type, p(x_1,...,x_n), of jpo
with 0, which contains the formula x_1≤
0^(m) &...&
x_n≤ 0^(m) for some m,
is realized in D, then every every
quantifier
free type of jpo with 0 is realized in
D.
We also study the question of whether
every jusl with the c.p.p. and size κ ≤ 2^ω is
embeddable in D. We show that for κ = 2^ω the answer is no, and that
for κ = ω_1 it is independent of ZFC. (It is true if MA(κ) holds.)