Identities of nested set algebraic expressions


by miraiw
Tags: algebraic, expressions, identities, nested
miraiw
miraiw is offline
#1
Apr29-12, 06:04 PM
P: 10
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
File Type: txt sym.txt (3.5 KB, 1 views)
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
Stephen Tashi
Stephen Tashi is offline
#2
Apr30-12, 08:16 PM
Sci Advisor
P: 3,173
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.
miraiw
miraiw is offline
#3
Apr30-12, 10:54 PM
P: 10
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