Page 1

Displaying 1 – 17 of 17

Showing per page

Polynomial time bounded truth-table reducibilities to padded sets

Vladimír Glasnák (2000)

Commentationes Mathematicae Universitatis Carolinae

We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class f -PAD of all f -padded sets, if it is a subset of { x 10 f ( | x | ) - | x | - 1 ; x { 0 , 1 } * } ). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a...

Provident sets and rudimentary set forcing

A. R. D. Mathias (2015)

Fundamenta Mathematicae

Using the theory of rudimentary recursion and provident sets expounded in [MB], we give a treatment of set forcing appropriate for working over models of a theory PROVI which may plausibly claim to be the weakest set theory supporting a smooth theory of set forcing, and of which the minimal model is Jensen’s J ω . Much of the development is rudimentary or at worst given by rudimentary recursions with parameter the notion of forcing under consideration. Our development eschews the power set axiom. We...

Currently displaying 1 – 17 of 17

Page 1