Nonnegative Sums of Rows and Columns

For any n\times n matrix A with real entries, is it possible to make the sum of each row and each column nonnegative just by multiplying rows and columns by -1? In other words, you are allowed to multiply any row or column by -1 and repeat a finite number of times.

My fellow office mate Kirill, who also has a math blog, gave me this problem a few weeks ago and I thought about it for a few minutes here and there. The solution is in the fourth paragraph, so if you’d like to think about it yourself stop here before you get close.
Read more…

Interview: Benjamin Smith

This interview is a start in what I hope to be a series of posts illustrating the human side of mathematics. Mathematicians as a group have distinctive cultural features. We have our own specialized humour and shared experiences that bring us together and make us laugh. A week ago, I read an interesting article by John Swallow entitled “Mathematical Community” in the Notices of the American Mathematical Society, which reminded me of the unfortunate truth—very few people outside of the mathematical community really knows what being a mathematician is about.

I hope that this will change, and I feel that it is very important to inform the general public about the work of mathematicians. And by this I don’t mean the technical details, but the culture and the general ideas that we work with every day. As part of this initiative, I thought I would interview a few of my fellow graduate students at McGill. My first interview is with Benjamin Smith, who is a PhD student in geometry.
Read more…

Every Set Has a Group Structure Iff Axiom of Choice

Here I explain the proof that in ZF, the axiom of choice (AC) is equivalent to every nonempty set having group structure (GS). I first learned of the nontrivial direction of this argument in this MathOverflow post and as far as I know first appeared in “Some new algebraic equivalents of the axiom of choice” by A. Hajnal and A. Kertész in Publ. Math. Debrecen 19 (1972), pp. 339-340.

Read more…

The Sumset of Sets of Positive Measure, Continued

In the previous post, we saw how to use a basic theorem on Lebesgue points to prove that if A and B are measurable subsets of the real line with positive measure, then A+B contains an interval. We shall continue now to prove this again using a different, less involved method. This solution is based on a hint in Problem 19 of Chapter 9 in Rudin’s book.

The Proof

Recall that we are proving: if A and B are measurable sets of real numbers such that A and B have positive measure, then A+B contains an interval.
Read more…

The Sumset of Sets of Positive Measure

Today I shall continue in the spirit of my last post, which was essentially a revised set of notes on material for my qualifying exam. Here, and in the next post, we shall see two ways to prove that if A and B are Lebesgue-measurable subsets of the real line with positive measure, then A+B contains an interval. The notation A+B means \{ a + b : a\in A, b\in B\}.

Before we start, let us examine counterexamples. Firstly, the converse to the statement is not true. I’ll leave it as an exercise to show that the Cantor set C is such that C+C contains an interval, yet C has measure zero. On the other hand, \mathbb{Q}+\mathbb{Q}=\mathbb{Q}, and \mathbb{Q} does not contain an interval. In fact, if we prove the above then we shall have another proof that \mathbb{Q} has measure zero, although this follows more directly by observing that \mathbb{Q} is countable, and that points have measure zero.

Both these solutions were hinted at in Rudin’s “Real and Complex Analysis”. I’ve broken up these solutions into two posts for convenience. In the sequel, measurable means Lebesgue measurable on the real line, and m denotes the Lebesgue measure.
Read more…

Fundamental Theorem of Calculus, Lebesgue Version

For my qualifying exam next week, I made a few notes on the fundamental theorem of calculus in the Lebesgue setting and I’ve decided to post them in case they might be of use to someone else. I shall sketch the proof and try to explain the main points, aiming for a broad overview. The interested reader should consult Chapter 7 of Rudin’s Real and Complex Analysis for full proofs.

In the Riemann setting, for a continuous Riemann-integrable function f:[a,b]\to\mathbb{R} differentiable on (a,b), one form of the fundamental theorem is that

\int_a^x f'(t)dt = f(x) - f(a).

Here the integral is the Riemann integral. Now, one can make various technical modifications to the hypotheses of the usual analysis ilk, such as allowing f to be differentiable on (a,b) except for some finite set, but the above statement seems to capture the essence of the fundamental theorem. Now, the proof of the fundamental theorem is short and sweet: use the definition of the Riemann integral as a limit of Riemann sums and apply the mean value theorem.

We would like a similar statement to hold for the Lebesgue measure \mu on the real line.
Read more…

Model Theory and Cardinal Products

Contrary to the usual counterexample post, I shall describe something which originally inspired me to start this blog: an application of mathematical logic to mathematics. Eventually, I’d like to work towards describing some of the model theory in algebraic geometry, but for now I’ll be satisfied with set theory.

An early theorem proved in the theory of sets is that if \kappa is an infinite cardinal, then \kappa\cdot\kappa = \kappa. One can prove this directly using transfinite induction or some variant, but I recently thought of a route through model theory that I find most interesting, if only because it’s indirect, and such proofs are my favourite.

We shall work with first-order logic. Consider the language L = \{ f\} where f is a binary function symbol. We let S be the set of first-order axioms saying just that f is bijective (note that we can do this with a first-order sentence). We know that |\mathbb{N}\times\mathbb{N}| = |\mathbb{N}|, so that S has a countable model. Now by Löwenheim-Skolem, there is a model of cardinality \kappa for every infinite cardinal \kappa. This proves that there is a bijective map f:\kappa\times\kappa\to\kappa, although we certainly don’t have any idea from this proof what the map might “look like”.

This is a short proof, and doesn’t use any advanced theorems from logic, but for instance, it does use Löwenheim-Skolem and thus the compactness theorem.

Nakayama and Finite Generation

It’s no secret that all sorts of neat theorems and ideas go haywire upon the dropping of their finite generation hypotheses. A paltry but illustrative example is that an injective linear map T:V\to V on a finite dimensional vector space V is also surjective. From a counterexample point of view this pretty proposition isn’t terribly interesting.

Let us then make a short journey to the land of modules over arbitrary rings, and consider the trite and trivial observation that if M is a nontrivial module over some ring, then 0M\not= M. This is hardly worth mention, and any capable mathematician would be wont to want more. Luckily there’s a generalization called Nakayama’s Lemma, which aside from being immensely useful, it has a short and entertaining proof.
Read more…

Old Category Theory Quotation

Category theory is tremendously useful now, so it’s amusing to read the following paragraph from the introduction to Mitchell’s “The Theory of Categories”:

A number of sophisticated people tend to disparage category theory as consistent as others disparage certain kinds of classical music. When obliged to speak of a category they do so in an apologetic tone, similar to the way some say, “It was a gift–I’ve never even played it” when a record of Chopin Nocturnes is discovered in their possession. For this reason I add to the usual prerequisite that the reader have a fair amount of mathematical sophistication, the further prerequisite that he have no other kind.

C[0,1] Is Not Noetherian

I’m going to talk a bit about flatness. I created the following exercise for myself while studying flatness: describe some good examples of flat modules that are not projective.

We call a left R-module F flat if the functor -\otimes F is exact, and of course the analogue can be made for right R-modules. As the tensor functor -\otimes F is always right exact, this is a rather natural definition to make. Recall that there is a similar definition for the \mathrm{Hom}(P,-) functor: we call an R-module P projective if \mathrm{Hom}(P,-) is exact.

Projective modules have a rather nice characterisation. That is, a module P is projective if and only if it is the direct summand of a free module. In particular free modules are projective. Mac Lane in his book “Homology” gives an example of a projective module that is not free: take the ring \mathbb{Z}\oplus\mathbb{Z} and consider the submodule \mathbb{Z}\oplus 0 of it.
Read more…