Alright I need to put out a new blog post before the month ends otherwise my readers get mad so uhhhhhhh here is this cool trick.

EDIT: I have failed to release the post in February by a minute. This is extremely sad.

Reading Difficulty: 2.5/5

Prereqs:

• Know what injective/bijective/surjective functions are
• Know the difference between a countably infinite set and an uncountably infinite set (both Google-able!)

Background

Rational numbers are basically fractions between integers and natural numbers. Since both integers and naturals are countable, we know that the set of rational numbers is, perhaps surprisingly, countable.

(If you need a quick refresher, recall that a set is countable if, roughly speaking, you can "count them up" one-by-one, possibly forever, such that you're guaranteed to reach any particular element of the set eventually. More formally, a set is countable if there exists an injective function , i.e. " is a set that is smaller than the size of the natural numbers".)

Why is this surprising? It's because the rationals are dense. Basically, a dense set is a set that is "close to everything". In the case of the rationals, , we say that this set is "dense in " because every real number can be approximated as closely as you want with a rational number. Some interesting consequences of this are:

• If you look at any non-empty interval of , it contains a rational.
• There is always a rational number between any two different real numbers.
• If we look at the set of rational points, which is the set of all points both of whose coordinates are rational, then this set is also "dense in ", which roughly means that if you draw and circle, it will always contain a rational point.

So, rational numbers are really, really everywhere... and yet, if you decide to color a number line red and blue, with rational numbers red and irrational numbers blue, you'd see that the number line is painted overwhelmingly blue, because there are uncountably many irrational numbers but "only" countably many rational numbers. Sad!

....or is that really sad? In this post, we will see that the rational numbers being both countable and dense at the same time is extremely powerful.

Specifically, we will use this fact (called "separability of ") to prove that certain things are well-behaved or that certain sets are small (i.e. at most countable).

Let's Have Fun!

Victim 1: If a function is increasing (not necessarily strictly; that is, if then ), then the number of discontinuities of is at most countable.

Proof.

• Each discontinuity is a jump discontinuity (I'm going to take this for granted because I want to make this post accessbile, but in university real analysis this is a fact that would demand proof).
• At every such discontinuity, jumps from to where .
• But there is a rational between and .
• Since the rationals are countable, the number of jumps is at most countable. End of proof.

Whoa. Let's try and dive into the logic a bit deeper.

1. First, I found a property that the things I'm trying to count have. In this case, this property is the "jump".
2. Then, I found a way to relate this property to the rationals. In this case, I use the fact that there is a rational number between any two distinct real numbers.
3. Finally, I use this relation to assign every object in the set to a different rational number. formally...
   I'm using the Axiom of Choice to construct an injective function from the set of discontinuities to the set of rationals. This proves that the set of discontinuities is a countable set!
   It is essential that each jump gets assigned to a different rational number! Remember, the punchline we want to show is that there can't be more jumps than rational numbers. I'm chilling here because no two jumps can "cross" since is increasing, so indeed each jump will be assigned to a different rational.

Victim 2: A set is called "isolated" if for every number in , we can find a small positive number such that is the only element of inside the interval . Prove that every isolated set is at most countable.

Proof. We want to pick a rational number inside each of those intervals, but they might overlap. The trick for preventing this is to shrink every interval's size in half! Is it possible for two intervals and to overlap, where and are two different elements of ?

It turns out that they cannot overlap. To formally prove this, assume without loss of generality that . If the intervals overlap, there is a real number such that and . By the triangle inequality, we can then write
This means that is an element of that is within of , which is a contradiction!

Now we can freely pick a rational number inside every interval over all . No two intervals overlap, so we pick a different rational every time. So the intervals are at most countable. So is at most countable.

Super-Duper Injecting!

Remember how we mentioned in the introduction that is a dense subset of ? This is amazing - is also countable! And is countable! And is countable! And... uh... yeahhhh you see where this is going don't you?

Victim 3: Consider a function . We say that has a strict local minimum at some point if, for some small number , we have that for every that is within of , i.e. for every such that . Example

Prove that the number of strict local minima of is at most countable.

Proof.

This is harder now. But just remember the protocol: Start by finding some nice property of the thing we're counting, and then try and associate it with rationals...

Ok, let's take some where has a strict local minimum. Then we can find such that for all satisfying . Hm... could we just pick a rational in the interval ?

Unfortunately no! This is because we're not guaranteed that the the intervals won't overlap, so we might pick the same rational twice. For example, it could be the case that the function goes down and up again within the interval . Bummer!

We need more power... hmmmmmmmmmmmmmmmm.... what if we picked TWO rationals instead?

Yeah! Let's pick a rational inside and another rational inside . So, for every , we pick two rationals and such that:

• for all between and , and
• for all between and .

Is it possible that we end up picking the same TWO rationals for two different 's?

Let's take two different points and where has a strict local minimum, with , and let us assume for contradiction that we choose the same rational numbers and for them. Then . Now:

• Since we chose for the point , we know that for all between and . Since , we can plug in to get .
• Since we chose for the point , we know that for all between and . Since , we can plug in to get .

So and . Contradiction!

So, we have successfully associated every strict local minimum with a different pair of rationals . Since is at most countable, so is the number of strict local minima. Voila!

Moral of the story: Pick more rationals to gain more info! We can pick as many rationals as we want (as long as its finite...) in order to uniquely characterize the thing we're looking at more and more.

Victim 4: Is it possible to draw uncountably many non-intersecting figure-8-shapes in the plane?


(They don't have to look so round; they just need to be two loops attached to each other.)

Answer: No.

Proof. Last time we injected into . This time, we're going to inject into ! For each figure-8, pick two rational points: One rational point in one loop, and another rational point in the other. (Since each rational point consists of two rationals, we're indeed choosing a total of rational numbers!)



Is it possible to choose the same two rational points for two different figure-8's? The answer is no! Try it for yourself: It's pretty hard for two different 8's to share the same two points without intersecting each other...



...rigorously proving this is a job for a topologist though. And I am no topologist. Onwards!

The next example is the highlight of this post.

Victim 5: Can you draw uncountably many non-intersecting Y-shapes in a plane?



The solution is so good that I'm going to spoiler it. Consider thinking about it for yourself before revealing the insane methodology.

Hint 1

Hint 2

Hint 3 (MAJOR SPOILERS)

Solution

Your Turn

1. Is it possible to place uncountably many carpets (of positive length and width) on an infinite plane, without any of them overlapping? Why or why not?
2. We can define strict local minimums for 3D functions too! When is a function, we say that has a strict local minimum at if we can find a small positive such that for all points (distinct from ) within a distance of , we have .
   
   Prove that again, the number of strict local minimums of is at most countable.
3. Prove that any function has at most countably many jump discontinuites. ( has a jump discontinuity at if the left limits and both exist, but are not equal to each other.)
4. (Harder) Let be a function. Call a point bad if the left derivative and right derivative both exist, but they are not equal to each other. Prove that the number of bad points is at most countable.