S subset N, exists an r in N such that if r in S then S=N

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

adanedhel728
Posts: 52
Joined: Sat Nov 07, 2009 11:03 pm UTC
Location: Central U.S.

S subset N, exists an r in N such that if r in S then S=N

Postby adanedhel728 » Fri Aug 23, 2013 8:14 pm UTC

Sorry for the weird title.

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?

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: S subset N, exists an r in N such that if r in S then S=

Postby DavCrav » Fri Aug 23, 2013 8:49 pm UTC

The first line says: let S be a subset of N, so you have a fixed subset before you start. It's the difference between the two sentences:

1) For any number x, there is a number y such that y is larger than x.
2) There is a number y such that, for any number x, y is larger than x.

Since S is chosen to begin with, if S is not N, let r be any element of N\S, and if S=N then let r be any element of N.

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby fishfry » Fri Aug 23, 2013 9:00 pm UTC

[math][/math]
adanedhel728 wrote: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.



Oh I get it. It's a logic issue relating to vacuous implication. That is: FALSE implies TRUE. If 2 + 2 = 5 then I am the Pope.

So. Suppose S is a proper subset of N. And here N is an arbitrary set, it doesn't even have to be the natural numbers. If S is a proper subset, there exists x element-of N but x not-element-of S.

[sorry can't figure out the markup on this board. help please. tried math and imath tags with latex markup, didn't work.]

Now consider the proposition: There exists x such that IF x is in S, THEN the moon is made of cheese.

Well, there IS such an x: namely our x from above. We already know that x not-element-of S.

So *IF* x element-of S, then the moon is made of cheese and S = N. That's because x not-element-of S. So if x element-of S, the antecedent is a contradiction, hence it's false, hence the implication is true!!

On the other hand, suppose that S is not a proper subset of N. Then S = N. So again the implication is true.

This is a logic problem, not a math problem. It has nothing to do with properties of numbers. And it's weird but valid.

(ps) I see DavCrav already said this using fewer words :-)

Tmabbbb
Posts: 7
Joined: Sun May 17, 2009 9:47 pm UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby Tmabbbb » Fri Aug 23, 2013 9:26 pm UTC

Similarly, in any bar there exists a person such that if they are drinking, then everybody is drinking.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: S subset N, exists an r in N such that if r in S then S=

Postby DavCrav » Fri Aug 23, 2013 10:09 pm UTC

This sort of thing is OK in a nice set like the natural numbers, but suppose we replace N by R. Now this sentence becomes a bit more interesting. Let S be the subset of all definable numbers. This can mean definable in *any way*: by computer programs, by algorithms, using words, anything reasonable. I claim that S is countable, and that might put a little bit of a restriction on what I mean by "reasonable", but pick your favourite.

Since S is countable, S is not equal to R. But there is no element of R\S that can be defined, so you have to be a little tricksy when it comes to making statements like that.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby Qaanol » Fri Aug 23, 2013 11:47 pm UTC

Tmabbbb wrote:Similarly, in any bar there exists a person such that if they are drinking, then everybody is drinking.

And in every non-empty hospital there exists a person such that if they survive the night, then everybody in the hospital survives the night.
wee free kings

Moole
Posts: 93
Joined: Sun Jan 08, 2012 9:52 pm UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby Moole » Sat Aug 24, 2013 3:45 am UTC

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.


You could rephrase that as (replacing the last clause with its contrapositive):

For any subset S of N, there exists an r such that, if S=/=N then r isn't in S


