There is a piece of paper with 100 sentences written on: " 1.
logic/hundred Added material
Problem
There is a piece of paper with 100 sentences written on:
" 1. Exactly one sentence on this page is false.
2. Exactly two sentences on this page are false.
3. Exactly three sentences on this page are false.
4. Exactly four sentences on this page are false.
5. Exactly five sentences on this page are false.
.
.
.
99. Exactly 99 sentences on this page are false.
100. Exactly 100 sentences on this page are false."
How many sentences are false and how many are true?
What if we replace "exactly" by "at least"?
Show solution
From _Litton's Problematical Recreations_
It is tempting to argue as follows:
At most one statement can be true (they are mutually contradictory).
If they are all false, statement 100 would be true, which is no good.
So 99 are false, and statement 99 is true.
If replaced by "at least", and the "real" number of false statements is
x, then statements x+1 to 100 will be false (since they falsely claim
that there are more false statements than there actually are). So,
100-x are false, ie. x=100-x, so x=50. The first 50 statements are
true, and statements 51 to 100 are false.
However, there is a hidden and incorrect assumption in this argument.
To see this, suppose that there is one statement on the sheet and it
says "One statement is false" or "At least one statement is false,"
either way it implies "this statement is false," which is a familiar
paradoxical statement. We have learned that this paradox arises
because of the false assumption that all statements are either true or
false. This is the hidden assumption in the above reasoning.
If it is acknowledged that some of the statements on the page may be
neither true nor false (i.e., meaningless), then nothing whatsoever can
be concluded about which statements are true or false.
This puzzle has been carefully contrived to appear to be solvable
(like the vacuous statement "this statement is true"). By changing the
numbers in some statements and changing "true" to "false," various
circular forms of the liar's paradox can be constructed. A much more
complicated version of the same puzzle is:
1) At least one of the last two statements in this list is true.
2) This is either the first true or the first false statement in the
list.
3) There exist three consecutive false statements.
4) The difference beween the numbers of the last true statement and
the first true statement is a factor of the unknown number.
5) The sum of the numbers of the true statements is the unknown
number.
6) This is not the last true statement.
7) Each true statement's number is a factor of the unknown number.
8) The unknown number equals the percentage of these statements which
are true.
9) The number of different factors which the unknown number has
(excluding 1 and itself) is more than the sum of the numbers of the
true statements.
10) There are no three consecutive true statements.
What is the number?
The incorrect but plausible solution is:
By 2, either way 1 must be false, and then so must both 9 and 10.
6, if false, says "This is the last true statement", which gives
a paradox, thus 6 must be true, and so must 7 and/or 8.
7 and 8 cannot both be true, as the number had to be a multiple
of 6,7,8 , that is a multiple of 168 (by 7), and less than 100 (by 8)
If 8 is false, then 3 is true (8,9,10 is false), if 8 is true, then
3 is false (3 cannot be true when both 6 and 8 are true, then there
are no three consecutive statements left).
So we have either
A) F X F X X T F T F F
or
B) F X T X X T T F F F
In A), 4 and 5 must be true (by false 10), and 2 may be true or false.
So by 5 the number shall be either 27 (2+3+4+5+6+7) or 25 (3+4+5+6+7).
None of these can fullfill 8, though, so A) is out leaving us with B)
Now, (by 7) 3,6 and 7 are factors, the number must be a multiple of
42, as 2+3+4+5+6+7=27, 5 must be false.
By false 10, 2 and 4 must be true, that is 5 shall be a multiple
of the number. Now the number must be a multiple of 2,3,4,5,6 and 7,
that is a multiple of 3*4*5*7=420. 420 has 22 different factors
(2,3,4,5,6,7,10,12,14,15,20,21,28,30,35,42,60,70,84,105,140,210)
and the sum 2+3+4+6+7 = 22, so the only multiple of 420 that
fulfills false 9 is 420.
Additional material
[ Editor: a correction to the "incorrect but plausible solution" of the
ten-statement version above, posted to rec.puzzles in October 1995. ]
> So we have either
>
> A) F X F X X T F T F F
> or
> B) F X T X X T T F F F
>
> In A), 4 and 5 must be true (by false 10), and 2 may be true or false.
This is where I disagree. Seeing how 3 is false, 2 MUST be true, or
there would be three false statements in a row (1,2,3). This however
does not change any of the following reasoning, but it is a slight
inconsistency.
-- Robert-Jan Westerhof <WESTERHOF@stpc.wi.LeidenUniv.nl>
[ Editor: mail between Chris Cole and Jamie Dreier, January 1998, on
whether such puzzles may assume that every statement is true or false.
Cole had asked for the number of true sentences on each of three
lists; Dreier's answers are quoted in the first mail. ]
List 1:
a) This statement is true.
List 2:
a) This statement is false.
List 3:
a) There is exactly one false statement on this list.
b) There are exactly two false statements on this list.
>Why, one, of course!
>Whew, I thought your final question would be a killer.
I asked you the number of true sentences on each list. For the first
list your answer was "indeterminate," for the second list your answer
was "I'd rather not say" and for the third list your answer is "one."
In none of the cases did I tell you anything about the truth values of
the statements, so I'm guessing that you proceeded in each case by
assuming that each statement was either true or false. But in the
first case this assumption leads to an indeterminate result, in the
second case this assumption leads to a contradiction, and only in the
third case does it lead to a definite answer. Doesn't that make you
question whether the assumption is justified? And if the assumption
cannot be made, then why isn't the answer the same in all three cases,
namely, "indeterminate?"
-- Chris Cole <chris@questrel.com>
>>Doesn't that make you question whether the assumption is >justified? And
>if the assumption cannot be made, then
>>why isn't the answer the same in all three cases,
>>namely, "indeterminate?"
>
>I'm sorry, you've already asked your *final* question.
>
>Actually, I agree, but after all, when we do puzzles we generally make some
>natural assumptions as long as they seem to make sense. So, when assuming
>that each sentence is either true or false is coherent and leads to a single
>determinable answer, we do that (just as we'd assume that the temperature in
>the room is about 70 degrees if we were given a puzzle about ice cubes). But
>if the assumption turns out to be incoherent, or doesn't yield any
>determinable answer, then we say that instead.
>
>I think that's fair. I think that's reasonable. Now my lawyer advises me to
>answer no further questions unless I'm granted immunity.
>
Well, I have several comments, which range from the outright philosophical
to the downright idiosyncratic:^)
1. A "puzzle" (as opposed to a mere "problem") should enlighten in
some way, and one frequent way is to have unintended or surprising
consequences of seemingly innocuous assumptions. Indeed, much of the
challenge of a "true" puzzle is in figuring out what assumptions are
reasonable. Therefore, I think it is pretty interesting if we can pose
a puzzle that lures people into making assumptions that turn out to
cause trouble in closely related problems. As an example: how many
true statements are on the following list?
a) Statement b is true and the gold is in the box.
b) Statement a is false and the gold is in the box.
If we assume that both statements are either true or false, we will
deduce that both statements are false. But we will also deduce that
the gold is not in the box. But this is perfectly wild, because the
gold is in the box! (I'm not saying where the box is, but it has gold
in it, trust me ;^)
2. From a purely logical point of view, when we assume that the
statements on a particular list are either true or false, this is
because this assumption is a special case of the general rule that all
statements are either true or false. Otherwise, are we singling out
these particular statements? This makes no sense.
But the general rule has unintended consequences, and in particular we
can prove it is not true by applying it to the statement: "This
statement is false." Thus, the general rule is wrong, and we cannot
use it in any case. Again from a purely logical point of view, it is
never legitimate to assume that all the statements on any list are
either true or false.
3. The issue of what kind of statements are true or false is a very
interesting issue in the philosophy of language, leading as it does to
the investigation of metalanguages. I look on puzzles of this type as
great excuses to introduce people to this hard-won and profound
insight. In particular, we can introduce Tarski's seemingly jejune but
actually very profound observation that:
"Snow is white" is true if and only if snow is white.
What this means is that a statement can only be true or false if it is
"about" something. Circularly self-referential statements such as
those on the lists we have been discussing are not "about" anything;
this is the real reason why they have no truth value. And that, to me,
is pretty darn interesting!
-- Chris Cole <chris@questrel.com>
Chris,
I'm not really disagreeing with your main point.
I knew about the Gold in the box example from Smullyan. I guess it's an
application of Lob's Theorem in disguise.
>2. From a purely logical point of view, when we assume that the
>statements on a particular list are either true or false, this is
>because this assumption is a special case of the general rule that all
>statements are either true or false. Otherwise, are we singling out
>these particular statements? This makes no sense.
Well, I have two comments on this. First, I do not believe that the
relevant assumption is "all statements are either true or false." For one
thing, we do not need to mention 'false' at all, since obviously we can do
just as well with 'not true'. Now the assumption that every statement is
either true or not true is clearly a special case of the general principle
of Excluded Middle. Every fire engine, I feel fairly safe in saying, is
either red or not red. For exactly the same reason I always felt safe
thinking that every statement was either true or not true. What I'm saying
is that the assumption is not especially *semantical* (Excluded Middle is
as much about redness as it is about the semantical property, truth). The
reforms needed to avoid paradoxes are more radical, I think, than just
giving up the assumption that every statement is either true or false.
Second, since we can't very well ignore Excluded Middle as a general rule
(we could try or pretend, but I doubt we could really do it), I think the
sensible pragmatic approach, not very satisfying but what we have to make
do with, is to continue to rely on it when we can see that it causes no
trouble, as it doesn't in the earlier, unparadoxical examples. That's why I
was willing to give a definite answer to the earlier ones.
>3. The issue of what kind of statements are true or false is a very
>interesting issue in the philosophy of language, leading as it does to
>the investigation of metalanguages. I look on puzzles of this type as
>great excuses to introduce people to this hard-won and profound
>insight. In particular, we can introduce Tarski's seemingly jejune but
>actually very profound observation that:
>
>"Snow is white" is true if and only if snow is white.
I agree.
Of course, it appears that Tarski was mistaken. Not about "Snow is white"
in particular, but I mean, we can't assert every instance of the schema.
Tarski said that natural languages are inconsistent, but personally I don't
know what that means. (English isn't a theory.)
>What this means is that a statement can only be true or false if it is
>"about" something. Circularly self-referential statements such as
>those on the lists we have been discussing are not "about" anything;
>this is the real reason why they have no truth value. And that, to me,
>is pretty darn interesting!
There's certainly *something* interesting involved, but I don't agree with
your diagnosis.
The statements on the list obviously are 'about' something. They are about
each other and themselves! And even the mildly suspicious part about a
sentence being about itself is, as I'm sure you know, inessential, e.g.,
(i) Sentence (ii) is false.
(ii) Sentence (i) is true.
Here, of course, there is a 'circle of reference', but even *that* is
inessential (the example doesn't come right to mind, but I can find it if
you're interested -- it's due to Stephen Yablo).
The problem has to do with sentences that are about other sentences. That
in itself poses no particular difficulty, since we can happily say of some
sentence that it is seventeen words long and the like. It's rather the
ungroundedness of the sentences (like unfounded sets?). And the solution
can't be that they have no truth value, I think, since if they had no truth
value they would not be true, and if the Liar sentence is not true, we're
off into a contradiction again.
Well, that's easy to say, but I have no idea what to do about it. I feel a
little better knowing that nobody on earth knows what to do about it.
-- Jamie Dreier <James_Dreier@Brown.edu>
[ Editor: Dreier's next mail answers one from Cole that is not in the
collected material; Cole's lines are quoted in it. ]
Yes, that is essentially the argument.
I would generally use Excluded Middle as a rule, not a premise, but it
amounts to the same thing. To be explicit, let's call my Liar, "(L)". And
I'll use "Tarski's Rule" rather than a schema; the rule says that from any
sentence you can derive the sentence saying of the first that it is true,
and vice versa. And finally, I'll use "Substitution", saying names of the
same sentence can be substituted freely for one another.
(The first column states the assumptions on which the given line is
resting; the second column numbers the lines; the third column lists the
sentences in the derivation; the last column states the rules and lines
from which the current line is derived.)
(L) (L) is not true.
(1) (1) (L) is not true. ASSUMPTION
(1) (2) "(L) is not true" is true. (1), Tarski's Rule
(1) (3) (L) is true. (2), Substitution
(1) (4) (L) is true and (L) is not true. (1), (3), Conjunction
-- (5) (L) is true. (1), (4), Reductio ad absurdum
-- (6) "(L) is not true" is true. (5), Substitution
-- (7) (L) is not true. (6), Tarski's Rule
-- (8) (L) is true and (L) is not true. (5), (7), Conjunction
The contradiction rests on no assumptions (the only assumption was
discharged by application of Reductio ad absurdum).
So one of the rules is faulty.
>Perhaps the Tarski Schema does not apply to all statements.
(Or Tarski's Rule is not validly applied to all statements, right.)
> Perhaps
>(2) is a statement of the type that the Schema does not apply to. Indeed,
>intuitively, the Tarski Schema seems to be saying that statements are true
>iff they refer to true facts (or, using your terminology, they are "founded").
>But (2) seems to refer only to itself.
Pretty much. The rule does capture some of the force behind the
'correspondence' notion of truth, but it is supposed to be weaker than a
full-blown correspondence theory.
>In fact, isn't this what Tarski invented metalanguages to explain? Surely
>(2) is just the kind of statement that Tarski would not expect his Schema to
>apply to.
Well, we are doing our reasoning in *English*. The metalanguage is
identical to the object language.
Tarski's work was all about *formal* languages, and indeed he proved that a
formal language cannot contain its own truth predicate (as long as it is
rich enough). If we were using a formal language, Tarski would say that
there is no single truth predicate that can be meaningfully applied to each
and every sentence in the language. Each sentence has a level, and there is
one truth predicate for each level, and the level of a sentence is the
level of its highest levelled truth predicate, and a truth predicate can be
applied only to sentences of a lower degree than it has itself. So (L)
could have no level, so it is not well formed.
But this is English we're talking about (and using). What are we supposed
to say? Are we going to deny any instance of Tarski's schema? Which one?
For instance, suppose we deny this one:
(T1) "(L) is not true" is true iff (L) is not true.
We could deny this in two ways: either (i) maintaining that "(L) is not
true" is true, whereas it is not the case that (L) is not true; or (ii)
maintaining that "(L) is not true" is not true, whereas (L) is not true.
(Since that is hard to parse: we either assert the left side and deny the
right side, or we assert the right side and deny the left side. That's how
we deny a biconditional.)
Do we really want to say either of those things??? Try (i). So Fred says,
HEY, (L) IS NOT TRUE!, and we say, THAT'S TRUE, FRED, AND YET, IT IS NOT
THE CASE THAT (L) IS NOT TRUE. Well, we sound like someone who doesn't
understand English. And (ii) isn't any better.
Keep in mind that the really blatant self-reference of (L) is not strictly
needed. Tarski, of course, used a kind of self reference like Godel's. And
later worked uses 'empirical self-reference', with definite descriptions
like "the only sentence written on Chris Cole's forehead on January 13th
1998, is not true." That is why I doubt the problem can be solved by ruling
out some sentences as pathological and meaningless.
-- Jamie Dreier <James_Dreier@Brown.edu>