9

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

Salvo Tringali
  • 9,617
  • 2
  • 25
  • 56
  • Do you know any nontrivial (i. e. $X\ne\emptyset$) instance of non-cancellability of finite spaces? – მამუკა ჯიბლაძე May 11 '17 at 19:42
  • @მამუკაჯიბლაძე The answer is already written at the bottom of the post. By the way, note that, by construction, $\mathcal M$ doesn't include the class of the empty space. – Salvo Tringali May 11 '17 at 19:43
  • Oops sorry did not notice that – მამუკა ჯიბლაძე May 11 '17 at 19:44
  • Just to check: "being associate" means $t_1 | t_2$ and $t_2 | t_1$? I guess you also know that the category of finite topological spaces is equivalent to the category of finite preorders; I don't know if this makes things easier to think about, but it might. – Todd Trimble May 11 '17 at 19:47
  • @ToddTrimble Yes to your 2nd question, no to the 1st: If $H$ is a monoid and $x, y \in H$, then $x$ is said to be associate to $y$ if $x = u yv$ for some units $u, v \in H$. – Salvo Tringali May 11 '17 at 19:50
  • 3
    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
  • How can there be any unit except the identity (the one-point space with its unique topology)? – Todd Trimble May 11 '17 at 19:57
  • 1
    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
  • @ToddTrimble Right, that's why I wrote that $\mathcal M$ is reduced (this means precisely that the only unit is the identity). But somehow I didn't take it into account when unwrapping the abstract definition of a length function. So probably I should be clearer on this point: In a reduced monoid, being associate is the same as being equal. Let me fix it. – Salvo Tringali May 11 '17 at 19:59
  • 1
    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
  • Might be related: https://math.stackexchange.com/questions/1052688/cancellation-of-direct-product-in-top – Ivan Di Liberti May 11 '17 at 20:09
  • @StevenLandsburg I agree with the 1st part of your reasoning ("$A \times U$ is open in $X\times Y$ iff $U$ is open in $Y$", and similarly with $Z$ in place of $Y$), but the 2nd part ("hence $Z$ and $Y$ are homeomorphic") sounds to me as a non sequitur. I can't say that you're wrong: If we trust Eric Wofsey's answer, then your conclusions are correct. However, I think that your argument is at least incomplete, and here's an indirect proof: If not, non-empty finite spaces would be cancellable from any product (as you're using nowhere that $Y$ and $Z$ are finite), and the same would (...) – Salvo Tringali May 11 '17 at 22:38
  • (...) be true, more in general, for any space $X$ whose poset of non-empty open sets, ordered by $\subseteq$, has a minimal element. Accordingly, B. Banaschewski and R. Lowen's A Cancellation Law for Partially Ordered Sets and $T_0$ Spaces [Proc. AMS 132 (Dec., 2004), No. 12, 3463-3466], would be seriously challenged, considering the effort put by the authors on showing that the Sierpiński (3-point) space is cancellable from any product (Corollary 2.7). – Salvo Tringali May 11 '17 at 22:38
  • 2
    @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
  • 2
    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
  • @StevenLandsburg I'm still not convinced about the soundness of your reasoning, as my indirect argument is still valid: In particular, if $X$ is a non-empty finite space, then $X \times Y$ and $X\times Z$ are homeomorphic only if $|Y|=|Z|$. So again, Corollary 2.7 in Banaschewski and Lowen's PAMS paper would be, in a way, trivial, and so would many more results from many more papers. – Salvo Tringali May 11 '17 at 22:50
  • @SalvoTringali : I agree that this seems too easy, but it still seems right to me. I've gone ahead and posted it as an answer. If you can point out the spot where it goes wrong, I'll be grateful for the correction. – Steven Landsburg May 11 '17 at 22:57
  • 1
    @GerhardPaseman I checked it. In Chapter 5 of McKenzie, McNulty, and Taylor's book, they're doing factorization theory on structures (which is precisely the motivation behind my question): I didn't know anything similar had already been done (not in such a general form!), and that's just beautiful! In particular, the answer to my question is that, to the contrary of what I believed, $\mathcal M_{\rm fin}$ is cancellative, as it follows from Corollary 3 (p. 321) to Theorem 5.23 in the book, which is, in turn, a very special case of Theorem 4.1 in (...) – Salvo Tringali May 12 '17 at 08:41
  • 1
    (...) L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967), 321-328. And yes, the proof is, in essence, the same as the one provided by Eric Wofsey (just more complicate, insofar as it deals with a more general situation). So to come to conclusion, why don't you post your comment as an answer? I was asking for a reference, and it turns out that you provided it. – Salvo Tringali May 12 '17 at 08:42
  • @StevenLandsburg As pointed out by Eric Wofsey in a comment to an answer you have now canceled (that's an unintentional pun!), the problem is that I don't see how you can jump directly from the 1st part of your reasoning to the conclusion that there exists a homeomorphism from $Y$ to $Z$. – Salvo Tringali May 12 '17 at 09:13
  • Update. I have to stand corrected: After a closer look, it seems we cannot use Theorem 5.23 in McKenzie, McNulty, and Taylor's book, since they deal uniquely with single-sorted algebraic structures, whereas the cat of $\mathscr U$-small finite topological spaces is isomorphic to the cat of $\mathscr U$-small finite preorders, which is a cat of single-sorted relational structures. However, we can still appeal to Theorem 4.1 in Lovász's paper, where the structures in play are general enough to cover preorders. – Salvo Tringali May 16 '17 at 08:10

4 Answers4

23

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

Eric Wofsey
  • 30,718
  • 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 00:10
  • @bof Have you already noted Gerhard Paseman's comment to the OP? – Salvo Tringali May 12 '17 at 08:11
  • 1
    @SalvoTringali No, I missed that, thanks for pointing it out. – bof May 12 '17 at 08:35
  • 1
    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
9

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.

Salvo Tringali
  • 9,617
  • 2
  • 25
  • 56
Gavin Wraith
  • 321
  • 1
    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
  • 2
    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
  • 2
    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
5

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.

Gerhard Paseman
  • 12,968
  • 1
    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
  • 1
    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
  • Never mind, I was just played another trick by the auto-correct of your cellphone. – Salvo Tringali May 12 '17 at 14:57
  • So you're saying category theory is in opposition to structuralism? What does "structuralism" mean in that case? – Todd Trimble May 12 '17 at 16:50
  • I was at an MSRI conference on Category Theory and Universal Algebra back in another millennium. No fighting broke out over whether the empty algebra (structure of a given type with underlying universe being an empty set) should belong to commonly treated classes, but there was noticeable tension in the air. I found thinking in terms of structures (specifically universal algebras with nonempty underlying universes) easier for me than thinking in terms of category theory. For me, the word abbreviates "Universal Algebraic". Gerhard "Maybe 'General Algebraic' Is Better" Paseman, 2017.05.12. – Gerhard Paseman May 12 '17 at 17:10
  • Well then, no opposition that I can detect from your response. Yes, for various reasons which will not be mentioned here, that MSRI conference will not be forgotten by category theorists who were there. (I wasn't among them.) – Todd Trimble May 12 '17 at 18:32
  • @Todd, If you read the chapter 5 (and also chapter 3 which does categories and perhaps chapter 4 on free algebras and HSP theorem), and you find it espouses a categorical viewpoint, I won't argue the point. Gerhard "Won't Agree With It Either" Paseman, 2017.05.12. – Gerhard Paseman May 12 '17 at 18:44
  • I don't know the book. But you're the one who brought up category theory, for some reason which escapes me. By introducing the negative "is not category-theoretic", it sounds in fact like you're editorializing a little. Not sure why. (As long as you are "editing along to get along", you might consider whether such editorializing is helpful.) – Todd Trimble May 12 '17 at 19:05
  • 1
    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
  • Gerhard, I accept the fact that category theory might not be really needed in a solution or in the problem formulation, so we agree there. And I don't think that should surprise anybody. But saying "it takes a view that largely is not category theoretic, which I found appealing as a student" may serve to confirm others in their anti-category-theory biases, which is not needed IMHO. (Incidentally, Eric's sole mention of category theory was not gratuitous and contains in fact a useful observation, I think.) – Todd Trimble May 12 '17 at 19:43
  • I agree on the usefulness of the observation Eric made, as well as the framework Salvo proposed. Let me suggest an alternate reading of the tail end of my post. I was not comfortable with category theory as a student, and that has not changed much since. Much as category theoretic formulation may be useful, I am more comfortable with the viewpoint of algebraic structures. That's about me (and Chapter 5). Gerhard "Likes The General Algebraic Perspective" Paseman, 2017.05.12. – Gerhard Paseman May 12 '17 at 20:11
  • Might I suggest in turn that you consider rewording the tail end of your post (including "the structuralist approach", which I found and still find rather confusing)? Anyway, thanks for explaining in more detail. – Todd Trimble May 12 '17 at 20:15
  • @Gerhard. I've just noted one of your comments above, where you write, "[...] 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." You have a point here: The cat of $\mathscr U$-small finite topological spaces is isomorphic to the cat of $\mathscr U$-small preorders, which is a cat of single-sorted (relational) structures in the sense of Lovász's paper. Yet, a more accurate reading to McKenzie, McNulty, and Taylor's book reveals that they deal uniquely with (...) – Salvo Tringali May 13 '17 at 18:50
  • (...) algebraic structures (unless I'm missing something else), so we cannot use Theorem 5.23 in that book to answer the present question: Instead, we have to refer directly to Theorem 4.1 in Lovász's paper! Sorry for the mistake: I think this should be definitely fixed/clarified in your answer. – Salvo Tringali May 13 '17 at 18:57
  • @Salvo, I will check up on Lovasz's paper if I can. I will post an edit in a few hours from now. Gerhard "Now Is A Relative Term" Paseman, 2017.05.13. – Gerhard Paseman May 13 '17 at 23:14
  • @Gerhard. Very good idea: This will reduce the risk that I may have missed something else. When I first skimmed through McKenzie, McNulty, and Taylor's book, I had convinced myself that their notion of structure was including preordered sets, or rather that the setup of Chapter 5 in the book was the same as in Lovász's paper. But your comment put me on the alert. – Salvo Tringali May 13 '17 at 23:28
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.

Gerhard Paseman
  • 12,968
  • 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 07:24