Define a formula ξ(v) taking one free variable to be f(┌ϕ┐,┌f(v,v)┐).
Now define ψ to be f(┌ξ┐,┌ξ┐). By the definition of f we have ψ↔ξ(┌ξ┐).
We have ϕ(┌ψ┐)↔f(┌ϕ┐,┌ψ┐)↔f(┌ϕ┐,┌f(┌ξ┐,┌ξ┐)┐)↔ξ(┌ξ┐)↔ψ
The first step follows by the definition of f, the second by the definition of ψ, the third by the definition of ξ, and the fourth by the property of ψ mentioned above. Since ψ∈S0 by the type signature of f, this completes the proof.
Things I’m not sure about:
It’s a little unclear to me what the Syn(A,B) notation means. In particular, I’ve assumed that f takes as inputs Gödel numbers of formulas rather than the formulas themselves. If f takes as inputs the formulas themselves, then I don’t think we can assume that the formula ξ exists without doing more arithmetization work (i.e. the equivalent of ξ would need to know how to convert from the Gödel number of a formula to the formula itself).
If the biconditional “↔” is a connective in the logic itself, then I think the same proof works but we would need to assume more about f than is given in the problem statement, namely that the theory we have can prove the substitution property of f.
The assumption about the quantifier complexity of S0 and S1 was barely used. It was just given to us in the type signature for f, and the same proof would have worked without this assumption, so I am confused about why the problem includes this assumption.
So, a proof can’t be “s2A” or “s2B” or “s2A” or “s2B” or “s2B” or “s2C” or “worlds” or “possible worlds” or “no known world”. But it might well be that the proof is correct enough given the premises.
Attempted solution and some thoughts on #9:
Define a formula ξ(v) taking one free variable to be f(┌ϕ┐,┌f(v,v)┐).
Now define ψ to be f(┌ξ┐,┌ξ┐). By the definition of f we have ψ↔ξ(┌ξ┐).
We have ϕ(┌ψ┐)↔f(┌ϕ┐,┌ψ┐)↔f(┌ϕ┐,┌f(┌ξ┐,┌ξ┐)┐)↔ξ(┌ξ┐)↔ψ
The first step follows by the definition of f, the second by the definition of ψ, the third by the definition of ξ, and the fourth by the property of ψ mentioned above. Since ψ∈S0 by the type signature of f, this completes the proof.
Things I’m not sure about:
It’s a little unclear to me what the Syn(A,B) notation means. In particular, I’ve assumed that f takes as inputs Gödel numbers of formulas rather than the formulas themselves. If f takes as inputs the formulas themselves, then I don’t think we can assume that the formula ξ exists without doing more arithmetization work (i.e. the equivalent of ξ would need to know how to convert from the Gödel number of a formula to the formula itself).
If the biconditional “↔” is a connective in the logic itself, then I think the same proof works but we would need to assume more about f than is given in the problem statement, namely that the theory we have can prove the substitution property of f.
The assumption about the quantifier complexity of S0 and S1 was barely used. It was just given to us in the type signature for f, and the same proof would have worked without this assumption, so I am confused about why the problem includes this assumption.
Here’s the proof from the paper again:
=s2A < px0,0..p9x0> xx0x0x0x0x0e0..6y0e0x0e0x0e0x0e0e0e0x0e0e0x0e0e0x0.x0e0x0e0e0x0e0e0e0x0e0.x0e0bx<x0e0e0x0e0e0e0e0x0e0.x0e0e0.e0e0.x0e0e0e0e0..2e0e0.x0e0e0e0e0).
So, a proof can’t be “s2A” or “s2B” or “s2A” or “s2B” or “s2B” or “s2C” or “worlds” or “possible worlds” or “no known world”. But it might well be that the proof is correct enough given the premises.
So we assume the proof is correct!