-1
$\begingroup$

Basic concepts question.

I am used to the Cartesian product of two sets: $A \times B = \{(a,b) \mid a \in A, b \in B\}$.

Is there an operator that produces sets instead of tuples? We might call it set-product and define $A \otimes B := \{a \cup b \mid a\in A, b\in B\}$.

What I am actually trying to do is "factorize" a given set-family $\mathcal M \subseteq 2^V$ where $V$ is the base set. That is, I would like to write $\mathcal M = M_1 \otimes M_2 \otimes M_3$ with $M_i \subseteq 2^V$.

example:

  • $\mathcal M = \{\{1,2\}, \{1,3\}, \{1,6\}\}$ can be factorized into $\{\{1\}\} \otimes \{\{2\},\{3\},\{6\}\}$

My questions are:

  • do people use this operator (if so, what is it called? I don't want to reinvent the wheel)?
  • do you know of results relating to the factorizability of sets in this way?

My goal is to connect what I am doing to existing work.

EDIT:

  • fixed errors in question and definition of $\otimes$
$\endgroup$
2
  • $\begingroup$ You ask whether there is such an operation. Yes, because you just defined it. Did you intend to ask a question about it? Obviously in the general case not every $\cal M$ will be factorizable in three factors. So what is the question you intend to ask, exactly? $\endgroup$ Commented Jun 16, 2021 at 12:59
  • $\begingroup$ Have you seen this operation before? Also, see update. $\endgroup$
    – Leevi L
    Commented Jun 16, 2021 at 13:14

1 Answer 1

4
$\begingroup$

As far as I understand, you start with a "base set" $V$ and consider the monoid obtained by endowing the power set of the power set of $V$ with the binary operation that sends a pair $(A, B)$ of families of subsets of $V$ to $\{X \cup Y \colon X \in A,\, Y \in B\}$, which is still a family of subsets of $V$. If my understanding is correct (is it?), then you may want to read about power monoids, especially if you are interested in questions relating to factorization (as it seems that you are).

Given a (multiplicatively written) monoid $H$, the full power monoid of $H$ is the monoid $\mathcal P(H)$ obtained by equipping the collection of all non-empty subsets of $H$ with the operation of setwise multiplication induced by $H$, so that $AB := \{ab: a \in A, \, b \in B\}$ for all $A, B \in \mathcal P(H)$. The OP is about the special case where $H$ is the monoid obtained by endowing the power set of a certain set $V$ with the binary operation $(X, Y) \mapsto X \cup Y$. So the answer to the question:

do you know of results relating to the factorizability of sets in this way?

is yes in the sense that this is a special case of a broader class of monoids where people (including myself) have studied, and are studying, various properties that can be labelled with the "Factorization" tag. However, you may want to consider that, before even starting to tackle the basic question of the existence of a factorization for certain elements of the monoid you're implicitly considering (and, more generally, of any monoid), you should somehow decide which "building blocks" are allowed in the factorization process, which is a (delicate) question of independent interest.

From the perspective of the classical theory (of factorization), the "canonical choice" would be to use as building blocks either the atoms or the irreducibles of the monoid $M$ under consideration, where an atom is a non-unit $a \in M$ such that $a \ne xy$ for all non-units $x, y \in M$ (this definition is commonly attributed to P.M. Cohn), and an irreducible is a non-unit $a \in M$ such that $a \ne xy$ for all $x, y \in M$ such that $MxM \ne MaM \ne MyM$ (in the commutative case, this definition is commonly attributed to D.D. Anderson & S. Valdes-Leon). However, none of these choices is fit for your case, unless $V$ is a finite set.

If, on the other hand, you're actually interested in the case where the elements of your monoid are non-empty, finite families of subsets of $V$ (are you?), then things are quite different and, with the same notation as above, you would better move from the full power monoid $\mathcal P(H)$ to the power monoid $\mathcal P_{\rm fin}(H)$ of $H$, that is, the submonoid of $\mathcal P(H)$ whose elements are the (non-empty) finite subsets of $H$: It is obvious that $\mathcal P_{\rm fin}(H)$ is strongly $\subseteq$-artinian, meaning that the $\subseteq$-height of every $X \in \mathcal P_{\rm fin}(H)$ is finite; as a result, every $X \in \mathcal P_{\rm fin}(H)$ factors into a (finite) product of $\subseteq$-irreducibles (see the notes below). Then, you are left with the problem of characterizing the $\subseteq$-irreducibles. (You could also use other preorders, but the inclusion order is a natural go-to here.)

By the way, product-sets in all sorts of monoids (and, in particular, sumsets in additively written groups) are one of the main objects of study in arithmetic combinatorics. So, stitching the pieces together, I would say that also the answer to the question:

do people use this operator (if so, what is it called? I don't want to reinvent the wheel)?

is yes (and you are reinventing the wheel).

Notes. Given a preorder $\preceq$ on a monoid $M$, a $\preceq$-non-unit of $M$ is an element $u \in M$ that is not $\preceq$-equivalent to the identity $1_M$ (two elements $x, y \in M$ are $\preceq$-equivalent if $x \preceq y \preceq x$). Then, the $\preceq$-height of an element $x \in M$ is the supremum of the set of all integers $n \ge 1$ for which there exist $\preceq$-non-units $x_1, \ldots, x_n \in M$ with $x_1 = x$ and $x_{i+1} \prec x_i$ for $1 \le i < n$, with the understanding that $\sup \emptyset := 0$; and a $\preceq$-irreducible of $M$ is a $\preceq$-non-unit $a \in M$ such that $a \ne xy$ for all $\preceq$-non-units $x, y \in M$ with $x \prec a$ and $y \prec a$.

$\endgroup$
5
  • $\begingroup$ Thanks for your response. I will see if I can read up on monoids and factorization. $\endgroup$
    – Leevi L
    Commented Jun 17, 2021 at 10:22
  • $\begingroup$ Yes, I am interested only in finite families of subsets and a finite $V$. $\endgroup$
    – Leevi L
    Commented Jun 17, 2021 at 10:30
  • $\begingroup$ I just discovered arxiv.org/abs/1701.09152 and thanks for pointing me to the terminology. Now I can ask more precise questions. $\endgroup$
    – Leevi L
    Commented Jun 17, 2021 at 14:18
  • 1
    $\begingroup$ I'm hesitant to add links to my own work. But since we are there, I'd recommend to have a look at the next paper in the series (joint with Austin A. Antoniou). It, too, is on arXiv. $\endgroup$ Commented Jun 17, 2021 at 14:24
  • 1
    $\begingroup$ thanks again. For my future self and anyone who might stumble upon this question, here is the link to the next paper arxiv.org/abs/1804.10913 $\endgroup$
    – Leevi L
    Commented Jun 17, 2021 at 15:23

Not the answer you're looking for? Browse other questions tagged .