8 ms·
Did someone get why "It cannot be that S has an even number of elements" (in the first subsection)?
by xenonite 6y ago
Did someone get why "It cannot be that S has an even number of elements" (in the first subsection)?
- ColinWright 6y agoBecause if you just add one element to the set it no longer has the property, and hence the predicate is not monotone. In more detail ... He's talking about properties (or predicates) that are monotone. That means that if P(S) is true, and T contains S, then P(T) must also be true. But when P(X) is true if and only if X has an even number of elements, then P({a,b}) would be true, but P({a,b,c}) will not be true. Then P would not be monotone.
- xenonite 6y agoGreat, thank you very much for your explanation! I now get that the sentence describes a new example predicate that is not connected to the sentence before (“S includes at least half of the elements of [n]”). This makes sense. Thank you for your thoughts.
- JadeNB 6y agoIt's worded confusingly; it certainly can be that `S` has an even number of elements. (For a silly example, if `f(S) = 1` identically, then `f(∅) = 1` even though `∅` has an even number of elements.) What cannot be is that `f(S) = 1` is equivalent to `S` having an even number of elements (because, as the sibling thread https://news.ycombinator.com/item?id=23967766 https://news.ycombinator.com/item?id=23967766 by @ColinWright points out, that is not a monotone property … unless `n = 0`!)
- xenonite 6y agoThank you a lot for your answer with a further possible interpretation, even. Indeed the wording didn’t make it clear to me this is a second example. Now it is totally clear. Thank you, it’s great to follow your thoughts!