Lecture No # 28

Hello class! Today we'll discuss countable sets, focusing on examples like the Cartesian product of integers, ℤ x ℤ. Can anyone tell me what a countable set is?

I think a countable set is one that can be listed or enumerated?

Exactly! Countable sets can be finite or have the same cardinality as the set of positive integers. Let's illustrate this with ℤ x ℤ. When we take all ordered pairs of integers, it seems like there are many elements. But let's explore an enumeration method.

How do we start enumerating it?

We start from (0, 0) and then spiral outwards. This way, we'll access every point without repetition. Remember: spiral from the center outward. That’s our memory aid for this concept!

So every point will eventually appear as you spiral out?

Correct! And that proves ℤ x ℤ is countable. Can someone summarize what we just learned?

We learned that the Cartesian product of integers is countable because we can list every pair with a spiral enumeration.

Great summary! We'll build on this with more examples.

Now let's dive into the set of rational numbers, ℚ. Initially, some might think they're uncountable due to density. What do you think?

I thought since there are infinitely many rational numbers between any two, they must be uncountable!

A common misconception! However, we can list rational numbers using an enumeration technique similar to the Cartesian product. Can anyone suggest how we could approach that?

Maybe using the pairs (p, q) from ℤ x ℤ and listing p/q where q is not zero?

Exactly! By following this method and skipping pairs where q = 0 and duplicates, we can enumerate all rational numbers. What’s our conclusion?

Rational numbers can be counted, which means they are a countable set.

Spot on! Remember this process as it will be vital for our next examples!

Next, let's consider binary strings. What does Π* refer to?

It represents all binary strings of finite length!

Correct! And since each length contributes a finite number of strings, how would we show that Π* is countable?

We can list them by length, starting with length 0, 1, 2, and so on.

Right! So by going through each length in order and organizing them by binary order, every string will eventually appear in our list. Would someone summarize why Π* is countable?

Each set of strings by length is finite, and we can organize them in a sequence that captures every binary potential.

Well put! Understanding how binary strings work will aid us in grasping larger concepts about countability.

Now let’s discuss the union of countable sets. If you have two countable sets A and B, what can we say about their union?

I'd guess their union is also countable?

Exactly! Can anyone provide a scenario where both sets A and B are countably infinite?

Like, say two sets of even and odd integers?

Great example! We can list even integers and odd integers in a sequence. Let’s find a way to merge these lists without missing any elements. Anyone suggest?

We could alternate between elements from each set!

Perfect! This approach ensures that all numbers will eventually appear in the union. Who can summarize what we took away from this?

Unions of countable sets are countable, and we can arrange the elements in a sequence to prove this.

That's right! Understanding unions adds another layer to our discussion on countability.