The Universe of DiscourseThe Universe of Discourse (Mark Dominus Blog)tag:blog.plover.com,2005:/mathBlosxomhttp://perl.plover.com/favicon.ico2014-03-01T00:00:00Ztag:blog.plover.com,2014:/math/IL-contradictionProof by contradiction2014-03-01T00:00:00Z2014-03-01T00:00:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>Intuitionistic logic is deeply misunderstood by people who have not
studied it closely; such people often seem to think that the
intuitionists were just a bunch of lunatics who rejected the law of
the excluded middle for no reason. One often hears that
intuitionistic logic rejects proof by contradiction. This is only half
true. It arises from a typically classical misunderstanding of
intuitionistic logic.</p>
<p>Intuitionists are perfectly happy to accept a reductio ad absurdum
proof of the following form:</p>
<p>$$(P\to \bot)\to \lnot P$$</p>
<p>Here <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbot%24"> means an absurdity or a contradiction; <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%5cto%20%5cbot%24"> means that assuming
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> leads to absurdity, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28P%5cto%20%5cbot%29%5cto%20%20%5clnot%20P%24"> means that if assuming <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">
leads to absurdity, then you can conclude that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is false. This
is a classic proof by contradiction, and it is intuitionistically
valid. In fact, in many formulations of intuitionistic logic, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> is
<em>defined</em> to mean <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%5cto%20%5cbot%24">.</p>
<p>What is rejected by intuitionistic logic is the similar-seeming claim
that:</p>
<p>$$(\lnot P\to \bot)\to P$$</p>
<p>This says that if assuming <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> leads to absurdity, you can conclude
that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is true. This is <em>not</em> intuitionistically valid.</p>
<p>This is where people become puzzled if they only know classical
logic. “But those are the same thing!” they cry. “You just have to
replace <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> in the first one, and you get the second.”</p>
<p>Not quite. If you replace <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> in the first one, you do not get the second
one; you get:</p>
<p>$$(\lnot P\to \bot)\to \lnot \lnot P$$</p>
<p>People familiar with classical logic are so used to shuffling the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%24">
signs around and treating <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> the same as <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> that they often don't
notice when they are doing it. But in intuitionistic logic, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">
are not the same. <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> is weaker than <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">, in the sense that
from <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> one can always conclude <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">, but not always vice versa. Intuitionistic logic
is happy to agree that if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> leads to absurdity, then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">. But it
does not agree that this is sufficient to conclude <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">.</p>
<p>As is often the case, it may be helpful to try to understand
intuitionistic logic as talking about provability instead of truth.
In classical logic, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is true and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24">
means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is false. If <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not false it is true, so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">
mean the same thing. But in intuitionistic logic <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is
<em>provable</em>, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not provable. <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> means that it is
impossible to prove that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not provable.</p>
<p>If <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is provable, it is certainly impossible to prove that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not
provable. So <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> implies <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">. But just because it is impossible to
prove that there is no proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> does not mean that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> itself is
provable, so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> does not imply <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">.</p>
<p>Similarly,</p>
<p>$$(P\to \bot)\to \lnot P $$</p>
<p>means that if a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> would lead to absurdity, then we may conclude
that there cannot be a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">. This is quite valid. But</p>
<p>$$(\lnot P\to \bot)\to P$$</p>
<p>means that if assuming that a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is impossible leads to
absurdity, there must be a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">. But this itself isn't a
proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">, nor is it enough to prove <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">; it only shows that
there is no proof that proofs of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> are impossible.</p>
tag:blog.plover.com,2014:/math/CauchyCauchy and the continuum2014-01-04T13:43:00Z2014-01-04T13:43:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>There is a famous mistake of Augustin-Louis Cauchy, in which he is
supposed to have "proved" a theorem that is false. I have seen this
cited many times, often in very serious scholarly literature, and as
often as not Cauchy's purported error is completely misunderstood, and
replaced with a different and completely dumbass mistake that nobody
could have made.</p>
<p>The claim is often made that Cauchy's <em>Course d'analyse</em> of 1821
contains a "proof" of the following statement: a convergent sequence
of continuous functions has a continuous limit. For example, <a href="https://en.wikipedia.org/w/index.php?title=Uniform_convergence&oldid=583507328#History">the
Wikipedia article on "uniform
convergence"</a>
claims:</p>
<blockquote>
<p>Some historians claim that Augustin Louis Cauchy in 1821 published a
false statement, but with a purported proof, that the pointwise
limit of a sequence of continuous functions is always continuous…</p>
</blockquote>
<p><a href="http://ncatlab.org/nlab/show/Cauchy+sum+theorem#statements">The nLab article on "Cauchy sum theorem"</a> states:</p>
<blockquote>
<p>Non-theorem (attributed to Cauchy, 1821). Let <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%3d%28f_1%2cf_2%2c%5cldots%29%24">
be an infinite sequence of continuous functions from the real line
to itself. Suppose that, for every real number <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">, the sequence
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28f_1%28x%29%2c%20f_2%28x%29%2c%20%5cldots%29%24"> converges to some (necessarily unique)
real number <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%28x%29%24">, defining a function <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24">; in
other words, the sequence <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24"> converges pointwise? to
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24">. Then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24"> is also continuous.</p>
</blockquote>
<p>Cauchy never claimed to have proved any such thing, and it beggars
belief that Cauchy could have made such a claim, because the
counterexamples are so many and so easily located. For example, the
sequence <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%20f_n%28x%29%20%3d%20x%5en%24"> on the interval <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5b%2d1%2c1%5d%24"> is a sequence of
continuous functions that converges everywhere on <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5b0%2c1%5d%24"> to a
discontinuous limit. You would have to be a mathematical ignoramus to
miss this, and Cauchy wasn't. </p>
<p>Another simple example, one that converges everywhere in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cmathbb%0aR%24">, is any sequence of functions <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_n%24"> that are everywhere zero,
except that each has a (continuous) bump of height 1 between
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d%5cfrac1n%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac1n%24">. As <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%5cto%5cinfty%24">, the width of the
bump narrows to zero, and the limit function <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24"> is
everywhere zero except that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%280%29%3d1%24">. Anyone can think of
this, and certainly Cauchy could have. A concrete example of this type
is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=f_n%28x%29%20%3d%20e%5e%7b%2dx%5e%7b2%7d%2fn%7d"> which converges to 0
everywhere except at <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%20x%3d0%20%24">, where it converges to 1.</p>
<p>Cauchy's controversial theorem is not what Wikipedia or nLab claim.
It is that that the pointwise limit of a convergent <strong>series</strong> of
continuous functions is always continuous. Cauchy is not claiming that
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=f_%5cinfty%28x%29%20%3d%20%5clim_%7bi%5cto%5cinfty%7d%20f_i%28x%29"> must be continuous if the
limit exists and the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_i%24"> are continuous. Rather, he claims that
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=S%28x%29%20%3d%20%5csum_%7bi%3d1%7d%5e%5cinfty%20f_i%28x%29"> must be continuous if
the sum converges and the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_i%24"> are continuous. This is a
completely different claim. It premise, that the sum converges, is
much stronger, and so the claim itself is much weaker, and so much
more plausible. </p>
<p>Here the counterexamples are not completely trivial. Probably the
best-known counterexample is that a square wave (which has a jump
discontinuity where the square part begins and ends) can be
represented as a Fourier series.</p>
<p>(Cauchy was aware of this too, but it was new mathematics in 1821.
Lakatos and others have argued that the theorem, understood in the way
that continuity was understood in 1821, is not actually erroneous, but
that the idea of continuity has changed since then. One piece of
evidence strongly pointing to this conclusion is that nobody
complained about Cauchy's controversial theorem until 1847. But had
Cauchy somehow, against all probability, mistakenly claimed that a
<em>sequence</em> of continuous functions converges to a continuous limit,
you can be sure that it would not have taken the rest of the
mathematical world 26 years to think of the counterexample of
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%5en%24">.)</p>
<p>The confusion about Cauchy's controversial theorem arises from a
perennially confusing piece of mathematical terminology: a convergent
<em>sequence</em> is not at all the same as a convergent <em>series</em>. Cauchy
claimed that a convergent <em>series</em> of continuous functions has a
continuous limit. He did not ever claim that a convergent <em>sequence</em>
of continuous functions had a continuous limit. But I have often
encountered claims that he did that, even though such such claims are
extremely implausible.</p>
<p>The claim that Cauchy thought a sequence of continuous functions
converges to a continuous limit is not only false but is manifestly
so. Anyone making it has at best made a silly and careless error, and
perhaps doesn't really understand what they are talking about, or
hasn't thought about it.</p>
<p>[ I had originally planned to write about this controversial theorem
in <a href="http://blog.plover.com/math/major-screwups.html">my series of articles about major screwups in
mathematics</a>, but the
longer and more closely I looked at it the less clear it was that
Cauchy had actually made a mistake. ]</p>
tag:blog.plover.com,2012:/math/koanOn the consistency of PA2012-08-25T04:11:00Z2012-08-25T04:11:00ZMark Dominushttp://www.plover.com/mjd@plover.com
A monk asked Li Fu, "Master, how do we know that the Peano axioms are
consistent?"<p>
Li Fu said, "The axioms are consistent because they have a model."<p>
tag:blog.plover.com,2012:/math/topology-closed-2More about ZF's asymmetry between union and intersection2012-08-24T05:37:00Z2012-08-24T05:37:00ZMark Dominushttp://www.plover.com/mjd@plover.com
In <a href="http://blog.plover.com/math/topology-closed.html">an article earlier this
week</a>, I explored some oddities of defining a toplogy in terms of
closed sets rather than open sets, mostly as a result of analogous
asymmetry in the <a
href="http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory">ZF
set theory axioms</a>.<p>
Let's review those briefly. The relevant axioms concern the
operations by which sets can be constructed. There are two that are
important. First is the axiom of union, which says that if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> is a family
of sets, then we can form <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcup%20%7b%5cmathcal%20F%7d%24">, which is the union of all
the sets in the family.<p>
The other is actually a family of axioms, the
specification axiom schema. It says that for any one-place predicate
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cphi%28x%29%24"> and any set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> we can construct the subset of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> for
which <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cphi%24"> holds:<p>
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%5c%7b%20x%5cin%20X%20%5c%3b%7c%5c%3b%20%5cphi%28x%29%20%5c%7d%24%24%0a"></p><p>
Both of these are required. The axiom of union is for making bigger sets out of
smaller ones, and the specification schema is for extracting smaller sets from bigger
ones. (Also important is the axiom of pairing, which says that if
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24y%24"> are sets, then so is the two-element set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%7bx%2c%20y%5c%7d%24">;
with pairing and union we can construct all the finite sets. But we
won't need it in this article.)<p>
Conspicuously absent is an axiom of intersection. If you have a
family <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> of sets, and you want a set of every element that is in
<i>some</i> member of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">, that is easy; it is what the axiom of union gets
you. But if you want a set of every element that is in <i>every</i>
member of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">, you have to use specification. <p>
Let's begin by defining this compact notation:
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%5cbigcap_%7b%28X%29%7d%20%7b%5cmathcal%20F%7d%24%24%0a"></p><p>
for this longer formula:
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%5c%7b%20x%5cin%20X%20%5c%3b%7c%5c%3b%20%5cforall%20f%5cin%20%7b%5cmathcal%20F%7d%20%2e%20x%5cin%20f%20%5c%7d%24%24%0a"></p><p>
This is our intersection of the members of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">, taken "relative to
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24">", as we say in the biz. It gives us all the elements of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24">
that are in every member of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">. The <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> is mandatory in
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap_%7b%28X%29%7d%24">, because ZF makes it mandatory when you construct a
set by specification. If you leave it out, you get the Russell paradox.<p>
Most of the time, though, the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> is not very important. When
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> is nonempty, we can choose some element <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%5cin%20%7b%5cmathcal%20F%7d%24">, and
consider <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap_%7b%28f%29%7d%20%7b%5cmathcal%20F%7d%24">, which is the "normal" intersection of
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">. We can easily show that
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%5cbigcap_%7b%28X%29%7d%20%7b%5cmathcal%20F%7d%5csubseteq%20%5cbigcap_%7b%28f%29%7d%20%7b%5cmathcal%20F%7d%24%24%0a"></p>
for any <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> whatever, and this immediately implies that
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%5cbigcap_%7b%28f%29%7d%20%7b%5cmathcal%20F%7d%20%3d%20%5cbigcap_%7b%28f%27%29%7d%7b%5cmathcal%20F%7d%24%24%0a"></p>
for any two elements
of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">, so when <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> contains an element <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24">, we can omit the
subscript and just write
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%5cbigcap%20%7b%5cmathcal%20F%7d%24%24%0a"></p>
for the usual intersection of members of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">.<p>
Even the usually troublesome case of an
empty family <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> is no problem. In this case we have no <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24"> to
use for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap_%7b%28f%29%7d%20%7b%5cmathcal%20F%7d%24">, but we can still take some other set
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> and talk about <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap_%7b%28X%29%7d%20%5cemptyset%24">, which is just
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24">.<p>
Now, let's return to topology. I suggested that we should consider
the following definition of a topology, in terms of closed sets, but
without an a priori notion of the underlying space:<p>
A <b>co-topology</b> is a family <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> of sets, called "closed"
sets, such that:<p>
<ol><li>The union of any two elements of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> is again in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">, and
<li>The intersection of any subfamily of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> is again in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">.
</ol>
Item 2 begs the question of which intersection we are talking about
here. But now that we have nailed down the concept of intersections,
we can say briefly and clearly what we want: It is the intersection
relative to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcup%20%7b%5cmathcal%20F%7d%24">. This set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcup%20%7b%5cmathcal%20F%7d%24"> contains
anything that is in any of the closed sets, and so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcup%20%7b%5cmathcal%20F%7d%24">,
which I will henceforth call <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%24">, is effectively a universe of
discourse. It is certainly big enough that intersections relative to
it will contain everything we want them to; remember that
intersections of subfamilies of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> have a maximum size, so there
is no way to make <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%24"> too big. <p>
It now immediately follows that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%24"> itself is a closed set, since it
is the intersection <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap_%7b%28U%29%7d%20%5cemptyset%24"> of
the empty subfamily of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">.<p>
If <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> itself is empty, then so is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%24">, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap_%7b%28U%29%7d%20%7b%5cmathcal%20F%7d%0a%3d%20%5cemptyset%24">, so that is all right. From here on we will assume that
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24"> is nonempty, and therefore that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap%20%7b%5cmathcal%20F%7d%24">, with no
relativization, is well-defined.<p>
We still cannot prove that the empty set is closed; indeed, it might
not be, because even <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24M%20%3d%20%5cbigcap%20%7b%5cmathcal%20F%7d%24"> might not be empty. But as David
Turner pointed out to me in email, the elements of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24M%24"> play a role
dual to the extratoplogical points of a topological
space that has been defined in terms of open sets. There might be
points that are not in any open set anywhere, but we may as well
ignore them, because they are topologically featureless, and just
consider the space to be the union of the open sets. Analogously and
dually, we can ignore the points of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24M%24">, which are topologically
featureless in the same way. Rather than considering <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">, we
should consider <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cwidehat%7b%5cmathcal%20F%7d%7d%24">, whose members are the members of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathcal%20F%7d%24">,
but with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24M%24"> subtracted from each one:<p>
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%7b%5cwidehat%7b%5cmathcal%20F%7d%7d%20%3d%20%5c%7b%5chat%7bf%7d%5cin%202%5eU%20%5c%3b%7c%5c%3b%20%5cexists%20f%5cin%20%7b%5cmathcal%20F%7d%20%2e%20%5chat%7bf%7d%20%3d%20f%5csetminus%20M%20%5c%7d%24%24%0a"></p><p>
So we may as well assume that this has been done behind the scenes and
so that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap%20%7b%5cmathcal%20F%7d%24"> is empty. If we have done this, then the
empty set is closed.<p>
Now we move on to open sets. An open set is defined to be the
complement of a closed set, but we have to be a bit careful, because ZF
does not have
a global notion of the complement <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%5eC%24"> of a set. Instead, it has only
relative complements, or differences. <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%5csetminus%20Y%24"> is defined as:
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24X%5csetminus%20Y%20%3d%20%5c%7b%20x%5cin%20X%20%5c%3b%7c%5c%3b%20x%5cnotin%20Y%5c%7d%20%24%24%0a"></p><p>
Here we say that the complement of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24Y%24"> is taken relative to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24">.<p>
For the definition of open sets, we will say that the complement is
taken relative to the universe of discourse <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%24">, and a set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24G%24"> is
open if it has the form <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%5csetminus%20f%24"> for some closed set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24">.<p>
Anatoly Karp pointed out on Twitter that we know that the empty set is
open, because it is the relative complement of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%24">, which we already
know is closed. And if we ensure that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap%20%7b%5cmathcal%20F%7d%24"> is empty, as in
the previous paragraph, then since the empty set is closed, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24U%24"> is
open, and we have recovered all the original properties of a
topology.<p>
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">General Topology</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/0387901256"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=0387901256" BORDER="0" ALIGN="center" ALT="General Topology" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/0387901256"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/0387901256"><font size="-1">no kickback</font></a>
</td></tr></table></div>
But gosh, what a pain it was; in contrast recovering the missing
axioms from the corresponding open-set definition of a topology was
painless. (John Armstrong said it was bizarre, and probably several
other people were thinking that too. But I did not invent this
bizarre idea; I got it from the opening paragraph of <a
href="https://secure.wikimedia.org/wikipedia/en/wiki/John_L._Kelley">John L. Kelley</a>'s
famous book <cite>General Topology</cite>, which has been in print
since 1955. <p>
<p align=center><a href="http://pic.blog.plover.com/math/topology-closed-2/kelley.png"><img align=center
src="http://pic.blog.plover.com/math/topology-closed-2/kelley-th.png"></a><p></p>
Here Kelley deals with the empty set and the universe in
two sentences, and never worries about them again.
In contrast, doing the same thing for closed sets was fraught with
technical difficulties, mostly arising from ZF. (The exception was the
need to repair the nonemptiness of the minimal closed set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24M%24">, which
was not ZF's fault.)<p>
<br clear="right"><div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">On Numbers and Games</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568811277"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=9781568811277" BORDER="0" ALIGN="center" ALT="On Numbers and Games" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568811277"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/9781568811277"><font size="-1">no kickback</font></a>
</td></tr></table></div>
I don't think I have much of a conclusion here, except that whatever
the advantages of ZF as a millieu for doing set theory, it is
overrated as an underlying formalism for actually doing
mathematics. (Another view on this is laid out by J.H. Conway in the
Appendix to Part Zero of <cite>On Numbers and Games</cite> (Academic
Press, 1976).) None of the problems we encountered were technically
illuminating, and nothing was clarified by examining them in
detail.<p>
On the other hand, perhaps this conclusion is knocking down a straw
man. I think working mathematicians probably don't concern themselves
much with whether their stuff works in ZF, much less with what silly
contortions are required to make it work in ZF. I think day-to-day
mathematical work, to the extent that it needs to deal with set theory
at all, handles it in a fairly naïve way, depending on a sort of
folk theory in which there is some reasonably but not absurdly big
universe of discourse in which one can take complements and
intersections, and without worrying about this sort of technical
detail.<p>
[ MathJax doesn't work in Atom or RS<!-- -->S syndication feeds, and can't be
made to work, so if you are reading a syndicated version of this
article, such as you would in Google Reader, or on Planet Haskell or
PhillyLinux, you are seeing inlined images provided by the Google
Charts API. The MathJax looks much better, and if you would like to
compare, please visit <a href="http://blog.plover.com/math/topology-closed-2.html">my
blog's home site</a>. ]<p>
tag:blog.plover.com,2012:/math/topology-closedThe non-duality of open and closed sets2012-08-22T00:31:00Z2012-08-22T00:31:00ZMark Dominushttp://www.plover.com/mjd@plover.com
I had long thought that it doesn't matter if we define a topology in
terms of open sets or in terms of closed sets, because the two
definitions are in every way dual and equivalent. This seems not to
be the case: the definition in terms of closed sets seems to be
slightly weaker than the definition in terms of open sets.<p>
We can define a topology without reference to
the underlying space as follows: A family <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathfrak%20I%7d%24"> of sets is a topology
if it is closed under pairwise intersections and arbitrary unions, and
we call a set "open" if it is an element of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathfrak%20I%7d%24">. From this we can
recover the omitted axiom that says that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cemptyset%24"> is open: it must
be in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathfrak%20I%7d%24"> because it is the empty union <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcup_%7bg%5cin%5cemptyset%7d%0ag%24">. We can also recover the underlying space of the topology, or at
least <i>some</i> such space, because it is the unique maximal open set
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%3d%5cbigcup_%7bg%5cin%7b%5cmathfrak%20I%7d%7d%20g%24">. The space <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> might be embedded in some
larger space, but we won't ever have to care, because that larger
space is topologically featureless. From a topological point of view,
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> is our universe of discourse. We can then say that a set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%24"> is
"closed" whenever <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%5csetminus%20C%24"> is open, and prove all the usual
theorems.<p>
If we choose to work with closed sets instead, we run into problems.
We can try starting out the same way: A family <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathfrak%20I%7d%24"> of sets is a
co-topology if it is closed under pairwise unions and arbitrary
intersections, and we call a set "closed" if it is an element of
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7b%5cmathfrak%20I%7d%24">. But we can no longer prove that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cemptyset%5cin%7b%5cmathfrak%20I%7d%24">. We can
still recover an underlying space <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%20%3d%20%5cbigcup_%7bc%5cin%7b%5cmathfrak%20I%7d%7d%20c%24">, but we
cannot prove that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> is closed, or identify any maximal closed set
analogous to the maximal open set of the definition of the previous
paragraph. We can construct a <i>minimal</i> closed set
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigcap_%7bc%5cin%7b%5cmathfrak%20I%7d%7d%20c%24">, but we don't know anything useful about it,
and in particular we don't know whether it is empty, whereas with the
open-sets definition of a topology we can be sure that the empty set
is the unique minimal open set.<p>
We can repair part of this asymmetry by changing the "pairwise unions"
axiom to "finite unions"; then the empty set is closed because it is a
finite union of closed sets. But we still can't recover any maximal
closed set. Given a topology, it is easy to identify the unique
maximal closed set, but given a co-topology, one can't, and indeed
there may not be one. The same thing goes wrong if one tries to define
a topology in terms of a Kuratowski closure operator.<p>
We might like to go on and say that complements of closed sets are
open, but we can't, because we don't have a universe of discourse in
which we can take complements.<p>
None of this may make very much difference in practice, since we
usually do have an a priori idea of the universe of discourse, and so
we do not care much whether we can define a topology without reference
to any underlying space. But it is at least conceivable that we might
want to abstract away the underlying space, and if we do, it appears
that open and closed sets are not as exactly symmetric as I thought
they were.<p>
Having thought about this some more, it seems to me that the ultimate
source of the asymmetry here is in our model of set theory. The role
of union and intersection in ZF is not as symmetric as one might like.
There is an axiom of union, which asserts that the union of the
members of some family of sets is again a set, but there is no
corresponding axiom of intersection. To get the intersection of a
family of sets <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cmathcal%20S%24">, you use a specification axiom. Because of
the way specification works, you cannot take an empty intersection,
and there is no universal set. If topology were formulated in a set
theory with a universal set, such as NF, I imagine the asymmetry would
go away.<p>
[ This is my first blog post using <a
href="http://www.mathjax.org">MathJax</a>, which I hope will
completely replace the ad-hoc patchwork of systems I had been using to
insert mathematics. Please email me if you encounter any
bugs. ]<p>
[ Addendum 20120823: MathJax depends on executing Javascript, and so
it won't render in an RSS or Atom feed or on any page where the blog
content is syndicated. So my syndication feed is using the Google
Charts service to render formulas for you. If the formulas look funny,
try looking at <a
href="http://blog.plover.com/">http://blog.plover.com/</a>
directly. ]<p>
[ Addendum 20120824: <a
href="http://blog.plover.com/math/topology-closed-2.html">There is a followup to this
article</a>. ]<p>
tag:blog.plover.com,2012:/math/russellElaborations of Russell's paradox2012-01-10T18:46:00Z2012-01-10T18:46:00ZMark Dominushttp://www.plover.com/mjd@plover.com
When Iris was five or six, I told her about Russell's paradox in the
following form: in a certain library, some books are catalogs that
contain lists of other books. For example, there is a catalog of all
the books on the second floor, and a catalog of all the books about
birds. Some catalogs might include themselves. For example, the
catalog of all the books in the library certainly includes itself.
Such catalogs have red covers; the other catalogs, which do not
include themselves, such as the catalog of all the plays of
Shakespeare, have blue covers. Now is there a catalog of all the
catalogs with blue covers?<p>
I wasn't sure she would get this, but it succeeded much better than I
expected. After I prompted her to consider what color cover it would
have, she thought it out, first ruling out one color, and then, when
she got to the second color, she just started laughing.<p>
A couple of days ago she asked me if I could think of anything that
was like that but with three different colors. Put on the spot, I
suggested she consider what would happen if there could be green
catalogs that might or might not include themselves. This is
somewhat interesting, because you now <i>can</i> have a catalog of
all the blue catalogs; it can have a green cover. But I soon thought
of a much better extension.<p>
I gave it to Iris like this: say you have a catalog, let's call it
<i>X</i>. If <i>X</i> mentions a catalog that mentions <i>X</i>, it
has a gold stripe on the spine. Otherwise, it has a silver stripe.
Now:<p>
<ol>
<li>Could there be a red catalog with a gold stripe?
<li>Could there be a red catalog with a silver stripe?
<li>Could there be a blue catalog with a gold stripe?
<li>Could there be a blue catalog with a silver stripe?
</ol>
And more interesting:<p>
<ol start=5>
<li>Is there a catalog of all the catalogs with gold stripes?
<li>Is there a catalog of all the catalogs with silver stripes?
</ol>
I knew that early 20th century logicians, trying to repair the Russell paradox,
first tried a very small patch: since comprehension over the predicate
<i>X</i>∉<i>X</i> causes problems, just forbid that
predicate. This unfortunately doesn't solve the problem at all; there
are an infinite number of equally problematic predicates. (Whitehead
and Russell's theory of types is an attempt to fix this; Quine's New
Foundations is a different attempt.) One of these predicates is
¬∃Y.X∈Y and Y∈X. You can't construct the set of all
<i>X</i> such that ¬∃Y.X∈Y and Y∈X because there is no
such set, for reasons similar to the reason why there's no set of all
<i>X</i> such that <i>X</i>∉<i>X</i>, so that's where I got the
silver stripe predicate.<p>
Translating this into barber language is left as an exercise for the
reader.<p>
tag:blog.plover.com,2011:/math/concertsConcerts2011-06-11T17:35:00Z2011-06-11T17:35:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">Unknown book with tag 'Tao problems'</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/0000000000"></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/0000000000"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/0000000000"><font size="-1">no kickback</font></a>
</td></tr></table></div>
At a book sale I recently picked up Terence Tao's little book on
problem solving for 50¢. One of the exercises
(pp. 85–86) is the following little charmer: There are six
musicians who will play a series of concerts. At each concert, some
of the musicians will be on stage and some will be in the audience.
What is the fewest number of concerts that can be played to that each
musician gets to see the each of the others play?<p>
Obviously, no more than six concerts are required. (I have a new
contribution to the long-debated meaning of the mathematical jargon
term "obviously": if my six-year-old daughter could figure out the
answer, so can you.) And an easy argument shows that four are
necessary: let's say that when a musician views another, that is a
"viewing event"; we need to arrange at least 5×6 = 30 viewing
events. A concert that has <i>p</i> performers and 6-<i>p</i>
in the audience arranges <i>p</i>(6 - <i>p</i>) events, which must be
5, 8, or 9. Three concerts yield no more than 27 events, which is
insufficient. So there must be at least 4 concerts, and we may as
well suppose that each concert has three musicians in the audience and
three onstage, to maximize the number of events at 9·4 =
36. (It turns out there there is no solution otherwise, but that is a
digression.)<p>
Each musician must attend at least 2 concerts, or else they would see
only 3 other musicians onstage. But 6 musicians attending 2 concerts
each takes up all 12 audience spots, so every musician is at exactly 2
concerts. Each musician thus sees exactly six musicians onstage, and
since five of them must be different, one is a repeat, and the viewing
event is wasted. We knew there would be some waste, since there are
36 viewing avents available and only 30 can be useful, but now we know
that each spectator wastes exactly one event.<p>
A happy side effect of splitting the musicians evenly between the
stage and the audience in every concert is that we can exploit the
symmetry: if we have a solution to the problem, then we can obtain a
dual solution by exchanging the performers and the audience in each
concert. The conclusion of the previous paragraph is that in any
solution, each spectator wastes exactly one event; the duality tells
us that each performer is the subject of exactly one wasted event.<p>
Now suppose the same two musicians, say <i>A</i> and <i>B</i>, perform
together twice. We know that some spectator must see <i>A</i> twice;
this spectator sees <i>B</i> twice also, this wasting two events. But
each spectator wastes only one event. So no two musicians can share
the stage twice; each two musicians share the stage exactly once. By
duality, each two spectators are in the same audience together exactly
once.<p>
So we need to find four 3-sets of the elements { A, B, C, D, E, F }, with
each element appearing in precisely two sets, and such that each two
sets have exactly one element in common.<p>
Or equivalently, we need to find four triangles in <i>K</i><sub>4</sub>, none of which
share an edge.<p>
The solution is not hard to find:<p>
<p align=center>
<table cellpadding=2>
<tr><td > <td bgcolor="pink" align="center">1<td bgcolor="white" align="center">2<td bgcolor="pink" align="center">3<td bgcolor="white" align="center">4
<tr><td align="center">On stage<td bgcolor="pink" align="center">A B C<td bgcolor="white" align="center">C D E<td bgcolor="pink" align="center">E F A<td bgcolor="white" align="center">B D F
<tr><td align="center">In audience<td bgcolor="pink" align="center">D E F<td bgcolor="white" align="center">A B F<td bgcolor="pink" align="center">B C D<td bgcolor="white" align="center">A C E
</table>
</p>
And in fact this solution is essentially unique.<p>
If you generalize these arguments to 2<i>m</i> musicians, you find
that there is a lower bound of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%5cleft%5clceil%7b4m%5e2%20%2d%202m%20%5cover%20m%5e2%20%7d%5cright%5crceil"> concerts,
which is 4. And indeed, even with as few as 4 musicians, you still need four
concerts. So it's tempting to wonder if 4 concerts is really
sufficient for all even numbers of musicians. Consider 8 musicians,
for example. You need 56 viewing events, but a concert with half
the musicians onstage and half in the audience provides 16 events, so you
might only need as few as 4 concerts to provide the necessary
events.<p>
The geometric formulation is that you want to find four
disjoint <i>K</i><sub>4</sub>s in a <i>K</i><sub>4</sub>; or alternatively, you want to find four
4-element subsets
of { 1,2,3,4,5,6,7,8 }, such that each element appears in exactly two
sets and no two elements are in the same. There seemed to be no immediately obvious
reason that this wouldn't work, and I spent a while tinkering around
looking for a way to do it and didn't find one. Eventually I did an
exhaustive search and discovered that it was impossible.<p>
But the tinkering and the exhaustive search were a waste of time,
because there <i>is</i> an obvious reason why it's impossible. As
before, each musician must be in exactly two audiences, and can share
audiences with each other musician at most once. But there are only 6
ways to be in two audiences, and 8 musicians, so some pair of
musicians must be in precisely the same pair of audiences, this wastes
too many viewing events, and so there's no solution. Whoops!<p>
It's easy to find solutions for 8 musicians with 5 concerts, though.
There is plenty of room to maneuver and you can just write one down
off the top of your head. For example:<p>
<p align=center>
<table cellpadding=2 >
<tr><td align="center"> <td bgcolor="pink" align="center">1<td bgcolor="white" align="center">2<td bgcolor="pink" align="center">3<td bgcolor="white" align="center">4<td bgcolor="pink" align="center">5
<tr><td " align="center">On stage <td bgcolor="pink" align="center">E F G H<td bgcolor="white" align="center">B C D H<td bgcolor="pink" align="center">A C D F G<td bgcolor="white" align="center">A B D E G<td bgcolor="pink" align="center">A B C E F H
<tr><td align="center">In audience<td bgcolor="pink" align="center">A B C D<td bgcolor="white" align="center">A E F G<td bgcolor="pink" align="center">B E H <td bgcolor="white" align="center">C F H <td bgcolor="pink" align="center">D G
</table>
</p>
Actually I didn't write this one down off the top of my head; I have a
method that I'll describe in a future article. But this article has
already taken me several weeks to get done, so I'll stop here for
now.<p>
[ Addendum: For <i>n</i> = 1…10 musicians, the least number of
concerts required is 0, 2, 3, 4, 4, 4, 5, 5, 5, 5; beyond this, I only
have bounds. ]<p>
tag:blog.plover.com,2010:/math/topology-docA draft of a short introduction to topology2010-11-15T18:31:00Z2010-11-15T18:31:00ZMark Dominushttp://www.plover.com/mjd@plover.com
One of my ongoing projects is to figure out how to explain topology
briefly. For example, <a href="http://blog.plover.com/math/metric.html">What is
Topology?</a>, putatively part 1 of a three-part series that I have
not yet written parts 2 or 3 of yet.<p>
CS grad students often have to take classes in category theory. These
classes always want to use groups and topological spaces as examples,
and my experience is that at this point many of the students shift
uncomfortably in their seats since they have not had undergraduate
classes in group theory, topology, analysis, or anything else
relevant. But you do not have to know much topology to be able to
appreciate the example, so I tried to write up the minimal amount
necessary. Similarly, if you already understand intuitionistic logic,
you do not need to know much topology to understand the way in which
topological spaces are natural models for intuitionistic
logic—but you do need to know more than zero.<p>
So a couple of years ago I wrote up a short introduction to topology
for first-year computer science grad students and other people who
similarly might like to know the absolute minimum, and only the
absolute minimum, about topology. It came out somewhat longer than I
expected, 11 pages, of which 6 are the introduction, and 5 are about
typical applications to computer science. But it is a very light,
fluffy 11 pages, and I am generally happy with it.<p>
I started writing this shortly after my second daughter was born, and
I have not yet had a chance to finish it. It contains many errors.
Many, many errors. For example, there is a section at the end about
the <a
href="http://en.wikipedia.org/wiki/Compactness_theorem">compactness
principle</a>, which can only be taken as a sort of pseudomathematical
lorem ipsum. This really is a draft; it is only three-quarters
finished.<p>
But I do think it will serve a useful function once it is finished,
and that finishing it will not take too long. If you have any
interest in this project, I invite you to help.<p>
The current draft is version <b>0.6</b> of <b>2010-11-14</b>. I do
not want old erroneous versions wandering around confusing people in
my name, so please do not distribute this draft after
<b>2010-12-15</b>. I hope to have an improved draft available here
before that.<p>
Please do send me corrections, suggestions, questions, advice,
patches, pull requests, or anything else.<p>
<ul>
<li><a href="http://pic.blog.plover.com/math/topology-doc/topology-draft-0.6.pdf">PDF</a><br>
<li><a href="http://pic.blog.plover.com/math/topology-doc/topology-draft-0.6.tex">LaTeX source</a>
<li><a href="https://github.com/mjdominus/topology-doc">Github git
repository</a> (<tt>git://github.com/mjdominus/topology-doc.git</tt>)
</ul>
tag:blog.plover.com,2010:/math/semiSemi-boneless ham2010-11-08T18:11:00Z2010-11-08T18:11:00ZMark Dominushttp://www.plover.com/mjd@plover.com
The Math Project on Wikipedia is having a discussion about whether or
not to have an article about the jargon term "semi-infinite", which I
have long considered one of my favorite jargon terms, because it
sounds so strange, but makes so much sense. A structure is
semi-infinite when it is infinite in one direction but not in the
other. For example, the set of positive integers is semi-infinite,
since it possesses a least element (1) but no greatest element.
Similarly rays in geometry are semi-infinite.<p>
The term is informal, however, and it's not clear just what it should
mean in all cases. For example, consider the set <i>S</i> of
1/<i>n</i> for every positive integer <i>n</i>. Is this set
semi-infinite? It is bounded in both directions, since it is
contained in [0, 1]. But as you move left through the set, you
ancounter an infinite number of elements, so it ought to be
semi-infinite in the same sense that <i>S</i> ∪ { 1-<i>x</i> :
<i>x</i> ∈ <i>S</i> } is fully-infinite. Whatever sense that is.<p>
Informal and ill-defined it may be, but the term is widely used; one
can easily find mentions in the literature of semi-infinite paths,
semi-infinite strips, semi-infinite intervals, semi-infinite
cylinders, and even semi-infinite reservoirs and conductors.<p>
<img src="http://pic.blog.plover.com/math/semi/Sextant.png" align="left"/> <img
src="http://pic.blog.plover.com/math/semi/hyperbola.png" align="right"/> The term has spawned an
offshoot, the even stranger-sounding "quarter-infinite". This seems
to refer to a geometric object that is unbounded in the same way that
a quarter-plane is unbounded, where "in the same way" is left rather
vague. Consider the set (depicted at left) of all points of the plane
for which 0 ≤ |<i>y</i>/<i>x</i>| ≤ √3, for example; is
this set quarter-infinite, or only 1/6-infinite? Is the set of points
(depicted at right) with <i>xy</i> > 1 and <i>x</i>, <i>y</i> >
0 quarter-infinite? I wouldn't want to say. But the canonical
example is simple: the product of two semi-infinite intervals is a
quarter-infinite set.<p>
I was going to say that I had never seen an instance of the obvious
next step, the eighth-infinite solid, but in researching this article I
did run into a few. I can't say it trips off the tongue, however.
And if we admit that a half of a quarter-infinite plane segment is
also eighth-infinite, we could be getting ourselves into trouble.<p>
(This all reminds me of the complaint of J.H. Conway of the
increasing use of the term "biunique". Conway sarcastically asked if
he should expect to see "triunique" and soforth, culminating in the
idiotic "polyunique".)<p>
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">General Topology</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/0387901256"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=0387901256" BORDER="0" ALIGN="center" ALT="General Topology" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/0387901256"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/0387901256"><font size="-1">no kickback</font></a>
</td></tr></table></div>
Sometimes "semi" really does mean exactly one-half, as in "semimajor
axis" (the longest segment from the center of an ellipse to its
boundary), "semicubic parabola" (determined by an equation with a term
<i>kx</i><sup>3/2</sup>), or "semiperimeter" (half the perimeter of a
triangle). But just as often, "semi" is one of the dazzling supply of
mathematical pejoratives. ("Abnormal, irregular, improper,
degenerate, inadmissable, and otherwise undesirable", says Kelley's
<cite>General Topology</cite>.) A semigroup, for example, is not half of a
group, but rather an algebraic structure that possesses less structure
than a group. Similarly, one has semiregular polyhedra and semidirect
products.<p>
I was planning to end with a note that mathematics has so far avoided
the "demisemi-" prefix. But alas! Google found this 1971 paper on <a
href="http://www.springerlink.com/content/r225012888j46612/">Demi-semi-primal
algebras and Mal'cev-type conditions</a>.<p>
tag:blog.plover.com,2009:/math/GdlAnother short explanation of Gödel's theorem2009-12-14T15:27:00Z2009-12-14T15:27:00ZMark Dominushttp://www.plover.com/mjd@plover.com
In <a href="http://blog.plover.com/math/Gdl-Smullyan.html">yesterday's article</a>, I
said:<p>
<blockquote>
A while back I started writing up an article titled "World's shortest
explanation of Gödel's theorem". But I didn't finish it...
</blockquote><p> <!-- I started it on 2008-01-09 -->
I went and had a look to see what was wrong with it, and to my
surprise, there seemed to be hardly anything wrong with it. Perhaps I
just forgot to post it. So if you disliked yesterday's brief
explanation of Gödel's theorem—and many people did—you'll probably
dislike this one even more. Enjoy!<p>
<hr>
A reader wrote to question my characterization of Gödel's theorem in <a href="http://blog.plover.com/math/major-screwups.html">the
previous article</a>. But I think I characterized it correctly; I
said:<p>
<blockquote>
The only systems of mathematical axioms strong enough to prove all
true statements of arithmetic, are those that are so strong that they
also prove all the false statements of arithmetic.
</blockquote>
I'm going to explain how this works.<p>
You start by choosing some system of mathematics that has some
machinery in it for making statements about things like numbers and for
constructing proofs of theorems like 1+1=2. Many such systems exist.
Let's call the one we have chosen
<i>M</i>, for "mathematics". <p>
Gödel shows that if <i>M</i> has enough mathematical machinery in it to
actually do arithmetic, then it is possible to produce a statement
<i>S</i> whose meaning is essentially "Statement <i>S</i> cannot be
proved in system <i>M</i>."<p>
It is not at all obvious that this is possible, or how it can be done,
and I am not going to get into the details here. Gödel's contribution
was seeing that it <i>was</i> possible to do this.<p>
So here's <i>S</i> again:<p>
<blockquote>
<i>S</i>: Statement <i>S</i> cannot be
proved in system <i>M</i>.
</blockquote><p>
Now there are two possibilities. Either <i>S</i> is in fact provable
in system <i>M</i>, or it is not. One of these must hold.<p>
If <i>S</i> is provable in system <i>M</i>, then it is false, and so
it is a false statement that can be proved in system <i>M</i>.
<i>M</i> therefore proves some false statements of arithmetic.<p>
If <i>S</i> is not provable in system <i>M</i>, then it is true, and
so it is a true statement that cannot be proved in system <i>M</i>.
<i>M</i> therefore fails to prove some true statements of
arithmetic.<p>
So something goes wrong with <i>M</i>: either it fails to prove some
true statements, or else it succeeds in proving some false
statements. <p>
List of topics I deliberately omitted from this article, that
mathematicians should not write to me about with corrections:
Presburger arithmetic. Dialetheism. Inexhaustibility.
ω-incompleteness. Non-RE sets
of axioms.<p>
<hr>
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">Godel's Theorem: An Incomplete Guide to Its Use and Abuse</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568812388"><IMG SRC="http://pic.blog.plover.com/covers/FranzenGodel.jpg" BORDER="0" ALIGN="center" ALT="Godel's Theorem: An Incomplete Guide to Its Use and Abuse" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568812388"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/9781568812388"><font size="-1">no kickback</font></a>
</td></tr></table></div><div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">Inexhaustibility: A Non-Exhaustive Treatment</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568811756"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=9781568811756" BORDER="0" ALIGN="center" ALT="Inexhaustibility: A Non-Exhaustive Treatment" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568811756"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/9781568811756"><font size="-1">no kickback</font></a>
</td></tr></table></div>
Well, I see now that left out the step where I go from "<i>M</i>
proves a false statement" to "<i>M</i> proves all false statements".
Oh well, another topic for another post. <p>
If you liked this post, you may
enjoy Torkel Franzén's books <cite>Godel's Theorem: An Incomplete
Guide to Its Use and Abuse</cite> and <cite>Inexhaustibility: A
Non-Exhaustive Treatment</cite>. If you disliked this post, you are
even more likely to enjoy them.<p>
<br clear=all>
<hr>
Many thanks to Robert Bond for his contribution.<p>
tag:blog.plover.com,2009:/math/Gdl-SmullyanWorld's shortest explanation of Gödel's theorem2009-12-13T10:05:00Z2009-12-13T10:05:00ZMark Dominushttp://www.plover.com/mjd@plover.com
A while back I started writing up an article titled "World's shortest
explanation of Gödel's theorem". But I didn't finish it, and
later I encountered Raymond Smullyan's version, which is much shorter
anyway. So here, shamelessly stolen from Smullyan, is the World's
shortest explanation of Gödel's theorem.<p>
We have some sort of machine that prints out statements in some sort
of language. It needn't be a statement-printing machine exactly; it
could be some sort of technique for taking statements and deciding if
they are true. But let's think of it as a machine that prints out
statements. <p>
In particular, some of the statements that the machine might (or might
not) print look like these:<p>
<table align=center>
<tr><td align=right><tt>P*</tt><i>x</i>
<td>(which means that
<td>the machine will print <i>x</i>)
<tr><td align=right><tt>NP*</tt><i>x</i>
<td>(which means that
<td>the machine will never print <i>x</i>)
<tr><td align=right><tt>PR*</tt><i>x</i>
<td>(which means that
<td>the machine will print <i>xx</i>)
<tr><td align=right><tt>NPR*</tt><i>x</i>
<td>(which means that
<td>the machine will never print <i>xx</i>)
</table><p>
For example, <tt>NPR*FOO</tt> means that the machine will never print
<tt>FOOFOO</tt>. <tt>NP*FOOFOO</tt> means the same thing. So far, so
good.<p>
Now, let's consider the statement <tt>NPR*NPR*</tt>. This statement
asserts that the machine will never print <tt>NPR*NPR*</tt>.<p>
Either the machine prints <tt>NPR*NPR*</tt>, or it never prints
<tt>NPR*NPR*</tt>.<p>
If the machine prints <tt>NPR*NPR*</tt>, it has printed a false
statement. But if the machine never prints <tt>NPR*NPR*</tt>, then
<tt>NPR*NPR*</tt> is a true statement that the machine never
prints.<p>
So either the machine sometimes prints false statements, or there are
true statements that it never prints.<p>
So any machine that prints only true statements must fail to print
some true statements.<p>
Or conversely, any machine that prints every possible true statement
must print some false statements too.<p>
<hr>
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">5000 B.C. and Other Philosophical Fantasies</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/9780312295170"><IMG SRC="http://pic.blog.plover.com/covers/5000BC.jpg" BORDER="0" ALIGN="center" ALT="5000 B.C. and Other Philosophical Fantasies" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/9780312295170"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/9780312295170"><font size="-1">no kickback</font></a>
</td></tr></table></div>
The proof of Gödel's theorem shows that there are statements of
pure arithmetic that essentially express <tt>NPR*NPR*</tt>; the trick
is to find some way to express <tt>NPR*NPR*</tt> as a statement about
arithmetic, and most of the technical details (and cleverness!) of
Gödel's theorem are concerned with this trick. But once the
trick is done, the argument can be applied to any machine or other
method for producing statements about arithmetic.<p>
The conclusion then translates directly: any machine or method that
produces statements about arithmetic either sometimes produces false
statements, or else there are true statements about arithmetic that it
never produces. Because if it produces something like
<tt>NPR*NPR*</tt> then it is wrong, but if it fails to produce
<tt>NPR*NPR*</tt>, then that is a true statement that it has failed to
produce.<p>
So any machine or other method that produces only true statements
about arithmetic must fail to produce some true statements.<p>
Hope this helps!<p>
(This explanation appears in Smullyan's book <cite>5000 BC and Other
Philosophical Fantasies</cite>, chapter 3, section 65, which is where
I saw it. He discusses it at considerable length in Chapter 16 of
<cite>The Lady or the Tiger?</cite>, "Machines that Talk About
Themselves". It also appears in <cite>The Mystery of
Scheherezade</cite>.)<p>
<br clear=all>
<hr>
I gratefully acknowledge Charles Colht for his generous donation to
this blog.<p>
<hr>
[ Addendum 20091214: <a href="http://blog.plover.com/math/Gdl.html">Another article
on the same topic</a>. ]<p>
tag:blog.plover.com,2009:/math/gray-codesGray code at the pediatrician's office2009-06-21T15:14:00Z2009-06-21T15:14:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<img style="float: left; margin-right: 2em;" src="http://pic.blog.plover.com/math/gray-codes/bin.png">
<img style="float: right; margin-left: 2em;" src="http://pic.blog.plover.com/math/gray-codes/gray.png">
Last week we took Iris to the pediatrician for a checkup, during which
they weighed, measured, and inoculated her. The measuring device,
which I later learned is called a stadiometer, had a bracket on a slider that went up and down on a
post. Iris stood against the post and the nurse adjusted the bracket
to exactly the top of her head. Then she read off Iris's height from
an attached display.<p>
How did the bracket know exactly what height to report? This was done
in a way I hadn't seen before. It had a
photosensor looking at the post, which was printed with this
pattern:<p>
<p align=center><a href="http://pic.blog.plover.com/math/gray-codes/index200.html"><img
src="http://pic.blog.plover.com/math/gray-codes/17895976833.jpg" border=0></a></p>
(Click to view the other pictures I took of the post.)<p>
The pattern is binary numerals. Each numeral is a certain fraction of
a centimeter high, say 1/4 centimeter. If the sensor reads the number
433, that means that the bracket is 433/4 = 108.25 cm off the ground,
and so that Iris is 108.25 cm tall.<p>
The patterned strip in the left margin of this article is a
straightforward translation of binary numerals to black and white
boxes, with black representing 1 and white representing 0:<p>
<blockquote>
0000000000<br>
0000000001<br>
0000000010<br>
0000000011<br>
0000000100<br>
0000000101<br>
0000000101<br>
...<br>
1111101000<br>
1111101001<br>
...<br>
1111111111<br>
</blockquote>
If you are paying attention, you will notice that although the strip
at left is similar to the pattern in the doctor's office, it is not
the same. That is because the numbers on the post are Gray-coded.<p>
Gray codes solve the following problem with raw binary numbers.
Suppose Iris is close to 104 = 416/4 cm tall, so that the photosensor is in
the following region of the post:<p>
<blockquote>
...<br>
0110100001 (417)<br>
0110100000 (416)<br>
0110011111 (415)<br>
0110011110 (414)<br>
...<br>
</blockquote>
But suppose that the sensor (or the post) is slightly mis-aligned, so
that instead of properly reading the (416) row, it reads the first
half of the (416) row and last half of the (415) row. That makes
0110111111, which is 447 = 111.75 cm, an error of almost 7.5%.
(That's three inches, for my American and Burmese readers.) Or the
error could go the other way: if the sensor reads the first half of
the (415) and the second half of the (416) row, it will see 0110000000
= 384 = 96 cm.<p>
Gray code is a method for encoding numbers in binary so that each
numeral differs from the adjacent ones in only one position:<p>
<blockquote>
0000000000<br>
000000000<b>1</b><br>
00000000<b>1</b>1<br>
000000001<b>0</b><br>
0000000<b>1</b>10<br>
000000011<b>1</b><br>
00000001<b>0</b>1<br>
000000010<b>0</b><br>
000000<b>1</b>100<br>
...<br>
100001<b>1</b>100<br>
100001110<b>1</b><br>
...<br>
100000000<b>0</b><br>
</blockquote>
This is the pattern from the post, which you can also see at the right
of this article.<p>
Now suppose that the mis-aligned sensor reads part of the (416) line and
part of the (417) line. With ordinary binary coding, this could
result in an error of up to 7.75 cm. (And worse errors for children
of other heights.) But with Gray coding no error results from the
misreading: <p>
<blockquote>
...<br>
0101110000 (417)<br>
0101010000 (416)<br>
0101010001 (415)<br>
0101010011 (414)<br>
...<br>
</blockquote>
No matter what parts of 0101110000 and 0101110001 are stitched
together, the result is always either 416 or 417. <p>
Converting from Gray code to standard binary is easy: take the binary
expansion, and invert every bit that is immediately to the right of a
1 bit. For example, in 1<font color="red">1</font><font color="red">1</font><font color="red">1</font><font color="red">1</font><font color="red">0</font>1<font color="red">0</font>00, each red bit is to the right of a
1, and so is inverted to obtain the Gray code 1<font color="red">0</font><font color="red">0</font><font color="red">0</font><font color="red">0</font><font color="red">1</font>1<font color="red">1</font>00. <p>
Converting back is also easy:
of the Gray code. Replace every sequence of the form 1000...01
with 1111...10; also replace 1000... with 1111... if it appears at the
end of the code. For
example, Gray code <font color="red">100001</font><font
color="blue">11</font>00 contains two such sequences, <font
color="red">100001</font> and <font color="blue">11</font>, which are
replaced with <font color="red">111110</font> and <font
color="blue">10</font>, to give <font color="red">111110</font><font
color="blue">10</font>00. <p>
[ Addendum 20110525: Every so often someone asks why the stadiometer
is so sophisticated. <a href="http://blog.plover.com/tech/stadiometer.html">Here is
the answer</a>. ]<p>