Today in my A. Calc class, my professor gave us a diagnostic quiz for logic, and this is how I remember one of the questions. When I get it back I'll make it verbatim, but I can't help but think that I must be interpreting this wrong.

Let S be a subset of N. Show that there exists an r in N such that if r is in S, then S=N.

His proof made little sense to me, and he said it involved the law of the excluded middle. I understand the law of excluded middle, at least in principle, but I certainly didn't understand that. It seems to me like { r } ~= N is a clear counterexample.

One of my officemates gave this solution (this IS verbatim):

S is nailed down first.

r is chosen second.

We can use knowledge of S to pick r.

We can't use knowledge of [r] to pick S.

Try: Let r = min{N\S}

If r exists, r is in S implies that S = N

("r is in S" is always false. "r is in S implies that S = N" is always true.)

If r does not exist, set r=1/2.

r in S implies that S = N.

("r in S" is false, "r in S implies that S = N" is true.)

I have a problem with this starting from the first line, because I don't think that "S is nailed down first" makes any sense.

The very last thing makes sense, because if r does not exist then N\S must be the empty set. But I don't understand the line that "If r exists, r is in S implies that S = N." The statement is vacuously true, but that doesn't mean that the conclusion is true.

Like I said, when I get the question verbatim, I'll post it here, but does anybody have any idea of how to clarify this?