/sci/ - Science & Math » Thread #11291277

45KiB, 617x250, Step 2.png

View Same Google iqdb SauceNAO

Circular proof in my lecture notes

Anonymous Fri 10 Jan 13:49:09 2020 No.11291277 View Reply Original Report

Quoted By: >>11291287

This proof is in the lecture notes provided by my university.

Isn't the highlighted part circular? This proof is trying to show that an infinite subset of a countably infinite set has the same cardinality as a countably infinite set, but if there existed an infinite set smaller than countable infinity then this proof wouldn't catch it.

Am I wrong or is there some better proof for this?

Anonymous

Anonymous Fri 10 Jan 2020 13:59:03 No.11291287 Report

Quoted By: >>11291307

>>11291277
That's a shit way of writing something very important. The point is, if you give me any natural number i, the sequence has an ith number because the sequence is not finite. So a_i exists and f(a_i) = i. Since we can take i to be any natural number, the image of f is N, and f is onto.

Anonymous

Anonymous Fri 10 Jan 2020 14:10:46 No.11291307 Report

Quoted By: >>11291309 >>11291312

>>11291287
>if you give me any natural number i, the sequence has an ith number because the sequence is not finite

This is the circularity I was talking about. Your statement only holds true if countable infinity is the smallest infinity. If A was not finite but also |A| < |N|, then there wouln't necessarily be an ith number in A for any i in N.

If you compare it to the natural numbers and the reals it becomes more obvious. Imagine if someone said "if you give me any real number i, there is an element i_r of the set subset N, since N is not finite". It doesn't hold because the "not finite" of the natural numbers is very different to thhe "not finite" of the reals.

How do we know that there isn't some similar subset of N that is comparable?

Anonymous

Anonymous Fri 10 Jan 2020 14:10:52 No.11291308 Report

Quoted By: >>11291312 >>11291313

if for some n, the sequence A doesn't have an nth element, then A is a finite sequence. so any injective mapping from A to N is also onto

Anonymous

Anonymous Fri 10 Jan 2020 14:12:48 No.11291309 Report

Quoted By:

>>11291307
>an element i_r
I meant "an element n_i"

Anonymous

Anonymous Fri 10 Jan 2020 14:14:00 No.11291312 Report

Quoted By: >>11291315

>>11291307

do you agree that each element in A can be assign a unique number in N? if so, then surjectivity follows from contradiction.

>>11291308

Anonymous

Anonymous Fri 10 Jan 2020 14:14:13 No.11291313 Report

Quoted By: >>11291318 >>11291329

>>11291308
>if for some n, the sequence A doesn't have an nth element, then A is a finite sequence
says who? why?

Anonymous

Anonymous Fri 10 Jan 2020 14:16:08 No.11291315 Report

Quoted By:

>>11291312
yes, each element in A can be assigned a unique number in N, but I don't see how EVERY element of N has to have an element in A assigned to it

Anonymous

Anonymous Fri 10 Jan 2020 14:18:32 No.11291318 Report

Quoted By: >>11291332 >>11291333

>>11291313

since A is a subset of the integers, it must have a least element, right? call it a1. if it has a second least element, we can call that element a2, and so forth. suppose that for some i, there is no element greater than ai. then the set is finite.

the result follows from the assumption, but it isn't circular logic.

Anonymous

Anonymous Fri 10 Jan 2020 14:25:21 No.11291329 Report

Quoted By: >>11291367

>>11291313
If there's no nth element, then there's no (n+1)th, (n+2)th, and so on. You've stopped at (n-1).
So there n-1 elements. n-1 is a finite number.
Is this hard to understand? Just think about it for more than a second.

Anonymous

Anonymous Fri 10 Jan 2020 14:26:27 No.11291332 Report

Quoted By: >>11291345 >>11291367

>>11291318
>suppose that for some i, there is no element greater than ai
you can have one set have a smaller cardinality than another without the smallest having a greatest element, though.

To draw a comparison:
>N is a subset of the open interval [1,?), it has a least element, n1=1 It has a second least element, we can call that element n2, andd so forth. suppose that for some i there is not element greater than ni. ten theh set is finite.

If your proof is valid then I just proved thhat the natural numbers are finite

Anonymous

Anonymous Fri 10 Jan 2020 14:26:42 No.11291333 Report

Quoted By: >>11291345 >>11291367 >>11291373

>>11291318
cont.

so i guess the "trick" here is the inductive definition of the sequence A, which is possible because the natural numbers are well-ordered. we can pick out the least element, and then go up from there.

Anonymous

Anonymous Fri 10 Jan 2020 14:31:53 No.11291345 Report

Quoted By: >>11291367

>>11291332
>you can have one set have a smaller cardinality than another without the smallest having a greatest element, though.

i'm not totally sure what you're saying, but see
>>11291333

>>11291332
>If your proof is valid then I just proved thhat the natural numbers are finite

it's a proof by contradiction. we assumed that A is not a finite set. if you can't come up with an i'th element then this assumption is violated.

Anonymous

Anonymous Fri 10 Jan 2020 14:43:10 No.11291367 Report

Quoted By: >>11291382

>>11291329
>>11291333
>>11291345
shit, I just got it.
The reason why my comparison to the reals doesn't work is because you can't list out the reals.
For my comparison in >>11291332 the second least element would have to be n? instead of n2, where ? is the second least element of the interval [1,?). But such a second least element doesn't exist.

Thanks for the help

Anonymous

Anonymous Fri 10 Jan 2020 14:45:51 No.11291373 Report

Quoted By: >>11291375

>>11291333
cont.

of course, this is an especially easy case because you're only dealing with a subset of the natural numbers. you can also show that other sets like the integers are countable even though some of them are not subsets of N or well-ordered. as long as you can define the mapping and show that it's a bijection.

Anonymous

Anonymous Fri 10 Jan 2020 14:48:19 No.11291375 Report

Quoted By:

>>11291373
yeah, I understood the proofs that show things like the integers or the even numbers are countably infinite, it was just this one that rubbed me the wrong way.

Anonymous

Anonymous Fri 10 Jan 2020 14:52:38 No.11291382 Report

Quoted By: >>11291396

>>11291367
>The reason why my comparison to the reals doesn't work is because you can't list out the reals.

well yes, but there is no largest natural number. i only made the assumption that A had a largest element to draw a contradiction.

every natural number has a successor. that's how the set is defined iirc.

Anonymous

Anonymous Fri 10 Jan 2020 14:59:26 No.11291396 Report

Quoted By:

>>11291382
>well yes, but there is no largest natural number. i only made the assumption that A had a largest element to draw a contradiction.
>every natural number has a successor. that's how the set is defined iirc.

yes, but I was trying to say that set A could also have similar properties.

Like if you listed all the primes then that would be a subset of N with no largest element even though they get scarcer the higher you go up.

Although the set of all primes is countably infinite, I was arguing that there could be some set A which had no largest element but had a smaller cardinality than N.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches