Hopefully Interesting

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…)

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…)

Create a free website or blog at WordPress.com.