Then, moving the phrase "if S=/=N" earlier (it doesn't depend on r anyways):

For any subset S of N, if S=/=N there exists an r such that r isn't in S


And making this pretty:

For any proper subset S of N, there exists an r in N but not in S
Mathematical hangover (n.): The feeling one gets in the morning when they realize that that short, elementary proof of the Riemann hypothesis that they came up with at midnight the night before is, in fact, nonsense.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby korona » Sat Aug 24, 2013 12:50 pm UTC

DavCrav wrote:This sort of thing is OK in a nice set like the natural numbers, but suppose we replace N by R. Now this sentence becomes a bit more interesting. Let S be the subset of all definable numbers. This can mean definable in *any way*: by computer programs, by algorithms, using words, anything reasonable. I claim that S is countable, and that might put a little bit of a restriction on what I mean by "reasonable", but pick your favourite.

Since S is countable, S is not equal to R. But there is no element of R\S that can be defined, so you have to be a little tricksy when it comes to making statements like that.

That is not correct.
1) Definable in "any way" is not well defined. The best you could do is: Let S be the set of all c so that there is a predicate P (in your favorite theory, let's say ZFC) so that there exists an x in R so that P(x) and P(x) implies x = c. This set is indeed well defined and countable.
2) Using restricted comprehension and the AoC we can still extract an element x from R\S. This does not imply that there is a predicate that uniquely determines x.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: S subset N, exists an r in N such that if r in S then S=

Postby DavCrav » Sat Aug 24, 2013 4:24 pm UTC

korona wrote:
DavCrav wrote:This sort of thing is OK in a nice set like the natural numbers, but suppose we replace N by R. Now this sentence becomes a bit more interesting. Let S be the subset of all definable numbers. This can mean definable in *any way*: by computer programs, by algorithms, using words, anything reasonable. I claim that S is countable, and that might put a little bit of a restriction on what I mean by "reasonable", but pick your favourite.

Since S is countable, S is not equal to R. But there is no element of R\S that can be defined, so you have to be a little tricksy when it comes to making statements like that.

That is not correct.
1) Definable in "any way" is not well defined. The best you could do is: Let S be the set of all c so that there is a predicate P (in your favorite theory, let's say ZFC) so that there exists an x in R so that P(x) and P(x) implies x = c. This set is indeed well defined and countable.
2) Using restricted comprehension and the AoC we can still extract an element x from R\S. This does not imply that there is a predicate that uniquely determines x.


1) Hence "anything reasonable", and my clarification of what I mean, giving examples, e.g., algorithms. Most standard methods of generating numbers can only generate countably many numbers.

2) The axiom of choice is like magic, in that you can invoke it to do things that are both reasonable and unreasonable. The axiom of choice and statements about definability don't mix well. You cannot assume choice and simultaneously talk about algorithms, like I did, otherwise you get weird stuff happening, like there being uncountably many algorithms. Choice is best suited to those times when you want to know things exist without actually being able to produce one. Since I was talking about actual stuff, rather than pretend mathsy nonsense, choice has no place.

Edit: At any rate, what you said does not contradict what I said. I said you had to be more tricksy in the uncountable case: you said you needed restricted comprehension and the AoC. I don't see how they are different,

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby fishfry » Sat Aug 24, 2013 7:38 pm UTC

korona wrote:2) Using restricted comprehension and the AoC we can still extract an element x from R\S. This does not imply that there is a predicate that uniquely determines x.


You do not, repeat you do NOT, require AC to choose an element from a nonempty set. As a pure example of the issues you are concerned about, let X = the set of undefinable reals. Since that set is nonempty, I can choose an undefinable real x. No Choice is needed. I agree with you that such a choice is not uniquely determined, nor is it definable by a predicate. Those issues are not relevant. I can still choose an element from a nonempty set.

You only need Choice when you want to make infinitely many simultaneous choices from nonempty sets in circumstances where you can't uniquely characterize the choice made from each set.

In other words if I have countably many well-ordered nonempty sets I can choose the smallest element from each without Choice. But if I have countably many arbitrary nonempty sets, I need AC to choose an element from each. [This is the famous example of needing Choice to choose one member of each of infinitely many pairs of socks; but not needing Choice to choose one member of each of infinitely many pairs of shoes.]

But if I only have one nonempty set, I can always choose an element from it without the need for Choice.

adanedhel728
Posts: 52
Joined: Sat Nov 07, 2009 11:03 pm UTC
Location: Central U.S.

Re: S subset N, exists an r in N such that if r in S then S=

Postby adanedhel728 » Sat Aug 24, 2013 8:05 pm UTC

Well, I kinda/sorta get it now, both from this and from a description that another officemate gave me. It caused quite a discussion in the department lounge yesterday.

Thanks everyone, I appreciate it.

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby fishfry » Sat Aug 24, 2013 9:23 pm UTC

DavCrav wrote:2) The axiom of choice is like magic


Actually what's magic here is the universal quantifier. I believe that's at the heart of the issue.

The universal quantifier is able to quantify over uncountable sets. So when we say, "For every real number x ..." we are specifically referencing each and every real number ... including the uncomputable and the undefinable ones.

I believe this is essentially a matter of philosophy. When computer scientists say "for all" they are secretly thinking of a for-loop that never terminates. In other words they're thinking of the counting numbers 1, 2, 3, ...

But mathematicians have a much more general understanding of "for all." They have no problem quantifying over uncountable sets; and they have no requirement that an entity be definable by a finite string of symbols.

There is a huge amount of philosophical magic hidden in the universal quantifier. If I say that proposition P is true for all real numbers, I am saying P(x) for every possible real number x ... even the ones that I could never define or characterize with an algorithm or any finite string of symbols.

I often think this is a bit of sleight-of-hand. For example in calculus we abolish infinitesimals by saying "For All epsilon > 0 there exists a delta ..." to define the idea of continuity. But that "For All" is quantifying over an uncountable set. It's a "conservation of philosophical mystery" principle. We abolish infinitesimals by quantifying over uncountable sets. We haven't really explained anything, just transferred the mystery.

Anyway I do think that we often fail to give due respect to the awesome power of the universal quantifier. It lets us quantify over uncountable sets, most of whose members we could never name. That's a lot of power ... use it wisely! :-)

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby korona » Sat Aug 24, 2013 11:31 pm UTC

fishfry wrote:But if I only have one nonempty set, I can always choose an element from it without the need for Choice.

You are right of course. I don't know why I was thinking about the AoC at all when I wrote the post.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: S subset N, exists an r in N such that if r in S then S=

Postby DavCrav » Sun Aug 25, 2013 12:42 am UTC

fishfry wrote:
DavCrav wrote:Anyway I do think that we often fail to give due respect to the awesome power of the universal quantifier. It lets us quantify over uncountable sets, most of whose members we could never name. That's a lot of power ... use it wisely! :-)


Luckily I rarely have to invoke uncountable anything in my research, so only when teaching those pesky students with their products of compact spaces and their absolute Galois groups.

Oh, and while you don't need choice to prove existence, it does help in producing a canonical choice. Simply take a well ordering on R and take the smallest element of R\S. There is a distinction between asserting the existence of (say) undefinable numbers, which can be done inside ZF, and writing them down, which cannot. I have a certain problem with saying that I can prove that it exists although I can never produce it. How very quantum.

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: S subset N, exists an r in N such that if r in S then S=

Postby fishfry » Sun Aug 25, 2013 9:02 pm UTC

DavCrav wrote:Oh, and while you don't need choice to prove existence, it does help in producing a canonical choice. Simply take a well ordering on R and take the smallest element of R\S.


I am not following that. Doesn't "canonical" mean that any two properly trained mathematicians would pick the same item? Like the canonical basis for R^3 or the canonical homomorphism from Z to Z/5Z.

In this case, no well-ordering of the reals is definable. Nobody's ever seen one and nobody ever will. We just know that it exists; or rather, that its existence is logically equivalent to AC.

How can you say that you are using AC to choose a canonical element of an arbitrary nonempty set, using the standard meaning of "canonical?"

Can you produce a canonical element of the open unit interval? Sure, there's a well-ordering that starts with 1/2, another that starts with 1/pi. But which is canonical? Which is specific?


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests