The Universe of Discourse

Consecutive squareful numbers

On Saturday I was thinking about how each of !!48, 49, 50!! is a multiple of a square number, and similarly !!98, 99, 100!!. No such sequence of four numbers came immediately to mind. The smallest example turns out to be !!242, 243, 244, 245!!.

Let's say a number is “squareful” if it has the form $$a\cdot b^2$$ for !!b>1!!. The opposite, “squarefree”, is a standard term, but “non-squarefree” sounds even worse than “squareful”. Do ten consecutive squareful numbers exist, and if so, how can we find them?

I did a little algebraic tinkering but didn't come up with anything. If !!n,n+1, n+2!! are consecutive squareful numbers, then so are !!2n, 2n+2, 2n+4!!, except they aren't consecutive, but maybe we could find the right !!n!! so that !!2n+1!! and !!2n+3!! are also squareful. I couldn't make this work though, so I wrote some brute-force search programs to get the lay of the land.

The computer quickly produced sequences of length 7:

$$\begin{array}{rcrr} 217070 & = & 4430 \ · & 7^2 \\ 217071 & = & 24119 \ · & 3^2 \\ 217072 & = & 54268 \ · & 2^2 \\ 217073 & = & 17 \ · & 113^2 \\ 217074 & = & 1794 \ · & 11^2 \\ 217075 & = & 8683 \ · & 5^2 \\ 217076 & = & 54269 \ · & 2^2 \end{array} $$

and length 8:

$$\begin{array}{rcrr} 1092747 & = & 3027 \ · & 19^2 \\ 1092748 & = & 273187 \ · & 2^2 \\ 1092749 & = & 22301 \ · & 7^2 \\ 1092750 & = & 43710 \ · & 5^2 \\ 1092751 & = & 9031 \ · & 11^2 \\ 1092752 & = & 273188 \ · & 2^2 \\ 1092753 & = & 121417 \ · & 3^2 \\ 1092754 & = & 6466 \ · & 13^2 \\ \end{array} $$

Neither of these suggested anything to me, and nor did any of the other outputs, so I stuck !!1092747!! into OEIS. With numbers like that you don't even have to ask for the whole sequence, you only need to ask for the one number. Six sequences came up but the first five are all the same and were what I was looking for: A045882: Smallest term of first run of (at least) n consecutive integers which are not squarefree.

This led me to Louis Marmet's paper First occurrences of square-free gaps and an algorithm for their computation. The paper provides the earliest sequences of !!k!! consecutive squareful numbers, for !!k≤ 18!!, and bounds for how far out these sequences must be when !!k≤24!!. This is enough to answer the questions I originally asked:

• Are there ten consecutive squareful numbers? Yes, the smallest example starts at !!262\,315\,467!!, found in 1999 by D. Bernier.

• How can we find them? Marmet gives a sieve method that starts simple and becomes increasingly elaborate.

The paper is from 2007, so it seems plausible that the same algorithms on 2021 computers could produce some previously unknown results.

[ Addendum 20211124: The original version of this article ended “The general problem, of whether there are arbitrarily long sequences of squareful numbers, seems to be open.” This is completely wrong. Daniel Wagner and Shreevatsa R. pointed out that the existence of arbitrarily long sequences is quite elementary. Pick any squares you like that do not share a common factor, say for example !!49, 9, 4,!! and !!25!!. Now (because Chinese remainder theorem) you can find consecutive numbers that are multiples of those specific squares; in this case !!28322, 28323, 28324, 28325!!. ]

[ In only vaguely related news, I was driving Toph to school this morning, and a car in front of mine had license plate number !!5625 = 75^2!!. ]

[Other articles in category /math] permanent link

In simple English, what does it mean to be transcendental?

I've been meaning to write this up for a while, but somehow never got around to it. In my opinion, it's the best Math Stack Exchange post I've ever written. And also remarkable: its excellence was widely recognized. Often I work hard and write posts that I think are really good, and they get one or two upvotes; that's okay, because the work is its own reward. And sometimes I write posts that are nothing at all that get a lot of votes anyway, and that is okay because the Math.SE gods are fickle. But this one was great and it got what it deserved.

I am really proud of it, and in this post I am going to boast as shamelessly as I can.

The question was:

In simple English, what does it mean to be transcendental?

There were several answers posted immediately that essentially recited the definition, some better than others. At the time I arrived, the most successful of these was by Akiva Weinberger, which already had around fifty upvotes.

… Numbers like this, that satisfy polynomial equations, are called algebraic numbers. … A real (or complex) number that's not algebraic is called transcendental.

