Proving Godel's completeness theorem does not point to the core of first-order logic???

Voted to close as it's unclear what the question is. Please elaborate more completely as to what you're asking.

The is no clearer way to post my question. The question is if a proof I am giving is known or not.

@ConstantineFrangakis Why is the predicate in (2) a truth predicate? Also I have no idea what a "truth signature" or a "countable signature" means. However this sounds like a well-known proof that a complete and sound (not just consistent) computably axiomatized theory of arithmetic cannot exist, since in that case it would be true that the provability predicate is a truth predicate, which violates Tarski's theorem.

clarification: I am assuming array S(m'th predicate, at x input), and I mean "not.Tr(S(x,x)) ,x=1,2,…. (that’s what I I mean by signature) disagrees with the signature Tr(S(m,x)), x=1,2,… for any S(m, .) in the array. thank you

@ConstantineFrangakis I think I understand what you're saying. Like if we enumerate the single-variable formulas $\phi_n(x)$ and then a certain formula, say $\phi_m(x),$ would be the formula that says "$\phi_x(x)$ is not provable" and then $\phi_m(m)$ would generate a contradiction?

But that's not quite right: If $\phi_m(m)$ is provable, then by $\Sigma_1$-completeness "$\phi_m(m)$ is provable" and "$\phi_m(m)$ is not provable" are both provable, so that contradicts consistency. However in the other case where $\lnot\phi_m(m)$ is provable, this just means "$\lnot\phi_m(m)$ is provable" and "$\phi_m(m)$ is provable" are provable. Which means "the system is inconsistent" is provable, which doesn't imply the system is indeed inconsistent without some form of soundness. Also I think the "under the hood" machinery needed here exceeds what is needed for a typical proof of GIT1.

@spaceisdarkgreen: I think one of us has missed the other's point. Let me use your notation: we have constructed the sentence "S*(x)='phi(x,x) is not provable'. This I can do because by completeness, there is a finite process of proving a phi or a not.phi. Next, is the value of the VECTOR { "is S*(x) provable ?", x=1, 2, ...} equal to the vector when asking the same question to the open phi(k, x), x=1, 2...,? Suppose it is, for k=5. Then we would have :

@spaceisdarkgreen: ...we would have that at least the 5th element of the two vectors the same. But that would be saying (from the S* based vector ): "is {phi(5,5) not provable} provable ?", EQUAL to the phi(k,) based vector : "is phi(5, 5) provable? "

@spaceisdarkgreen: Now, let's look closely as you did: say phi(5,5) is provable in the system, so The right hand side of the above equality, "is phi(5,5) probable" is provable (no soundness needed). Now consistency (to which I will stick) would mean that the negation, "phi(5,5) is NOT provable" is NOT provable, which is the negation of the left hand side of the above equality. So, CONTRADICTION. So (since we insist on consistency above), COMPLETENESS is false. No soundness here needed.

@spaceisdarkgreen: by the way, if you agree, I would very like like to exchange our views more directly- I am really interested in this; my name is Constantine Frangakis, I am professor of Biostatistics at Johns Hopkins, and my email is [email protected]

I have voted to reopen, because I think the question deserves a full answer (in the answers, rather than in the comments). You ask users here to respect the effort of the person who writes. I think you will receive much more positive responses if you respect the people who take the time to engage with your question by following the rules of this site: see the guide here. A big part of this is using MathJax formatting (similar to LaTeX) for all mathematical symbols.

Thanks for this, Dr Kruckman. I respect the forum, and my best way is to post succinctly as possible my question. I am a bit too old for the math formatting stuff (it acts distractingly on my focus).

By the way, I think the question has improved a lot since the original version that was downvoted and closed. It's much more clear what the question is now. I've taken it the rest of the way by fixing grammar and adding the MathJax formatting for you. Having gone to that effort, I'm going to leave it to someone else to write a comprehensive answer. (I sympathize with your comment about focus - I find it very difficult to focus on reading a question if I'm distracted by ugly plain-text-based formatting!

Thanks Dr. Kruckman. I do not know if this is not part of protocol, but since you have understood my question, I would be very appreciative if you would express your thought about whether it is valid/known proof or not. In any case, my email is [email protected] (I am a professor at Johns Hopkins, Biostatistics, and amateur student of logic).

@ConstantineFrangakis I had said myself that if $\phi_5(5)$ were provable, the system would be inconsistent, contrary to assumption (and not needing soundness)... ok then, say it's not provable. How do you get an inconsistency then? (I don't necessarily dispute this can be done in some way without soundness, but I don't understand your argument.)

@spaceisdarkgreen: thank you for bearing with me. Here are the two cases fully.

A. First, the assumption of completeness and consistency: (a) if p( S) then not p (not S) (b) if not p(S) then p(not S)

@spaceisdarkgreen: \\ step 1. Define phi*(x)= not p(phi(x,x)\\ step 2. Say phi*(x) is in the list as phi(5,x); then p(phi(5,x)) = P(phi*(x)) = p(not phi(x,x)) \\ step 3. At x=5: suppose p(phi(5,5)) holds, then by the RHS of 2, we also have p(not phi(5,5)), and this contradicts A.1 for S set to phi(5,5).\\ step 4. Suppose not p(phi(5,5)) (by completeness, there is no other choice); then by RHS of 2, we have:**not p (not phi(x,x))**; but assumption A (b) says that from not p(phi(5,5)) it follows that p(not phi(5,5)), which is contradiction

@ConstantineFrangakis Where is 2 coming from? If we have $\phi(5,x) = \lnot P(\phi(x,x))$, then $P(\phi(5,x))$ is $P(\lnot P(\phi(x,x)),$ no? How are you getting $P(\lnot\phi(x,x))$? I would recommend we move this to chat (don't want to email), but for some reason, the usual prompt to do so is not showing up.

@spaceisdarkgreen: I am sorry for the error, but the result persists. First, step 2 comes from the fact that we have assumed listing of all well formed predicates, and phi*(x) is a well formed predicate. Second, I have amended the steps below:

@spaceisdarkgreen: step 1. Define phi*(x)= not p(phi(x,x) step 2. Say phi*(x) is in the list as phi(5,x); then p(phi(5,x)) = p(phi*(x)) = p(not p{ phi(x,x)}) step 3. At x=5: suppose p(phi(5,5)) holds, then by the RHS of 2, we also have p(not p{phi(5,5)}), which, by A(b) is p(p(not phi(5,5))) and this is just p(not phi(5,5)). This contradicts A(a) for S set to phi(5,5).

@spaceisdarkgreen: step 4. Suppose not p(phi(5,5)) (by completeness, there is no other choice); then by RHS of 2, we have: 4.1=not p (not p{ phi(x,x)}) ; but assumption A (b) says that, from not-p(phi(5,5)) it follows that 4.2=p(not phi(5,5)). Write the outer “not p” in 4.1 as “p not”, to get 4.1 = p { not (not phi(5,5))}, which reduces to p (phi(5,5)), which is I ncontradiction to 4.2.

@ConstantineFrangakis Ok, the issue I'm pointing out is in step 4. You write "write the outer "not p" as "p not""... quite alright under the assumption of completeness. But you dropped a p! We started with $\lnot P(\lnot P(\phi(5,5)).$ Doing this and cancelling the double negative gives $P(P(\phi(5,5))),$ not $P(\phi(5,5)).$ So no contradiction... (unless, again, you assume the theory is correct about what it can prove).

I have also checked that the steps above ar based solely on consistency and completeness, NOT on soundness. Even without soundness, I used the implications forced by consistency (and completeness), such as if provable(S) then not provable(not S).

@spaceisdarkgreen Claim: p(S)=ppS : The left side says p(S) is system-true; if the RHS, were false, then not p (p(S)), and completeness implies p(not p(S)), so not p(S) is system true also. This gives a contradiction, because we have consistency.

@ConstantineFrangakis ok… that shows (I think) that P(S) implies P(P(S)). I’m saying the other direction might be false.

@spaceisdarkgreen wait: if P(P(S)) is system true, then P(S) must be system-true, because the system cannot prove a system-false (P(S)) statement. (I am emphasizing system-false or system-true, as opposed to soundly false or true). Right ?

@ConstantineFrangakis what does “system-true” mean? This is not a standard term.

@spaceisdarkgreen By S being system-true in the complete+consistent system, I meant that there is a string that can be checked (objectively) to prove S (with the system's rules even if unsound). Let me try to argue that for the diagonal (defined as phi(5,x) earlier) , although we should have p(S) = p(not p{S}) (at x=5), this cannot happen.

@spaceisdarkgreen case 1: p(S) is system true. Then not P(S) is system false (consistency), and p(not p(S)) must be system-false because p() proves all and only system-true statements. -> Contradiction; case 2: if p(S) is system false; then not P(S) is system-true, and p(not (p(S)) is system true. -> Contradiction.