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)\)
 

Related to 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)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Translate the statements into set inclusion
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
888
Union of sets and indexed sets question from Vellerman
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
931
MHB Proving Symmetric Difference Properties of Sets
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
MHB Please help with bool algebra and logic things
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
MHB How Can We Prove Basic Properties of Set Theory?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
886
MHB Statements about the preimages
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
3K
MHB Minimal successor set - difficult
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Do we have to show that the relation is irreflexive?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Proof of Second Sentence:$m<n \leftrightarrow m'<n'$
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top