Self-Reference and Diagonalization

June 8, 2010

S. Abramsky and J. Zvesper have uploaded

From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference

In section 4 ‘The Lawvere Fixpoint Lemma’ contains a ‘positive’ version of Cantor’s theorem.

Advertisements

Russel’s Paradox and Fixed Points of Involutions

December 2, 2009

The n-category cafe is a place for creative and inspiring discussions. Admittedly, I do not understand enough of category theory to contribute and therefore I was really happy when in the recent discussion about Feferman set theory I saw the following two quotes.

By the end of his remark John Baez states:

I don’t know any good way to deal with Russell’s paradox, but I believe there is one.  I believe someday we’ll find it.  But I don’t think we’ll find it by trying to ‘weasel out’ of the problem. Somehow we need to think a new way — a clearer way, that makes the paradox just disappear.

Tom Leinster answers:

I’ve pretty much entirely moved over to a point of view in which it doesn’t make sense to ask of any two sets A and B the question ‘is A∈B?’  For example, I don’t think it makes sense to ask whether ∅∈ℚ.  And once you’ve adopted this point of view, the ‘paradox’ dissolves.

These two statements are crystal clear. John Baez is not satisfied with the state of discussion on the paradox and Tom Leinster answers this by disallowing certain questions. His idea, in a way, exemplifies how we deal with this problem usually. We disallow things.

What if we can go the other way. Like with the introduction of the complex numbers. Instead of disallowing the square root of a negative number we take it and see how far we get.

In our situation this means we allow the question ‘is A∈B’ for all objects under consideration and then rapidly approach Russel’s paradox (and some others). From this paradox we learn that there are sets which contain and not contain themselves simultaneously. However:

That is only a problem in a two valued logic!

Let us assume there are other truth values but ‘true’ and ‘false’. Especially, that there is at least one truth value equal to its own negation. In this sense, negation is an involution on the set of truth values as we know it and negation has a fixed point. This fixed point is something new, like the square root of -1. In my opinion, that is what we learn from the paradox. The logic of mathematics has to be multi-valued.

Unfortunately this innocent looking assumption/observation leads us far away from anything we are used to know about sets. Circularity starts to surface everywhere and instead of calling it a ‘bug’ we are forced to call it a ‘feature’ (if we want to proceed on this way).

I elaborate this in further posts here, albeit in small steps, because the consequences are really mind-boggling.