MHB Axiomatized Formal Theory Proof

  • Thread starter Thread starter agapito
  • Start date Start date
  • Tags Tags
    Proof Theory
AI Thread Summary
The discussion centers around the undecidability of a Consistent and Sufficiently Strong Axiomatized Formal Theory (AFT), with references to the Diagonal Argument and its application. Participants clarify that AFT refers to Axiomatized Formal Theory and emphasize the importance of formal proofs, particularly those verified by proof assistants like Coq and Isabelle. Key points include Church's theorem, which establishes that pure first-order predicate calculus is undecidable by demonstrating that Turing machines can be encoded within it, and the undecidability of Robinson's system Q, which shows that computable functions can be represented in Q. The diagonal argument is highlighted as crucial for proving Gödel's second theorem regarding the incompleteness of Peano Arithmetic. Recommended resources for further reading include the Open Logic Project books and "Computability and Logic" by Boolos et al.
agapito
Messages
46
Reaction score
0
Can someone please direct me to ,or show, a proof that a Consistent and Sufficiently Strong AFT is not decidable. It presumably involves the Diagonal Argument, but I can't figure out how to apply it.

Many thanks.
 
Technology news on Phys.org
What is AFT?

Also, "formal" in the context of proof lately means proofs that have been verified by a computer program (proof assistant, such as Coq, Isabelle, Agda and so on). Do you have a formalized proof in mind or simply a proof from a textbook?
 
I realized that AFT stands for Axiomatized Formal Theory.

There is Church's theorem that says that pure first-order predicate calculus is not decidable. This is proved by showing that Turing machines can be encoded in predicate calculus and the fact that a machine halts can be expresses as a formula. There is also a theorem that Robinson's system $Q$ (Peano Arithmetic without induction) is undecidable. This is proved by showing that computable functions are representable in $Q$. Again, for each machine and input there exists a formula saying that the machine halts on that input, and the machine indeed halts iff that formula is provable.

These two results can be found, for example, in the Open Logic Project books "Sets, Logic, Computation" and "Incompleteness and Computability". Another comprehensive book that deals with this is Computability and Logic by Boolos et al.

The diagonal argument is used, in particular, in the proof of second Gödel's theorem about incompleteness of Peano Arithmetic.
 
Thank you very much.
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
Back
Top