Mykyta Narusevych

activity

20222026

collaborators

5 papers

math.LO2026

Forcing in bounded arithmetic and set theory: analogies and differences

Radek Honzik, Ondrej Ježil, Mykyta Narusevych

We provide a modern overview of several forcing methods in bounded arithmetic and compare them with forcing in set theory. We specifically discuss the countable forcing framework o…

math.LO2026

Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic

Mykyta Narusevych

We formulate a factorization hypothesis for linear orders definable by oracle polynomial-time machines. Assuming this hypothesis, we provide an approach to constructing a nonstanda…

math.LO2024

An independence of the MIN principle from the PHP principle

Mykyta Narusevych

The minimization principle $MIN (◃)$ studied in bounded arithmetic says that a strict linear ordering $◃$ on any finite interval $[0, \dots, n)$ has t…

math.LO2024

Ajtai's theorem for $T_{2}^{2} (R)$ and pebble games with backtracking

Eitetsu Ken, Mykyta Narusevych

We introduce a pebble game extended by backtracking options for one of the two players (called Prover) and reduce the provability of the pigeonhole principle for a generic predicat…

math.LO2022

Models of Bounded Arithmetic and variants of Pigeonhole Principle

Mykyta Narusevych

We give elementary proof that theory $T_{2}^{1} (R)$ augmented by the weak pigeonhole principle for all $Δ_{1}^{b} (R)$ -definable relations does not prove the bijective pigeonhole principle…

Forcing in bounded arithmetic and set theory: analogies and differences

Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic

An independence of the MIN principle from the PHP principle

Ajtai's theorem for T22​(R) and pebble games with backtracking

Models of Bounded Arithmetic and variants of Pigeonhole Principle

Ajtai's theorem for $T_{2}^{2} (R)$ and pebble games with backtracking