Identities of nested set algebraic expressions

[miraiw]

Are there any useful identities for simplifying an expression of the form:
$$((\ldots((x_{1} *_{1} x_{2}) *_{2} x_{3}) \ldots) *_{n - 1} x_{n})$$
Where each $$*_{i}$$ is one of $$\cap, \cup$$ and $$x_1 \ldots x_n$$ are sets?

I believe I found two; though I haven't proved them, I think they make sense:
$$((\ldots((x_{1} \cup x_{2}) *_{2} x_{3}) \ldots) \cup x_{1}) \equiv ((\ldots(x_{2} *_{2} x_{3}) \ldots) \cup x_{1})$$
$$((\ldots((x_{1} \cap x_{2}) *_{2} x_{3}) \ldots) \cap x_{1}) \equiv ((\ldots(x_{2} *_{2} x_{3}) \ldots) \cap x_{1})$$

Generally, how would you prove these? Just induction?

I tested a few expressions with the attached perl script which is why I think they work.

 

[Stephen Tashi]

There are various distributive laws like
$$(A \cup B) \cap C = (A\cap C) \cup (B \cap C)$$
$$(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$$

Since you are using $*_i$ to represent something that can be either $\cup$ or $\cap$ , I can't tell offhand if your identities are correct. I'd have to consider each possible interpretation of the operation as a separate case.

Induction would be the method of proof, assuming that your "..." indicates a an expression of arbitrary but finite length. If you have in mind some sort of infinitely long expressions, you have to start with the problem of defining what they would mean.

 

[miraiw]

I restated the problem in terms of propositions like $$x \in A_{1} \wedge x \in A_{2}$$ and considered that whatever was in the ellipsis would either depend on the innermost expression or not and if it did would either have a value opposite the innermost or the same as. From there I just exhaustively listed the cases and compared. Also, I assumed that the $A_{1}$ doesn't show anywhere in the ellipsis.

I think that's all I need since I can just deal with the rest recursively.