Mathematical logic | Mathematical proofs | Methods of proof

Proof of impossibility

In mathematics, a proof of impossibility is a proof that demonstrates that a particular problem cannot be solved as described in the claim, or that a particular set of problems cannot be solved in general. Such a case is also known as a negative proof, proof of an impossibility theorem, or negative result. Proofs of impossibility often put to rest decades or centuries of work attempting to find a solution. Proving that something is impossible is usually much harder than the opposite task, as it is often necessary to develop a theory. Impossibility theorems are usually expressible as negative existential propositions or universal propositions in logic (see universal quantification for more). The irrationality of the square root of 2 is one of the oldest proofs of impossibility. It shows that it is impossible to express the square root of 2 as the ratio of two integers. Another proof of impossibility was the 1882 proof of Ferdinand von Lindemann, which showed that the ancient problem of squaring the circle cannot be solved because the number π is transcendental (i.e., non-algebraic) and only a subset of the algebraic numbers can be constructed by compass and straightedge. Two other classical problems—trisecting the general angle and doubling the cube—were also proved impossible in the 19th century. A problem that arose in the 16th century was that of creating a general formula using radicals expressing the solution of any polynomial equation of fixed degree k, where k ≥ 5. In the 1820s, the Abel–Ruffini theorem (also known as Abel's impossibility theorem) showed this to be impossible, using concepts such as solvable groups from Galois theory—a new subfield of abstract algebra. Among the most important proofs of impossibility found in the 20th century were those related to undecidability, which showed that there are problems that cannot be solved in general by any algorithm at all, with the most famous one being the halting problem. Gödel's incompleteness theorems are other examples that uncover some fundamental limitations in the provability of formal systems. In computational complexity theory, techniques like relativization (see oracle machine) provide "weak" proofs of impossibility, excluding certain proof techniques. Other techniques, such as proofs of completeness for a complexity class, provide evidence for the difficulty of problems by showing them to be just as hard to solve as other known problems that have proved intractable. (Wikipedia).

Video thumbnail

The Quotient Rule: Proof

This video explains and proves the quotient rule as seen in A Level mathematics and beyond. I do "borrow" a result that I don't prove, so this proof lacks a little rigour, but I'm hoping the trade-off is the video will be easier to understand. Introduction:

From playlist Proofs and Explanations

Video thumbnail

Proof: a³ - a is always divisible by 6 (2 of 2: Proof by exhaustion)

More resources available at www.misterwootube.com

From playlist The Nature of Proof

Video thumbnail

How to Prove a Function is Injective(one-to-one) Using the Definition

Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys How to prove a function is injective. Injective functions are also called one-to-one functions. This is a short video focusing on the proof.

From playlist Proofs

Video thumbnail

Introduction to Proof by Counter Example

This video provides an introduction to the proof method of proof by counter example. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Introduction to Proof by Contradiction: sqrt(2) is irrational

This video introduces the mathematical proof method of proof by contradiction and provides an example of a proof. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Existence Proofs

Ben discusses constructive and non-constructive proofs with examples.

From playlist Basics: Proofs

Video thumbnail

1=2 Proof

►MY COURSE Prove It Like A Mathematician! (Intro To Math Proofs) https://www.udemy.com/course/prove-it-like-a-mathematician/?referralCode=D4A14680C629BCC9D84C ►WEBSITE https://www.brithemathguy.com ►BECOME A CHANNEL MEMBER https://www.youtube.com/channel/UChVUSXFzV8QCOKNWGfE56YQ/join I

From playlist Shorts

Video thumbnail

Euler's and Fermat's last theorems, the Simpsons and CDC6600

NEW (Christmas 2019). Two ways to support Mathologer Mathologer Patreon: https://www.patreon.com/mathologer Mathologer PayPal: paypal.me/mathologer (see the Patreon page for details) This video is about Fermat's last theorem and Euler's conjecture, a vast but not very well-known genera

From playlist Recent videos

Video thumbnail

The Charm in Proving Something is Impossible: a Complexity Theoretic View by Nutan Limaye

PROGRAM SUMMER SCHOOL FOR WOMEN IN MATHEMATICS AND STATISTICS (ONLINE) ORGANIZERS: Siva Athreya (ISI-Bengaluru, India), Purvi Gupta (IISc, India), Anita Naolekar (ISI-Bengaluru, India) and Dootika Vats (IIT-Kanpur, India) DATE: 14 June 2021 to 25 June 2021 VENUE: ONLINE The summer sch

From playlist Summer School for Women in Mathematics and Statistics (ONLINE) - 2021

Video thumbnail

Four Step Recovery Programme for Division by Zero Deniers

Division by zero has been possible since 1957. LINKS: Transmathematica Channel https://youtube.com/channel/UC2ro5bMjox_KhU-UbUvx7jQ Rehab Playlist https://youtube.com/playlist?list=PL2qvIMkhqXu036a0M_TLAryIqjiRO6OKs History of division by zero https://doi.org/10.36285/tm.37 Suppes htt

From playlist Summer of Math Exposition Youtube Videos

Video thumbnail

The PROOF: e and pi are transcendental

Today’s video is dedicated to introducing you to two of the holy grails of mathematics, proofs that e and pi are transcendental numbers. For the longest time I was convinced that these proofs were simply out of reach of a self-contained episode of Mathologer, and I even said so in a video

From playlist Recent videos

Video thumbnail

Machine learning for optimizing certain kinds of classification proofs: Carlos Simpson

Machine Learning for the Working Mathematician: Week Nine 28 April 2022 Carlos Simpson, Machine learning for optimizing certain kinds of classification proofs for finite structures Seminar series homepage (includes Zoom link): https://sites.google.com/view/mlwm-seminar-2022

From playlist Machine Learning for the Working Mathematician

Video thumbnail

Efficient Verification of Computation on Untrusted Platforms - Yael Kalai

Computer Science/Discrete Mathematics Seminar I Topic: Efficient Verification of Computation on Untrusted Platforms Speaker: Yael Kalai Affiliation: Massachusetts Institute of Technology/Microsoft Date: February 13, 2023 Efficient verification of computation is fundamental to computer sc

From playlist Mathematics

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

2000 years unsolved: Why is doubling cubes and squaring circles impossible?

Today's video is about the resolution of four problems that remained open for over 2000 years from when they were first puzzled over in ancient Greece: Is it possible, just using an ideal mathematical ruler and an ideal mathematical compass, to double cubes, trisect angles, construct regul

From playlist Recent videos

Video thumbnail

Maths Skills: Proof by Contradiction

We discuss the idea of proof by contradiction and work through a small example - to prove that there is no smallest positive rational number. Another useful dose of Maths for everyone by Dr Sarada Herke. For more in-depth videos check out my Graph Theory channel http://youtube.com/drsarad

From playlist Maths Skills

Video thumbnail

The Contrapositive and Proof by Contrapositive

The contrapositive is a powerful tool that can be used to prove various mathematical statements. It is most useful when a direct proof is awkward or impossible, and - if it can be used - is often a much more elegant method that employing proof by contradiction. #proof #contrapositive #proo

From playlist Proofs and Explanations

Video thumbnail

Quadratic Reciprocity proof -- Number Theory 23

Suggest a problem: https://forms.gle/ea7Pw7HcKePGB4my5 Please Subscribe: https://www.youtube.com/michaelpennmath?sub_confirmation=1 Patreon: https://www.patreon.com/michaelpennmath Merch: https://teespring.com/stores/michael-penn-math Personal Website: http://www.michael-penn.net Randolp

From playlist Number Theory v2

Related pages

Playfair's axiom | G. H. Hardy | Theorem | Bell's theorem | Arrow's impossibility theorem | Pythagoras | Rice's theorem | Abel–Ruffini theorem | Euler's sum of powers conjecture | Turing machine | Asymptote | Equilateral polygon | Ferdinand von Lindemann | Ernest Nagel | Computational complexity theory | Universal quantification | Alfred North Whitehead | Penrose tiling | Undecidable problem | Matiyasevich's theorem | Pierre de Fermat | Gödel's incompleteness theorems | Fermat's Last Theorem | Completeness (logic) | David Hilbert | Mathematical proof | Squaring the circle | Entscheidungsproblem | Degree of a polynomial | Counterexample | Richard's paradox | Alan Turing | Euclid's Elements | Kolmogorov complexity | Integer | Constructible polygon | Well-ordering principle | Nikolai Lobachevsky | Cantor's diagonal argument | Constructible number | Complexity class | Speed of light | Infinite loop | Galois theory | Transcendental number | Greibach's theorem | Alonzo Church | Decision problem | Hans Reichenbach | Algebraic number | Straightedge and compass construction | Square root of 2 | Mathematics | Uncertainty principle | Pi | Hilbert's tenth problem | Turing's proof | Bernhard Riemann | Solvable group | János Bolyai | Axel Thue | Carl Friedrich Gauss | Oracle machine | Doubling the cube | Cube root | Proof by contradiction | Parallel postulate | Constructive proof | Post–Turing machine | E. M. Wright | Halting problem | Post correspondence problem | Principia Mathematica | Ratio | Abstract algebra | Irrational number | Bertrand Russell | Conservation of energy | List of unsolved problems in mathematics | Algorithm