Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 5 of 5
Full-Text Articles in Logic and Foundations
Comparing The Strength Of Diagonally Non-Recursive Functions In The Absence Of Σ02 Induction, Francois G. Dorais, Jeffry L. Hirst, Paul Shafer
Comparing The Strength Of Diagonally Non-Recursive Functions In The Absence Of Σ02 Induction, Francois G. Dorais, Jeffry L. Hirst, Paul Shafer
Dartmouth Scholarship
We prove that the statement "there is a k such that for every f there is a k-bounded diagonally non-recursive function relative to f" does not imply weak K\"onig's lemma over RCA0+BΣ02. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that every k-bounded diagonally non-recursive function computes a 2-bounded diagonally non-recursive function may fail in the absence of IΣ02.
Lowness And Π Nullsets, Rod Downey, Andre Nies, Rebecca Weber, Liang Yu
Lowness And Π Nullsets, Rod Downey, Andre Nies, Rebecca Weber, Liang Yu
Dartmouth Scholarship
We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Lof randomness.
An Almost Deep Degree, Peter Cholak, Marcia Groszek, Theodore Slaman
An Almost Deep Degree, Peter Cholak, Marcia Groszek, Theodore Slaman
Dartmouth Scholarship
We show there is a non-recursive r.e. set A such that if W is any low r.e. set. then the join W ⊕ A is also low. That is. A is “almost deep”. This answers a question of Joekusch. The almost deep degrees form an definable ideal in the r.e. degrees (with jump.)
A Basis Theorem For Perfect Sets, Marcia J. Groszek, Theodore A. Slaman
A Basis Theorem For Perfect Sets, Marcia J. Groszek, Theodore A. Slaman
Dartmouth Scholarship
We show that if there is a nonconstructible real, then every perfect set has a nonconstructible element, answering a question of K. Prikry. This is a specific instance of a more general theorem giving a sufficient condition on a pair M ⊂ N of models of set theory implying that every perfect set in N has an element in N which is not in M.
A Special Class Of Almost Disjoint Families, Thomas E. Leathrum
A Special Class Of Almost Disjoint Families, Thomas E. Leathrum
Dartmouth Scholarship
The collection of branches (maximal linearly ordered sets of nodes) of the tree ${}^{<\omega}\omega$ (ordered by inclusion) forms an almost disjoint family (of sets of nodes). This family is not maximal -- for example, any level of the tree is almost disjoint from all of the branches. How many sets must be added to the family of branches to make it maximal? This question leads to a series of definitions and results: a set of nodes is {\it off-branch} if it is almost disjoint from every branch in the tree; an {\it off-branch family} is an almost disjoint family of off-branch sets; ${\frak o}=\min\{|{\Cal O}|: {\Cal O}$ is a maximal off-branch family$\}$. Results concerning $\frak o$ include: (in ZFC) ${\frak a}\leq{\frak o}$, and (consistent with ZFC) $\frak o$ is not equal to any of the standard small cardinal invariants $\frak b$, $\frak a$, $\frak d$, or ${\frak c}=2^\omega$. Most of these consistency results use standard forcing notions -- for example, $Con({\frak b}={\frak a}<{\frak o}={\frak d}={\frak c})$ comes from starting with a model of $ZFC+CH$ and adding $\omega_2$-many Cohen reals. Many interesting open questions remain, though -- for example, $Con({\frak o}<{\frak d})$.