The formalist) school of math philosophy thinks that meaningful questions have to be phrased in terms of finite computational processes. But if you try to write a program for determining the truth value of “this statement is false”, you’ll see it recurses and never terminates:
def f():
return (not f())
See also Kleene-Rosser paradox. This may or may not dissolve the original question for you, but it works for me.
There’s more to be said about the paradox because it keeps turning up in many contexts. For example, see Terry Tao’s posts about “no self-defeating object”. Also note that if we replace “truth” with “provability”, the liar’s paradox turns into Godel’s first incompleteness theorem, and Curry’s paradox turns into Löb’s theorem.
ETA: see also Abram Demski’s explanation of Kripke’s fixed point theory here on LW, if that’s your cup of tea.
Also note that if we replace “truth” with “provability”, the liar’s paradox turns into Godel’s first incompleteness theorem, and Curry’s paradox turns into Löb’s theorem.
The wikipedia link for Curry’s paradox claims “It has also been called Löb’s paradox after Martin Hugo Löb.” Given that you require a word substitution I take it that wikipedia is oversimplyifying something? (Or perhaps overloading the Lob keyword at tad.)
The two are related, so the overloading is probably not accidental. When I studied math we used to joke that every area of classical math has a Gauss theorem, and more often than not it’s the most important theorem in the area.
The two are related, so the overloading is probably not accidental.
Not accidental and not surprising either. But still undesirable. It obfuscates the meaning of people who are talking about either of the concepts specifically.
I was curious enough to look into some background. “Different but basically the same for practical purposes” seems to be the conclusion.
The best part of this unified scheme is that it shows that there are really no paradoxes. There are limitations. Paradoxes are ways of showing that if you permit one to violate a limitation, then you will get an inconsistent systems. The Liar paradox shows that if you permit natural language to talk about its own truthfulness (as it—of course—does) then we will have inconsistencies in natural languages.
I’m not sure if I like this paper (it seems to be trying to do too much), but it did contain something new to me—Yablo’s non-self-referential version of the Liar Paradox: for every natural number n, let S(n) be the statement that for all m>n S(m) is false. Also there is a funny non-self-referential formulation by Quine: “Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.
Interestingly, the Yablo’s paradox vanishes when there is no infinity. If the last statement of the Yablo’s sequence exists, it is true. And all at the preceding positions are false. Everything is well. Another reason, I am an infinity atheist.
The “last statement”? This would require that there exists a highest natural number. That seems like it would be a weirder occurrence than the mostly harmless Yablo’s paradox.
Although I suppose we can always choose to work in “the natural numbers mod N”, for some value of N, which is one way to banish “infinity”.
If I remember rightly, the process is called “quining” and while it produces similar paradoxes and problems, it is distinct from self-reference. Linguistically, at least—logically one might be a form of the other.
Not to me it doesn’t. Yablo’s version has a “forall” that your translation misses. So in Yablo’s version there’s no consistent way to assign truth values to S(n), but in your version we could make S(n) = “n is odd” or something.
Not exactly. My version is incorrect, yes. But there is, uhm, controversial way of consistent assignment of truth values to Yablo’s statements.
In my version n-th step of loop unrolling is
S'(n) = not not ... {n times} ... S
or
S'(n)=not S'(n+1)
Yablo’s version
S(n)=not exists m>n such that S(m)=true
or
S(n)=(not S(n+1)) && (not exists m>n+1 such that S(m)=true)
If we extend set of natural numbers by element omega such that
forall n in N : (omega>n),
not exists n in N : (n+1=omega),
omega=omega+1
Than we can assign S(n)=false for all n in N, and S(omega)=true.
Edit: Oops, second version of Yablo’s statement, which I included to demonstrate why I had an idea of loop unrolling, is not consistent when n equals omega. Original Yablo’s statement is consistent although.
Edit: Meta. The thing I always hated about my mind is that it completely refuses to form intuitions about statements which aren’t directly connected to object level (but then what is object level?).
Edit: Meta Meta. On introspection I don’t feel anything about previous statement. Pretty damn consistent...
The above comment is the closest that I have ever found to the following Predicate Logic formalization:
“This sentence is not true.”
∃x ∈ finite strings from the alphabet of predicate logic
∃T ∈ Predicates
∃hasProperty ∈ Predicates |
x = hasProperty(x, ~T(x))
Finite string x asserts that it has the property of the negation of the Boolean value result of evaluating predicate T with itself as T’s only argument.
The above is based on Tarski formal correctness of True:
For all x, True(x) if and only if φ(x)
The formalist) school of math philosophy thinks that meaningful questions have to be phrased in terms of finite computational processes. But if you try to write a program for determining the truth value of “this statement is false”, you’ll see it recurses and never terminates:
See also Kleene-Rosser paradox. This may or may not dissolve the original question for you, but it works for me.
There’s more to be said about the paradox because it keeps turning up in many contexts. For example, see Terry Tao’s posts about “no self-defeating object”. Also note that if we replace “truth” with “provability”, the liar’s paradox turns into Godel’s first incompleteness theorem, and Curry’s paradox turns into Löb’s theorem.
ETA: see also Abram Demski’s explanation of Kripke’s fixed point theory here on LW, if that’s your cup of tea.
The wikipedia link for Curry’s paradox claims “It has also been called Löb’s paradox after Martin Hugo Löb.” Given that you require a word substitution I take it that wikipedia is oversimplyifying something? (Or perhaps overloading the Lob keyword at tad.)
The two are related, so the overloading is probably not accidental. When I studied math we used to joke that every area of classical math has a Gauss theorem, and more often than not it’s the most important theorem in the area.
Not accidental and not surprising either. But still undesirable. It obfuscates the meaning of people who are talking about either of the concepts specifically.
I was curious enough to look into some background. “Different but basically the same for practical purposes” seems to be the conclusion.
See also: A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points, which treats the Liar’s paradox as an instance of a generalization of Cantor’s theorem (no onto mapping from N->2^N).
I’m not sure if I like this paper (it seems to be trying to do too much), but it did contain something new to me—Yablo’s non-self-referential version of the Liar Paradox: for every natural number n, let S(n) be the statement that for all m>n S(m) is false. Also there is a funny non-self-referential formulation by Quine: “Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.
Interestingly, the Yablo’s paradox vanishes when there is no infinity. If the last statement of the Yablo’s sequence exists, it is true. And all at the preceding positions are false. Everything is well. Another reason, I am an infinity atheist.
The “last statement”? This would require that there exists a highest natural number. That seems like it would be a weirder occurrence than the mostly harmless Yablo’s paradox.
Although I suppose we can always choose to work in “the natural numbers mod N”, for some value of N, which is one way to banish “infinity”.
There is no need for ridiculously large numbers. There is always the last statement in a row and this way and only this way, no Yablo paradox arises.
I’m not sure what you mean by this. “There is no need”? So is there a highest natural number, or not? Because if not:
If S(N) is the last statement, N is a natural number.
Therefore N + 1 is a natural number and N + 1 > N.
Therefore the statement S(N + 1) exists.
Therefore S(N) is not the last statement. Contradiction.
If there is no infinity (the premise) then there must be.
If there is no infinity there must not be a highest natural number, but there could be if there is infinity?
s/not //
Edit: That looks bad. Let’s see.
s/.ot /
That works.
The second has an implied “This sentence …” so I’d say it’s still self-referential.
edit: actually I don’t think that’s required (the quote is the subject) so it does count I suppose.
If I remember rightly, the process is called “quining” and while it produces similar paradoxes and problems, it is distinct from self-reference. Linguistically, at least—logically one might be a form of the other.
(Upvoted the edit!)
Yablo’s version looks like unrolled infinite loop of function
Not to me it doesn’t. Yablo’s version has a “forall” that your translation misses. So in Yablo’s version there’s no consistent way to assign truth values to S(n), but in your version we could make S(n) = “n is odd” or something.
Not exactly. My version is incorrect, yes. But there is, uhm, controversial way of consistent assignment of truth values to Yablo’s statements.
In my version n-th step of loop unrolling is
or
Yablo’s version
or
If we extend set of natural numbers by element omega such that
Than we can assign S(n)=false for all n in N, and S(omega)=true.
Edit: Oops, second version of Yablo’s statement, which I included to demonstrate why I had an idea of loop unrolling, is not consistent when n equals omega. Original Yablo’s statement is consistent although.
Edit: Meta. The thing I always hated about my mind is that it completely refuses to form intuitions about statements which aren’t directly connected to object level (but then what is object level?).
Edit: Meta Meta. On introspection I don’t feel anything about previous statement. Pretty damn consistent...
The above comment is the closest that I have ever found to the following Predicate Logic formalization:
“This sentence is not true.” ∃x ∈ finite strings from the alphabet of predicate logic ∃T ∈ Predicates ∃hasProperty ∈ Predicates | x = hasProperty(x, ~T(x))
Finite string x asserts that it has the property of the negation of the Boolean value result of evaluating predicate T with itself as T’s only argument.
The above is based on Tarski formal correctness of True: For all x, True(x) if and only if φ(x)
Copyright Pete Olcott 2016 ,2017
http://LiarParadox.org/
Helpful links. As stated though this doesn’t dissolve the strengthened liars paradox.
Does holding the view that meaningful questions have to be phrased in terms of finite computational processes imply the other tenets of formalism?