Countable and Uncountable Sets - Discrete Mathematics

[@Trevtutor]

Check out my new course in Set Theory: trevtutor.com/p/master-discrete-mathematics-set-theory It comes with video lectures, text lectures, practice problems, solutions, and a practice final exam!

[@tjlavin88]

I just realized this video in the DM1 series was recently posted. A massive thanks to you for continuing to update these playlists and get this guy in his 30s off to a great start in DM1 for a CS degree!!

[@suyziljackson8202]

OMG. i was struggling to understand this concept and you explained it flawlessly!

[@Xennso]

I started learning this 3 days ago, im so glad you released a video on it! whenever I have problems understanding a discrete mathematics topic I instatly google the keyword and your name xD Thank you so much for content!

[@5iiwvwj58jfw8wnevu5]

I literally have an exam in 3 hours, and I couldn't find a video on countable sets from you last night but here you go, saving my life last minute

[@Trevtutor]

The timing is impeccable ;)

[@God-ld6ll]

count... yourself 🍀

[@shayorshayorshayor]

How was the fail?

[@5iiwvwj58jfw8wnevu5]

@@shayorshayorshayorgot an A

[@Cm-zc2zx]

Sameee broo😂

[@Trevtutor]

I think this video is a bit overdue by now. But here we go: countable and uncountable sets!

[@kaujla8435]

Thank you so much dude! Aside from the helpful content, the pacing of this video is perfect. I've watched soo many other math, coding, etc. videos where they rush through the content or speak too quickly and it makes an otherwise informative video incredibly frustrating and worth disliking. Glad I found your channel!

[@gackerman99]

afaik in this playlist we haven't yet talked about bijections/surjections etc. so this was a bit abrupt.

[@Flaystray]

Wouldn't the uncountablity proof work for the natural numbers, too?

[@Nino-eo8ey]

For the example shown at 2:07, if we keep the 0, can I set the function to be f(n) = 1/(n+1)²? It sounds correct, but something feels off about it.

[@rishabhnarula1999]

thank you sir, very well explained.

[@alexgorakine6262]

Thank you for the video! May I ask why the set of natural numbers sometimes contains zero? Like why for the first problem, zero is included, while you disregarded zero for the set in the second problem? Thanks!

[@_7__716]

Not sure the playlist is in order

[@Carrymejane]

Yep i do think the playlist isn't in order 😌

[@youcefzerrouki1175]

Thank you ❤❤❤

[@JwalinBhatt]

Thank for the video and the proof, but I am a bit confused. Wouldnt this make the natural numbers uncountable as well? Lets say I have a1=1 a2=2 a3=3 Now I go through all and keep appending them. so a4=123 When I get to a123, the new number would get 123 appended at the end and hence wouldnt be in the set. What am I missing?

[@Trevtutor]

The proof for rationals differs from integers as for every two rational numbers x and y, you can always create a new number (x+y)/2. With integers, there are no numbers between, so we can order them according to the video without asking “what about the numbers in-between? For example, with rational numbers, what’s after 0.0001? 0.00001? 0.0002? Well, if 0.0002 is next, then I can create 0.00015 between the two. Then I can make a number between 0.00015 and 0.0002. Etc. there’s always a new number available to create. The proof of rationals and it’s contradiction gets at that idea.

[@JwalinBhatt]

@@Trevtutor thanks for the reply. You gave the example of rationals. But aren't the rationals countable?

[@Flaystray]

2:18 why are you able to exclude zero?

[@ghfudrs93uuu]

Amazing video

[@afengg174]

bro just saved my life, i got a DM test in 5 mins. whish me luck.

[@kanty2178]

my exams is tomorrow thanks god, helped me

[@johannesndjimba]

Can you help me with this? 11. (15 points) Draw an undirected graph with six nodes and nine edges. Label the nodes 1 through 6. Write down the formal 2-tuple describing your graph. What is the lexicographically first maximal independent set of your graph? Is it a maximum independent set? Explain why or provide a maximum independent set.

[@olayinkaanifowose5099]

So is it not a contradiction that we generated a real number greater than 0, but less than 1 and claimed for it not to be in the set of real numbers less than 1 and greater than zero? Surely this should reflect that the method breaks down somewhere?

[@Trevtutor]

That contradiction is what enables us to say it’s uncountable. If it were countable we wouldn’t be able to get to a contradiction.

[@olayinkaanifowose5099]

@@Trevtutor oh right, that makes sense.

[@tukemo5788]

Will that function di always work?

[@RFsalman]

2:10 isn't it because 0 is not in the natural number set ?

[@arthurlbn]

R/Q = Irrationals. All point in this set are an acummlation point?

[@johnpasses]

2:12 Sorry Is zero in the set of natural numbers?

[@Daisynbn]

I understand how to make the new number but I don't understand what is its purpose. To prove that although we make a new set from original set, the new set is still uncountable?

[@kaitan8824]

Assume there is a set of real numbers between 0 and 1 that is countable, which means there is a 1-to-1 mapping between the set and the natural numbers. Now we can create a new number, which is still a real number between 0 and 1, add this new number to the previous set to make a new set, so the new set does not have a 1-to-1 mapping with natural numbers. This new set is still a subset of all the real numbers between 0 and 1. So all the real numbers between 0 and 1 does not have a 1-to-1 mapping with natural numbers, so it is uncountable.

[@Daisynbn]

@Kai Tan I get it:3 Thank you 😊

[@jdkdjd3126]

@@kaitan8824 great explanation. I had no idea how to do this in my discrete structure lecture. I get how to do this after watching the video but don't know why. Your explanation clearly explained everything!

[@masculinityremains]

amazing

[@_Anna_Nass_]

I feel very clever now 😮

[@tonywang7933]

Thank you for the nice tutorial. But I think that last prove of accountability is not intuitive to me. All what we are trying to do is to show that there there much more numbers in (0, 1) than natural number. Instead, suppose I have the following mapping f: 0.1 to 1 0.11 to 2 0.111 to 3 ... Hences the number of 1s will map exactly to their corresponding natural number. lt obvious that all my input is from (0, 1), and the image is indeed natural number. So now 0.2 is definitely a new number and it is in (0, 1), to include 0.2 into the domain of f, f(0.2) has to be one of the natural number that is already mapped, thus breaking the injective part of the bijective assumption.

[@MuffinsAPlenty]

Something to keep in mind: a set S is countable if there _exists_ a bijection between S and N. This is not equivalent to _all_ functions between S and N being bijections. Finding a particular function which isn't a bijection does not settle the issue - how do you know that there isn't some other function out there which is a bijection?

[@jakeyshakey5475]

I forgot 0 is natural

[@edahsindani1758]

Hey i didn't get the a¹¹ part

[@MohammedIdris-th9xe]

Is zero really a natural number ??

[@eugenek951]

Natural numbers don't have 0

[@Trevtutor]

It depends on the mathematician. Some exclude 0, some don’t.