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 English it is also sometimes called a cycle of implications, closed chain inference, or circular implication; however, it should be distinguished from circular reasoning, a logical fallacy. 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. In proving the equivalence of n {\displaystyle n} statements, it requires the direct proof of only n {\displaystyle n} out of the n ( n − 1 ) / 2 {\displaystyle n(n-1)/2} implications between these statements. In contrast, for instance, choosing one of the statements as being central and proving that the remaining n − 1 {\displaystyle n-1} statements are each equivalent to the central one would require 2 ( n − 1 ) {\displaystyle 2(n-1)} implications, a larger number. The difficulty for the mathematician is to find a sequence of statements that allows for the most elegant direct proofs possible.
References