I wish to prove that for sets $A$ and $B$, $A \cap B = B \cap A$ using logic. I used a rule of inference called the universal biconditional transitivity which is in the form of:
$A\cap B = B\cap A \leftrightarrow \forall x, (x\in A \cap B \leftrightarrow x\in B\cap A)$
$\forall x \in D, P(x) \leftrightarrow Q(x)$
$\forall x \in D, Q(x) \leftrightarrow R(x)$
$\therefore \forall x \in D, P(x) \leftrightarrow R(x)$
for predicate symbols $P, Q, R$, and predicate variable $x$ with domain of $D$.
Here is how the prove went:
Let the domain of $x$ be some universe of discourse. The following are then true propositions,
$\forall x, (x\in A \cap B \leftrightarrow (x\in A \wedge x\in B))$
$\forall x, (x\in B \cap A \leftrightarrow (x\in B \wedge x\in A))$
by definition of sets intersection. Let $c$ be particular but arbitrarily chosen from the domain, then by universal instantiation, $c\in A \cap B \leftrightarrow (c\in A \wedge c\in B)$ is a true statement. Since the conjunction of statements (or propositions) are commutative (proven by truth table), i.e. $c \in A \wedge c \in B \equiv c \in B \wedge c\in A$, we know that $c\in A \cap B \leftrightarrow (c\in B \wedge c\in A)$ is true.
Since $c$ was arbitrary, by universal generalization, we deduce that $\forall x, (x\in A\cap B \leftrightarrow (x\in B \wedge x\in A))$ is true. From
$$\forall x, (x\in A\cap B \leftrightarrow (x\in B \wedge x\in A)) \equiv \forall x, ((x\in B \wedge x\in A)\leftrightarrow x\in A\cap B)$$
we know that $\forall x, ((x\in B \wedge x\in A)\leftrightarrow x\in A\cap B)$ is also true. By the universal biconditional transitivity, we deduce that
$$\forall x, (x\in B \cap A \leftrightarrow x\in A\cap B)$$
is true. By the definition of set equality, we deduce that
$$B\cap A = A\cap B$$
which can also be written as $A\cap B = B\cap A$.
Is there any mistake(s) in this proof? Is there anything that can be improved? Thanks
Best Answer
A (much simpler) proof using the commutativity law:
$A \cap B $
$ = \{ x | x \in A \wedge x \in B \}$ by definition of intersection
$ = \{ x| x\in B \wedge x \in A \}$ by commutativity law
$ = B \cap A $ by definition of intersection
You could also employ a semantic approach by drawing a comparative truth table and observing that every interpretation results in the same truth value for propositions $x \in A \wedge x \in B$ and $x \in B \wedge x \in A$.