6 citations · 6 across the 6 of their papers we have counts for
8 papers
Nonembeddings of Combinatory Algebras
Patrick Lutz, Paul Shafer, Sebastiaan A. Terwijn
In the theory of combinatorial algebras, there is a sequence of embeddings between Kleene's second model, van Oosten's model, and Scott's graph model. We prove that none of these e…
A Note on a Conjecture of Sacks: It is Harder to Embed Height Three Partial Orders than Height Two Partial Orders
Kojiro Higuchi, Patrick Lutz
A long-standing conjecture of Sacks states that it is provable in ZFC that every locally countable partial order of size continuum embeds into the Turing degrees. We show that this…
Coding information into all infinite subsets of a dense set
Matthew Harrison-Trainor, Lu Liu, Patrick Lutz
Suppose you have an uncomputable set and you want to find a set , all of whose infinite subsets compute . There are several ways to do this, but all of them seem to produ…
Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions
Patrick Lutz, Benjamin Siskind
Martin's Conjecture is a proposed classification of the definable functions on the Turing degrees. It is usually divided into two parts, the first of which classifies functions whi…
The Solecki Dichotomy and the Posner-Robinson Theorem are Almost Equivalent
Patrick Lutz
The Solecki dichotomy in descriptive set theory and the Posner-Robinson theorem in computability theory bear a superficial resemblance to each other and can sometimes be used to pr…
Sparse tree-based initialization for neural networks
Patrick Lutz, Ludovic Arnould, Claire Boyer +1
Dedicated neural network (NN) architectures have been designed to handle specific data types (such as CNN for images or RNN for text), which ranks them among state-of-the-art metho…
Formalizing Galois Theory
Thomas Browning, Patrick Lutz
We describe a project to formalize Galois theory using the Lean theorem prover, which is part of a larger effort to formalize all of the standard undergraduate mathematics curricul…
Incompleteness and Jump Hierarchies
Patrick Lutz, James Walsh
This paper is an investigation of the relationship between Gödel's second incompleteness theorem and the well-foundedness of jump hierarchies. It follows from a classic theorem of…