Zobrazeno 1 - 5
of 5
pro vyhledávání: '"Narusevych, Mykyta"'
Autor:
Narusevych, Mykyta
We extend the typical forcing of M. M\"uller and derive conditions on the forcing frame for which generic expansions preserve injective/bijective pigeonhole principle for polynomial-time computable graphs of functions. Applying this machinery, we sho
Externí odkaz:
http://arxiv.org/abs/2406.14930
Autor:
Ken, Eitetsu, Narusevych, Mykyta
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 predicate $R$ in the bounded arithmetic $T^2_2(R)$ to the existence of a parti
Externí odkaz:
http://arxiv.org/abs/2406.10924
Autor:
Narusevych, Mykyta
We give elementary proof that theory $T^1_2(R)$ augmented by the weak pigeonhole principle for all $\Delta^b_1(R)$-definable relations does not prove the bijective pigeonhole principle for $R$. This can be derived from known more general results but
Externí odkaz:
http://arxiv.org/abs/2208.14713
Autor:
Narusevych, Mykyta
We study mutual relations of various versions of the pigeonhole principle over bounded arithmetic theory T1 2 (R). The main two variants are the ordinary ontoPHPn+1 n (R), formalizing that R is not the graph of a bijective function from [n + 1] into
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od______2186::dcf6a8eefd412e2d2301bbe95bef42f4
http://www.nusl.cz/ntk/nusl-506573
http://www.nusl.cz/ntk/nusl-506573
Autor:
Narusevych, Mykyta
The thesis is devoted to the cardinal arithmetic. The first step is to formulate the Singular Cardinals Hypothesis (SCH) which simplifies the cardinal exponentiation of sin- gular cardinal numbers. We then define stationary sets and closed and unboun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od______2186::cb67f487f3a2fdc19c06b04e8df85eff
http://www.nusl.cz/ntk/nusl-435636
http://www.nusl.cz/ntk/nusl-435636