The Universe of Discourse

Was the Lollipop Guild inspired by W.W. Denslow?

Yesterday I was thinking on these creepy Munchkins, and wondering what they were doing there:

It occurred to me that these guys are quite consistent with the look of the original illustrations, by W.W. Denslow. Here's Denslow's picture of three Munchkins greeting Dorothy:

(Click for complete illustration.)

Denslow and Frank Baum had a falling out after the publication of The Wonderful Wizard of Oz, and the illustrations for the thirteen sequels were done by John R. Neill, in a very different style. Dorothy aged up to eleven or twelve years old, and became a blonde with a fashionable bob.

[Other articles in category /art] permanent link

One song to the tune of another

I just randomly happened upon this recording of Pippa Evans singing “How Much is that Doggie in the Window” to the tune of “Cabaret”, and this reminded me of something I was surprised I hadn't mentioned before.

In the 1939 MGM production of The Wizard of Oz, there is a brief musical number, The Lollipop Guild, that has the same music as the refrain of Money, also from Cabaret. I am not aware of anyone else who has noticed this.

One has the lyrics “money makes the world go around” and the other has “We represent the lollipop guild”. And the two songs not only have the same rhythm, but the same melody and both are accompanied by the same twitchy, mechanical dance, performed by three creepy Munchkins in one case and by creepy Liza Minelli and Joel Grey in the other.

Surely the writers of Cabaret didn't do this on purpose? Did they? While it seems plausible that they might have forgotten the “Lollipop Guild” bit, I think it's impossible that they could both have missed it completely; they would have been 11 and 12 years old when The Wizard of Oz was first released.

