Misplaced Pages

Ringschluss

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Closed chain inference)
This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (August 2024)
Proof strategy for showing a collection of statements are pairwise equivalent.

In mathematics, a Ringschluss (German: Beweis durch Ringschluss, lit. 'Proof by ring-inference') is a mathematical proof technique where the equivalence of several statements can be proven without having to prove all pairwise equivalences directly.

In order to prove that the statements φ 1 , … , φ n {\displaystyle \varphi _{1},\ldots ,\varphi _{n}} are each pairwise equivalent, proofs are given for the implications φ 1 ⇒ φ 2 {\displaystyle \varphi _{1}\Rightarrow \varphi _{2}} , φ 2 ⇒ φ 3 {\displaystyle \varphi _{2}\Rightarrow \varphi _{3}} , … {\displaystyle \dots } , φ n − 1 ⇒ φ n {\displaystyle \varphi _{n-1}\Rightarrow \varphi _{n}} and φ n ⇒ φ 1 {\displaystyle \varphi _{n}\Rightarrow \varphi _{1}} .

The pairwise equivalence of the statements then results from the transitivity of the material conditional.

Example

For n = 4 {\displaystyle n=4} the proofs are given for φ 1 ⇒ φ 2 {\displaystyle \varphi _{1}\Rightarrow \varphi _{2}} , φ 2 ⇒ φ 3 {\displaystyle \varphi _{2}\Rightarrow \varphi _{3}} , φ 3 ⇒ φ 4 {\displaystyle \varphi _{3}\Rightarrow \varphi _{4}} and φ 4 ⇒ φ 1 {\displaystyle \varphi _{4}\Rightarrow \varphi _{1}} . The equivalence of φ 2 {\displaystyle \varphi _{2}} and φ 4 {\displaystyle \varphi _{4}} results from the chain of conclusions that are no longer explicitly given:

φ 2 ⇒ φ 3 {\displaystyle \varphi _{2}\Rightarrow \varphi _{3}} .  φ 3 ⇒ φ 4 {\displaystyle \varphi _{3}\Rightarrow \varphi _{4}} . This leads to: φ 2 ⇒ φ 4 {\displaystyle \varphi _{2}\Rightarrow \varphi _{4}}
φ 4 ⇒ φ 1 {\displaystyle \varphi _{4}\Rightarrow \varphi _{1}} .  φ 1 ⇒ φ 2 {\displaystyle \varphi _{1}\Rightarrow \varphi _{2}} . This leads to: φ 4 ⇒ φ 2 {\displaystyle \varphi _{4}\Rightarrow \varphi _{2}}

That is φ 2 ⇔ φ 4 {\displaystyle \varphi _{2}\Leftrightarrow \varphi _{4}} .

Motivation

The technique saves writing effort above all. By dispensing with the formally necessary chain of conclusions, only n {\displaystyle n} direct proofs need to be provided for φ i ⇒ φ j {\displaystyle \varphi _{i}\Rightarrow \varphi _{j}} instead of n ( n − 1 ) {\displaystyle n(n-1)} direct proofs. The difficulty for the mathematician is to find a sequence of statements that allows for the most elegant direct proofs possible.

See also

References

  1. Plaue, Matthias; Scherfner, Mike (2019-02-11). Mathematik für das Bachelorstudium I: Grundlagen und Grundzüge der linearen Algebra und Analysis [Mathematics for the Bachelor's degree I: Fundamentals and basics of linear algebra and analysis] (in German). Springer-Verlag. p. 26. ISBN 978-3-662-58352-4.
  2. Struckmann, Werner; Wätjen, Dietmar (2016-10-20). Mathematik für Informatiker: Grundlagen und Anwendungen [Mathematics for Computer Scientists: Fundamentals and Applications] (in German). Springer-Verlag. p. 28. ISBN 978-3-662-49870-5.
Categories: