## Can you prove these are countable?

**Moderators:** mvs_staff, forum_admin, Marilyn

23 posts
• Page

**1**of**2**•**1**, 2### Can you prove these are countable?

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.

I'd like to see your argument for (or against) this theorem.

- davar55
- Intellectual
**Posts:**726**Joined:**Tue Jun 13, 2006 4:24 pm**Location:**New York City

### Re: Can you prove these are countable?

This is a non-rigorous proof, using only concepts already present in similar threads, so that trolls won't have statements to misinterpret.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.

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:**2551**Joined:**Tue Mar 10, 2009 11:01 am

### Re: Can you prove these are countable?

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?

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:**726**Joined:**Tue Jun 13, 2006 4:24 pm**Location:**New York City

### Re: Can you prove these are countable?

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

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.)Uses the fact that the counting numbers are an infinite set, in that there's always an n+1 if there's an n.

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).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,...

- JeffJo
- Intellectual
**Posts:**2551**Joined:**Tue Mar 10, 2009 11:01 am

### Re: Can you prove these are countable?

There is a fundamental flaw in JeffJo's argument:

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.

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.

****

Why ask a question if you do not have the ability to evaluate the answer?

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:**2761**Joined:**Mon Jun 18, 2007 9:21 am

### Re: Can you prove these are countable?

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

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).

How much wood would a woodchuck chuck if a woodchuck could chuck wood?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.

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:**2551**Joined:**Tue Mar 10, 2009 11:01 am

### Re: Can you prove these are countable?

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:**726**Joined:**Tue Jun 13, 2006 4:24 pm**Location:**New York City

### Re: Can you prove these are countable?

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:**2761**Joined:**Mon Jun 18, 2007 9:21 am

### Re: Can you prove these are countable?

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

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.

Yep.And by "order" you mean a sequencing,

- JeffJo
- Intellectual
**Posts:**2551**Joined:**Tue Mar 10, 2009 11:01 am

### Re: Can you prove these are countable?

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.robert 46 wrote:Your ploy is to deny evidence contrary to your claim.

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.It is not "algorithmicly" [1] possible because the second step will not complete.

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

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:**2551**Joined:**Tue Mar 10, 2009 11:01 am

### Re: Can you prove these are countable?

JeffJo wrote: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 finiterobert 46 wrote:Your ploy is to deny evidence contrary to your claim.

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:**2761**Joined:**Mon Jun 18, 2007 9:21 am

### Re: Can you prove these are countable?

Who needs to "apply" it? If describes what you need, while proving it exists.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???

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:**2551**Joined:**Tue Mar 10, 2009 11:01 am

### Re: Can you prove these are countable?

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.

"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:**726**Joined:**Tue Jun 13, 2006 4:24 pm**Location:**New York City

### Re: Can you prove these are countable?

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]davar55 wrote:Prove that any subset of the counting numbers has a smallest element.

It sounds trivial, but perhaps it isn't.

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:**2551**Joined:**Tue Mar 10, 2009 11:01 am

### Re: Can you prove these are countable?

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.

"...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:**726**Joined:**Tue Jun 13, 2006 4:24 pm**Location:**New York City

23 posts
• Page

**1**of**2**•**1**, 2### Who is online

Users browsing this forum: No registered users and 3 guests