Why a program that values the truth of a sentence is not possible
Bertrand Russell’s paradox applied
Introduction
We will start this post by talking once more about a great mathematician and philosopher of our last century: Bertrand Russell. In particular, we will mention the paradox he formalised regarding the Cantor’s set theory. A little bit of Natural Language Processing and Sentiment Analysis will be introduced to the reader. Once this done, we will suppose the existence of a program that values the truth of a sentence. By applying the paradox concept seen before, we will demonstrate that this program cannot exist.
Bertrand Russell’s paradox
Georg Cantor formalised at the end of the 19th century the naive set’s theory, as part of his study of infinite sets. Won’t mention too about it, just think on the set’s theory you see at college.
Let’s follow a bit to the year 1901, and listen to what Bertrand Russell, a British mathematician and philosopher Cambridge teacher postulated:
We know set’s can contain things, well let’s think of a set containing other sets. In particular, let R be the set of all sets that are not members of themselves.
Now suppose R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves.
This contradiction is Russell’s paradox.
This can be think also as the very well known paradox I’m lying. Suppose it’s true, then you cannot lie, so you are telling the truth by saying you are a lier… contradiction. Suppose it’s false, then you are not a liar, then you are telling the truth by telling you are lying, so you must be a liar… contradiction.
This is the concept of Russell’s paradox: a sentence (or proposition in logic’s language) that cannot have a value of truth either false.
A very good book to read about this that I recommend is Hofstadter’s book Godel Escher Bach, a best seller that explains Godel’s theory and its relations with Escher and Bach’s work. A very good book. We find in this book the source of all these issues of propositions that cannot have truth value as the auto reference that lives in those sentences: I’m lying and a set’s theory proposition talking about the set’s theory.
Natural Language Processing
Natural language processing (NLP) is a field of computer science, artificial intelligence, and linguistics concerned with the interactions between computers and human (natural) languages. As such, NLP is related to the area of human–computer interaction. — Wikipedia
NLP is a science field that is been studied since a few years ago and looks after the kind of programs that mine information on unstructured data, in particular every day sentences. Whenever you get an email on Gmail where a friend of yours asks you to go to a movie and you get a Google alert asking if you want to add that event to your calendar, that’s where NLP is taking place: it has read your email and got the data of an appointment to suggest you to add it to the calendar.
Now I’ll mention a method (or science?) that shows up on NLP studies: Sentiment analysis.
Sentiment analysis (also known as opinion mining) refers to the use of natural language processing, text analysis and computational linguistics to identify and extract subjective information in source materials. — Wikipedia
Yes, this is possible though it sounds like not. Programs that read text and are able to note if the content refers to a love letter or suicide letter. We can see uses of this on the industry, for example LiveHelpNow or Medallia, companies that use sentiment analysis to provide product improvements based on user experiences’ feedback.
Just wanted to mention that these kind of programs exist. But what about the next one.
A program that values a sentence truth’s value
Let’s suppose it exists a program such that, given a sentence (a sequence of characters) it returns a boolean value saying either is truth or false. This assumption seems like the one that sentiment analysis uses: programs that given a sentence return the sentiment of it.
Let’s not think on sentences that cannot be taken as propositions, let’s think on well formed sentences (not my gral he tre grfdv) and also sentences such that are logic propositions, sentences like: The cat inside the box is alive, The TV is on, If 2+2=4 then 2+2+1=4+1. The problem of computing if the sentence is of this kind is tractable(it can be computed in a reasonable time).
But let’s consider now a sentence such that it talks about itself, let’s try our program with this input
This sentence is false
Well let’s see the output value of our function (here the demonstration starts):
If the output is true, then the sentence This sentence is false is true, but then that sentence must be false while we said it was true… contradiction.
If the output is false, then the sentence This sentence is false is false, then that sentence must be true while we said it was false… contradiction.
Ergo, the program such that returns a sentence’s truth value with This sentence is false as argument cannot return either true nor false.
We have applied Russell’s paradox to our program to demonstrate that this program cannot compute what it should while having this auto referenced sentence as input.
And what should it return? An exception we could say. Some sort of error. But well we have another issue now, how do we find the auto reference in a sentence? Just think that auto reference could be not in that direct scenario:
The next sentence is false.
The sentence above is false.
This has been taken from Godel Escher Bach‘s book to demonstrate that the auto reference could not always be that easy to find. Here we have it on two levels, not one like in the other sentence we studied.
This is it for now. Thinking that finally our problem is how to find auto references in the sentences? Until this is done, a program such that computes the truth value of a sentence cannot exist.
