[FOM] "Hidden" contradictions

[Rafee Kamouna]

The Church-Rosser Argument


A Function which is TOTAL if and only if NOT TOTAL

Definition:
 The Kleene-Rosser paradox reads: ``The $\lambda$-calculus expression 
consisting of the $\lambda$ term (k) which may not be applied to itself,
 when combined with itself, negates itself (kk)".
$$k\ =\ (\lambda x.\neg (xx))$$
$$kk\ =\ (\lambda x.\neg (xx)) k\ =\ \neg (kk)$$

k_i may be applied to $k_i\ \equiv\ k_i$  may not be applied to k_i

k_ik_i is total
 $\Longleftrightarrow\ k_ik_i$ is not total

======================================================
Proofs:
======================================================
Theorem 2.1: Established Belief: The Church-Rosser Argument
\forall i, k_ik_i = \neg k_ik_i is undefined

It is the $\lambda$-calculus corresponding counter-part for the Turing machine halting problem. Hence, it is undecidable.

Proof: The proof is by contradiction. After universal quantification over $\Lambda$, a counter-example is constructed:

1.
 If all functions defined by $\lambda$-expressions in $\Lambda$ were 
total, then one would have [k_ik_i = \neg k_ik_i] for the diagonal 
function $k_i$.

2. This means that some functions, including the diagonal function, are not total.

3. Since one  does not have k_ik_i = \neg k_ik_i, instead one has [k_ik_i=\neg k_ik_i] is  undefined.

4. It is the $\lambda$-calculus corresponding counter-part for the
 Turing
 machine halting problem.
==========================================================================

Refutation:
A
 counter-example is constructed after universal quantification. Since 
the constructed counter-example (for established belief) is a 
contradictory expression, so if the universal quantification used an 
opposite property, still the same counter-example is derived.

Theorem: Refutation of Established Belief:
\forall i   k_ik_i = \neg k_ik_i is defined

Proof: The proof is by contradiction. After universal quantification over $\Lambda$, a counter-example is constructed:

1. If all functions
 defined by $\lambda$-expressions in $\Lambda$ were not total, then one would have:

2. k_i may not be applied to k_i.

3. (2) \equiv k_i may be applied to k_i.

4. Implies: [k_ik_i = \neg k_ik_i]$ for the diagonal function k_i.

5. Implies: one has [k_ik_i = \neg k_ik_i]. Contradiction derived, (1) must be negated.

6. $\exists$ some functions, including the diagonal function, that are total.

7. The diagonal function [k_ik_i = \neg k_ik_i] is defined.

The Kleene-Rosser paradox can be articulated as in the following re-formulations:
[k_ik_i =\neg\ k_ik_i] is defined\ if and only if   [k_ik_i=\neg\ k_ik_i]  is undefined
[k_ik_i=\neg\ k_ik_i] is total\ if and only if [k_ik_i=\neg\ k_ik_i] is not total.
[k_ik_i=\neg\ k_ik_i] is decidable if and only if  [k_ik_i=\neg k_ik_i]" is not
 undecidable.

It is easy to extend this (by diagonalization) over Turing machines.

================================================================================

Best,
Rafee Kamouna.

==================================================================================

From: Mark Steiner <mark.steiner at mail.huji.ac.il>
To: FOM at cs.nyu.edu 
Sent: Monday, August 12, 2013 1:39 PM
Subject: [FOM] "Hidden" contradictions
 


In 1939, Turing debated Wittgenstein in a class the latter was giving at Cambridge.  Turing argued that working with an inconsistent system could result in “bridges falling down.”
 
To Wittgenstein’s argument that we don’t need to reason from a contradiction, Turing replied that we might not ever see the contradiction, and yet the inconsistency could still result in wildly incorrect calculations.
 
It would seem that in principle that Turing was correct (this is an example of Wittgenstein himself): suppose we give the axioms for multiplication without limiting the cancellation law  ab = ac à b=c to nonzero a.  One could imagine that many students would not notice the problem.  Indeed, in a recent survey at the City University of New York, 93% of precalculus students asked to solve the equation x^2 = x, divided by x and got x = 1 (as the only solution).  One could dress this problem up quite a bit.  In these cases, one gets correct solutions, but misses others, and this could indeed make “bridges fall down.”
 
Are there any historical examples in which inconsistent systems actually yielded false theorems that could have made “bridges fall down” without anybody noticing the inconsistency?
 
Thanks,
Mark Steiner
 
 
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130814/21c7e68b/attachment-0001.html>