# When $X \times Y \cong X \times Z$ implies $Y \cong Z$ (in the category of finite topological spaces)

The title has it all. I'm looking for a reference to the following:

Q. Let $X, Y, Z$ be finite, non-empty (topological) spaces. When does $X \times Y \cong X \times Z$ imply $Y \cong Z$ (in the category of topological spaces)?

This is, at the end of the day, a special instance of a famous problem (concerning the cancellativity, up to iso, of direct products or other "binary operations" in all sorts of categories), originated from a question of M.S. Ulam that first appeared as Problème 56 on p. 285 of Fund. Math 20 (1933), No. 1; see also footnote 2 in R.H. Fox, On a problem of S. Ulam concerning cartesian products, Fund. Math. 27 (1947), No. 1, 278-287. But the literature is vast (even sticking to topological spaces), and I couldn't find a reference to the case in which I'm presently interested.

Let me mention that I don't have an example showing that $X \times Y \cong X \times Z$ need not imply $Y \cong Z$ in my question (to be honest, I haven't even tried to find one), though I don't believe the contrary.

Background. The point of the question is simple, so let me make it a bit more complicate, but only in the hope of also making it a little more interesting (at least from certain points of view).

Fix a non-empty universe $\mathscr U$. Let $\mathscr T$ be the class of all $\mathscr U$-small, non-empty (topological) spaces, and $\sim$ the equivalence relation on $\mathscr T$ that identifies two spaces iff they are homeomorphic. Then the quotient of $\mathscr T$ by $\sim$ is naturally made into a commutative, reduced monoid, $\mathcal M$, by endowing it with the obvious binary operation induced by the direct product of spaces.

Let $\mathcal M_{\rm fin}$ be the submonoid of $\mathcal M$ consisting of all and only the equivalence classes containing finite spaces: This is a divisor-closed, unit-cancellative submonoid of $\mathcal M$ (for terminology, see the notes at the bottom of this post), and it is straigthfoward that there is a function $\lambda: \mathcal M_{\rm fin} \to \mathbf N$ such that $\lambda(\mathsf t_1) < \lambda(\mathsf t_2)$ for all distinct classes $\mathsf t_1, \mathsf t_2 \in \mathcal M_{\rm fin}$ with $\mathsf t_1 \mid \mathsf t_2$ in $\mathcal M_{\rm fin}$ (just map each isomorphism class $\mathsf t \in \mathcal M_{\rm fin}$ to the number of elements of any space $T \in \mathsf t$). So, it follows from elsewhere that $\mathcal M_{\rm fin}$ is a BF-monoid, i.e., (i) every class is a finite product of atoms of $\mathcal M_{\rm fin}$ and (ii) the factorizations (into atoms) of a fixed class cannot be arbitrarily large. Accordingly, it's natural to ask if $\mathcal M_{\rm fin}$ is cancellative, as this would make life much easier (at least from the perspective of factorization theory, which is the motivation behind my question).

Notes. Let $H$ be a multiplicatively written monoid $H$. We say that $H$ is unit-cancellative if $xy = x$ or $yx = x$, for some $x, y \in H$, implies $y \in H^\times$, where $H^\times$ is the group of units of $H$. An element $a \in H$ is referred to as an atom if (i') $a \notin H^\times$ and (ii') $a \ne xy$ for all $x, y \in H \setminus H^\times$. Finally, a submonoid $M$ of $H$ is called divisor-closed if $x \in M$ whenever $x \mid_H y$ and $y \in M$.

