Archive:
Subtopics:
Comments disabled |
Mon, 22 Nov 2021 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:
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 Thu, 18 Nov 2021
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: 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.
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:
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:
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 Tue, 16 Nov 2021I had a small dispute this week about whether the Osborne 1 computer from 1981 could be considered a “laptop”. It certainly can't: 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 Sat, 13 Nov 2021
I said it was obvious but it was false
In a recent article about Norbert Wiener's construction of ordered pairs, I wrote:
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 Fri, 12 Nov 2021
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'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:
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:
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:
There are categories in which the initial and terminal objects are the same:
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 Wed, 10 Nov 2021
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 Tue, 09 Nov 2021
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 Sat, 06 Nov 2021
History of Science Shitcommenting
A recent post on History of Science and Mathematics stack exchange asks:
This kind of question astounds me. It reminds me of this episode from Understood Betsy:
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:
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 Tue, 02 Nov 2021
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:
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 Mon, 01 Nov 2021!!\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
so that 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:
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
(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 Fri, 29 Oct 2021
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:
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:
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 Thu, 28 Oct 2021
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 |