Can you prove these are countable?

Got a great idea? Tell the world about it here.

Moderators: mvs_staff, forum_admin, Marilyn

Can you prove these are countable?

Postby davar55 » Wed Oct 07, 2015 2:22 pm

Can you prove that all infinite subsets of the counting numbers are countable?

I'd like to see your argument for (or against) this theorem.
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Re: Can you prove these are countable?

Postby JeffJo » Thu Oct 08, 2015 7:13 am

davar55 wrote:Can you prove that all infinite subsets of the counting numbers are countable?

I'd like to see your argument for (or against) this theorem.
This is a non-rigorous proof, using only concepts already present in similar threads, so that trolls won't have statements to misinterpret.

Let S be any infinite subset of the counting numbers N.

Let s(1) be the smallest number in S.

For any n in N, let s(n+1) be the smallest number in S that is greater than s(n). [1]

The function s(*) establishes a 1:1 correspondence between S and N.

QED.

+++++

[1] If there is no number in S that is greater than s(n), then S must be finite. Since S is infinite, there is such an element.
JeffJo
Intellectual
 
Posts: 2605
Joined: Tue Mar 10, 2009 11:01 am

Re: Can you prove these are countable?

Postby davar55 » Thu Oct 08, 2015 12:04 pm

Nice job. Correct and complete. Covers all the "bases."

Uses the fact that the counting numbers are an infinite set,
in that there's always an n+1 if there's an n.

It is a "rigorous" proof, up to set theory.

If someone were to ask: how can you find the smallest
element of S when it might be arbitrarily far along in
a list of the elements of S, i.e. no matter how many
elements you've seen, if you haven't seen 1 you may
not have seen the smallest? would your answer involve
set theory definitions or a computational approach?
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Re: Can you prove these are countable?

Postby JeffJo » Thu Oct 08, 2015 1:20 pm

davar55 wrote:Nice job. Correct and complete. Covers all the "bases."
Well, there are bits I could have covered more completely, than merely stating them as I did. You implied one of those:

Uses the fact that the counting numbers are an infinite set, in that there's always an n+1 if there's an n.
More accurately, the set of all integers is defined to contain n+1 if it contains n. (After all, the set of even integers is infinite but does not contain n+1 if it contains n.)

If someone were to ask: how can you find the smallest element of S when it might be arbitrarily far along in a list of the elements of S,...
Are you asking for a way to find the number in a physically existing list? The proof does not need to do that, which is one of the flaws in robert's objections. There is an algorithmic approach that is impossible to perform physically. It assumes you can answer a question about the set without needing to look at an arbitrarily large number of elements. Just ask if s(n)+1 is in the set; if not, ask about s(n)+2, then s(n)+3, etc. Since the set has infinite members, there is an eventual "yes" in a finite time (the distance between any two integers is always finite).
JeffJo
Intellectual
 
Posts: 2605
Joined: Tue Mar 10, 2009 11:01 am

Re: Can you prove these are countable?

Postby robert 46 » Fri Oct 09, 2015 10:00 am

There is a fundamental flaw in JeffJo's argument:
JeffJo wrote:Let S be any infinite subset of the counting numbers N.

Let s(1) be the smallest number in S.

This is indeterminate under the following condition:
If the smallest number in S is not the smallest possible number is S then it is impossible to determine the smallest number s(1) in S.

Assume that the smallest number in S is not 1- the smallest possible number in S. The first number found in the set S will be the tentative smallest number in S, s(1)tentative. If a smaller number is found then it will replace s(1)tentative. For as long as smaller numbers are found in S they will replace s(1)tentative, and at some point the smallest number in S will be found. However, whereas this number s(1)tentative is not 1, the entire remainder of S must be examined to confirm that there is no number smaller than s(1)tentative. Whereas S is an infinite set, it is impossible to confirm that s(1)tentative is the smallest number in S because an infinite process cannot be completed and thereby an infinite remainder cannot be checked.
For any n in N, let s(n+1) be the smallest number in S that is greater than s(n).

The function s(*) establishes a 1:1 correspondence between S and N.

The function s(n) does not return any value when the smallest number in S is not the currently smallest possible number in S because the function searches endlessly without confirmation that the smallest number has been found. Thus only if S is the entire set of counting numbers will JeffJo's method extract the numbers s(n) indefinitely.

****
davar55 wrote:Nice job. Correct and complete. Covers all the "bases."

Why ask a question if you do not have the ability to evaluate the answer?
robert 46
Intellectual
 
Posts: 2832
Joined: Mon Jun 18, 2007 9:21 am

Re: Can you prove these are countable?

Postby JeffJo » Fri Oct 09, 2015 10:16 am

See what I mean about allowing trolls to have new food?

robert 46 wrote:There is a fundamental flaw in JeffJo's argument:
JeffJo wrote:Let S be any infinite subset of the counting numbers N.

Let s(1) be the smallest number in S.

This is indeterminate under the following condition:
If the smallest number in S is not the smallest possible number is S then it is impossible to determine the smallest number s(1) in S.
How much wood would a woodchuck chuck if a woodchuck could chuck wood?

That statement makes about as much sense as yours. And you accuse me of trying to be glib?

S is a set. The numbers in it all differ by at least 1. All of its members are greater than 0. This makes it algorithmicly possible, as I described before for davar.

But it also isn't necessary, if you have have any other method of ordering the numbers. Like the one you used: "the first number found," "the next." Any order implies countability. The rationals are countable by ordering them 1,1/2,1/3,2/3,1/4,2/4,3/4,... . (You can, but don't have to, remove equivalent fractions).
JeffJo
Intellectual
 
Posts: 2605
Joined: Tue Mar 10, 2009 11:01 am

Re: Can you prove these are countable?

Postby davar55 » Fri Oct 09, 2015 12:33 pm

JeffJo wrote:...
But it also isn't necessary, if you have have any other method of ordering the numbers. Like the one you used: "the first number found," "the next." Any order implies countability. The rationals are countable by ordering them 1,1/2,1/3,2/3,1/4,2/4,3/4,... . (You can, but don't have to, remove equivalent fractions).

Getting there, but not quite.

You DO have to remove equivalent fractions or the correspondence isn't 1-1.

And by "order" you mean a sequencing, equivalent to a listing (which is just
a 1-1 correspondence with the counting numbers). Another meaning of order
is the "less than" operation on the positive reals, which is NOT a sequence order.
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Re: Can you prove these are countable?

Postby robert 46 » Fri Oct 09, 2015 3:17 pm

JeffJo wrote:S is a set. The numbers in it all differ by at least 1. All of its members are greater than 0. This makes it algorithmicly [sic] possible, as I described before for davar.

Your ploy is to deny evidence contrary to your claim, and you have done it again here- so soon. It is not "algorithmicly" [1] possible because the second step will not complete, so your method is not constructive. Try again with something sensible if you can.


[1] What JeffJo's "algorithmicly possible" means to him is that he has his own personal definition of what an algorithm is: Whatever JeffJo says is "algorithmicly" correct is "algorithmicly" correct in his own mind- never mind that it may be false for others who can think rationally.
robert 46
Intellectual
 
Posts: 2832
Joined: Mon Jun 18, 2007 9:21 am

Re: Can you prove these are countable?

Postby JeffJo » Sat Oct 10, 2015 5:12 am

davar55 wrote:You DO have to remove equivalent fractions or the correspondence isn't 1-1.
Sorry; I didn't mean to imply that was the 1:1 correspondence. I was just trying to give the troll less ammunition.

The set of symbols {"1","1/2","1/3","2/3","1/4","2/4","3/4",...} is countable. The set of unique rational numbers, which corresponds to a subset of it, is therefore also countable. How you might "find" the duplicates is irrelevant this way.

And by "order" you mean a sequencing,
Yep.
JeffJo
Intellectual
 
Posts: 2605
Joined: Tue Mar 10, 2009 11:01 am

Re: Can you prove these are countable?

Postby JeffJo » Sat Oct 10, 2015 5:16 am

robert 46 wrote:Your ploy is to deny evidence contrary to your claim.
What "evidence?" Any such "evidence" that it can't be found suffers from the exact same problem you claim exists here. You can't claim it isn't found, either, until everything is searched. Both are suppositions based on trying to treat the infinite as finite, and neither is relevant.

It is not "algorithmicly" [1] possible because the second step will not complete.
Yes, it is. There is an integer which is smaller than any other in the set. All I need to show is its existence, not where it is in the set.

  1. Is there a (finite) integer s1 that is less than any other integer in the set? Yes, there must be.
  2. Is there any reason I can't call it s1 without knowing its value, or where[1] it is in the set? No.
  3. Is there a (finite) integer s2 that is greater than s1 but less than any other integer in the set? Yes, there must be.
That's all that is needed.

If you don't like this universally-accepted method, go found your own branch of mathematics. This one is valid.

+++++

[1]The fact that you claim there is a position for every number provides another way to order the set, and proves the same thing. You carefully avoiding quoting that part of what I wrote before, which is your "ploy."
JeffJo
Intellectual
 
Posts: 2605
Joined: Tue Mar 10, 2009 11:01 am

Re: Can you prove these are countable?

Postby robert 46 » Sat Oct 10, 2015 9:15 am

JeffJo wrote:
robert 46 wrote:Your ploy is to deny evidence contrary to your claim.
What "evidence?" Any such "evidence" that it can't be found suffers from the exact same problem you claim exists here. You can't claim it isn't found, either, until everything is searched. Both are suppositions based on trying to treat the infinite as finite

So who is trying to apply an algorithm which works in the finite case to the infinite case where it doesn't work by treating infinity as if it was a finite value???
robert 46
Intellectual
 
Posts: 2832
Joined: Mon Jun 18, 2007 9:21 am

Re: Can you prove these are countable?

Postby JeffJo » Sat Oct 10, 2015 12:57 pm

robert 46 wrote:So who is trying to apply an algorithm which works in the finite case to the infinite case where it doesn't work by treating infinity as if it was a finite value???
Who needs to "apply" it? If describes what you need, while proving it exists.

Tell me, can you "find" all the even integers? If you can't, then how do you know they exist?

The algorithm e(n) = 2*n describes every element that must exist in the set, with all the properties necessary. Nobody needs to "apply" it.

Can you "find" all of the differences that prove 1/2+1/4+1/8+...=1? Can you "find" the end of these differences? If you can't, does that mean the sum isn't 1?

These examples constitute direct evidence that your insistence on finding such things is just another ploy you use to keep arguing. But I'm sure you will ignore this direct evidence, just like you ignore all evidence against you.

Why don't you try directing your insatiable energy to the simple proof I presented for you, in good faith?
JeffJo
Intellectual
 
Posts: 2605
Joined: Tue Mar 10, 2009 11:01 am

Re: Can you prove these are countable?

Postby davar55 » Sat Oct 10, 2015 7:32 pm

This is intended to be supportive:

"Is there a (finite) integer s1 that is less than any other integer in the set? Yes, there must be."

You said the proof wasn't rigorous.
He basically said there's no terminating algorithm that would always produce s1.

Can you expand on this quoted claim to solidify this point? i.e.

Prove that any subset of the counting numbers has a smallest element.

It sounds trivial, but perhaps it isn't.
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Re: Can you prove these are countable?

Postby JeffJo » Sun Oct 11, 2015 6:49 am

davar55 wrote:Prove that any subset of the counting numbers has a smallest element.

It sounds trivial, but perhaps it isn't.
Yes, it is, but you have to treat the set as in infinite entity, not a finite one. That means, as I said before, that you can test a property ("is there an element that fits a finitely-identified description") of the whole set.[1]

Every finite number is finite, and every counting number is greater than 0.

Let n=1 and a(1) be any member of your S.

If there is a member of S in [1,a(n)-1], then let a(n+1) be that number and n=n+1. Repeat. If not, end.

This will terminate within a(1) steps, with a(n) being the smallest element.

BUT, you are also ignoring a point. This isn't a computer science issue. Terminating isn't the important thing. Existence is the only question.

There is a finite element s(1) of S. There are a finite number of elements between 1 and s(1), inclusive. One of them is smaller than all the others.

Robert's methodology is to try to make himself sound superior to anybody else in this forum. He does it by raising irrelevant objections to anything anybody else says. If they are responded to, he ignores the response by either adding new irrelevancies, or obfuscating the ones he has stated already until they are so ambiguous you can't make him budge. Then he repeats those indefinitely.

Here, his indefinite point is that you can only approach infinite sets by "finding" whatever you need in them. He is wrong. All you need to do, in the proof you asked for, is demonstrate that there must be a minimum value within any range. I have.

+++++

[1] It is only if you have to look through the entire set element-by-element to test the property - that is, treat it like you would a finite entity - that you can't be sure you will find anything matching it.

But then, as robert ignores, the element-by-element list serves the purpose that finding the minimum did in my proof.
JeffJo
Intellectual
 
Posts: 2605
Joined: Tue Mar 10, 2009 11:01 am

Re: Can you prove these are countable?

Postby davar55 » Mon Oct 12, 2015 2:38 am

This too is intended to be supportive:

"...you have to treat the set as in infinite entity, not a finite one. That means, as I said before, that you can test a property ("is there an element that fits a finitely-identified description") of the whole set."

You CAN test the property, for a given n in N, whether n is in S
(by the set theoretical definition of S being a subset of N).
This is a closure property on finite OR INFINITE sets that must
be accepted as an axiom of set theory.

Hence you CAN use the property "There is a finite element s(1) of S"
(since S is non-empty since S is an infinite set).

So you CAN say "There are a finite number of elements in S between 1 and s(1), inclusive"
because you can examine each one in that range (from N) and determine if it is in S.

So "One of them is smaller than all the others" because this is a finite set of
comparable (commensurate) numbers.

I trust these additional "details" will help your proof's rigor.
davar55
Intellectual
 
Posts: 728
Joined: Tue Jun 13, 2006 4:24 pm
Location: New York City

Next

Return to Great Ideas

Who is online

Users browsing this forum: No registered users and 2 guests

cron