How Can I Show That the Symmetric Difference of Sets is Associative?

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Sets
In summary, "show equality of sets" refers to demonstrating that two sets contain exactly the same elements. To prove equality, one must show that the sets have the same elements. Sets can be equal even if they have different orders, and this concept is used in various areas of mathematics. The difference between equality of sets and subsets is that subsets contain some or all of the elements of another set, while equal sets have exactly the same elements.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)I want to show that $ (A \triangle B) \triangle C=A \triangle (B \triangle C) $.

I have tried the following:

$$ x \in (A \triangle B) \triangle C \Leftrightarrow x \in (A \triangle B)\setminus C \lor x \in C \setminus (A \triangle B) \\ \Leftrightarrow (x \in A \triangle B \wedge x \notin C) \lor (x \in C \wedge x \notin A \triangle B ) \\ \Leftrightarrow (((x \in A \wedge x \notin B) \lor (x \in B \wedge x \notin A)) \wedge x \notin C)\\ \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \wedge x \notin C) \lor (x \in B \wedge x \notin A \wedge x \notin C)) \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \cup C) \lor (x \in B \wedge x \notin A \cup C))\lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) $$

How could we continue?
 
Physics news on Phys.org
  • #2
If you are patient, it is possible to reduce both sides to a disjunctive normal form, i.e., a disjunction of conjunctions, where every element of a conjunction is $x\in S$ or $x\notin S$ and $S$ is one of $A$, $B$, or $C$. A similar approach is to consider eight cases where $x$ belongs or does not belong to each of $A$, $B$, and $C$, and for each of those cases calculate the truth value of both sides.

If you can rely on the fact that addition is associative in $\mathbb{Z}_2$, then you can notice that $x\in S_1\vartriangle S_2$ iff $\chi_1(x)+\chi_2(x)=1$ where $\chi_i(x)=\begin{cases}1,&x\in S_i\\0,&x\notin S_i\end{cases}$ is the characteristic function of $S_i$. Then
\[
\begin{align}
x\in (A\vartriangle B)\vartriangle C&\iff (\chi_A(x)+\chi_B(x))+\chi_C(x)=1\\
&\iff \chi_A(x)+(\chi_B(x)+\chi_C(x))=1\\&\iff x\in A\vartriangle (B\vartriangle C).
\end{align}
\]
 
  • #3
evinda said:
Hello! (Wave)I want to show that $ (A \triangle B) \triangle C=A \triangle (B \triangle C) $.

I have tried the following:

$$ x \in (A \triangle B) \triangle C \Leftrightarrow x \in (A \triangle B)\setminus C \lor x \in C \setminus (A \triangle B) \\ \Leftrightarrow (x \in A \triangle B \wedge x \notin C) \lor (x \in C \wedge x \notin A \triangle B ) \\ \Leftrightarrow (((x \in A \wedge x \notin B) \lor (x \in B \wedge x \notin A)) \wedge x \notin C)\\ \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \wedge x \notin C) \lor (x \in B \wedge x \notin A \wedge x \notin C)) \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \cup C) \lor (x \in B \wedge x \notin A \cup C))\lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) $$

How could we continue?

