Source author record

Linda Brown Westrick

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO math.DS

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

The determined property of Baire in reverse math

We define the notion of a determined Borel code in reverse math, and consider the principle $DPB$ , which states that every determined Borel set has the property of Baire. We show that this principle is strictly weaker than $ATR$ . Any $ω$ -model of $DPB$ must be closed under hyperarithmetic reduction, but $DPB$ is not a theory of hyperarithmetic analysis. We show that whenever $M\subseteq 2^ω$ is the second-order part of an $ω$ -model of $DPB$ , then for every $Z \in M$ , there is a $G \in M$ such that $G$ is $Δ^1_1$ -generic relative to $Z$ .

preprint2016arXiv

Effectiveness of Hindman's theorem for bounded sums

We consider the strength and effective content of restricted versions of Hindman's Theorem in which the number of colors is specified and the length of the sums has a specified finite bound. Let $\mathsf{HT}^{\leq n}_k$ denote the assertion that for each $k$ -coloring $c$ of $\mathbb{N}$ there is an infinite set $X \subseteq \mathbb{N}$ such that all sums $\sum_{x \in F} x$ for $F \subseteq X$ and $0 < |F| \leq n$ have the same color. We prove that there is a computable $2$ -coloring $c$ of $\mathbb{N}$ such that there is no infinite computable set $X$ such that all nonempty sums of at most $2$ elements of $X$ have the same color. It follows that $\mathsf{HT}^{\leq 2}_2$ is not provable in $\mathsf{RCA}_0$ and in fact we show that it implies $\mathsf{SRT}^2_2$ in $\mathsf{RCA}_0$ . We also show that there is a computable instance of $\mathsf{HT}^{\leq 3}_3$ with all solutions computing $0'$ . The proof of this result shows that $\mathsf{HT}^{\leq 3}_3$ implies $\mathsf{ACA}_0$ in $\mathsf{RCA}_0$ .

preprint2016arXiv

Ramsey's theorem for singletons and strong computable reducibility

We answer a question posed by Hirschfeldt and Jockusch by showing that whenever $k > \ell$ , Ramsey's theorem for singletons and $k$ -colorings, $\mathsf{RT}^1_k$ , is not strongly computably reducible to the stable Ramsey's theorem for $\ell$ -colorings, $\mathsf{SRT}^2_\ell$ . Our proof actually establishes the following considerably stronger fact: given $k > \ell$ , there is a coloring $c : ω\to k$ such that for every stable coloring $d : [ω]^2 \to \ell$ (computable from $c$ or not), there is an infinite homogeneous set $H$ for $d$ that computes no infinite homogeneous set for $c$ . This also answers a separate question of Dzhafarov, as it follows that the cohesive principle, $\mathsf{COH}$ , is not strongly computably reducible to the stable Ramsey's theorem for all colorings, $\mathsf{SRT}^2_{<\infty}$ . The latter is the strongest partial result to date in the direction of giving a negative answer to the longstanding open question of whether $\mathsf{COH}$ is implied by the stable Ramsey's theorem in $ω$ -models of $\mathsf{RCA}_0$ .

preprint2016arXiv

Seas of squares with sizes from a $Π^0_1$ set

For each $Π^0_1$ $S\subseteq \mathbb{N}$ , let the $S$ -square shift be the two-dimensional subshift on the alphabet $\{0,1\}$ whose elements consist of squares of 1s of various sizes on a background of 0s, where the side length of each square is in $S$ . Similarly, let the distinct-square shift consist of seas of squares such that no two finite squares have the same size. Extending the self-similar Turing machine tiling construction of Durand, Romashchenko and Shen, we show that if $X$ is an $S$ -square shift or any effectively closed subshift of the distinct square shift, then $X$ is sofic.

preprint2013arXiv

A lightface analysis of the differentiability rank

We examine the computable part of the differentiability hierarchy defined by Kechris and Woodin. In that hierarchy, the rank of a differentiable function is an ordinal less than omega_1 which measures how complex it is to verify differentiability for that function. We show that for each recursive ordinal alpha>0, the set of Turing indices of C[0,1] functions that are differentiable with rank at most alpha is Pi_{2 alpha + 1}-complete. This result is expressed in the notation of Ash and Knight.

preprint2013arXiv

Topological conjugations are not constructable

We construct two computable topologically conjugate functions for which no conjugacy is computable, or even hyperarithmetic, resolving an open question of Kennedy and Stockman.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Linda Brown Westrick

Research overview

Is this your work?

6 publications

The determined property of Baire in reverse math

Effectiveness of Hindman's theorem for bounded sums

Ramsey's theorem for singletons and strong computable reducibility

Seas of squares with sizes from a $Π^0_1$ set

A lightface analysis of the differentiability rank

Topological conjugations are not constructable

See the researcher in context

Building this map preview

Linda Brown Westrick

Research overview

Is this your work?

6 publications

The determined property of Baire in reverse math

Effectiveness of Hindman's theorem for bounded sums

Ramsey's theorem for singletons and strong computable reducibility

Seas of squares with sizes from a Π10Π^0_1Π10​ set

A lightface analysis of the differentiability rank

Topological conjugations are not constructable

See the researcher in context

Building this map preview

Seas of squares with sizes from a $Π^0_1$ set