Hopefully Interesting

October 29, 2009

A Hands-On Proof of Lusin’s Theorem

Filed under: analysis,math.CA — Pietro @ 3:40 am

Today I’d like to share a cute proof I came up with. Actually this is one of those posts that have been in the oven for the last year and a half, while my wife and I have been busy getting married, travelling across Europe, moving into a new place, defending my MSc in Logic and then moving to Los Angeles. But, since I’m retaking basic Real Analysis as a requirement of the PhD program at UCLA, it seems adequate to revisit this little idea and finally post it.

The proofs I’ve seen of Lusin’s theorem go through Egorov’s theorem; that’s how Stein-Shakarchi, Folland and Wikipedia do it. I don’t feel it is a particularly elegant proof, and it produces a truncated version of Lusin’s theorem, which holds only for sets of finite measure. A simple \sigma-finiteness argument takes care of this shortcoming, but one is left with the feeling that Egorov’s theorem is our hammer, and we’re trying to see Lusin’s as a nail. Hence the motivation for a different proof. I hope you will also appreciate how there are no real obstacles in the route below; everything that needs to be done can be done nearly without thinking. (more…)


March 17, 2008

Dilworth’s Theorem II

Filed under: math.CO,motivated theorems — Pietro @ 6:48 am
Tags: ,

We continue our discussion of Dilworth’s theorem from last time. To recall, we proved by (a very algorithmic) induction that, if (P,\leq ) is a finite poset whose largest antichain has m elements, then P is the union of m chains. Today we’ll see how a batch of standard (and important) techniques can prove the theorem for general P, from the finite case. As before, we will often refer to decompositions of P into chains as colorings of P, which will always be subject to the restriction that two similarly colored elements be comparable. When we wish to emphasize this property, we may employ the term consistent coloring. It is easy to see that colorings using m colors are equivalent to decompositions into m chains. (more…)

March 14, 2008

Quantitative Borel-Cantelli Lemma

Filed under: math.CA,motivated theorems — Pietro @ 12:00 pm
Tags: ,

Everyone knows and loves the Borel-Cantelli lemma: it is widely used, intuitive and has a cute proof. Let’s recall it.

Borel-Cantelli Lemma. Let (X,\mathcal{M},\mu) be a measure space, and (E_n)_{n\in\mathbb{N}} a sequence of measurable sets such that \sum_{n\in\mathbb{N}} \mu(E_n) < \infty. Then the points of X that lie in infinitely many E_n form a set of measure zero.

Proof. We present the usual slick proof of the lemma, and postpone intuition until the development of a quantitative statement. Define F_\infty to be the set of points lying in infinitely many E_n, and notice that F_\infty = \bigcap_{n\in\mathbb{N}} \bigcup_{k\geq n} E_k. It follows that F_\infty is measurable, and contained in each cofinite union \bigcup_{k\geq n} E_k. Now, \mu(\bigcup_{k\geq n}E_k) \leq \sum_{k\geq n} \mu(E_k), and the latter goes to zero as n\to\infty, because \sum_{n\in\mathbb{N}} \mu(E_n) converges. Thus \mu(F_\infty)=0, as claimed. \Box

Alright, so the set of points lying in “very many” E_n is “very small”. A natural quantitative question to ask at this point is: how small is the set of points lying in “moderately many” E_n? More precisely, if F_k is the set of points lying in at least k of the E_n, and G_k = F_k \backslash F_{k+1} the set of points lying in exactly k of the E_n, can we get bounds on \mu(F_k) and \mu(G_k), depending on k?


March 6, 2008

Dilworth’s Theorem I

Filed under: math.CO,motivated theorems — Pietro @ 10:46 am

Today I’d like to talk about a gorgeous theorem in order theory. Since partial orders are such general objects, the theorem potentially has many applications, especially in combinatorics (we shall see a few, in fact); and to top it off, I found a very cute inductive proof.

Here’s the statement:

Theorem 1. Let (P,\leq ) be a partially ordered set (a poset) in which the largest antichain has size m. Then it is possible to decompose P into the union of m chains.


December 29, 2007

Topological Notation

Filed under: opinion — Pietro @ 7:19 am
Tags: ,

In general topology, one talks about open and closed sets a lot. A lot. So it seems a bit silly that there isn’t standard notation for that; it’s sort of like writing “equals” longhand throughout and entire semester of calculus. So I came up with the following simple symbols:

  • A \subseteq^\circ X (A is open in X);
  • A \subseteq^\bullet X (A is closed in X);
  • A^\circ (the interior of A);
  • A^\bullet (the closure of A).

They’ve been saving me a lot of time and thought since then, like notation’s supposed to. Witness A \subseteq^\circ B \subseteq^\circ X \Longrightarrow A \subseteq^\circ X . The closure symbol, in particular, has ended the ambiguity with \bar{A}, which often denotes the complement of A in other contexts. It’s easy to know which is meant if you think about it, but this sort of thing should be run by the cerebellum.

December 28, 2007

Length and Area I

Filed under: math.CA — Pietro @ 6:54 am

This is a topic which has fascinated me for years, and on which I’ve spent many (fortunately unsuccessful) hours trying to prove theorems that are actually false. I find it to be a good introduction to the weirdness of analysis: you know, the gradual realization that much of our intuition about lines, surfaces and continuity is simply not applicable to the analytical formalization of lines, surfaces and continuity. Some mathematicians, like Weyl and Brouwer, blamed this weirdness on the fact that the intuitive notion of a continuum (the line) is not very well captured by something as disconnected as a set of points (the real numbers).

In any case, we have to develop some new intuitions if we’re going to expect, rather than be surprised by, the Koch snowflake, nonmeasurable sets, and families of curves that have positive area but only at the endpoints. (more…)

November 15, 2007

On Limits II

Filed under: math.LO — Pietro @ 12:18 pm
Tags: ,

(This is a continuation of On Limits I.)

Think of Pelé. When somebody asks “who is Pelé”, you might reply, “the best football player ever”. Notice that you are implicitly defining Pelé in terms of his relationship to other footballers; an observation which is often obscured by the fact that there is also an actual person you can point to, and say “that’s Pelé”.

Now suppose a toy company came out with a football trading card game, where each card represents a famous player, and contains various numerical ratings like precision, speed, stamina etc. You might now explain that Pelé (meaning the Pelé card) is “the card with highest speed and precision”. Even though there is still an actual card you call “Pelé” (and children might think of it this way), it is now clear that the thrust of the definition is quite another: what is important about the Pelé card is its relationship to the other cards, not its particular shape, or whether it’s made of paper or plastic.

Similarly, if you ask a child what is a chess pawn, they will most likely point to the actual, physical chess piece: “that’s a pawn”. Which is fine if we had asked “what is a chess pawn, in the physical world?” However, the deeper content of our question was “what is a chess pawn, in the game of chess?” Since grandmasters are able to play entire games in their minds, a pawn can’t be just a wooden piece. In fact, even novice players experience no confusion if pawns are replaced with (say) beans, as long as they agree to it beforehand. So we see that the main defining feature of chess pawns is not their wooden incarnation, nor their color, but their relation to other pieces; that is, the rules they obey in the game of chess. The physical pawn is just a memory aid. (more…)

November 8, 2007

On Limits I

Filed under: math.LO — Pietro @ 6:11 am
Tags: ,

What on earth could one usefully say about limits, that hasn’t been printed for centuries on a thousand calculus textbooks?

I don’t know about usefulness, but one can certainly say something different. For all their numerosity, calculus texts are remarkably homogeneous in their treatment of this elementary topic, and I see at least one point that could stand clarification.

Limits — especially expressions involving “dot dot dot”, such as 0.999… — still seem to be a source of confusion for many beginning calculus students. Since all the popular treatises give thorough mathematical definitions of the concept, the problem must lie somewhere other than mathematics. I conjecture that what’s missing is not a more easily understandable definition, but instead a straightforward discussion of how definitions work in mathematics.

To get into definitions, I’m going to start by talking about symbols — in particular, symbols that represent numbers. (more…)

October 30, 2007

First post

Filed under: Uncategorized — Pietro @ 6:11 pm

Hello. I am Pietro, a brazilian student of logic and mathematics. Of course, like everybody else, I am much more than just that; but that is what will come through the most in these pages.

In this blog, I hope to share interesting things I come across in logic and math, which may not be widely known. Also, I may occasionally share a different way of thinking about well-known things, if I feel I have developed it enough, and it is uncommonly enough seen in mainstream sources like textbooks and papers. I find it enormously important for people to exchange their “inner ways” of thinking, rather than just the “outer” results they reach; communication becomes much clearer, more interesting, and conductive to progress. I thank Terry Tao, Tim Gowers , the n-Category Café and the Catsters for proving this point so forcefully.

Though I’m brazilian, I will be writing in english, simply because I will be understood by a larger number of people that way. It’s fine to be protective of one’s culture and language, but I feel this is simply not the place. If my experience on orkut is any indication, for every portuguese-speaking reader I lose, I will gain five readers from India.

Finally, the “kc” in this blog’s URL are my other initials.

Blog at WordPress.com.