If you're going to essentially quote the definition, I don't think you can do better than to explain it the way Akiva Weinberger did. It was a good answer!

Once one answer gets several upvotes, it moves to the top of the list, right under the question itself. People see it first, and they give it more votes. A new answer has zero votes, and is near the bottom of the page, so people tend it ignore it. It's really hard for new answers to surpass a highly-upvoted previous answer. And while fifty upvotes on some stack exchanges is not a large number, on Math SE fifty is a lot; less than 0.2% of answers score so high.

I was unhappy with the several quoting-the-definition answers. Because honestly "numbers… that satisfy polynomial equations" is not “simple English” or “layman's terms” as the OP requested. Okay, transcendental numbers have something to do with polynomial equations, but why do we care about polynomial equations? It's just explaining one obscure mathematical abstraction in terms of second one.

I tried to think a little deeper. Why do we care about polynomials? And I decided: it's because the integer polynomials are the free ring over the integers. That's not simple English either, but the idea is simple and I thought I could explain it simply. Here's what I wrote:

We will play a game. Suppose you have some number !!x!!. You start with !!x!! and then you can add, subtract, multiply, or divide by any integer, except zero. You can also multiply by !!x!!. You can do these things as many times as you want. If the total becomes zero, you win.

For example, suppose !!x!! is !!\frac23!!. Multiply by !!3!!, then subtract !!2!!. The result is zero. You win!

Suppose !!x!! is !!\sqrt[3] 7!!. Multiply by !!x!!, then by !!x!! again, then subtract !!7!!. You win!

Suppose !!x!! is !!\sqrt2 +\sqrt3!!. Here it's not easy to see how to win. But it turns out that if you multiply by !!x!!, subtract 10, multiply by !!x!! twice, and add !!1!!, then you win. (This is not supposed to be obvious; you can try it with your calculator.)

But if you start with !!x=\pi!!, you cannot win. There is no way to get from !!\pi!! to !!0!! if you add, subtract, multiply, or divide by integers, or multiply by !!\pi!!, no matter how many steps you take. (This is also not supposed to be obvious. It is a very tricky thing!)

Numbers like !!\sqrt 2+ \sqrt 3!! from which you can win are called algebraic. Numbers like !!\pi!! with which you can't win are called transcendental.

Why is this interesting? Each algebraic number is related arithmetically to the integers, and the winning moves in the game show you how so. The path to zero might be long and complicated, but each step is simple and there is a path. But transcendental numbers are fundamentally different: they are not arithmetically related to the integers via simple steps.

This answer was an immediate hit. It rocketed past the previous top answer into the stratosphere. Of 190,000 Math SE, answers, there are twenty with scores over 500; mine is 13th.

The original version left off the final paragraph (“Why is this interesting?”). Fortunately, someone posted a comment pointing out the lack. They were absolutely right, and I hastened to fix it.

I love this answer for several reasons:

• It's not as short as possible, but it's short enough.

• It's almost completely jargonless. It doesn't use the word “coefficient”. You don't have to know what a polynomial is. You only have to understand grade-school arithmetic. You don't even need to know what a square root is; you can still try the example if you have a calculator with a square root button.

• Sometimes to translate a technical concept into plain language, one must sacrifice perfect accuracy, or omit important details. This explanation is technically flawless.

• One often sees explanations of “irrational number” that refer to the fact such a number has a nonrepeating decimal expansion. While this is true, it's a not what irrationality is really about, but a secondary property. The real root of the matter is that an irrational number is not the ratio of any two integers.

  My post didn't use the word “polynomial” and took a somewhat different path than the typical explanation, but it nevertheless hit directly at the root of the topic, not at a side issue.

• Also I had some unusually satisfying exchanges with critical commenters. There are a few I want to call out for triumphant mockery, but I have a policy of not mocking private persons on this blog, and this is just the kind of situation I intended to apply it to.

This is some good work. When I stand in judgement and God asks me if I did my work as well as I could, this is going to be one of the things I bring up.

[Other articles in category /math/se] permanent link

What is not portable

I had a small dispute this week about whether the Osborne 1 computer from 1981 could be considered a “laptop”. It certainly can't:

Bilby, CC BY 3.0 via Wikimedia Commons

The Osborne was advertised as a “portable” computer. Wikipedia describes it, more accurately, as “luggable”. I had a friend who owned one, and at the time I remarked “those people would call the Rock of Gibraltar ‘portable’, if it had a handle.”.

