Register to reply 
Identities of nested set algebraic expressions 
Share this thread: 
#1
Apr2912, 06:04 PM

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. 


#2
Apr3012, 08:16 PM

Sci Advisor
P: 3,295

There are various distributive laws like
[tex] (A \cup B) \cap C = (A\cap C) \cup (B \cap C) [/tex] [tex] (A \cap B) \cup C = (A \cup C) \cap (B \cup C) [/tex] Since you are using [itex] *_i [/itex] to represent something that can be either [itex] \cup [/itex] or [itex] \cap [/itex] , 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. 


#3
Apr3012, 10:54 PM

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 [itex] A_{1}[/itex] doesn't show anywhere in the ellipsis.
I think that's all I need since I can just deal with the rest recursively. 


Register to reply 
Related Discussions  
Algebra II Simplifying Rational Algebraic Expressions  Precalculus Mathematics Homework  13  
Expand and Simplifying Algebraic Expressions  Precalculus Mathematics Homework  2  
How do you expand algebraic expressions to the nth power?  Precalculus Mathematics Homework  3  
Factoring Algebraic Expressions with Fractional Exponents  Precalculus Mathematics Homework  3  
How to find algebraic expressions?  Precalculus Mathematics Homework  3 