4
$\begingroup$

Suppose we have a language/theory $\mathcal{L}$ in First Order Logic, and we look at what it proves. Is it possible that there are two meta-languages/theories, say $\mathcal{L_1}$ and $\mathcal{L_2}$, that take $\mathcal{L}$ as an object language/theory (the symbols of $\mathcal{L}$ constitute the constants of $\mathcal{L_{1,2}}$) and they disagree over what $\mathcal{L}$ can prove?

For example, $\mathcal{L_1} \vdash (\mathcal{L} \vdash p )$ and $ \mathcal{L_2} \vdash (\mathcal{L} \vdash \neg p )$ or $\mathcal{L_1} \vdash (\mathcal{L} \vdash p) $ and $\mathcal{L_2} \vdash (\mathcal{L} \not\vdash p )$ ?

I realize that $\vdash$ might mean different things in the above sentences, but I am confused, is my question well-defined and if so, is there any work on this problem that you know of?

$\endgroup$
5
  • 1
    $\begingroup$ This is a slightly confusing question -- languages don't prove anything. Is it just that you mean "theory" (or "deductive system" or something such) when you say "language" or is there something else going on? $\endgroup$
    – hmakholm left over Monica
    Commented Oct 12, 2018 at 10:32
  • $\begingroup$ I meant axioms & deductive rules, for example, FOL axioms + ZFC axioms + Modus Ponens. ZFC can take as an object language and manipulate the syntax of FOL+PA axioms to show that it proves certain facts. $\endgroup$
    – AgentSmith
    Commented Oct 12, 2018 at 11:40
  • 1
    $\begingroup$ Yes, that's usually called "systems" rather than "languages". A language is usually just the set of non-logical symbols that can be used to build formulas -- e.g. most set theories work in the same language, namely $\{{\in}\}$ or in words: "there is a binary predicate notated $\in$ and nothing else". $\endgroup$
    – hmakholm left over Monica
    Commented Oct 12, 2018 at 12:18
  • 1
    $\begingroup$ It is simple enough to make examples of your situations where one or both of $\mathcal L_1$ and $\mathcal L_2$ think $\mathcal L$ is inconsistent, but that's a bit unsatisfying. I don't think there is anything fundamental the prevents more interesting examples from occurring, but I can't come up with any right off the cuff. $\endgroup$
    – hmakholm left over Monica
    Commented Oct 12, 2018 at 12:21
  • $\begingroup$ I will change my question accordingly, thank you. $\endgroup$
    – AgentSmith
    Commented Oct 12, 2018 at 12:35

1 Answer 1

Reset to default
2
$\begingroup$

Yes, it is clearly possible - as in the comments, for example $A$ might prove $\lnot \text{Con}(\text{ZFC})$ and $B$ might prove $\text{Con}(\text{ZFC})$.

But, in some sense, this is only kind of example. Assume that $A$ and $B$ are consistent theories each of which is strong enough to work with the same formalized provability predicate $\text{Pr}_C$ for some effective theory $C$, so $\text{Pr}_C$ is the same in the language of $A$ and the language of $B$. Also assume that $A \vdash \text{Pr}_C(\phi)$ and $B \vdash \lnot \text{Pr}_C(\phi)$ for some sentence $\phi$ in the language of $C$.

Then $A \cup B \vdash \text{Pr}_C(\phi) \land \lnot \text{Pr}_C(\phi)$, so $A\cup B$ is inconsistent. This means that there is a finite subset $A'$ of $A$ and a finite subset $B'$ of $B$ so that $A' \cup B'$ is inconsistent, so $A' \vdash \lnot \bigwedge B'$. Hence, if the situation above happens, there are particular axioms of $A$ that are incompatible with particular axioms of $B$.

This means, in particular, that the situation will never happen with the usual hierarchy of foundational theories, because these are all compatible with each other.

Now, continue with the assumptions in the second paragraph. Because $\psi \equiv \text{Pr}_C(\phi)$ is a $\Sigma^0_1$ statement, then if it is true then it is true in every model of arithmetic, even nonstandard models. This means that, if $\psi$ is true then the only way for $B \vdash \lnot \psi$ to happen is for $B$ to be inconsistent. We assumed otherwise, so $\psi$ is false. This means that, for the situation in the second paragraph to happen, $\phi$ is not provable in $C$. Thus $\psi$ is false in every $\omega$-model of arithmetic, and so $A$ has no $\omega$-models.

That is exactly the kind of situation we get from the example in the first paragraph, where $\text{Con}(\text{ZFC})$ holds in every $\omega$-model and a theory that proves $\lnot \text{Con}(\text{ZFC})$ has no $\omega$-models.

$\endgroup$
5
  • $\begingroup$ Thank you for your answer! But then how should I decide which theory to trust? The usual hierarchy of foundational theories are compatible, but what makes them so foundational and explanatory of nature? This is a soft question, but I would like to have some references. $\endgroup$
    – AgentSmith
    Commented Oct 12, 2018 at 16:21
  • $\begingroup$ Hmm, can you be more specific about what it is you mean by "this is the only kind of example"? I can follow your argument to the conclusion that $A$ has no $\omega$-models -- is that all you mean by "kind of example"? $\endgroup$
    – hmakholm left over Monica
    Commented Oct 14, 2018 at 20:07
  • $\begingroup$ @Henning Makholm: I did say "in some sense"... I just mean in the sense that I wrote about. Certainly it would be possible to find examples at higher levels of the arithmetical hierarchy, for example. But the two theories that verify the provability and disprovability, respectively, will not be compatible with each other, and moreover one of them will not have $\omega$ models. That says to me that it is unlikely there will be examples that are more "natural" than the ones about consistency. $\endgroup$
    – Carl Mummert
    Commented Oct 14, 2018 at 20:12
  • $\begingroup$ @CarlMummert: Okay. I was confused because you referred to my comments to the question, and all was thinking of there was a case there $A$ thinks $C$ is inconsistent. A priori I think there might conceviably be an example where $A$ and $B$ agrees that $C$ is consistent but have different incomparable ideas about what it proves. (I accept your argument that then neither $A$ nor $B$ can have $\omega$-models, but such an example would feel less trivial to me, and I could neither come up with one nor find a reason why it couldn't exist). $\endgroup$
    – hmakholm left over Monica
    Commented Oct 14, 2018 at 20:21
  • $\begingroup$ @Henning Makholm: I want to find an example that is easy to verify - I think there are many examples involving induction or reflection principles as well, harder to check. Let $T$ be PA, so that $\text{Con}(T + \text{Con}(T))$ is independent of $T + \text{Con}(T)$ by the incompleteness theorem. Let $B$ be $T + \text{Con}(T)+ \text{Con}(T + \text{Con}(T))$ and $A$ be $T + \text{Con}(T) + \lnot \text{Con}(T + \text{Con}(T))$. So both $A$ and $B$ think $T$ is consistent. Now let $\phi \equiv [\text{Con}(T) \to 0=1].$ Then $A \vdash \text{Pr}_T(\phi),$ and $B \vdash \lnot \text{Pr}_T(\phi)$. $\endgroup$
    – Carl Mummert
    Commented Oct 14, 2018 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .