Here is something that I was certain would have an easy-to-prove positive answer; but it turns out that there is an exceedingly simple counterexample.
Let be the first infinite ordinal; its successor is .We consider a map , or put differently, a -Matrix of real numbers.
We assume that has the following properties:
(1) For all we have , or more informally, we have “convergence to the right”.
(2) For all we have , or more informally, we have “convergence to the bottom”.
(3) , or more informally, the right-hand entries of converge to the bottom right element .
Question: Does this imply that , that is, do the bottom entries of also converge to ?
Answer: There is, surprisingly (to me, at least) an easy example showing that the answer is No. Let be defined by if and otherwise. It is easy to verify that (1), (2), (3) above are satisfied. Note that the right-hand entries are all 0, and they trivially converge to ; but we have for all therefore .
For the kind of two-dimensional convergence we are looking for we need some form of “simultaneous” convergence (conceptually related to uniform convergence), which I might address in a later post.
These days we hear about medians of all kinds of things: household income, lifetime of items such as lightbulbs, and so on. It’s time to get a rigorous grip on the concept.
Definition. Suppose is a set, a totally ordered set, and a function. Then is said to be a median of if the sets and have equal size.
It is a reflex of mathematicians to ask about existence and uniqueness of any concept they stumble upon. (Note that I wrote “a median” and not “the median” above.) Indeed, as much as the definition above seems to make sense: Even for simple example, the median needs not exist. Let and let be defined by and . Then has no median according to the definition above. On the other hand, if and is the inclusion map, then every element of the open interval is a median!
There are many common fixes to the problems of existence and uniqueness, but no definition is really elegant. (Most resort to listing the elements in ascending order and to pick the arithmetical middle of the “middle elements” in the list or something similar.)
Other difficulties arise when we want to pick medians of infinite sample sets. Let be a totally ordered set. We say that is a median of if the sets and have equal cardinality. Note that in every element is a median, but has no median at all!
Sometimes it happens to me that I become aware of a mathematical fact that surprises me – and the proof for the fact would even fit in a tweet.
When goofing around with graph homomorphisms, I realised that the following is true:
Fact. If is a graph homomorphism, then — no matter whether the graphs involved are finite or infinite.
Proof. Colorings are homomorphisms to complete graphs. If is a homomorphism, then so is .
The funny thing is: If I had been told just the statement of the fact “out of the blue”, I would have said that you probably need some condition on the homomorphism , like it being surjective etc. So I find it a bit surprising that the statement holds in this generality — even if there is a tweet-length proof for it.
In many categories such as Set, Group, Top (topological spaces) there is a morphism between any two objects, usually in both directions. (If one object is “empty”, like the empty space, or the empty set, there is the “empty” morphism from to the other object, but not the other way round.)
However in the category Graph it is possible that non-empty graphs have no graph homomorphism between them in either direction:
Let be the complete graph on 3 points and let be any triangle-free graph with , for instance the Grötzsch graph, which has chromatic number 4.
Since is triangle-free, there is no graph homomorphism and if there were a homomorphism , this map would be an -coloring of for some .