Looking into it a little more this week, I learned that the Osborne weighed 24½ pounds. Or, in British terms, 1¾ stone. If your computer has a weight measurable in “stone”, it ain't portable.

[Other articles in category /tech] permanent link

I said it was obvious but it was false

In a recent article about Norbert Wiener's construction of ordered pairs, I wrote:

The first thing I thought of was $$\pi_2(p) = \bigcup \{x\in p: |x| = 1\}$$ (“give me the contents of the singleton elements of !!p!!”) but one could also do $$\pi_2(p) = \{x: \{\{x\}\} \in p\},$$ and it's obvious that both of these are correct.

I said “it's obvious that both are correct”, but actually no! The first one certainly seems correct, but when I thought about it more carefully, I realized that the first formula is extremely complex, vastly moreso than the second. That !!|x|!! notation, so intuitive and simple-seeming, is hiding a huge amount of machinery. It denotes the cardinality of the set !!x!!, and cardinality is not part of the base language of set theory. Normally we don't worry about this much, but in this context, where we are trying to operate at the very bottom bare-metal level of set theory, it is important.

To define !!|x|!! requires a lot of theoretical apparatus. First we have to define the class of ordinals. Then we can show that every well-ordered set is order-isomorphic to some ordinal. Zermelo's theorem says that !!x!! has a well-ordering !!W!!, and then !!\langle x, W\rangle!! is order-isomorphic to some ordinal. There might be multiple such ordinals, but Zermelo's theorem guarantees there is at least one, and we can define !!|x|!! to be the smallest such ordinal. Whew! Are we done yet?

We are not. There is still more apparatus hiding in the phrases “well-ordering” and “order-isomorphic”: a well-ordering is certain kind of relation, and an order isomorphism is a certain kind of function. But we haven't defined relations and functions yet, and we can't, because we still don't have ordered pairs! And what is that !!\langle x, W\rangle!! notation supposed to mean anyway? Oh, it's just the… um… whoops.

So the !!|x|=1!! idea is not just inconveniently complex, but circular.

