The function that takes two quotient sets and merges them

Question

I want to know the definition and the well-definedness of the function that takes two quotient sets (disjoint-set data structures), merges them and returns a quotient set.

For example, if the function takes two inputs, {{1, 2}, {3, 4, 5}, {6, 7}} and {{2, 6}, {8}}, then it returns {{1, 2, 6, 7}, {3, 4, 5}, {8}}.

Please let me know if you have the answer (or the reference to these discussions). I am also very pleased if you let me know that you do not have the answer (this is not common knowledge).

Q1.

Is there any (common) definition of this function?

Q2.

Is that function well-defined, i.e., the function always returns output, and the output is uniquely determined by the inputs?

Remark

I wrote a pseudo-code of this function (in a functional programming style).

let rec merge QS =
  if \exists S, S' \in QS.
    S \neq S' \land S \cap S' \neq \emptyset
  then
    merge (\{S \cup S'\} \cup ((SS \setminus S) \setminus S'))
  else
    QS

let merge_quotient_sets QS QS' =
  merge (QS \cup QS')

However, I found that

1. This seems too "algorithmic" and does not seems like a "mathematical definition".
2. I could not give well-definedness proof (which may not be difficult though).

Can someone give me a simpler and more algebraic(?) definition and an elegant proof?

Answer 1

What you have called a quotient set or a disjoint data structure, I would call a partition of a set. It's a standard fact that every partition of a set arises from a unique equivalence relation on that set, namely that $x\sim y$ if and only if $x$ and $y$ are in the same subset in the partition. In these terms, the operation you are describing, starting from two equivalence relations $R_1$ and $R_2$, seems to be the equivalence relation generated by $R_1\cup R_2$, which is the smallest equivalence relation containing both $R_1$ and $R_2$.