Thursday, July 01, 2004

This sentence is false

I've always found self-referential paradoxes fascinating. The most obvious one is the Liar's paradox, like the title of this post. Another I like is "this sentance has threee errors" (the third error being that it has only two. But wait, that means...).

Then there are the Godel-style ones which demonstrate the limits of logic. Consider the theorem G: There is no proof of G*. Is G true? Then it's not a proveable theorem (and with a bit of extra work we end up having to conclude that mathematics is incomplete). Is G false? But then we have a false proof (so mathematics is inconsistent)!

* = I've simplified that a bit, what we really want to consider is the theorem G: It is not the case that there exists x and y such that (x is a proof of y, and y is the Godel number of G), expressed in the language of arithmetic.

Or in metaphysics, realists about 'properties' have to face various problems regarding exemplification. [Quick background: an object is said to 'exemplify' a property if that property is possessed by the object - e.g. red objects exemplify the property of redness. A property is said to be 'self-exemplifying' (SE) if it exemplifies itself. For example, the property of 'Being a property' is SE, but 'being triangular' is not, since properties themselves have no shape.]

For consider the property of Being Non-Self-Exemplifying (BNSE). Does this property exemplify itself? If so, then it has this property: namely, being not SE - so it does not. If not, then it's not SE, so it has the property of BNSE, so it is! Either way, we have a contradiction.

What I've just been thinking about though, is the Rochester philosophy blog, whose name is "This is Not the Name of this Blog". At first I thought it was another nice paradox, but now I don't think it works at all. Instead, it's just plain false. For it is the name of the blog, and in asserting that it's not, it asserts something which is false. But there's no paradox there - its falseness does not imply its trueness, or anything interesting like that. So that's a pity.

If there is a book in the library that lists all and only the titles of the non-self-referencing books in the library(i.e books that don't allude to themselves), does the name of that book appear on the list itself?
Tim Low | Email | 1st Jul 04 - 5:15 pm | #

---------------

You can get a paradox without even having a sentence, as in "The smallest natural number that cannot be described in less than 10000 characters" (I just described it in 82 characters, including spaces).

There are at least 3 things you can do with paradoxes, admire them, try to get rid of them, or use them to prove stuff. We're all enjoying these paradoxes, but set theory has had to become much more complex and less elegant to fix the paradoxes that Russell noticed in the original version. Godel used a paradox to prove incompleteness, as Richard showed, and I can concluded from Tim's comment that there is no such book in the library.

You can use an analogous paradox to show that there are different sizes of infinity. See this link for a proof that the set of all subsets of any set is larger than that set, which implies that, given any infinite set, you can create another infinite set which is even larger: http://www.math.utah.edu/~alfeld/math/sets/largerproof.html
dan | Email | 1st Jul 04 - 7:13 pm | #

--------------

Hmm, some cool examples popping up there. This could turn into quite an interesting comments thread :)

That maths stuff reminds me of a slightly different sort of self-reference, called "diagonalisation".

Suppose we have the (infinite) list of all the real numbers between 0 and 1. So they all begin 0.xxx...

But now we can create a new number (between 0-1) not on the list. It starts off 0.abcd... where the 'a' is a digit different from the 1st digit of the 1st number in the list, the 'b' differs from the 2nd digit of the 2nd number, the 'c' differs from the 3rd of the 3rd, and so on.

This constructed number will have at least one digit different from every single number on the list. But it itself is a real number between 0 and 1!

Hence, there are unenumerably many real numbers. By contrast, the set of natural numbers is enumerable. Thus, the set of real numbers forms a larger infinity than the (infinite) set of natural numbers.
Richard | Email | Homepage | 2nd Jul 04 - 12:47 am | #

2. G'day logicals,
I have just found this potentially fascinating site in my search for an interpretation of what I am told is a liar's paradox.
I intend it to be the disclaimer on an autobiographical type novel.
There is no point in using it unless someone else can understand what I am saying.
The sentence is printed in a circle to have no start or end point.
...while remaining entirely factual this book contains one lie in an effort to confound the guilty...

Would anybody care to have a go at deciphering it or am I just wasting my time with nonsense?

Thanks from downunder,

Robert

3. Hi Robert, that just sounds like a plain contradiction (claiming to be "entirely factual" yet "contain[ing] one lie"). So that sentence is just straightforwardly false. If you wanted to turn it into a paradox, you could cut it down to just "this book contains one lie", whilst ensuring that it has no other lies.

Visitors: check my comments policy first.
Non-Blogger users: If the comment form isn't working for you, email me your comment and I can post it on your behalf. (If your comment is too long, first try breaking it into two parts.)