\(\displaystyle (x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee[x\in C((x\in A\wedge x\in B)\vee(x\notin A\wedge x\notin B))]\Leftrightarrow(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)\vee(x\in C\wedge x\notin A\wedge x\notin B)\)\(\displaystyle \Leftrightarrow[(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)]\vee[(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\notin A\wedge x\notin B)]\Leftrightarrow [x\in A\wedge (( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B))]\vee [x\notin A\wedge ((x\in B \wedge x\notin C)\vee(x\in C\wedge x\notin B))]\)

Can you go on from here??
 
Last edited:
  • #4
solakis said:
\(\displaystyle (x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee[x\in C((x\in A\wedge x\in B)\vee(x\notin A\wedge x\notin B))]\Leftrightarrow(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)\vee(x\in C\wedge x\notin A\wedge x\notin B)\)\(\displaystyle \Leftrightarrow[(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)]\vee[(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\notin A\wedge x\notin B)]\Leftrightarrow [x\in A\wedge (( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B))]\vee [x\notin A\wedge ((x\in B \wedge x\notin C)\vee(x\in C\wedge x\notin B))]\)

Can you go on from here??
In the above disjunction ,let us calculate each disjunct seperately.
So for :

\(\displaystyle [x\in A\wedge (( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B))]\) we have:

\(\displaystyle [x\in A\wedge (F\vee ( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B)\vee F)]\) (remember we are working in the domain of the algebra of propositions)
\(\displaystyle \Leftrightarrow x\in A\wedge[(x\in B\wedge x\notin B)\vee ( x\notin B\wedge x\notin C))\vee(x\in C\wedge x\in B)\vee (x\in C\wedge x\notin C)] \)

\(\displaystyle \Leftrightarrow x\in A\wedge[((x\in B\wedge x\notin B)\vee ( x\notin B\wedge x\notin C))\vee((x\in C\wedge x\in B)\vee (x\in C\wedge x\notin C))] \)in the \(\displaystyle ((x\in B\wedge x\notin B)\vee ( x\notin B\wedge x\notin C))\)

get common factor \(\displaystyle x\notin B\)

in the \(\displaystyle ((x\in C\wedge x\in B)\vee (x\in C\wedge x\notin C))\)

get common factor \(\displaystyle x\in C\) and so we have:

\(\displaystyle \Leftrightarrow x\in A\wedge[x\notin B\wedge(x\in B\vee x\notin C)\vee x\in C\wedge(x\in B\vee x\notin C)]\)

\(\displaystyle \Leftrightarrow x\in A\wedge[(x\notin B\vee x\in C)\wedge (x\in B\vee x\notin C)] \)

And using D.Morgan we have:

\(\displaystyle \Leftrightarrow x\in A\wedge\neg[\neg(x\notin B\vee x\in C)\vee\neg (x\in B\vee x\notin C)] \)

\(\displaystyle \Leftrightarrow x\in A\wedge\neg[(x\in B\wedge x\notin C)\vee (x\notin B\wedge x\in C)] \)

\(\displaystyle \Leftrightarrow x\in A\wedge x\notin (B\triangle C)\)......1

And for the other disjunct \(\displaystyle [x\notin A\wedge ((x\in B \wedge x\notin C)\vee(x\in C\wedge x\notin B))]\)

We have:

\(\displaystyle \Leftrightarrow x\notin A\wedge x\in(B\triangle C)\)........2

And the disjunction of (1) and (2) is:

\(\displaystyle [x\in A\wedge x\notin (B\triangle C)]\vee[ x\notin A\wedge x\in(B\triangle C)]\)

\(\displaystyle \Leftrightarrow A\triangle(B\triangle C)\)
 

FAQ: How Can I Show That the Symmetric Difference of Sets is Associative?

What is meant by "show equality of sets"?

"Show equality of sets" refers to the process of demonstrating that two sets contain exactly the same elements. This means that every element in one set is also in the other set, and vice versa.

How do you prove that two sets are equal?

To prove that two sets are equal, you must show that they have the same elements. This can be done by listing out the elements of each set and comparing them, or by using mathematical notation such as set-builder notation or set equality symbols.

Can sets be equal even if they have different orders?

Yes, sets can be equal even if they have different orders. The order of elements within a set does not affect its equality with another set. As long as the elements are the same, the sets are considered equal.

What is the difference between equality of sets and subsets?

The equality of sets refers to two sets containing exactly the same elements. Subsets, on the other hand, are sets that contain some or all of the elements of another set. In other words, all elements of a subset must also be in the larger set, but the larger set may have additional elements.

How is the concept of equality of sets used in mathematics?

The concept of equality of sets is used in many different areas of mathematics, including algebra, number theory, and calculus. It is a fundamental concept in set theory and is often used to prove theorems and solve problems involving sets and their elements.

Similar threads

MHB Prove Identities of Sets Hello! (Wave)
Replies
1
Views
1K
MHB Proving Symmetric Difference Properties of Sets
Replies
1
Views
2K
MHB How Can We Prove Basic Properties of Set Theory?
Replies
1
Views
1K
MHB Translate the statements into set inclusion
Replies
5
Views
1K
Union of sets and indexed sets question from Vellerman
Replies
4
Views
1K
MHB Minimal successor set - difficult
Replies
1
Views
1K
MHB Two-element Boolean algebra: How are the equalities derived?
Replies
13
Views
3K
MHB Please help with bool algebra and logic things
Replies
2
Views
1K
MHB Do we have to show that the relation is irreflexive?
Replies
1
Views
2K
I Understanding Subset Membership: Exploring the Concept of A ⊆ B
Replies
18
Views
4K

Hot Threads

Recent Insights

Back
Top