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
    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$ Jul 19, 2019 at 7:23
  • $\begingroup$ So something like consistency strength, yes? $\endgroup$
    – Master
    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$ Jul 19, 2019 at 16:23
  • $\begingroup$ ... continuation: I mean this theory: mathoverflow.net/questions/335912/… $\endgroup$ Jul 19, 2019 at 16:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.