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

Question

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$.

Answer 1

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.

Answer 2

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$.]

Answer 3

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.

Answer 4

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.