# Identities of nested set algebraic expressions

P: 17
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.
Attached Files
 sym.txt (3.5 KB, 1 views)
 Sci Advisor P: 3,295 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.
 P: 17 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.

 Related Discussions Precalculus Mathematics Homework 13 Precalculus Mathematics Homework 2 Precalculus Mathematics Homework 3 Precalculus Mathematics Homework 3 Precalculus Mathematics Homework 3