Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Donation Acolyte
    Now With Added BA
    23 Sep '03 14:53
    In each case, I will define a set of statements (though in some cases the definition may be paradoxical, in which case you should point this out). What can you say for certain about the veracity of the statements?

    A: consists of the elements 1 to 5, where n is the statement 'At most n elements of A are true.'

    B: consists of the elements 1 to 6, where n is the statement 'At most n elements of B are true.'

    C: consists of the elements 1,2,3,4,.... , where n is the statement 'At most n elements of C are true.'

    D: consists of the elements 1 to 5, where n is the statement 'At most n elements of D are false.'

    E: consists of the elements 1,2,3,4,.... , where n is the statement 'At most n elements of E are false.'

    Note: If resident logicians find these too easy, then please give others a chance to answer before you jump in.
  2. Standard member TheMaster37
    Kupikupopo!
    23 Sep '03 19:19
    Originally posted by Acolyte
    In each case, I will define a set of statements (though in some cases the definition may be paradoxical, in which case you should point this out). What can you say for certain about the veracity of the statements?

    A: consists of the elements 1 to 5, where n is the statement 'At most n elements of A are true.'

    B: consists of the elements 1 to 6, wher ...[text shortened]... nt logicians find these too easy, then please give others a chance to answer before you jump in.
    A:
    Let's say 1 is true. Because of the statement, that's the only statement that's true. So 5 is false, wich means there are more then five statements true. This is a contradiction, since there are only five statements. So 1 is false, and we just saw that 5 cannot be false. Four cannot be false either, since that would mean there are more then four statements true, and 1 is false. At this point, 3 cannot be false, because then we'd need more then three true statements. Now, if 3 is true then 2 has to be false, because when 3 is true, you have more then two statements true. 1F 2F 3T 4T 5T
  3. Standard member TheMaster37
    Kupikupopo!
    23 Sep '03 19:29
    Originally posted by Acolyte
    B: consists of the elements 1 to 6, where n is the statement 'At most n elements of B are true.'
    B:
    Same start as just now. 1F and 6T. Because of 1F, 5 has to be true. Now 4 has to be true as well. Now suppose 3T, then that means there are at most three true statments...contradiction, since 3,4,5 and 6 are true. If 3 is false however, that means there are more then three statements true, wich means 2 has to be true. That means there are at most 2 true statements, wich is also a contradiction. PARADOX
  4. Standard member TheMaster37
    Kupikupopo!
    23 Sep '03 19:38
    Originally posted by Acolyte
    C: consists of the elements 1,2,3,4,.... , where n is the statement 'At most n elements of C are true."
    I'll leave the other two for the others, i am jsut curous about this one too. 1F still applies. In fact, as soon as a statement is true, you have a limited number of true statements in the sequence, let's say N. Let's say M is the last true statement in the sequence. After that all statements must be false...and that means there are more then M statements are true (since M+1 is false). But since M is the last true statement we have a contradiction. This means that none of the statements can be true. Wich leads to a contradiction, because then we'd have there are more then 1, 2, 3, 4, ... statements true. PARADOX
  5. Donation Acolyte
    Now With Added BA
    23 Sep '03 20:18
    Correct! How about a more general puzzle:

    Call a set 'paradoxical' if it is not possible to consistently assign 'true' and 'false' to each element of the set (like B and C above.) Call it 'indeterminate' if there is more than one way to assign 'true' and 'false' consistently.

    Consider the set S, consisting of elements 'at most n elements of S are true,' where n ranges over some subset T of the natural numbers. For what subsets T is S
    (a) Paradoxical?
    (b) Indeterminate?

    Now try the same for S', which consists of elements 'at most n elements of S' are false.'
  6. Standard member TheMaster37
    Kupikupopo!
    23 Sep '03 20:47
    Originally posted by Acolyte
    Correct! How about a more general puzzle:

    Call a set 'paradoxical' if it is not possible to consistently assign 'true' and 'false' to each element of the set (like B and C above.) Call it 'indeterminate' if there is more than one way to assign 'true' and 'false' consistently.

    Consider the set S, consisting of elements 'at most n elements ...[text shortened]...

    Now try the same for S', which consists of elements 'at most n elements of S' are false.'
    Alright! Thank you for that puzzle! I'm defenitely looking forward in breaking my head over that one I see now that i can't do it with simply starting to write
  7. Standard member royalchicken
    CHAOS GHOST!!!
    23 Sep '03 21:17
    Originally posted by Acolyte
    Correct! How about a more general puzzle:

    Call a set 'paradoxical' if it is not possible to consistently assign 'true' and 'false' to each element of the set (like B and C above.) Call it 'indeterminate' if there is more than one way to assign 'true' and 'false' consistently.

    Consider the set S, consisting of elements 'at most n elements ...[text shortened]...

    Now try the same for S', which consists of elements 'at most n elements of S' are false.'
    Well, I assume that in case C you meant that there are more than 5 elements, since A is consistent. In general, a set with 1,2,3,4,5,6,... is paradoxical if 1 is true. Furthermore, there must only be a finite number of true statements, as TheMaster37 said. So let's rehash what he said (quite well).

    If we're looking at the statements 1,2,3,4,5,6...,K, then 1 must be false. Furthemore, if K is false, then they all are, which would be impossible. So K is true. Since 1 is false, there must be another true statement. This cannot be 2, because then each of the intervening statements would then be true, making 2 false. So K-1 is also true. Now to make 2 false, we need another, et cetera. Thus a set of this type can only work if |K-2-1| = 2, or K = 5 or 1.

    <<Eating........actual attention to the problem at hand to follow>>
  8. Standard member royalchicken
    CHAOS GHOST!!!
    23 Sep '03 23:16 / 2 edits
    There is no indeterminate set.

    Let's proceed by induction on the number of elements in the set (< = the largset element). If there is one element, then if it is true we have no trouble, but if it is false, then there is a contradiction since a set with all elements false contains at most one true element. Thus all 1-element sets of this type are determinate.

    Assume all N-1 element sets of this type are determinate. Now we need to show that each N-element set is determinate. Suppose an N-element set has largest element N. Then as we have said, it is paradoxical, and thus not indeterminate. Suppose now that the largest element is M>N. If some K<M is the smallest true statement in the set, then each of K, ..., M in the set is true as well, regardless of the structure of the set.

    (Eg if the set is 1,4,6,11,15 and 4 is true, then 6, 11 and 15 are as well. This set is not paradoxical, nor is it indeterminate.)

    If the number of true statements after K is <=K, then the set is not paradoxical.

    Now finally note that by our induction hypothesis, the set identical to the first N-1 elements of the N-element set in question is determinate. Suppose that there is some K in the set such that K elements of the set are >=K. Then since it is a determinate N-1 element set, and the distribution of truth in which K and all subsequent elements are true, and all prior ones false, we conclude that this distribution is the only one possible. By adding an Nth element after K, this distribution fails because there are K+1 elements larger than or equal to K, but since K<K+1, we cannot assign truth to each of these and falsehood to the predecessors without being paradoxical. If we add the Nth element before K, then we can call K onward true and the rest false as before, but this can still only be accomplished in one way. Thus there are no indeterminate sets.

    Sets are paradoxical if and only if there is no K in the set less than or equal to the total number of elements after it.

    There may be some errors there; I have to reread it.
  9. Donation Acolyte
    Now With Added BA
    24 Sep '03 07:57
    Originally posted by royalchicken
    Sets are paradoxical if and only if there is no K in the set less than or equal to the total number of elements after it.
    This doesn't sound right. What about T = 3,4,5 and T = 2,3,4 ?
  10. Standard member royalchicken
    CHAOS GHOST!!!
    24 Sep '03 12:10 / 2 edits
    Originally posted by Acolyte
    This doesn't sound right. What about T = 3,4,5 and T = 2,3,4 ?
    3T, 4T, 5T. This set contains three true statements, rendering it non-paradoxical, since it contains at most 4 and 5 true statements. It also contain K=3 that is eequal to the number of statements after it. 2,3,4 is paradoxical.

    My bicondition about paradoxical sets is wrong. However, it is also different from my first claim about paradoxical sets, so what do you think of my conclusion about indeterminate sets?
  11. Standard member royalchicken
    CHAOS GHOST!!!
    24 Sep '03 13:50 / 1 edit
    So which of these claims is correct?

    1. A set containing all natural numbers less than or equal to some N is paradoxical unless N=5 or 1
    2. For any non-paradoxical set, if K is a true statement, then any M>K is also true
    3. If a set is non-paradoxical, and M>K for some false statement M, then K is false. Thus in any non-paradoxical set of natural numbers, the falses are grouped together before the trues.
    4. If a set is non-paradoxical, there is some K in the set that is the smallest true statement.
    5. By 3 and 4, K is greater than or equal to the total number of elements greater than or equal to K (in a non-paradoxical set). In your examples, 3 serves that purpose in the first, while there is no smallest true statement in the second.


    "If the number of true statements after K is <=K, then the set is not paradoxical."

    This should read: "If the set is not paradoxical, then the number of true statements after and including K is <=K."

    This gives us no good information about why a set is paradoxical, though. In your example, 2;3;4, note that if we have such a K, namely 3. But the previous statement would also have to be true, since there are only two subsequent ones.

  12. Standard member TheMaster37
    Kupikupopo!
    24 Sep '03 19:09
    I think the set E in the first post in indeterminable. If there is no false statement, then all elements from E are true, eich sounds good to me.

    If they are all false, then they all say there need to be more false statements, wich is fine, since we have infinitely many elements.

    As for a general subset S of the integers, for the statements about truth of statements..

    If S has infinitely many elements we get a paradox:
    Suppose that at least one statement is true
    Then there is only a finite subsubset of true statements,
    and let's say that N is the largest of them.
    With a finite set of true statments, there must be infinitely many
    false statements. One of them is larger then N, wich would mean
    there are more then N+1 true statements. Contradiction.
    Suppose none of the statements are true. That means that every
    statement implies that there are true statements. Contradiction.

    Now we're left with the case that S contains a finite number of elements.

    You easily see that not all statements can be true, and not all statements can be false.

    If S contains 1 element then it must be true.

    Say that the number of elements in S is M (#S=M), with M > 1
    We can now number all elements in S in order of magnitude.
    name them S1, S2, ..., S(M-1), SM.

    Since #S =< SM, SM has to be true. Suppose S(M-1) is false.
    If #S-1 < S(M-1) then we get a contradiction with the number of elements in S. And if #S-1=S(M-1) we get a contradiction with the fact that all other statements must be true. So S(M-1) is true as well.

    Now look at the largest number SI wich is false(this cannot be S(M-1) or SM). All numbers SJ with J > I must be true then. SI false implies that there are more then SI true statements. This automatically means that all SK with K<I must be false. So for S we get this form:

    S1 F, S2 F, ..., SI F, S(I+1) T, ..., S(M-1) T, SM T

    That is where I decided to get some sleep for the day. Thanks for giving me something to do in the train!
  13. Donation Acolyte
    Now With Added BA
    24 Sep '03 19:53
    Originally posted by royalchicken
    So which of these claims is correct?

    1. A set containing all natural numbers less than or equal to some N is paradoxical unless N=5 or 1
    2. For any non-paradoxical set, if K is a true statement, then any M>K is also true
    3. If a set is non-paradoxical, and M>K for some false statement M, then K is false. Thus in any non-paradoxical set of natural ...[text shortened]... the previous statement would also have to be true, since there are only two subsequent ones.

    Statement 1 is false, though it doesn't have much to do with the other statements.

    "If the set is not paradoxical, then the number of true statements after and including K is <=K."

    This follows immediately from the truth of K. It doesn't help you find K, though. In fact, while K clearly exists for non-paradoxical sets, I don't think it's a particularly helpful concept. Why, for example, is 1,3,10,11,12 paradoxical, whereas 1,2,10,11,12 and 1,4,10,11,12 are not? I think I understand what's going on in the 'at most... true' case, but as problem-setter I should probably wait for others to answer it.
  14. Standard member royalchicken
    CHAOS GHOST!!!
    24 Sep '03 20:55 / 2 edits
    Originally posted by TheMaster37
    I think the set E in the first post in indeterminable. If there is no false statement, then all elements from E are true, eich sounds good to me.

    If they are all false, then they all say there need to be more false statements, wich i ...[text shortened]... ep for the day. Thanks for giving me something to do in the train!
    I meant "there are no indeterminate sets where the nth statement is that there are at most n true statements". I am fairly certain that this is the case.

    "S1 F, S2 F, ..., SI F, S(I+1) T, ..., S(M-1) T, SM T"

    This is essentially what I said before, although you have introduced a much more convenient notation. But what can you deduce from this?

    Acolyte:

    <<SEE EDIT BELOW>>Give an example of some N not equal to 1 or 5 such that {1,2,3,4,5,6,....N} is not paradoxical.<<SEE EDIT BELOW>>

    Also, my other posts were mainly related to the fact that there are no indeterminate sets of this form. My 'condition' for paradox was no condition at all, but it does help in proving the previous bit.

    The end of my last post was very unclear because the bell rang and I had to go to class.

    EDIT As regards my first request to you, say we've got the set 1,2,3,...K. Say the first true statement is L<K. So L,L+1,...K are true, and 1,2,...L-1 are false. We have K-L+1 true statements, and L-1 false ones. Since L - 1 is false, L = (K+1)/2. So indeed any odd K will do the trick. For example, 1F, 2T, 3T is consistent, as is 1F, 2F, 3F, 4T, 5T, 6T, 7T. I don't know where my "assertion 1" came from.
  15. Standard member royalchicken
    CHAOS GHOST!!!
    25 Sep '03 01:20 / 1 edit
    Originally posted by Acolyte
    It doesn't help you find K, though. In fact, while K clearly exists for non-paradoxical sets, I don't think it's a particularly helpful concept. Why, for example, is 1,3,10,11,12 paradoxical, whereas 1,2,10,11,12 and 1,4,10,11,12 are n ...[text shortened]... as problem-setter I should probably wait for others to answer it.
    Okay. On second thought:

    No set of this type is indeterminate.

    A set of this type with N elements, and the ith element being si, is paradoxical if and only if there is some si = N-i.

    (Note that the last also works with the business about {1,2,3,4,...2k} being paradoxical since 2k-k = k, and {1,2,3,4,...k+1} being consistent since 2k+1-k = k+1. In your examples, 2,3,4 is paradoxical since 3-1=2. Or, for example, 2,5,6,7,11 is consistent with 5 onwards being true.)

    Am I wrong?