Use mathematical logic to prove this proposition

Click For Summary
SUMMARY

This discussion focuses on proving the proposition ##\{A\implies B,B\implies C\}|- A\implies C## using axioms from a Hilbert System without employing the deduction theorem or Modus Ponens as a rule of inference. The axioms referenced include ##P\implies(Q\implies P)##, ##((P\implies(Q\implies R))\implies((P\implies Q)\implies(P\implies R))##, and ##(\neg P\implies\neg Q)\implies (Q\implies P)##. The proof is structured through a series of logical deductions, ultimately demonstrating that if both ##A\implies B## and ##B\implies C## hold, then ##A\implies C## must also hold.

PREREQUISITES
  • Understanding of Hilbert Systems and their axioms
  • Familiarity with propositional logic and logical inference
  • Knowledge of Modus Ponens and its application in proofs
  • Ability to manipulate logical expressions and implications
NEXT STEPS
  • Study the axioms of Hilbert Systems in detail
  • Learn about Modus Ponens and its role in logical proofs
  • Explore advanced topics in propositional logic
  • Review examples of formal proofs using Hilbert Systems
USEFUL FOR

Mathematicians, logicians, computer scientists, and students of formal logic who are interested in understanding the foundations of logical inference and proof techniques.

solakis1
Messages
407
Reaction score
0
Given the following axioms:
1) ##P\implies(Q\implies P)##
2) ##((P\implies(Q\implies R))\implies((P\implies Q)\implies(P\implies R))## Where ##P,Q,R## are any formulas
3)##(\neg P\implies\neg Q)\implies (Q\implies P)## then prove:

##\{A\implies B,B\implies C\}|- A\implies C##
Without using the deduction theorem and as a rule of inference M.ponens
 
Last edited by a moderator:
Physics news on Phys.org
Your OP outlines the axioms of a Hilbert System. Go to the wiki page on Hilbert Systems and search "(HS2)" to see a proof of the following proposition from those axioms using Modus Ponens as rule of inference.
$$(p \to q) \to ((q \to r) \to (p \to r))$$
Relabel ##p,q,r## as ##A,B,C## to get
$$(A \to B) \to ((B \to C) \to (A \to C))$$
Then we have:
\begin{align}
&\vdash(A \to B) \to ((B \to C) \to (A \to C))\\
(A \to B), (B \to C)&\vdash(A \to B) \to ((B \to C) \to (A \to C))\\
(A \to B), (B \to C)&\vdash A\to B\quad\quad\textrm{[1st axiom]}\\
(A \to B), (B \to C)&\vdash(B \to C) \to (A \to C)
\quad\quad\textrm{[Modus Ponens on 3, 2]}\\
(A \to B), (B \to C)&\vdash B\to C \quad\quad\textrm{[2nd axiom]}\\
(A \to B), (B \to C)&\vdash A \to C
\quad\quad\textrm{[Modus Ponens on 5, 4]}
\end{align}
 
  • Informative
Likes   Reactions: berkeman

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 22 ·
Replies
22
Views
3K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 4 ·
Replies
4
Views
802
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 10 ·
Replies
10
Views
3K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K