(Now I want to recast The Wizard of Oz with Minelli as Dorothy and Grey as the Wizard. Bonus trivia, Liza Minelli is Judy Garland's daughter. Bonus bonus trivia, Joel Grey originated the role of the Wizard in the stage production of Wicked).

[Other articles in category /music] permanent link

Yet another software archaeology failure

I have this nice little utility program called menupick. It's a filter that reads a list of items on standard input, prompts the user to select one or more of them, then prints the selected items on standard output. So for example:

    emacs $(ls *.blog | menupick)

displays a list of those files and a prompt:

      0.   Rocketeer.blog
      1.   Watchmen.blog
      2.   death-of-stalin.blog
      3.   old-ladies.blog
      4.   self-esteem.blog
      >

Then I can type 1 2 4 to select items 1, 2, and 4, or 1-4 !3 (“1 through 4, but not 3”) similarly. It has some other features I use less commonly. It's a useful component in other commands, such as this oneliner git-addq that I use every day:

    git add $(git dirtyfiles "$@" | menupick -1)

(The -1 means that if the standard input contains only a single item, just select it without issuing a prompt.)

The interactive prompting runs in a loop, so that if the menu is long I can browse it a page at a time, adding items, or maybe removing items that I have added before, adjusting the selection until I have what I want. Then entering a blank line terminates the interaction. This is useful when I want to ponder the choices, but for some of the most common use cases I wanted a way to tell menupick “I am only going to select a single item, so don't loop the interaction”. I have wanted that for a long time but never got around to implementing it until this week. I added a -s flag which tells it to terminate the interaction instantly, once a single item has been selected.

I modified the copy in $HOME/bin/menupick, got it working the way I wanted, then copied the modified code to my utils git repository to commit and push the changes. And I got a very sad diff, shown here only in part:

diff --git a/bin/menupick b/bin/menupick
index bc3967b..b894652 100755
--- a/bin/menupick
+++ b/bin/menupick
@@ -129,7 +129,7 @@ sub usage {
     -1: if there is only one item, select it without prompting
     -n pagesize: maximum number of items on each page of the menu
          (default 30)
-    -q: quick mode: exit as soon as at least one item has been selected
+    -s: exit immediately once a single item has been selected

 Commands:
     Each line of input is a series of words of the form

I had already implemented almost the exact same feature, called it -q, and completely forgotten to use it, completely failed to install it, and then added the new -s feature to the old version of the program 18 months later.

(Now I'm asking myself: how could I avoid this in the future? And the clear answer is: many people have a program that downloads and installs their utiities and configuration from a central repository, and why don't I have one of those myself? Double oops.)

[ Previously; previouslier ]

[Other articles in category /oops] permanent link

Excessive precision in crib slat spacing?

A couple of years back I wrote:

You sometimes read news articles that say that some object is 98.42 feet tall, and it is clear what happened was that the object was originally reported to be 30 meters tall …

As an expectant parent, I was warned that if crib slats are too far apart, the baby can get its head wedged in between them and die. How far is too far apart? According to everyone, 2⅜ inches is the maximum safe distance. Having been told this repeatedly, I asked in one training class if 2⅜ inches was really the maximum safe distance; had 2½ inches been determined to be unsafe? I was assured that 2⅜ inches was the maximum. And there's the opposite question: why not just say 2¼ inches, which is presumably safe and easier to measure accurately?

But sometime later I guessed what had happened: someone had determined that 6 cm was a safe separation, and 6cm is 2.362 inches. 2⅜ inches exceeds this by only !!\frac1{80}!! inch, about half a percent. 7cm would have been 2¾ in, and that probably is too big or they would have said so.

The 2⅜, I have learned, is actually codified in U.S. consumer product safety law. (Formerly it was at 16 CFR 1508; it has since moved and I don't know where it is now.) And looking at that document I see that it actually says:

The distance between components (such as slats, spindles, crib rods, and corner posts) shall not be greater than 6 centimeters (2⅜ inches) at any point.

Uh huh. Nailed it.

I still don't know where they got the 6cm from. I guess there is someone at the Commerce Department whose job is jamming babies’ heads between crib bars.

[Other articles in category /tech] permanent link

Annoying mathematical notation

Recently I've been thinking that maybe the thing I really dislike about set theory might the power set axiom. I need to do a lot more research about this, so any blog articles about it will be in the distant future. But while looking into it I ran across an example of a mathematical notation that annoyed me.

This paper of Gitman, Hamkins, and Johnstone considers a subtheory of ZFC, which they call “!!ZFC-!!”, obtained by omitting the power set axiom. Fine so far. But the main point of the paper:

Nevertheless, these deficits of !!ZFC-!! are completely repaired by strengthening it to the theory !!ZFC^−!!, obtained by using collection rather than replacement in the axiomatization above.

Got that? They are comparing two theories that they call “!!ZFC-!!” and “!!ZFC^-!!”.

(Blog post by Gitman)

[ Previously ]

[Other articles in category /math] permanent link

Bad writing

A couple of weeks ago I had this dumb game on my phone, there are these characters fighting monsters. Each character has a special power that charges up over time, and then when you push a button the character announces their catch phrase and the special power activates.

This one character with the biggest hat had the catch phrase

I follow my own destiny!

and I began to dread activating this character's power. Every time, I wanted to grab them by the shoulders and yell “That's what destiny is, you don't get a choice!” But they kept on saying it.

So I had to delete the whole thing.

[Other articles in category /misc] permanent link

A proposal for improved language around divisibility

Divisibility and modular residues are among the most important concepts in elementary number theory, but the terminology for them is clumsy and hard to pronounce.

• !!n!! is divisible by !!5!!
• !!n!! is a multiple of !!5!!
• !!5!! divides !!n!!

The first two are 8 syllables long. The last one is tolerably short but is backwards. Similarly:

• The mod-!!5!! residue of !!n!! is !!3!!

is awful. It can be abbreviated to

• !!n!! has the form !!5k+3!!

but that is also long, and introduces a dummy !!k!! that may be completely superfluous. You can say “!!n!! is !!3!! mod !!5!!” or “!!n!! mod !!5!! is !!3!!” but people find that confusing if there is a lot of it piled up.

Common terms should be short and clean. I wish there were a mathematical jargon term for “has the form !!5k+3!!” that was not so cumbersome. And I would like a term for “mod-5 residue” that is comparable in length and simplicity to “fifth root”.

For mod-!!2!! residues we have the special term “parity”. I wonder if something like “!!5!!-ity” could catch on? This doesn't seem too barbaric to me. It's quite similar to the terminology we already use for !!n!!-gons. What is the name for a polygon with !!33!! sides? Is it a triskadekawhatever? No, it's just a !!33!!-gon, simple.

Then one might say things like:

• “Primes larger than !!3!! have !!6!!-ity of !!±1!!”

• “The !!4!!-ity of a square is !!0!! or !!1!!” or “a perfect square always has !!4!!-ity of !!0!! or !!1!!”

• “A number is a sum of two squares if and only its prime factorization includes every prime with !!4!!-ity !!3!! an even number of times.”

• “For each !!n!!, the set of numbers of !!n!!-ity !!1!! is closed under multiplication”

For “multiple of !!n!!” I suggest that “even” and “odd” be extended so that "!!5!!-even" means a multiple of !!5!!, and "!!5!!-odd" means a nonmultiple of !!5!!. I think “!!n!! is 5-odd” is a clear improvement on “!!n!! is a nonmultiple of 5”:

• “The sum or product of two !!n!!-even numbers is !!n!!-even; the product of two !!n!!-odd numbers is !!n!!-odd, if !!n!! is prime, but the sum may not be. (!!n=2!! is a special case)”

• “If the sum of three squares is !!5!!-even, then at least one of the squares is !!5!!-even, because !!5!!-odd squares have !!5!!-ity !!±1!!, and you cannot add three !!±1's!! to get zero”

• “A number is !!9!!-even if the sum of its digits is !!9!!-even”

It's conceivable that “5-ity” could be mistaken for “five-eighty” but I don't think it will be a big problem in practice. The stress is different, the vowel is different, and also, numbers like !!380!! and !!580!! just do not come up that often.

The next mouth-full-of-marbles term I'd want to take on would be “is relatively prime to”. I'd want it to be short, punchy, and symmetric-sounding. I wonder if it would be enough to abbreviate “least common multiple” and “greatest common divsor” to “join” and “meet” respectively? Then “!!m!! and !!n!! are relatively prime” becomes “!!m!! meet !!n!! is !!1!!” and we get short phrasings like “If !!m!! is !!n!!-even, then !!m!! join !!n!! is just !!m!!”. We might abbreviate a little further: “!!m!! meet !!n!! is 1” becomes just “!!m!! meets !!n!!”.

[ Addendum: Eirikr Åsheim reminds me that “!!m!! and !!n!! are coprime” is already standard and is shorter than “!!m!! is relatively prime to !!n!!”. True, I had forgotten. ]

[Other articles in category /math] permanent link

Testing for divisibility by 8

I recently wrote:

Instead of multiplying the total by 3 at each step, you can multiply it by 2, which gives you a (correct but useless) test for divisibility by 8.

But one reader was surprised that I called it “useless”, saying:

I only know of one test for divisibility by 8: if the last three digits of a number are divisible by 8, so is the original number. Fine … until the last three digits are something like 696.

Most of these divisibility tricks are of limited usefulness, because they are not less effort than short division, which takes care of the general problem. I discussed short division in the first article in this series with this example:

Suppose you want to see if 1234 is divisible by 7. It's 1200-something, so take away 700, which leaves 500-something. 500-what? 530-something. So take away 490, leaving 40-something. 40-what? 44. Now take away 42, leaving 2. That's not 0, so 1234 is not divisible by 7.

For a number like 696, take away 640, leaving 56. 56 is divisible by 8, so 696 is also. Suppose we were going 996 instead? From 996 take away 800 leaving 196, and then take away 160 leaving 36, which is not divisible by 8. For divisibility by 8 you can ignore all but the last 3 digits but it works quite well for other small divisors, even when the dividend is large.

This not not what I usually do myself, though. My own method is a bit hard to describe but I will try. The number has the form !!ABB!! where !!BB!! is a multiple of 4, or else we would not be checking it in the first place. The !!BB!! part has a ⸢parity⸣, it is either an even multiple of 4 (that is, a multiple of 8) or an odd multiple of 4 (otherwise). This ⸢parity⸣ must match the (ordinary) parity of !!A!!. !!ABB!! is divisible by 8 if and only if the parities match. For example, 104 is divisible by 8 because both parts are ⸢odd⸣. Similarly 696 where both parts are ⸢even⸣. But 852 is not divisible by 8, because the 8 is even but the 52 is ⸢odd⸣.

[Other articles in category /math] permanent link

Pranking the Italian Senate

The news today contains the story “Italian Senate Accidentally Plays 30 Seconds Of NSFW Tifa Lockhart Video” although I have not been able to find any source I would consider reliable. TheGamer reports:

The conference was hosted Monday by Nobel Prize winner Giorgio Parisi and featured several Italian senators. At some point during the Zoom call, a user … broke into the call and started broadcasting hentai videos.

Assuming this is accurate, it is disappointing on so many levels. Most obviously because if this was going to happen at all one would hope that it was an embarrassing mistake on the part of someone who was invited to the call, perhaps even the Nobel laureate, and not just some juvenile vandal who ran into the room with a sock on his dick.

If someone was going to go to the trouble of pulling this prank at all, why some run-of-the mill computer-generated video? Why not something really offensive? Or thematically appropriate, such as a scene from one of Cicciolina's films?

I think the guy who did this should feel ashamed of his squandered opportunity, and try a little harder next time. The world is watching!

[Other articles in category /misc] permanent link

The squares are kinda Fibonacci-like

I got a cute little surprise today. I was thinking: suppose someone gives you a large square integer and asks you to find the next larger square. You can't really do any better than to extract the square root, add 1, and square the result. But if someone gives you two consecutive square numbers, you can find the next one with much less work. Say the two squares are !!b = n^2!! and !!a = n^2+2n+1!!, where !!n!! is unknown. Then you want to find !!n^2+4n+4!!, which is simply !!2a-b+2!!. No square rooting is required.

So the squares can be defined by the recurrence $$\begin{align} s_0 & = 0 \\ s_1 & = 1 \\ s_{n+1} & = 2s_n - s_{n-1} + 2\tag{$\ast$} \end{align} $$

This looks a great deal like the Fibonacci recurrence:

$$\begin{align} f_0 & = 0 \\ f_1 & = 1 \\ f_{n+1} & = f_n + f_{n-1} \end{align} $$

and I was a bit surprised because I thought all those Fibonacci-ish recurrences turned out to be approximately exponential. For example, !!f_n = O(\phi^n)!! where !!\phi=\frac12(1 + \sqrt 5)!!. And actually the !!f_0!! and !!f_1!! values don't matter, whatever you start with you get !!f_n = O(\phi^n)!!; the differences are small and are hidden in the Landau sign.

Similarly, if the recurrence is !!g_{n+1} = 2g_n + g_{n-1}!! you get !!g_n = O((1+\sqrt2)^n)!!, exponential again. So I was surprised that !!(\ast)!! produced squares instead of something exponential.

But as it turns out, it is producing something exponential. Sort of. Kind of. Not really.

!!\def\sm#1,#2,#3,#4{\left[\begin{smallmatrix}{#1}&{#2}\\{#3}&{#4}\end{smallmatrix}\right]}!!

There are a number of ways to explain the appearance of the !!\phi!! constant in the Fibonacci sequence. Feel free to replace this one with whatever you prefer: The Fibonacci recurrence can be written as $$\left[\matrix{1&1\\1&0}\right] \left[\matrix{f_n\\f_{n-1}}\right] = \left[\matrix{f_{n+1}\\f_n}\right] $$ so that $$\left[\matrix{1&1\\1&0}\right]^n \left[\matrix{1\\0}\right] = \left[\matrix{f_{n+1}\\f_n}\right] $$

and !!\phi!! appears because it is the positive eigenvalue of the square matrix !!\sm1,1,1,0!!. Similarly, !!1+\sqrt2!! is the positive eigenvalue of the matrix !!\sm 2,1,1,0!! that arises in connection with the !!g_n!! sequences that obey !!g_{n+1} = 2g_n + g_{n-1}!!.

For !!s_n!! the recurrence !!(\ast)!! is !!s_{n+1} = 2s_n - s_{n-1} + 2!!, Briefly disregarding the 2, we get the matrix form

$$\left[\matrix{2&-1\\1&0}\right]^n \left[\matrix{s_1\\s_0}\right] = \left[\matrix{s_{n+1}\\s_n}\right] $$

and the eigenvalues of !!\sm2,-1,1,0!! are exactly !!1!!. Where the Fibonacci sequence had !!f_n \approx k\cdot\phi^n!! we get instead !!s_n \approx k\cdot1^n!!, and instead of exploding, the exponential part remains well-behaved and the lower-order contributions remain significant.

If the two initial terms are !!t_0!! and !!t_1!!, then !!n!!th term of the sequence is simply !!t_0 + n(t_1-t_0)!!. That extra !!+2!! I temporarily disregarded in the previous paragraph is making all the interesting contributions: $$0, 0, 2, 6, 12, 20, \ldots, n(n-1) \ldots$$ and when you add the !!t_0 + n(t_1-t_0)!! and put !!t_0=0, t_1=1!! you get the squares.

So the squares can be considered a sort of Fibonacci-ish approximately exponential sequence, except that the exponential part doesn't matter because the base of the exponent is !!1!!.

How about that.

[Other articles in category /math] permanent link

Life with Dominus

This morning Katara and I were taking our vitamins, and Katara asked why vitamin K was letter “K”.

I said "It stands for ‘koagulation’.”

“No,” replied Katara.

“Yes,” I said.

“No.”

“Yes.”

By this time she must have known something was up, because she knows that I will make up lots of silly nonsense, but if challenged I will always recant immediately.

“‘Coagulation’ doesn't start with a ‘K’.”

“It does in German.”

Lorrie says she discovered the secret to dealing with me, thirty years ago: always take everything I say at face value. The unlikely-seeming things are true more often than not, and the few that aren't I will quickly retract.

[Other articles in category /misc] permanent link

Mike Wazowski's prevenge

I started to write an addendum to last week's article about how Mike Wazowski is not scary:

I have to admit that if Mike Wazowski popped out of my closet one night, I would scream like a little boy.

And then I remembered something I haven't thought of for a long, long time.

My parents owned a copy of this poster, originally by an artist named Karl Smith:

When I was a small child, maybe three or four, I was terrified of the creature standing by the word “Night”:

One night after bedtime I was dangling my leg over the edge of the bed and something very much like this creature popped right up through the floor and growled at me to get back in bed. I didn't scream, but it scared the crap out of me.

I no longer remember why I was so frightened by this one creature in particular, rather than say the snail-bodied flamingo or the dimetrodon with the head of Shaggy Rogers. And while are obviously a lot of differences between this person and Mike Wazowski (most obviously, the wrong number of eyes) there are also some important similarities. If Mike himself had popped out of the floor I would probably have been similarly terrified.

So, Mike, if you're reading this, please know that I accept your non-scariness not as a truly held belief, but only as a conceit of the movie.

[ If any of my Gentle Readers knows anything more about Karl Smith or this poster in particular, I would be very interested to hear it. ]

[Other articles in category /brain] permanent link

Hoares

Yesterday I related Wikitionary's explanation of why Vladamir Putin's name is transliterated in French as Poutine:

in French, “Putin” would be pronounced /py.tɛ̃/, exactly like putain, which means “whore”.

In English we don't seem to be so quivery. Plenty of people are named “Hoare”. If someone makes a joke about the homophone, people will just conclude that they're a boor. “Hoare” or “hoar” is an old word for a gray-white color, one of a family of common hair-color names along with “Brown”, “White”, and “Grey”.

There is a legend at Harvard University that its twelve residential houses are named for the first twelve presidents of Harvard: Dunster House, Eliot House, Mather House, and so on. Except, says the legend, they were unwilling to name a house after the fourth president, Leonard Hoar, and called it North House instead. The only part of this that is true is that most of the houses were named for presidents of Harvard.

(The common name “Green” is not a hair-color name. It refers to someone who lives by the green.)

[Other articles in category /lang] permanent link

What the fuck, Firefox?

I don't even want to know what happened here.

All I can think of is this guy:

[ Addendum: Joe Ardent informs me that the suggestions are actually provided by Goofle. ]

[Other articles in category /misc] permanent link

Poutines

In French Canada, poutine is a dish of fried potatoes with cheese curds and brown gravy. But today I learned that in French, Vladimir Putin's name is Vladimir Poutine.

	=
Poutine		Putin

Wiktionary explains: in French, “Putin” would be pronounced /py.tɛ̃/, exactly like putain, which means “whore”. “Poutine” is silly, but at least comparatively inoffensive.

Mario Tremblay of Montréal gave in to temptation, and opened a poutine restaurant named “Vladimir Poutine". There was a poutine dish on the menu named “Vladimir Poutine”. In a sort of nod to borscht, it was topped with beet confit. The restaurant has since closed.

[ Other people who are accidentally foods ]

Left-hand poutine photograph by Joe Shlabotnik from Forest Hills, Queens, USA, CC BY 2.0 https://creativecommons.org/licenses/by/2.0, via Wikimedia Commons. Right-hand photograph also via Wikimedia Commons.

[ Addendum 20220116: Further musings on names with bad homophones ]

[Other articles in category /lang] permanent link

Monsters University was a refreshing departure from the moral inanity of the typical kids’ movie

Back when it was fresh, I read this 2013 article by Luke Epplin, You Can Do Anything: Must Every Kids' Movie Reinforce the Cult of Self-Esteem?, and I've wanted to blog about it ever since. I agree with the author's thesis, which is:

No genre in recent years has been more thematically rigid than the computer-animated children's movie. … These movies revolve around anthropomorphized outcasts who must overcome the restrictions of their societies or even species to realize their impossible dreams.

Having had two kids grow up during that decade, I sympathize and agree. I have one serious complaint with the article, though. Epplin gives a list of examples:

• Kung Fu Panda (fat panda becomes kung fu master)
• Ratatouille (rat becomes French chef)
• Wreck-It Ralph (“8-bit villain yearns to be a video-game hero”)
• Monsters University (“unscary monster pursues a career as a top-notch scarer”)
• Turbo (“common garden snail … dreams of racing glory”)
• Planes (“unsatisfied crop-duster yearns to … compete in the famed Wings Around the Globe race”)

Yes, okay, I agree. I have only one complaint. This is terribly unjust to Monsters University.

I am not a fan of Monsters University. I don't regret seeing it once, but I will not be disappointed if I never see it again. But it does not belong in that list. I came out of the theatre saying “wow, at least it wasn't that same old Disney bullshit”. Monsters University is very consciously a negative reaction to the cult-of-self-esteem movies, a repudiation of them.

Monsters University sets up the same situation as the other self-esteem movies: the protagonist, Mike Wazowski, wants desperately to be a “scarer”, one of the monsters who pops out of a closet to scare a child after bedtime. He wants it so much! He works so hard! He may be competing against scarier monsters, but none of them has Mike's drive, they're all coasting on their actual talent. None has Mike's dreams or his commitment. None has learned as much about the theory and technique of scaring.

There's a problem, though: Mike, voiced by Billy Crystal, isn't scary.

Epplin complains:

The restless protagonists of these films never have to wake up to the reality that crop-dusters simply can't fly faster than sleek racing aircraft. Instead, it's the naysaying authority figures who need to be enlightened about the importance of never giving up on your dreams, no matter how irrational, improbable, or disruptive to the larger community.

Monsters University has that naysaying authority figure, a college dean (Helen Mirren) who tells Mike in three words why he will never be a scarer: “You're not scary.” Mike is determined to prove her wrong!

Mike fails.

Catastrophically, humiliatingly, disgracefully. The movie is merciless.

Any success Mike appeared to have was illusory, procured by cheating. (Mike was unaware of the cheating, but in the depths of his self-deception he doesn't question his improbable success.) In fact the dean was exactly right: Mike isn't scary. As anyone can see by looking at him.

After being exposed as a cheat, Mike is expelled from Monsters University.

An epilogue shows that Mike and his friend Sully have gotten jobs working in the mail room of the power plant where the real scarers work. They work their way up to the cafeteria, and beyond. It's a long, hard slog, and takes years, but the road ends in success: Sully (who is scary) is a top scarer, and (as we know from Monsters, Inc.) Mike is his coach and support, accomplished, respected, and admired as an indispensable part of Sully's top-performing team.

The naysaying dean is never refuted. She's right. Mike isn't scary. And even if he had been, he's more valuable as Sully's pit crew. He's found his real calling.

As I said, I didn't think much of the movie. But it absolutely did not follow the formula. And its moral lessons are ones I can really get behind. Not “never give up on your dreams, no matter how irrational”, which is stupid advice. But instead “life has ups and downs but goes on” and “success, when it comes, takes a lot of toil and hard work”. And one of my favorites: “play the hand you're dealt”.

(For some other articles appreciating Monsters University's unusual willingness to engage with failure and subsequent course correction, see “‘Monsters University’, Failure, and ‘Rudy’” and “Monsters University and the importance of failure in pop culture”.)

[ Addendum 20220118: It must be admitted that Mike Wazowski would be damn scary if run into unexpectedly. But movies are movies. ]

[Other articles in category /movie] permanent link

Many presentations of axiomatic set theory contain an error

[ Content warning: highly technical mathematics ]

I realized recently that there's a small but significant error in many presentations of the Zermelo-Frankel set theory: Many authors omit the axiom of the empty set, claiming that it is omittable. But it is not.

The overarching issue is as follows. Most of the ZF axioms are of this type:

If !!\mathcal A!! is some family of sets, then [something derived from !!\mathcal A!!] is also a set.

The axiom of union is a typical example. It states that if !!\mathcal A!! is some family of sets, then there is also a set !!\bigcup \mathcal A!!, which is the union of the members of !!\mathcal A!!. The other axioms of this type are the axioms of pairing, specification, power set, replacement, and choice.

There is a minor technical problem with this approach: where do you get the elements of !!\mathcal A!! to begin with? If the axioms only tell you how to make new sets out of old ones, how do you get started? The theory is a potentially vacuous one in which there aren't any sets! You can prove that if there were any sets they would have certain properties, but not that there actually are any such things.

This isn't an entirely silly quibble. Prior to the development of axiomatic set theory, mathematicians had been using a model called naïve set theory, and after about thirty years it transpired that the theory was inconsistent. Thirty years of work about a theory of sets, and then it turned out that there was no possible universe of sets that satisfied the requirements of the theory! This precipitated an upheaval in mathematics a bit similar to the quantum revolution in physics: the top-down view is okay, but the most basic underlying theory is just wrong.

If we can't prove that our new theory is consistent, we would at least like to be sure it isn't trivial, so we would like to be sure there are actually some sets. To ensure this, the very least we can get away with is this axiom:

!!A_S!!: There exists a set !!S!!.

This is enough! From !!A_S!! and specification, we can prove that there is an empty subset of !!S!!. Then from extension, we can prove that this empty subset is the unique empty set. This justifies assigning a symbol to it, usually !!\varnothing!! or just !!0!!. Once we have the empty set, pairing gives us !!\{0,0\} = \{0\} = 1!!, then !!\{0, 1\} = 2!! , and so on. Once we have these, the axioms of union and infinity show that !!\omega!! is a set, then from that the axiom of power sets gets us uncountable sets, and the sky is the limit. But we need something like !!A_S!! to get started.

In place of !!A_S!! one can have:

!!A_\varnothing!!: There exists a set !!\varnothing!! with the property that for all !!x!!, !!x\notin\varnothing!!.

Presentations of ZF sometimes include this version of the axiom. It is easily seen to be equivalent to !!A_S!!, in the sense that from either one you can prove the other.

I wanted to see how this was handled in Thomas Jech's Set Theory, which is a standard reference text for axiomatic set theory. Jech includes a different version of !!A_S!!, initially given (page 3) as:

!!A_∞!!: There exists an infinite set.

This is also equivalent to !!A_S!! and !!A_\varnothing!!, if you are willing to tolerate the use of the undefined term “infinite”. Jech of course is perfectly aware that while this is an acceptable intuitive introduction to the axiom of infinity, it's not formally meaningful without a definition of “infinite”. When he's ready to give the formal version of the axiom, he states it like this:

$$\exists S (\varnothing \in S\land (\forall x\in S) x\cup\{x\}\in S).$$

(“There is a set !!S!! that includes !!\varnothing!! and, whenever it includes some !!x!!, also includes !!x\cup\{x\}!!.” (3rd edition, p. 12))

Except, oh no, “!!\varnothing!!” has not yet been defined, and it can't be, because the thing we want it to refer to cannot, at this point, be proved to actually exist.

Maybe you want to ask why we can't use it without proving that it exists. That is exactly what went wrong with naïve set theory, and we don't want to repeat that mistake.

I brought this up on math Stack Exchange and Asaf Karagila, the resident axiomatic set theory expert, seemed to wonder why I complained about !!\varnothing!! but not about !!\{x\}!! and !!\cup!!. But the issue doesn't come up with !!\{x\}!! and !!\cup!!, which can be independently defined using the axioms of pairing and union, and then used to state the axiom of infinity. In contrast, if we're depending on the axiom of infinity to prove the existence of !!\varnothing!!, it's circular for us to assume it exists while writing the statement of the axiom. We can't depend on !!A_∞!! to define !!\varnothing!! if the very meaning of !!A_∞!! depends on !!\varnothing!! itself.

That's the error: the axioms, as stated by Jech, are ill-founded. This is a little hard to see because of the way he prevaricates the actual statement of the axiom of infinity. On page 8 he states !!A_\varnothing!!, which would work if it were included, but he says “we have not included [!!A_\varnothing!!] among the axioms, because it follows from the axiom of infinity.”

But this is wrong. You really do need an explicit axiom like !!A_\varnothing!! or !!A_S!!. As far as I can tell, you cannot get away without it.

This isn't specifically a criticism of Jech or the book; a great many presentations of axiomatic set theory make the same mistake. I used Jech as an example because his book is a well-known authority. (Otherwise people will say “well perhaps, but a more careful writer would have…”. Jech is a careful writer.)

This is also not a criticism of axiomatic set theory, which does not collapse just because we forgot to include the axiom of the empty set.

[Other articles in category /math] permanent link

Another test for divisibility by 7

[ Previously ]

Recently I thought of another way to check for divisibility by !!7!!. Let's consider !!\color{darkblue}{3269}!!. The rule is: take the current total (initially 0), triple it, and add the next digit to the right. So here we do:

$$ \begin{align} \color{darkblue}{3}·3 & + \color{darkblue}{2} & = && \color{darkred}{11} \\ \color{darkred}{11}·3 & + \color{darkblue}{6} & = && \color{darkred}{39} \\ \color{darkred}{39}·3 & + \color{darkblue}{9} & = && \color{darkred}{126} \\ \end{align} $$

and the final number, !!\color{darkred}{126} !!, is a multiple of !!7!! if and only if the initial one was. If you're not sure about !!126!! you can check it the same way:

$$ \begin{align} \color{darkblue}{1} ·3 & + \color{darkblue}{2} & = && \color{darkred}{5} \\ \color{darkred}{5} ·3 & + \color{darkblue}{6} & = && \color{darkred}{21} \\ \end{align} $$

If you're not sure about !!\color{darkred}{21} !!, you calculate !!2·3+1=7!! and if you're not sure about !!7!!, I can't help.

You can simplify the arithmetic by reducing everything mod !!7!! whenever it gets inconvenient, so checking !!3269!! really looks like this:

$$ \begin{align} \color{darkblue}{3} ·3 & + \color{darkblue}{2} & = && 11 = \color{darkred}{4} \\ \color{darkred}{4} ·3 & + \color{darkblue}{6} & = && 18 = \color{darkred}{4} \\ \color{darkred}{4} ·3 & + \color{darkblue}{9} & = && 21 = \color{darkred}{0} \\ \end{align} $$

This is actually practical.

I'm so confident this is already in the Wikipedia article about divisibility testing that I didn't bother to actually check. But I did check the email that Eric Roode sent me in 2018 about divisibility testing, and confirmed that it was in there.

Instead of multiplying the total by 3 at each step, you can multiply it by 2, which gives you a (correct but useless) test for divisibility by 8. Or you can multiply it by 1, which gives you the usual (correct and useful) test for divisibility by 9. Or you can multiply it by 0, which gives you a slightly silly (but correct) version of the usual test for divisibility by 10. Or you can multiply it by -1, which which gives you exactly the usual test for divisibility by 11.

You can of course push it farther in either direction, but none of the results seems particularly interesting as a practical divisibility test.

I wish I had known about this as a kid, though, because I would probably have been interested to discover that the pattern continues to work: if at each step you multiply by !!k!!, you get a test for divisibility by !!10-k!!. Sure, you can take !!k=9!! or !!k=10!! if you like, go right ahead, it still works.

And if you do it for base-!!r!! numerals, you get a test for divisibility by !!r-k!!, so this is a sort of universal key to divisibility tests. In base 16, the triple-and-add method tests not for divisibility by 7 but for divisibilty by 13. If you want to test for divisibility by !!7!! you can use double-and-add instead, which is a nice wrinkle.

The tests you get aren't in general any easier than just doing short division, of course. At least they are easy to remember!

[Other articles in category /math] permanent link

All polynomials of degree 3 or greater factor over the reals

A couple of years ago I wrote:

One day when I was in high school, I bumped into the fact that !!\sqrt{7 + 4 \sqrt 3}!!, which looks just like a 4th-degree number, is actually a 2nd-degree number. It's numerically equal to !!2 + \sqrt 3!!. At the time, I was totally boggled.

I had a kind of similar surprise around the same time in connection with the polynomial !!x^4+1!!.

Everyone in high school algebra learns that !!x^2-1 = (x-1)(x+1)!! but that !!x^2+1!! does not similarly factor over the reals; in the jargon it is irreducible.

Every cubic polynomial does factor over the reals, though, because every cubic polynomial has a real root, and a polynomial with real root !!r!! has !!x-r!! as a factor; this is Descartes’ theorem. (It's easy to explain why all cubic polynomials have roots. Every cubic polynomial !!P(x)!! has the form !! ax^3!! plus some lower-order terms. As !!x!! goes to !!±∞!! the lower-order terms are insignificant and !!P(x)!! goes to !!a·±∞!!. Since the value of !!P(x)!! changes sign, !!P(x)!! must be zero at some point.)

For example, $$\begin{align} x^3+1 & = (x+1)(x^2- x+1) \\ x^3-1 & = (x-1)(x^2+ x+1) \\ \end{align}$$

So: polynomials with real roots always factor, cubics always have roots, so cubics factor. Also !!x^2+1!! has no real roots, and doesn't factor. And !!x^4+1!!, which looks pretty much the same as !!x^2+1!!, also has no real roots, and so behaves the same as !!x^2+1!! so doesn't factor…

Wrong! It has no real roots, true, but it still factors over the reals:

$$x^4+1 = (x^2 + \sqrt2· x + 1) (x^2 - \sqrt2· x + 1)$$

Neither of the two factors has a real root. I was kinda blown away by this, sometime back in the 1980s.

The fundamental theorem of algebra tells us that the only irreducible real polynomials have degree 1 or 2. Every polynomial of degree 3 or higher can be expressed as a product of polynomials of degrees 1 and 2. I knew this, but somehow didn't put the pieces together in my head.

Raymond Smullyan observes that almost everyone has logically inconsistent beliefs. His example is that while you individually believe a large number of separate claims, you probably also believe that at least one of those claims is false, so you don't believe their conjunction. This is an example of a completely different type: I simultaneously believed that every polynomial had roots over the complex numbers, and also that !!x^4+1!! was irreducible.

[Other articles in category /math] permanent link