• Am I being stupid? Let $A$ be a minimal open set in $X$ and $U$ any subset of $Y$. Then it seems that $A\times U$ is open in $X$ iff $U$ is open in $Y$, which would mean that the topology on $Y$ is determined by the topology on $X\times Y$, and hence that $Z$ and $Y$ are homeomorphic. – Steven Landsburg May 11 '17 at 19:50
• My intuition is that $\mathcal M_{\rm fin}$ ought to be cancellative. You can recover quite a lot of information about $Y$ from $X\times Y$ by doing things like counting how many maps there are from arbitrary finite spaces into it. – Eric Wofsey May 11 '17 at 19:57
• In particular, it seems plausible to me that a finite preorder $Y$ is determined up to isomorphism by the function $T\mapsto |\operatorname{Hom}(T,Y)|$ where $T$ can be any finite preorder. That function is determined by the space $X\times Y$ (together with knowing what $X$ is), so that would imply $\mathcal M_{\rm fin}$ is cancellative. – Eric Wofsey May 11 '17 at 20:03
• @SalvoTringali: I thought I had (implicitly) used the finiteness of $Y$ and $Z$ as follows: Just by cardinalities, $Y$ and $Z$ must be isomorphic as sets (this would be false if $Y$ and $Z$ were infinite). Therefore we can assume $Z=Y$ as a set and ask whether two different topologies on this set can, when crossed with a given topological space $X$, produce different topologies on $X\times Y$. Answer: No, because the topology on $X\times Y$ determines the topology on $Y$. – Steven Landsburg May 11 '17 at 22:41
• You might like Chapter 5 of Algebras, Lattices, Varieties by McKenzie, McNulty, and Taylor. Their objects are algebras, but they include Lovasz's theorem for finite relational structures, which bears a strong resemblance to Eric Wofsey's answer. I imagine a categorical version exists and is or refers to the Lovasz 1967 paper. Gerhard "I Can Divide By One" Paseman, 2017.05.11. – Gerhard Paseman May 11 '17 at 22:44

For simplicity of presentation, I follow Lovasz in his paper Operations with Structures and work with structures with one finitary relation which I will choose to be binary. The extension to multiple finitary relations and algebraic structures is straightforward, and the paper of Lovasz and the book Algebras, Lattices, Varieties both give hints on the extension.

First, let us note a case where a relational structure $A$ is not isomorphic to $C$, yet $A\times C \simeq C \times C$. Indeed, let both structures have as universe the two element set with elements $a$ and $b$, and for $A$ the binary relation is identity, while for $C$ the binary relation is the complement, or non identity. The Cartesian product of the structure $C$ with itself has the ordered pair $(a,a)$ related to $(b,b)$ , $(a,b)$ related to $(b,a)$, and vice versa being a symmetric relation. For $A \times C$ we have $(a,a)$ related to $(a,b)$ , $(b,b)$ related to $(b,a)$, and again vice versa. The map that swaps the elements $(b,b)$ and $(a,b)$ gives the desired isomorphism between the two products. This example is noted in both the book and the paper. Thus, any class which contains $A, C$, and the two products fails to have cancellation as well as unique factorization. Fortunately, Salvo Tringali is not asking about such classes yet.

If we take Eric Wofsey's map $h$, we have a map from isomorphism types of finite structures (of the same finite type) into the monoid of a countable power of the nonnegative integers with multiplication. Because of this, we get uniqueness of kth roots in the monoid of interest. In order to get cancellation, we need a little more, namely that the cancelled algebra has a one element subuniverse, or in relational terms that the cancelled structure has an $x$ with $R(x,x,...,x)$ .

For the class of finite topological spaces, we need a way to produce a finitary relation or operation so that we can apply either Lovasz's theorem 4.1 or the book's theorem 5.23. Given a space $X$, and a point $x$, let $O(x)$ be the intersection of all open sets containing $x$, and let $R(x,y)$ be the relation that $O(x) \subseteq O(y)$. When $X$ is finite, this is saying that $x$ is in every open set containing $y$. I leave as an exercise that finite topological spaces $X$ and $Y$ are isomorphic if and only if the associated relational structures are isomorphic. It might help to observe that $R$ is a pre-order on $X$.

Now all these relational structures satisfy $R(x,x)$, not just for one $x$, but for every $x \in X$. Thus we can use Lovasz's Theorem 4.1 on the finite relational structures to get the result for the topologies.

I am still looking for a clean way to transform a topology into an algebra with at least one one element subuniverse, so that I can recover the topology from the algebra. I may need to use a pointed set to accomplish this. Until then, we have to wait before using Theorem 5.23.

I am not well acquainted with category theory to generalize or reframe this result in those terms. It is important for cancellation to have "enough maps", as Eric has noted. I still believe a category-theoretic version exists. I had not read Lovasz's paper before this question appeared and initially thought it might be category-theoretic in nature. It isn't.

Lovasz's paper has not only Cartesian product and disjoint union of relational structures, but also a form of exponentiation of one structure by another. He then expresses polynomials by replacing an integer exponent n by the n element structure with diagonal relation, and otherwise using arbitrary structures as coefficients, and then noting that if "the sum of the coefficients" has at least one diagonal element, then the polynomial as a function of the structure X is injective. He notes with the example above that exponentiation using arbitrary structures as exponents is not injective.

