## Intersection of a Chain of Subsets

Assume $\{F_x\}_{x \in \Gamma}$ is a collection of subsets (of a not-so important set!) such that every two are comparable, i.e for any $x$ and $y$, either $F_x \subset F_y \ \$ or $\ \ F_x \supset F_y \$ .

Considering the intersection $\cap_x F_x$ we see that many of the sets could be skipped without altering the intersection.

Question: Is it possible to attain the same intersection by taking only countably-many of the subsets?

Theorem: There is a chain of subsets of the unit interval whose intersection does not equal the intersection of any countably-many of them. They may be chosen measurable.

In order to give a proof we first show a simple lemma.

Lemma: If $\{A_j\}_{j=1}^\infty$ is a chain then there exists a decreasing sequence out of its members

$$G_1 \supset G_2 \supset \cdots$$

such that $\cap_j A_j = \cap_i G_i$ .

Proof: Take $G_1=A_1\$, and let $j(1)=1\$. We will move along the sequence $A_i$ and pick those that are needed in the intersection, which means those that are smaller. The details are as follows:

Let $j(2)$ be the first index bigger than $j(1)$ such that $A_{j(2)} \subsetneq G_{j(1)}$. If no such index exists then all the subsequent sets contain $A_1$, and so we can take the constant sequence $G_i=A_{j(1)}$ and it will satisfy the assertions in the claim.

Inductively, assuming that $G_1 \supset G_2 \supset \cdots \supset G_k$, and $j(1) < j(2) < \cdots < j(k)$ have been defined, we define $j(k+1)$ to be the least index after $j(k)$ such that $A_{j(k+1)} \subsetneq G_k=A_{j(k)}$, and $G_{k+1}=A_{j(k+1)}$. Again, if such an index does not exist then we could have the constant sequence $G_k$ satisfying the assertions of the claim.

If an infinite sequence $G_1 \supset G_2 \supset \cdots \$ emerges eventually, then it is the sequence claimed, because each $A_i$ was given a chance at some point! (If, say, $A_{2017}$ is none of the $G_j$’s, then it means that it contained one of them.)

Proof of the theorem: Take $\mathfrak{C}$ to be the collection of all Lebesgue-measurable subsets of the unit interval with measure equal to 1 and order it with the inclusion relation “$\subset$”.

We will reach a contradiction by assuming that the assertion of the theorem were false.

Take a chain $\mathfrak{F}=\{F_x\}_{x \in \Gamma}$ in $\mathfrak{C}$. There would be a countable subcollection $\{A_j\}_{j=1}^\infty$ giving the same intersection.

By the lemma, we can further restrict to a decreasing sequence $G_1 \supset G_2 \supset \cdots ; G_j \in \{F_x\}_x$ and still have $\cap_i G_i = \cap_j A_j = \cap_x F_x\$.

It is a fact of measure theory that

$$\mu (\cap_i G_i ) = \lim_{j \rightarrow \infty} \mu (G_j) = \lim_{j \rightarrow \infty} 1 =1 \ .$$

Observe that $\cap_i G_i$ is in $\mathfrak{C}$, and thus a lower bound to the chain $\mathfrak{F}$.

What we have shown is that every chain in $\mathfrak{C}$ has a lower bound. By Zorn’s lemma, there exists a smallest element in $\mathfrak{C}$. However, for any element is $\mathfrak{C}$ removing a single point gives an even smaller set in $\mathfrak{C}$.

This contradiction shows that for some chains in $\mathfrak{C}$ the intersection cannot be replaced by a countable intersection.

Note: We can work with smaller $\mathfrak{C}$ such as the collection $\{[0,1]\backslash D \ \ | \ \ D \text{ is finite}\}$.

## Applying to grad school? Here’s what you need to know: Part II

In my last post, I shared my experience with diving into grad school applications, as well as my advice for getting started with the application process. By now, you’ve hopefully decided whether (and why!) you’ll be applying to grad school, and if you are, you’ll have taken the GRE and settled on a few programs that pique your interest. (If not, not to worry – read my previous post on applying to grad school here.) In this post, I’ll share my thoughts on navigating two of the more complex aspects of grad school applications: crafting a statement of purpose (also known as: the longest two pages you’ll ever write) and advocating for yourself throughout the application process (and beyond).

Posted in Advice, Starting Grad Schol | Tagged , | 1 Comment

## Riddle of the Month (October)

Hi! This month, I thought I would take a brief break from writing about gauge theory to share a puzzle which I heard recently. As usual, if you have any riddles or puzzles that you think are interesting, send them to us and we’ll take a look at posting them!

Posted in Math Games, puzzles | Tagged , | 2 Comments

## Machine-Checked Proof

“In my view, the choice between the conventional process by a human referee and computer verification is as evident as the choice between a sundial and an atomic clock in science.” – Tom Hales (from [4])

“The rapid advance of computers has helped dramatize this point, because computers and people are very different. For instance, when Appel and Haken completed a proof of the 4-color map theorem using a massive automatic computation, it evoked much controversy. I interpret the controversy as having little to do with doubt people had as to the veracity of the theorem or the correctness of the proof. Rather, it reflected a continuing desire for human understanding of a proof, in addition to knowledge that the theorem is true” – Bill Thurston (from [6])

A machine-checked proof is a proof written in a piece of software called a ‘proof assistant’ which ensures the proof complies with the ‘axioms of mathematics’ and the rules of logic.  The question of the significance of computers in proving theorems can be polarizing (and for good reason). The quotations above represent some points of view relevant to this topic. In this post we will try answer three questions:

1. What exactly is a computer-assisted proof?
2. What are the advantages and the drawbacks of using computers to prove theorems?
3. What should an interested person do to start learning to use proof assistants?