0
$\begingroup$

I want to coin a notion for reducibility of theories. Generally this goes like that: if we have two equi-interpretable theories $T;Q$ and it is harder to interpret $T$ in $Q$ than to interpret $Q$ in $T$; then we are to say that: theory $T$ is reducible to theory $Q$.

For example lets take theory $ZF^{fin}$ to mean the theory $ZF -\text{Infinity} + \text{ all sets are finite}$. Now if we have: $$ \forall F [(F:PA \approx ZF^{fin} ) \to \exists G ((G: ZF^{fin} \approx PA) \land G \leq F)]$$; where $I: T \approx Q$ means, $I$ is an interpretation of $Q$ in $T$ , and $\leq$ means easier than or equal in hardness. Then since $PA$ and $ZF^{fin}$ are equi-interpretable theories, then we are to say that: $$ZF^{fin} \text { is reducible to } PA$$ If the opposite is not true, then we have $$\neg (PA \text { is reducible to } ZF^{fin})$$, then we'd say in this case that: $$ ZF^{fin} \text { is strictly reducible to } PA$$

Is there a mathematical criterion for hardness of interpret-ability of theories? For example which is considered harder? to interpret $ZF + \neg C$ in $ZFC$ or the opposite?

Can we even in some remote sense consider reducibility in this particular sense to be a crierion of truth? for example if $T$ is strictly reducible to $Q$, then $Q$ is the true theory?

$\endgroup$
8
  • $\begingroup$ Zuhair, if I just answered only your questions I would have the highest reputation on the site. On the subject of the question, is reducible a term you came up with this, or is this something that already has a definition and you are wondering how well it would work as a definition? $\endgroup$
    – Master
    Commented Jul 19, 2019 at 2:34
  • $\begingroup$ @Master, reducible has a general informal sense, but technically what I'm presenting here is something that I'm defining and wondering how well it would work as a definition. What are the conundrums of this approach? $\endgroup$ Commented Jul 19, 2019 at 7:23
  • $\begingroup$ So something like consistency strength, yes? $\endgroup$
    – Master
    Commented Jul 19, 2019 at 16:06
  • $\begingroup$ @Master, we'll no. Because this is reducibility between equi-consistent theories! For example suppose that theory I've presented at MathOverflow about an extended version of second order arithmetic (better called as second order ordinal arithmetic), if one comes with a proof that it is equi-consistent with ZFC, then we'd say that ZFC is reducible to it in the sense of reducibility given here. $\endgroup$ Commented Jul 19, 2019 at 16:23
  • $\begingroup$ ... continuation: I mean this theory: mathoverflow.net/questions/335912/… $\endgroup$ Commented Jul 19, 2019 at 16:24

0

You must log in to answer this question.

Browse other questions tagged .