Gerhard "Demurs Upon Considering Structural Tetration" Paseman, 2017.05.15.

• A brief internet perusal suggests the paper of Lovasz and Schrijver, Semidefinite functions on categories, as a possible extension. Gerhard "Making A Half Educated Guess" Paseman, 2017.05.16. – Gerhard Paseman May 16 '17 at 7:24

The monoid $\mathcal M_{\rm fin}$ is in fact cancellative.

To prove this, we start with a Lemma. Let us write $h(T,Y)$ for the cardinality of the set of continuous maps $T\to Y$ and $i(T,Y)$ for the cardinality of the set of injective continuous maps $T\to Y$.

Lemma: Let $Y$ and $Z$ be finite spaces such that $h(T,Y)=h(T,Z)$ for all finite spaces $T$. Then $i(T,Y)=i(Y,Z)$ for all finite spaces $T$.

Proof of Lemma: We use induction on $|T|$. Note that $$h(T,Y)=\sum_{\sim}i(T/{\sim},Y)$$ (and similarly for $Z$), where $\sim$ ranges over all equivalence relations on the set $T$, since a map $f:T\to Y$ factors uniquely to give an injection from the quotient of $T$ by the equivalence relation $a\sim b\iff f(a)=f(b)$. By induction on $|T|$, we know $i(T/{\sim},Y)=i(T/{\sim},Z)$ whenever $\sim$ is nontrivial, and we also know $h(T,Y)=h(T,Z)$. It follows that $i(T,Y)=i(T,Z)$.

Now suppose $X$ is a nonempty finite space and $Y$ and $Z$ are finite spaces such that $X\times Y\cong X\times Z$. For any finite space $T$, we have $h(T,X\times Y)=h(T,X)h(T,Y)$ and similarly for $Z$. Since $X$ is nonempty, $h(T,X)\neq 0$ for all $T$. It follows that $h(T,Y)=h(T,Z)$ for all $T$, and hence $i(T,Y)=i(T,Z)$ for all $T$ by the Lemma.

Since $i(Y,Y)>0$ (the identity map exists), we have $i(Y,Z)>0$: there exists a continuous injection $f:Y\to Z$. Similarly, there exists a continuous injection $g:Z\to Y$. The composition $gf:Y\to Y$ is a continuous injection, and hence a bijection since $Y$ is finite. Moreover, $(gf)^n=1_Y$ for some positive integer $n$, and it follows that $gf$ is actually a homeomorphism. Similarly, $fg$ is a homeomorphism. This implies that $f$ and $g$ are homeomorphisms, so $Y\cong Z$.