We can get rid of some of the complexity if we restrict the notion to finite sets (that eliminates the need for the full class of ordinals, for the axiom of choice and the full generality of Zermelo's theorem, and we can simplify it even more if we strip down our definition to the minimum requirements, which is that we only need to recognize cardinalities as large as 2.

But if we go that way we may as well dispense with a general notion of cardinality entirely, which is what the second definition does. Even without cardinality, we can still define a predicate which is true if and only if !!x!! is a singleton. That's simply: $$\operatorname{singleton}(x) \equiv_{def} \exists y. x = \{y\}.$$

One might want to restrict the domain of !!y!! here, depending on context.¹

To say that !!x!! has exactly two elements² we proceed analogously: $$\exists y. \exists z. z\ne y \land x = \{y, z\}.$$ And similarly we can define a predicate “has exactly !!n!! elements” for any fixed number !!n!!, even for infinite !!n!!. But a general definition of cardinality at this very early stage is far out of reach.

¹ This issue is not as complex as it might appear. Although it appears that !!y!! must range over all possible sets, we can sidestep this by restricting our investigation to some particular universe of discourse, which can be any set of sets that we like. The restricted version of !!x\mapsto |x|!! is a true function, an actual set in the universe, rather than a class function.

² There does not seem to be any standard jargon for a set with exactly two elements . As far as I can tell, “doubleton” is not used. “Unordered pair” is not quite right, because the unordered pair !!\{a, a\}!! has only one element, not two.

[Other articles in category /oops] permanent link

Stack Exchange is a good place to explain initial and terminal objects in the category of sets

The fact that singleton sets are terminal in the category of sets, and the empty set is initial, is completely elementary, so it's often passed over without discussion. But understanding it requires understanding the behavior of empty functions, and while there is nothing complex about that, novices often haven't thought it through, because empty functions are useless except for the important role they play in Set. So it's not unusual to see questions like this one:

I have trouble understanding the difference between initial and terminal objects in category theory. … Why there can be morphism from empty set to any other set? And why there is not morphism to empty set as well?

I'm happy with the following answer, which is of the “you already knew this, you only thought you didn't” type. It doesn't reveal any new information, it doesn't present any insights. All it does is connect together some things that the querent hasn't connected before.

This kind of connecting is an important part of pedagogy, one that Math Stack Exchange is uniquely well-suited to deal with. It is not well-handled by the textbook (which should not be spending time or space on such an elementary issue) or in lectures (likewise). In practice it's often handled by the TA (or the professor), during office hours, which isn't a good way to do it: the TA will get bored after the second time, and most students never show up to office hours anyway. It can be well-handled if the class has a recitation section where a subset of the students show up at a set time for a session with the TA, but upper-level classes like category theory don't usually have enough students to warrant this kind of organization. When I taught at math camp, we would recognize this kind of thing on the fly and convene a tiny recitation section just to deal with the one issue, but again, very few category theory classes take place at math camp.

Stack Exchange, on the other hand, is a great place to do this. There are no time or space limitations. One person can write up the answer, and then later querents can be redirected to the pre-written answer.

Your confusion seems to be not so much about initial and terminal objects, but about what those look like in the category of sets. Looking at the formal definition of “function” will help make clear some of the unusual cases such as functions with empty domains.

A function from !!A!! to !!B!! can be understood as a set of pairs $$\langle a,b\rangle$$ where !!a\in A!! and !!b\in B!!. And:

There must be exactly one pair !!\langle a,b\rangle!! for each element !!a!! of !!A!!.

Exactly one, no more and no less, or the set of pairs is not a function.

For example, the function that takes an integer !!n!! and yields its square !!n^2!! can be understood as the (infinite) set of ordered pairs:

$$\{ \ldots ,\langle -2, 4\rangle, \langle -1, 1\rangle, \langle 0, 0\rangle ,\langle 1, 1\rangle, \langle 2, 4\rangle\ldots\}$$

And for each integer !!n!! there is exactly one pair !!\langle n, n^2\rangle!!. Some numbers can be missing on the right side (for example, there is no pair !!\langle n, 3\rangle!!) and some numbers can be repeated on the right (for example the function contains both !!\langle -2, 4\rangle!! and !!\langle 2, 4\rangle!!) but on the left each number appears exactly once.

Now suppose !!A!! is some set !!\{a_1, a_2, \ldots\}!! and !!B!! is a set with only one element !!\{b\}!!. What does a function from !!A!! to !!B!! look like? There is only one possible function: it must be: $$\{ \langle a_1, b\rangle, \langle a_2, b\rangle, \ldots\}.$$ There is no choice about the left-side elements of the pairs, because there must be exactly one pair for each element of !!A!!. There is also no choice about the right-side element of each pair. !!B!! has only one element, !!b!!, so the right-side element of each pair must be !!b!!.

So, if !!B!! is a one-element set, there is exactly one function from !!A!! to !!B!!. This is the definition of “terminal”, and one-element sets are terminal.

Now what if it's !!A!! that has only one element? We have !!A=\{a\}!! and !!B=\{b_1, b_2, \ldots\}!!. How many functions are there now? Only one?

One function is $$\{\langle a, b_1\rangle\}$$ another is $$\{\langle a, b_2\rangle\}$$ and another is $$\{\langle a, b_3\rangle\}$$ and so on. Each function is a set of pairs where the left-side elements come from !!A!!, and each element of !!A!! is in exactly one pair. !!A!! has only one element, so there can only be one pair in each function. Still, the functions are all different.

You said:

I would find it more intuitive if one-element set would be initial object too.

But for a one-element set !!A!! to be initial, there must be exactly one function !!A\to B!! for each !!B!!. And we see above that usually there are many functions !!A\to B!!.

Now we do functions on the empty set. Suppose !!A!! is !!\{a_1, a_2, \ldots\}!! and !!B!! is empty. What does a function from !!A\to B!! look like? It must be a set of pairs, it must have exactly one pair for each element of !!a!!, and the right-side of each pair must be an element of !!B!!. But !!B!! has no elements, so this is impossible: $$\{\langle a_1, ?\rangle, \langle a_2, ?\rangle, \ldots\}.$$

There is nothing to put on the right side of the pairs. So there are no functions !!A\to\varnothing!!. (There is one exception to this claim, which we will see in a minute.)

What if !!A!! is empty and !!B!! is not, say !!\{b_1, b_2, \ldots\}!!? A function !!A\to B!! is a set of pairs that has exactly one pair for each element of !!A!!. But !!A!! has no elements. No problem, the function has no pairs! $$\{\}$$

A function is a set of pairs, and the set can be empty. This is called the “empty function”. When !!A!! is the empty set, there is exactly one function from !!A\to B!!, the empty function, no matter what !!B!! is. This is the definition of “initial”, so the empty set is initial.

Does the empty set have an identity morphism? It does; the empty function !!\{ \}!! is its identity morphism. This is the one exception to the claim that there are no functions from !!A\to\varnothing!!: if !!A!! is also empty, the empty function is such a function, the only one.

The issue for topological spaces is exactly the same:

• When !!B!! has only one element, there is exactly one continuous map !!A\to B!! for every !!A!!.
• When !!A!! is empty, there is exactly one continuous map !!A\to B!! for every !!B!!: the empty function is the homeomorphism.
• When !!A!! has only one element, there are usually many continuous maps !!A\to B!!, one different one for each element of !!B!!.

There are categories in which the initial and terminal objects are the same:

• In the category of groups, the trivial group (with one element) is both initial and terminal.

• A less important but simpler example is Set*, the category of pointed sets, whose objects are nonempty sets in which one element has been painted red. The morphisms of Set* are ordinary functions that map the red element in the domain to the red element of the codomain.

I hope this was some help.

[ Thanks to Rupert Swarbrick for pointing out that I wrote “homeomorphism” instead of “continuous map” ]

[Other articles in category /math/se] permanent link

Annoying Kuratowski pair projection formula

In a recent article I complained that it was too difficult to extract the second component from a Kuratowski pair. The formula given by Wikipedia is not simple:

$$\pi_2(p) = \bigcup\left\{\left. x \in \bigcup p\,\right|\,\bigcup p \neq \bigcap p \implies x \notin \bigcap p \right\}$$

I said “It's so non-obvious that I suspect that it's wrong”. Matthijs Blom then contacted me with this formal correctness proof using the Lean theorem prover. (Raw source code.)

I have also convinced myself that it is correct, using old-fashioned methods.

!!\def\pr#1#2{\langle{#1},{#2}\rangle}!! !!\def\kp#1#2{\{\{{#1}\}, \{{#1},{#2}\}\}}!!

Let's recall !!p = \pr ab = \kp ab!! and observe that then $$ \bigcup p = \{a, b\}\\ \bigcap p = \{a\} $$

where possibly !!a=b!!. Then the Wikipedia formula can be written as:

$$\pi_2(\pr ab) = \bigcup\left\{\left. x \in \{a, b\} \,\right| \,\{a, b\} \neq \{a\} \implies x \notin \{a\} \right\}.$$

!!\{a, b\} \ne \{a\}!! can be rewritten as !!b\ne a!!. The !!x\notin\{a\}!! can be rewritten as !!x\ne a!!. We can rewrite the whole !!S\implies T!! thing as !!\lnot S\lor T!!:

$$\pi_2(\pr ab) = \bigcup\left\{\left. x \in \{a, b\} \,\right| \,a = b \lor x \ne a \right\}.$$

When !!a≠b!! the !!a=b!! clause in the guard condition vanishes, leaving

$$\begin{align} \pi_2(\pr ab) & = \bigcup\left\{\left. x \in \{a, b\} \,\right| \,x \ne a \right\} \\ % & = \bigcup\{ x \in \{ b\} \} \\ & = \bigcup\{b\} \\ & = b. \end{align} $$

When !!a=b!!, the !!\{a,b\}!! expression reduces to !!\{b\}!! and the guard condition !!a = b \lor x \ne a!! is always true, so we get:

$$\begin{align} \pi_2(\pr ab) & = \bigcup\{ x \in \{b\}\} \\ & = \bigcup\{b\} \\ & = b. \end{align} $$

[Other articles in category /math] permanent link

Not the expected examples of nonbinary characters in fiction

A member of the Recurse Center community recently asked for recommendations of fiction that set in a place where gender is not generally undersood as binary. It's easy to come up with recent examples, especially in SF, but a surprising older example occurred to me. Isaac Asimov, not usually remembered for his nuanced treatment of gender, wrote a novel whose three-sexed alien society is not merely set dressing, but a major plot and character point.

The Gods Themselves is closely concerned with the three-sexed aliens in a parallel universe. Each of three sexes has a very strictly prescribed gender role. It's important to the outcome of the story that the three main characters each have difficulty conforming to their prescribed role, precisely because they're exceptionally gifted individuals. Their difficulty in performing the roles is presented as growing out of their extraordinary personalities and also as a source of those exceptional abilities.

I think there are parts of the book the deal with humans also, perhaps exclusively male humans. (I read it only once, decades ago.) I don't remember those parts as clearly.

Anyway, three-sexed gender-nonconformant aliens. By Isaac Asimov, of all people. 1972.

It won the Hugo, Locus, and Nebula awards. Check it out.

[ Addendum 20211110: A reader informs me that there is a significant female human character that I had forgotten. Sorry, Ike! ]

[Other articles in category /book] permanent link

History of Science Shitcommenting

A recent post on History of Science and Mathematics stack exchange asks:

What makes the right angle special enough to be distinguished in the French metric system?

…

Why was the right angle chosen? A somewhat equivalent question: Out of all possible angles, why is the right angle particularly special?

This kind of question astounds me. It reminds me of this episode from Understood Betsy:

She weighed out the salt needed on the scales, and was very much surprised to find that there really is such a thing as an ounce. She had never met it before outside the pages of her arithmetic book, and she didn't know it lived anywhere else.

Does this person seriously not know what a right angle is, apart from some formal definition involving ninety degrees or whatever? Do they know that a right angle lives outside the pages of a mathematics text? Maybe not!

Anyway, I was shocked, and left this comment:

RIGHT ANGLE SPECIAL. IF WALL NOT BUILT AT RIGHT ANGLE TO GROUND, FALL DOWN.

I expected this would be quickly deleted, and might even earn me a reprimand from the moderators. It didn't, and now has seven upvotes.

[Other articles in category /misc] permanent link

One way in which Wiener pairs are simpler than Kuratowski pairs

!!\def\kp#1#2{\{\{{#1}\}, \{{#1},{#2}\}\}}!!

!!\def\nwp#1#2{\{\{\{{#1}\}, \emptyset\}, \{\{{#2}\}\}\}}!!

In a recent article about Wiener's definition of ordered pairs, I said:

In any case the Kuratowski thing is still simpler. I wonder why Wiener didn't think of it first. … Perhaps he didn't consider the details important.

But today I thought of a specific technical advantage that Wiener's definition has over Kuratowski's. The Kuratowski definition is

$$\langle a, b\rangle = \kp ab$$

and in the special case where !!a=b!!, this reduces to:

$$\kp aa = \{\{a\}, \{a\}\} = \{\{a\}\}$$

This can complicate the proofs. For example suppose you want to prove that if !!\langle p,q\rangle = \langle r,s\rangle!! then !!p=r!! and !!q=s!!. You might like to start by saying that each side represents a set of two elements, and then compare the elements. But you can't, because either might be a set with one element, so there's a special case. Or maybe you have to worry about what happens if !!b=\{a\}!!, is it still all right?

With the Wiener pair, it easy to see that nothing like this can happen:

$$\langle a, b\rangle = \nwp ab$$

Here, no matter what !!a!! and !!b!! might be, !!\langle a, b\rangle!! is a set with two elements. The set !!\{\{a\}, \emptyset\}!! must have exactly two elements; it's impossible that !!\{a\} = \emptyset!!. And since !!\{\{a\}, \emptyset\}!! has two elements, it's impossible for it to equal !!\{\{b\}\}!!, which has one element. So !!\langle a, b\rangle!! is always a two-element set !!\{P_a, P_b\}!!. When !!a=b!! there's no special case. You just get $$\nwp aa$$ which doesn't look any different.

This analysis explains another possibly puzzling feature of Wiener's definition: Why !!\nwp ab!! and not the apparently simpler !!{\{\{a, \emptyset\}, \{b\}\}}!!? But that proposal, like Kuratowski's, has annoying special cases. For example, the proposal collases to !!\{\{\emptyset\}\}!! when !!a=b=\emptyset!!.

The components of a Wiener pair are easy to extract again: the !!P_b!! component is a singleton, satisfying !!\bigcup P_b = b!!, and the !!P_a!! component is a two-element set satisfying !!\bigcup P_a = a!!. This is all considerably simpler than with the Kuratowski pair, where you can't get !!b!! alone, you can only get !!\{a, b\}!! and then you have to take the !!a!! back out, except that if !!a=b!! you musn't. To extract the second component from a Wiener pair is easy. The first thing I thought of was $$\pi_2(p) = \bigcup \{x\in p: |x| = 1\}$$ (“give me the contents of the singleton elements of !!p!!”) but one could also do $$\pi_2(p) = \{x: \{\{x\}\} \in p\},$$ and it's obvious that both of these are correct. [ Addendum 20211112: Obvious perhaps, but wrong; the first one is not correct! ]

The analogous formula given by Wikipedia for the Kuratowski pair is not at all obvious:

$$\pi_2(p) = \bigcup\left\{\left. x \in \bigcup p\,\right|\,\bigcup p \neq \bigcap p \implies x \notin \bigcap p \right\}$$

It's so non-obvious that I suspect that it's wrong. (Wikipedia.) But I don't want to put in the effort it would take to check it.

[ Addendum 20211110: Matthijs Blom and I have confirmed that the formula is correct. ]

[ Addendum 20211112: my suggested definition of !!\pi_2(p) = \bigcup \{x\in p: |x| = 1\}!! does not work, because at this point we have not yet defined what !!|x|!! means. And we can't, because it requires functions and relations, which we can't define without an adequate model for orderded pairs. ]

[Other articles in category /math] permanent link

Let the computer do the work

!!\def\zpr#1#2{\langle{#1},{#2}\rangle}\def\zkp#1#2{\{\{{#1}\}, \{{#1},{#2}\}\}}!!In Friday's article about the cartesian product I needed to show what the Kuratowski ordered-pair construction looks like when you nest the pairs. I originally wrote out the TeX for these by hand, but later decided I ought to use TeX macros to generate the formulas. First I did

    \def\pr#1#2{\langle{#1},{#2}\rangle}

so that \pr ab would turn into !!\zpr ab!! and \pr a{\pr bc} would turn into !!\zpr a{\zpr bc}!!.

Then I defined a macro for Kuratowski pairs. The Kuratowski pair for !!\zpr ab!! is the set !!\zkp ab!!, which is kind of a mess:

    \def\kp#1#2{\{\{{#1}\}, \{{#1},{#2}\}\}}

Then the nested Kuratowski pairs turn into:

$$\begin{array}{cc} \verb+\kp a{\kp bc}+ & \zkp a{\zkp bc} \\ \verb+\kp{\kp ab}c+ & \zkp{\zkp ab}c \\ \end{array} $$

When I got this far I realized that my hand-expansion of \kp{\kp ab}c had actually been wrong! I had originally written: $$ \{\{\{a\}, \{a, b\}\}, \{\{\{a\}, \{a, b\}\}, c\}\}.\qquad\color{\maroon}{Wrong!}$$

(There's a pair of braces missing around the first of the two !!\zkp ab!!.)

I used to give classes on programming style and technique, and one of the maxims I taught was “let the computer do the work”: use the computer to automate repetitive or error-prone tasks.

I was going to say I wish I'd taken my own advice here but hey — I did take my own advice, and it worked!

[Other articles in category /prog] permanent link

The nonassociativity of the cartesian product

!!\def\pr#1#2{\langle{#1},{#2}\rangle}!!

Set theory doesn't include the ordered pair as a primitive type; ordered pairs have to be represented as sets somehow. This caused technical problems in Principia Mathematica, as I explained a couple of years ago:

In 1910 … a crucial piece of machinery was missing: the ordered pair.

This technical problem was solved the following year, by Norbert Wiener. We usually use the simpler definition invented later by Kazimierz Kuratowski:

!!\def\kp#1#2{\{\{{#1}\}, \{{#1},{#2}\}\}}!!

$$\pr ab = \kp ab$$

This works well enough (and it has worked well enough that we have used it for a hundred years) but it has some warts. We define the cartesian product of two sets like this: $$A\times B = \{\pr ab \mid a\in A\text{ and }b\in B\}$$

With Kuratwoski pairs, and this definition of product, it is not the case that $$A\times(B\times C) = (A\times B)\times C\qquad\color{darkred}{Not!}$$ because on the left side the elements look like $$\pr a{\pr bc} = \kp a{\kp bc}$$ and on the right side the corresponding element looks like $$\pr{\pr ab}c = \kp{\kp ab}c.$$

This doesn't present any serious technical problems; see Henning Makholm's discussion here. He says:

The nitty-gritty of getting such details to work completely formally is not generally worth the trouble.

Even with highly fussy technical details like this, you can almost always find some mathematician who said “Ah, but you have to be a little bit careful, because…”. As far as I know, this matter is an exception. If anyone thinks there is something interesting going on here that deserves further examination, I have not heard of it. Everyone ignores the matter.

Category theory takes the high road away from the issue, breezily dismissing it with a remark about how !!A\times(B\times C)!! and !!(A\times B)\times C!! are isomorphic, and equal up to unique isomorphism. This is the right answer, because as Wiener said in 1911, the structure of the pairs as actual sets is “largely a matter of choice”, and the whole point of category theory is to ignore this sort of irrelevant distraction, focusing on the API rather than on the internal implementation.

But last week I wondered: what if you do actually want !!A\times(B\times C)!! be the exact same set as !!(A\times B)\times C!!, and not just naturally isomorphic? Is there some clever way to define ordered pairs so that this happens?

I got the question all written up for Math Stack Exchange, when I realized the answer: No.

Consider the special case where !!A = \{a\}, B=\{b\},!! and !!C = \{c\}!!. Then !!A\times(B\times C) = (A\times B)\times C!! implies $$\pr a{\pr bc} = \pr{\pr ab}c.$$

But this violates the one property that we absolutely require of ordered pairs, which is that !!\pr pq = \pr rs!! if and only if !!p=r!! and !!q=s!!. To have !!\pr a{\pr bc} = \pr{\pr ab}c!! would imply !!a=\pr ab!!, which would imply !!\pr a{b'} = a = \pr ab!! even when !!b'\ne b!!.

Oh well, it would have been fun.

[Other articles in category /math] permanent link

Kuratowski pairs and Wiener pairs

I mentioned a couple of years back that Principia Mathematica was bloated with repetitive material because they hadn't been able to unify the idea of a relation and a set, because the ordered pair hadn't been invented yet. There's a section that defines set union, !!\cup!!, and then proves that it is commutative and associative and so on, and later there is a separate section that defines relation union, !!\dot\cup!!, and proves the exact same theorems in the same way. In 2021 (or even in 1921) we would say that a relation is a set of ordered pairs, and that relation union is just a special case of set union.

To do this we have to interpret ordered pairs set-theoretically. The method we usually use for this was invented by Kazimierz Kuratowski:

$$\langle a, b\rangle = \{\{a\}, \{a,b\}\}$$

But there were earlier developments that also sufficed. Hausdorff suggested the more intuitive, but technically more complex:

$$\langle a, b\rangle = \{\{a, 1\}, \{b, 2\}\}$$

where !!1!! and !!2!! are any two objects that are not among the things we want to include in our ordered pairs. And even earlier, the first interpretation of pairs as sets was in 1911 by Norbert Wiener. In modern notation, Wiener's definition is:

$$\langle a, b\rangle = \{\{\{a\}, \emptyset\}, \{\{b\}\}\}.$$

Wiener actually used the notation of Principia Mathematica, which I reproduce for your amusement:

$$\def\i{\iota`} \i(\i\i a\cup \i\Lambda)\cup\i\i\i b $$

The !!\i x!! notation means essentially the same as !!\{x\}!!. I thought Principia Mathematica had a better way to write !!\{x, y\}!! than as !!\i x\cup\i y!!, but if so I can't remember what it is.

Someone once told me that Wiener's definition is more complicated than Kuratowski's because it had to function in the context of Whitehead and Russell's type theory. Kuratowski was working later, in set theory, so could use a simpler definition that wouldn't function in type theory because the types didn't match up. I had never thought carefully about this until now but it seems to be wrong. The Kuratowski pair requires !!a!! and !!b!! to be the same type, or else you can't put them both into the class !!\{a, b\}!!. But the Wiener pair requires this also. Say !!a!! and !!b!! have type !!n!!. Then !!\{a\}!! and !!\{b\}!! have type !!n+1!!, and !!\{\{a\}, \emptyset\}!! and !!\{\{b\}\}!! have type !!n+2!!. And because they have the same type we can put them both into the class !!\{\{\{a\}, \emptyset\}, \{\{b\}\}\}!!. But for this to work, !!a!! and !!b!! have to have the same type to begin with.

I wanted to find out what Wiener said about this, and Wikipedia referred me to his paper A Simplification of the logic of relations, and helpfully pointed out that it was reprinted in van Heijenoort's Source Book in Mathematical Logic, which I have on the shelf. (I love when this happens. It makes me feel like a scholar.) Wiener agrees: !!a!! and !!b!! must have the same type. But, he points out, if !!a!! and !!b!! have different types you can still make it work by adjusting the nesting level of !!a!! or !!b!! accordingly. For example, if !!b!! had a type one higher than !!a!!, you could use !!\{\{\{a\}, \emptyset\}, \{b\}\}!! instead.

In any case the Kuratowski thing is still simpler. I wonder why Wiener didn't think of it first. But he does say “the particular method selected of doing this is largely a matter of choice”, so perhaps he didn't consider the details important. As in fact they aren't. The important point, and the real point of Wiener's paper, is that you can now construe a two-place relation as a class of ordered pairs.

The paper ends by observing that this fixes the !!\cup!!-versus-!!\dot\cup!! extravagance of Principia Mathematica, since now !!R\cup S = R\,\dot\cup\, S!!. Similarly the class of relations is now a subclass of the class of classes, and so forth.

[ Addendum 20211030: This construction makes the cartesian product nonassociative, but nobody cares. ]

[ Addendum 20211101: One way in which Wiener pairs are simpler than Kuratowski pairs. ]

[Other articles in category /math] permanent link