9 found
Order:
  1.  15
    Linear extensions of partial orders and reverse mathematics.Emanuele Frittaion & Alberto Marcone - 2012 - Mathematical Logic Quarterly 58 (6):417-423.
    We introduce the notion of τ-like partial order, where τ is one of the linear order types ω, ω*, ω + ω*, and ζ. For example, being ω-like means that every element has finitely many predecessors, while being ζ-like means that every interval is finite. We consider statements of the form “any τ-like partial order has a τ-like linear extension” and “any τ-like partial order is embeddable into τ” . Working in the framework of reverse mathematics, we show that these (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  26
    On Goodman Realizability.Emanuele Frittaion - 2019 - Notre Dame Journal of Formal Logic 60 (3):523-550.
    Goodman’s theorem states that HAω+AC+RDC is conservative over HA. The same result applies to the extensional case, that is, E-HAω+AC+RDC is also conservative over HA. This is due to Beeson. In this article, we modified the Goodman realizability and provide a new proof of the extensional case.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  16
    Reverse mathematics and initial intervals.Emanuele Frittaion & Alberto Marcone - 2014 - Annals of Pure and Applied Logic 165 (3):858-879.
    In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  23
    Reverse mathematics, well-quasi-orders, and Noetherian spaces.Emanuele Frittaion, Matthew Hendtlass, Alberto Marcone, Paul Shafer & Jeroen Van der Meeren - 2016 - Archive for Mathematical Logic 55 (3):431-459.
    A quasi-order Q induces two natural quasi-orders on $${\mathcal{P}(Q)}$$, but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq (Proceedings of the 22nd Annual IEEE Symposium 4 on Logic in Computer Science (LICS’07), pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on $${\mathcal{P}(Q)}$$ preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on $${\mathcal{P}(Q)}$$ are Noetherian, which means that they contain no (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  13
    Choice and independence of premise rules in intuitionistic set theory.Emanuele Frittaion, Takako Nemoto & Michael Rathjen - 2023 - Annals of Pure and Applied Logic 174 (9):103314.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  27
    Extensional Realizability and Choice for Dependent Types in Intuitionistic Set Theory.Emanuele Frittaion - 2023 - Journal of Symbolic Logic 88 (3):1138-1169.
    In [17], we introduced an extensional variant of generic realizability [22], where realizers act extensionally on realizers, and showed that this form of realizability provides inner models of $\mathsf {CZF}$ (constructive Zermelo–Fraenkel set theory) and $\mathsf {IZF}$ (intuitionistic Zermelo–Fraenkel set theory), that further validate $\mathsf {AC}_{\mathsf {FT}}$ (the axiom of choice in all finite types). In this paper, we show that extensional generic realizability validates several choice principles for dependent types, all exceeding $\mathsf {AC}_{\mathsf {FT}}$. We then show that adding (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  19
    A note on fragments of uniform reflection in second order arithmetic.Emanuele Frittaion - 2022 - Bulletin of Symbolic Logic 28 (3):451-465.
    We consider fragments of uniform reflection for formulas in the analytic hierarchy over theories of second order arithmetic. The main result is that for any second order arithmetic theory $T_0$ extending $\mathsf {RCA}_0$ and axiomatizable by a $\Pi ^1_{k+2}$ sentence, and for any $n\geq k+1$, $$\begin{align*}T_0+ \mathrm{RFN}_{\varPi^1_{n+2}} \ = \ T_0 + \mathrm{TI}_{\varPi^1_n}, \end{align*}$$ $$\begin{align*}T_0+ \mathrm{RFN}_{\varSigma^1_{n+1}} \ = \ T_0+ \mathrm{TI}_{\varPi^1_n}^{-}, \end{align*}$$ where T is $T_0$ augmented with full induction, and $\mathrm {TI}_{\varPi ^1_n}^{-}$ denotes the schema of transfinite induction up (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  14
    Completeness of the primitive recursive $$omega $$ ω -rule.Emanuele Frittaion - 2020 - Archive for Mathematical Logic 59 (5-6):715-731.
    Shoenfield’s completeness theorem states that every true first order arithmetical sentence has a recursive \-proof encodable by using recursive applications of the \-rule. For a suitable encoding of Gentzen style \-proofs, we show that Shoenfield’s completeness theorem applies to cut free \-proofs encodable by using primitive recursive applications of the \-rule. We also show that the set of codes of \-proofs, whether it is based on recursive or primitive recursive applications of the \-rule, is \ complete. The same \ completeness (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  7
    Reverse Mathematics and Partial Orders, University of Udine, Italy, 2014. Supervised by Alberto Marcone.Emanuele Frittaion - 2018 - Bulletin of Symbolic Logic 24 (2):196-196.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark