Proof theory | Metatheorems | Deductive reasoning | Theorems in the foundations of mathematics

Deduction theorem

In mathematical logic, a deduction theorem is a metatheorem that justifies doing conditional proofs—to prove an implication A → B, assume A as an hypothesis and then proceed to derive B—in systems that do not have an explicit inference rule for this. Deduction theorems exist for both propositional logic and first-order logic. The deduction theorem is an important tool in Hilbert-style deduction systems because it permits one to write more comprehensible and usually much shorter proofs than would be possible without it. In certain other formal proof systems the same conveniency is provided by an explicit inference rule; for example natural deduction calls it implication introduction. In more detail, the propositional logic deduction theorem states that if a formula is deducible from a set of assumptions then the implication is deducible from ; in symbols, implies . In the special case where is the empty set, the deduction theorem claim can be more compactly written as: implies . The deduction theorem for predicate logic is similar, but comes with some extra constraints (that would for example be satisfied if is a closed formula). In general a deduction theorem needs to take into account all logical details of the theory under consideration, so each logical system technically needs its own deduction theorem, although the differences are usually minor. The deduction theorem holds for all first-order theories with the usual deductive systems for first-order logic. However, there are first-order systems in which new inference rules are added for which the deduction theorem fails. Most notably, the deduction theorem fails to hold in Birkhoff–von Neumann quantum logic, because the linear subspaces of a Hilbert space form a non-distributive lattice. (Wikipedia).

Video thumbnail

Teach Astronomy - Deduction

http://www.teachastronomy.com/ Deduction is a way of combining observations or statements made in science logically. Deduction provides a very strong way of connecting observations with a conclusion. Typically we start with premises and combine them to draw conclusions. For example, if

From playlist 01. Fundamentals of Science and Astronomy

Video thumbnail

Verify the Deduction Rule: If P then Q. If (Not P) Then Q. Therefore Q.

This video explains how to verify a deduction rule using a truth table. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Is an Argument a Deduction Rule or Not: If (P and Q), Then R. Not P or Not Q. Therefore Not R

This video explains how to use a truth table to determine if an argument is a valid deduction rule or not. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Is an Argument a Deduction Rule or Not: If (P and Q) Then R. Not P or Not Q. Therefore Not R

This video explains how to use a truth table to determine if an argument is a valid deduction rule or not. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Determine if an Argument is a Deduction Rule or Not: If P Then R. If Q Then R. R. Therefore P or Q.

This video explains how to use a truth table to determine if an argument is a valid deduction rule or not. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Geometry - Ch. 2: Reasoning and Proofs (13 of 46) What is Deductive Reasoning?

Visit http://ilectureonline.com for more math and science lectures! In this video I will explain what is deductive reasoning. Sometime known as deductive logic or leading to a deductive conclusion. It is reasoning from one or more statements to reach a logical conclusion. And I will expla

From playlist GEOMETRY CH 2 PROOFS & REASONING

Video thumbnail

Foundations - Seminar 2

Billy Price and Will Troiani present a series of seminars on foundations of mathematics. In this seminar Billy introduces natural deduction as a proof system. You can join this seminar from anywhere, on any device, at https://www.metauni.org. This video was filmed in Deprecation (https:/

From playlist Foundations seminar

Video thumbnail

Deduction Rules: Modus Ponens and Modul Tollens

This video provides a definition of modus ponens and modus tollens and verifies them using a truth tables. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

What if Current Foundations of Mathematics are Inconsistent? | Vladimir Voevodsky

Vladimir Voevodsky, Professor, School of Mathematics, Institute for Advanced Study http://www.ias.edu/people/faculty-and-emeriti/voevodsky In this lecture, Professor Vladimir Voevodsky begins with Gödel's second incompleteness theorem to discuss the possibility that the formal theory of f

From playlist Mathematics

Video thumbnail

Foundations S2 - Seminar 1 - Ax-Grothendieck and model theory

A seminar series on the foundations of mathematics, by Will Troiani and Billy Snikkers. This season the focus is on the proof of the Ax-Grothendieck theorem: an injective polynomial function from affine space (over the complex numbers) to itself is surjective. There is an interesting role

From playlist Foundations seminar

Video thumbnail

Topos seminar Lecture 15: Abstraction and adjunction (Part 1)

I begin by explaining in a simple example the connection between formal reasoning involving distinct concepts, and adjunctions between classifying topoi. This leads to a discussion of models in topoi (focused on the particular example of the theory of abelian groups) then to the syntactic

From playlist Topos theory seminar

Video thumbnail

Foundations - Seminar 3

Billy Price and Will Troiani present a series of seminars on foundations of mathematics. In this seminar Billy continues to introduce natural deduction as a proof system, and proves soundness. You can join this seminar from anywhere, on any device, at https://www.metauni.org. This video

From playlist Foundations seminar

Video thumbnail

Michael R. Douglas - How will we do mathematics in 2030?

Abstract: We make the case that over the coming decade, computer assisted reasoning will become far more widely used in the mathematical sciences. This includes interactive and automatic theorem verification, symbolic algebra, and emerging technologies such as formal knowledge repositories

From playlist 2nd workshop Nokia-IHES / AI: what's next?

Video thumbnail

Math 131 083116 Lecture #01 Ordered Sets and Boundedness

[Notes for the course and others may be downloaded at http://community.scrippscollege.edu/wcwou/online-resources/class-notes/.] Heading towards the real (and complex) numbers: problems with the rational numbers (algebraic incompleteness, analytic incompleteness). Square root of two is ir

From playlist Course 7: (Rudin's) Principles of Mathematical Analysis

Video thumbnail

Gödel's Incompleteness Theorems: An Informal Introduction to Formal Logic #SoME2

My entry into SoME2. Also, my first ever video. I hope you enjoy. The Book List: Logic by Paul Tomassi A very good first textbook. Quite slow at first and its treatment of first-order logic leaves a little to be desired in my opinion, but very good on context, i.e. why formal logic is im

From playlist Summer of Math Exposition 2 videos

Video thumbnail

Philosophy & Our Mental Life - Hilary Putnam (1973)

The question which troubles laymen, and which has long troubled philosophers, even if it is somewhat disguised by today's analytic style of writing philosophy, is this: Are we made of matter or soul-stuff? To put it as bluntly as possible, are we just material beings, or are we "something

From playlist Philosophy of Mind

Video thumbnail

Introduction to Deductive Reasoning

http://www.mathispower4u.yolasite.com

From playlist Introduction to Proof

Related pages

Quantum logic | Linear subspace | Natural deduction | Peirce's law | Currying | Tautology (logic) | Propositional calculus | Lambda calculus | Theory (mathematical logic) | Axiom schema | Well-formed formula | Empty set | Distributive lattice | John von Neumann | Curry–Howard correspondence | Sentence (mathematical logic) | Metatheorem | Modus ponens | Conditional proof | Hilbert space | Mathematical logic | Rule of inference | Cut-elimination theorem | First-order logic | Garrett Birkhoff | Combinatory logic