Math SE report 201506
[ This page originally held the report for April
2015, which has moved. It now contains
the report for June 2015. ]
Is “smarter than” a transitive
relationship?
concerns a hypothetical "is smarter than" relation with the
following paradoxicalseeming property:
most X's are smarter than most Y's, but most Y's are such that it
is not the case that most X's are smarter than it.
That is, if !!\mathsf Mx.\Phi(x)!! means that most !!x!! have property
!!\Phi!!, then we want both $$\mathsf Mx.\mathsf My.S(x, y)$$ and
also $$\mathsf My.\mathsf Mx.\lnot S(x, y).$$
“Most” is a little funny here: what does it mean? But we can pin it
down by supposing that there are an infinite number of !!x!!es and
!!y!!s, and agreeing that most !!x!! have property !!P!! if there
are only a finite number of exceptions. For example, everyone
should agree that most positive integers are larger than 7 and that
most prime numbers are odd. The jargon word here is that we are
saying that a subset contains “most of” the elements of a larger set
if it is cofinite.
There is a model of this property, and OP reports that they asked
the prof if this was because the "smarter than" relation !!S(x,y)!!
could be antitransitive, so that one might have !!S(x,y), S(y,z)!!
but also !!S(z,x)!!. The prof said no, it's not because of that,
but the OP want so argue that it's that anyway. But no, it's not
because of that; there is a model that uses a perfectly simple
transitive relation, and the nontransitive thing nothing but a
distraction. (The model maps the !!x!!es and !!y!!s onto numbers,
and says !!x!! is smarter than !!y!! if its number is bigger.)
Despite this OP couldn't give up the idea that the model exists
because of intransitive relations. It's funny how sometimes people
get stuck on one idea and can't let go of it.
How to generate a random number between 1 and 10 with a sixsided
die? was a lot of
fun and attracted several very good answers. Topscoring is Jack
D'Aurizio's, which proposes a completely straightforward method:
roll once to generate a bit that selects !!N=0!! or !!N=5!!, and
then roll again until you get !!M\ne 6!!, and the result is !!N+M!!.
But several other answers were suggested, including two by me, one
explaining the general technique of arithmetic
coding, which I'll
probably refer back to in the future when people ask similar
questions. Don't miss NovaDenizen's clever simplification of
arithmetic coding,
which I want to think about more, or D'Aurizio's suggestion that if
you threw the die into a Vshaped trough, it would land with one
edge pointing up and thus select a random number from 1 to 12 in a
single throw.
Interesting question: Is there an easytoremember mapping from
edges to numbers from 1–12? Each edge is naturally identified by a
pair of distinct integers from 1–6 that do not add to 7.
The oddlyphrased Category theory with objects as logical
expressions over !!{\vee,\wedge,\neg}!! and morphisms
as? asks if there is
a standard way to turn logical expressions into a category, which
there is: you put an arrow from !!A\to B!! for each proof that !!A!!
implies !!B!!; composition of arrows is concatenation of proofs, and
identity arrows are empty proofs. The categorial product,
coproduct, and exponential then correspond to !!\land, \lor, !! and
!!\to!!.
This got me thinking though. Proofs are properly not lists, they are
trees, so it's not entirely clear what the concatenation operation
is. For example, suppose proof !!X!! concludes !!A!! at its root
and proof !!Y!! assumes !!A!! in more than one leaf. When you
concatenate !!X!! and !!Y!! do you join all the !!A!!'s, or what? I
really need to study this more. Maybe the Lambek and Scott book
talks about it, or maybe the Goldblatt Topoi book, which I actually
own. I somehow skipped most of the Cartesian closed category stuff,
which is an oversight I ought to correct.
In Why is the Ramsey`s theorem a generalization of the Pigeonhole
principle I gave
what I thought was a terrific answer, showing how Ramsey's graph
theorem and the pigeonhole principle are both special cases of
Ramsey's hypergraph theorem. This might be my favorite answer of
the month. It got several upvotes, but OP preferred a different
answer, with fewer details.
There was a thread a while
back about theorems
which are generalizations of other theorems in nonobvious ways. I
pointed out the Yoneda lemma was a generalization of Cayley's
theorem from group theory. I see that nobody mentioned the Ramsey
hypergraph theorem being a generalization of the pigeonhole
principle, but it's closed now, so it's too late to add it.
In Why does the Deduction Theorem use
Union? I explained
that the English word and actually has multiple meanings. I know I've
seen this discussed in elementary logic texts but I don't remember
where.
Finally, Which is the largest power of natural number that can be
evaluated by
computers? asks if
it's possible for a computer to calculate !!7^{120000000000}!!. The
answer is yes, but it's nontrivial and you need to use some tricks.
You have to use the multiplyingbysquaring trick, and for the
squarings you probably want to do the multiplication with DFT. OP
was dissatistifed with the answer, and seemed to have some axe to
grind, but I couldn't figure out what it was.
[Other articles in category /math/se]
permanent link