[If I'm not mistaken, this argument in fact works with topological spaces replaced by any category with a faithful "underlying set" functor to Sets which preserves products and such that any object has a quotient by any equivalence relation on its underlying set, as long as you require $X$ to be such that there exists a map from any object to $X$.]

• Nice! I'm afraid the bijections between $h(T, Y)$ and $h(T, Z)$ cannot be made natural in $T$, right? Otherwise, using Yoneda, we'd have another elegant proof. – Andrea Gagna May 11 '17 at 23:05
• Is this proof related to the results or methods of Lovász cited in answer to this question about finite groups? – bof May 12 '17 at 0:10
• @bof Have you already noted Gerhard Paseman's comment to the OP? – Salvo Tringali May 12 '17 at 8:11
• @SalvoTringali No, I missed that, thanks for pointing it out. – bof May 12 '17 at 8:35
• For the record, I upvoted this nice answer, but accepted the one by Gerhard Paseman, since it provides a reference --- which, at the end of the day, is what I was looking for. It's perhaps worth noting that the proof provided by McKenzie, McNulty, and Taylor in their book is essentially the same. – Salvo Tringali May 12 '17 at 18:49

I submitted a paper, Finitary Categories and Isomorphism Theorems, in 1997 to JPAA, but I don't think it ever got published. A category with finite Hom-sets and quite mild factorization properties has the property that if $X$ and $Y$ are objects such that, for any object $Z$, $\hom(Z,X)$ has as many elements as $\hom(Z,Y)$ then $X$ and $Y$ are isomorphic. If in such a category there is at least one map to an object $A$ from any other object, then $A$ is cancellable for products; i.e. $A \times X$ isomorphic to $A \times Y$ implies $X$ isomorphic to $Y$. I used L. Lovasz (1967) Operations with Structures. Acta Mathematica Academiae Scientiarum Hungaricae Tomus 18 (3-4) pp 321-328, and (1971) On the Cancellation Law among Finite Relational Structures. Periodica Mathematica Hungarica Vol 1 (2), pp 145-156.

• I took the freedom to TeX the mathematics in your post, hope this is fine for you. And I find it pitiful that the manuscript you mention hasn't (yet?) been published anywhere: It would be useful to have a reference like that. – Salvo Tringali May 14 '17 at 11:48
• Thanks Todd, Salvo. Maybe it was published in JPAA - I am ashamed to say I have forgotten and since 1999, when I retired, I have not had the means of checking up. Mike Barr made some useful comments and emendations to my original submission. I still have the correspondence (on a memory stick), and in the fourth letter he says I am ready to send it off, but I still had to make two changes. .. . Apologies to JPAA if it did get published. I was in the throes of being secretary of the maths examinations sub-board at the time, a job I heartily disliked, and so possibly not entirely on the ball. – Gavin Wraith May 14 '17 at 20:13
• Glad to see you here on MO! JPAA has a searchable open archive and it is certainly not there. Is there a chance that some manuscript of it still exists? – მამუკა ჯიბლაძე May 14 '17 at 23:15

Edit 2017.05.14 GRP : I have reviewed Lovasz's paper. While the comments below are generally correct, there are some specific details to be addressed, some of which is done in the paper. I am preparing another answer to highlight some of these details from the paper. An amended form of one of the comments is warranted: I believe a categorical version of the argument has been published, and refers to and is not in Lovasz's paper. End Edit 2017.05.14.

Per request, I am bringing some commentary to this answer.

Prior to Eric Wofsey's nice solution, Laszlo Lovasz proved something similar in 1967 in his paper Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967), 321-328. (Thanks to Salvo Tringali for looking up the reference.) I first learned about it from my advisor's book Algebras , Lattices, Varieties by McKenzie, McNulty, and Taylor. Phrased in terms of isomorphism types of finite relational structures, one can cancel in that monoid and also kth roots are unique ($A^k$ isomorphic to $B^k$ means $A$ isomorphic to $B$ as finite powers of finite relational structures). For those referring to the textbook and the paper, Salvo mentions that what is used in the proof of the general statement, is Corollary 3 (p. 321) to Theorem 5.23 in that book, which is, in turn, a very special case of Theorem 4.1 in Lovász's paper.

Chapter 5 of that book also has more to say about when cancellation does not occur for other classes of structures. Being a textbook on Universal Algebra, it takes a view that largely is not category theoretic, which I found appealing as a student.

Gerhard "Much Prefers The Structuralist Approach" Paseman, 2017.05.12.

• I assume that "Salvo Tribalism" is a side effect of some self-correcting feature of your browser, though it's funny! :D – Salvo Tringali May 12 '17 at 14:08
• Darn, I thought I edited that quickly enough. Gerhard "Auto-correct Takes Over Our Being" On-demand, 2017.05.12. – Gerhard Paseman May 12 '17 at 14:10
• I'd just add that what is used in the proof that $\mathcal M_{\rm fin}$ is cancellative, is Corollary 3 (p. 321) to Theorem 5.23 in McKenzie, McNulty, and Taylor's book: This is, in turn, a very special case of Theorem 4.1 in Lovász's paper. The whole thing was already mentioned in the comments to the OP, but it's perhaps better to include it in your answer to make it more visible. – Salvo Tringali May 12 '17 at 14:28
• It's my training. I was raised to think of the result in the context of Chapter 5, and it relates to other problems in the monoid of isomorphism types. If you think mention of kth roots seriously detracts from the post, I can remove it. (Sorry that my cellphone auto-correct thinks monoid means nobody.) Gerhard "Edits Along To Get Along" Paseman, 2017.05.12. – Gerhard Paseman May 12 '17 at 14:29
• Actually, the original post and Eric's answer mention and frame things in terms of categories. While Chapter 5 also uses the word, my belief (my editorial if you prefer) is that people who read this post may be surprised at how little category theory is used in the chapter and may wonder how it relates at all to a category of finite topological spaces. I think mentioning this belief helps those who will approach the chapter. Gerhard "But I Could Be Wrong" Paseman, 2017.05.12. – Gerhard Paseman May 12 '17 at 19:19