Source author record

Marta Fiori-Carones

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO math.CO Logic in Computer Science

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An isomorphism theorem for models of Weak König's Lemma without primitive recursion

We prove that if $(M,\mathcal{X})$ and $(M,\mathcal{Y})$ are countable models of the theory $\mathrm{WKL}^*_0$ such that $\mathrm{I}Σ_1(A)$ fails for some $A \in \mathcal{X} \cap \mathcal{Y}$ , then $(M,\mathcal{X})$ and $(M,\mathcal{Y})$ are isomorphic. As a consequence, the analytic hierarchy collapses to $Δ^1_1$ provably in $\mathrm{WKL}^*_0 + \neg\mathrm{I}Σ^0_1$ , and $\mathrm{WKL}$ is the strongest $Π^1_2$ statement that is $Π^1_1$ -conservative over $\mathrm{RCA}^*_0 + \neg\mathrm{I}Σ^0_1$ . Applying our results to the $Δ^0_n$ -definable sets in models of $\mathrm{RCA}^*_0 + \mathrm{B}Σ^0_n + \neg\mathrm{I}Σ^0_n$ that also satisfy an appropriate relativization of Weak König's Lemma, we prove that for each $n \ge 1$ , the set of $Π^1_2$ sentences that are $Π^1_1$ -conservative over $\mathrm{RCA}^*_0 + \mathrm{B}Σ^0_n + \neg\mathrm{I}Σ^0_n$ is c.e. In contrast, we prove that the set of $Π^1_2$ sentences that are $Π^1_1$ -conservative over $\mathrm{RCA}^*_0 + \mathrm{B}Σ^0_n$ is $Π_2$ -complete. This answers a question of Towsner. We also show that $\mathrm{RCA}_0 + \mathrm{RT}^2_2$ is $Π^1_1$ -conservative over $\mathrm{B}Σ^0_2$ if and only if it is conservative over $\mathrm{B}Σ^0_2$ with respect to $\forall Π^0_5$ sentences.

preprint2022arXiv

Uniquely orderable interval graphs

Interval graphs and interval orders are deeply linked. In fact, edges of an interval graphs represent the incomparability relation of an interval order, and in general, of different interval orders. The question about the conditions under which a given interval graph is associated to a unique interval order (up to duality) arises naturally. Fishburn provided a characterisation for uniquely orderable finite connected interval graphs. We show, by an entirely new proof, that the same characterisation holds also for infinite connected interval graphs. Using tools from reverse mathematics, we explain why the characterisation cannot be lifted from the finite to the infinite by compactness, as it often happens.

preprint2021arXiv

To reorient is easier than to orient: an on-line algorithm for reorientation of graphs

We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA_0 and hence is computably true.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.