1
$\begingroup$

I am trying to wrap my head around discrete mathematics in order to help my understanding of self taught programming. I am now trying to understand Set Theory, more specifically proving certain theorems. I understand the basic concept of proofs, but cannot seem to figure out how to approach/complete this one. Any help would be well received and greatly appreciated.

Prove: $$A \cap(B\cup A) = A$$

$\endgroup$
3
  • $\begingroup$ As for a lot of problems of type $A=B$ you can prove than $A \subset B$ and $B \subset A$ $\endgroup$
    – T_O
    Apr 2, 2014 at 14:33
  • $\begingroup$ In lattice theory, the statement $A \wedge (A \vee B)=A$ is called an absorption law. (The other absorption law is $A \vee (A \wedge B)=A.$) In the algebraic definition of a lattice, the absorption laws are taken as axioms; however, in the order-theoretic view, they're provable theorems. You should have a go at proving them from the order-theoretic definition of a lattice. $\endgroup$ Apr 2, 2014 at 14:43
  • $\begingroup$ You must use the above suggestion and apply it to the definitions : $x \in A \cup B$ iff $x \in A$ or $x \in B$, and $x \in A \cap C$ iff $x \in A$ and $x \in C$. Start from left and apply them, with suitble "intuitive" logical passages, in order to arrive at the goal. $\endgroup$ Apr 2, 2014 at 14:43

3 Answers 3

2
$\begingroup$

Let $x$ be in the LHS. Then $x\in A$, $x\in B\cup A$ by definition of intersection, so $x\in A$. This LHS$\subseteq A$.

Let $x\in A$. Then $x\in B\cup A$ by definition of union. Thus $x\in$ LHS by definition of intersection, so $A\subseteq$LHS.

If $X\subseteq Y$ and $Y\subseteq X$ then $X=Y$. This equality follows in your problem.

$\endgroup$
0
$\begingroup$

From $x\in A\cap(B\cup A)$ it follows by definition that $x\in A$

If conversely $x\in A$ then also $x\in B\cup A$ and these two facts lead to $x\in A\cap(B\cup A)$

This together proves that $A\cup(B\cap A)=A$

Alternatively if $P\subset Q$ then $P\cap Q=P$. You can apply that for $P=A$ and $Q=B\cup A$.

$\endgroup$
0
$\begingroup$

I would approach this as a simplification problem, most easily solved by starting with $\;A \cap (B \cup A)\;$, expanding the definitions and then simplifying using the rules of logic.

So we calculate which $\;x\;$ are in that set:

\begin{align} & x \in A \cap (B \cup A) \\ \equiv & \qquad \text{"definition of $\;\cap\;$; definition of $\;\cup\;$"} \\ (*) \;\;\; \phantom{\equiv} & x \in A \;\land\; (x \in B \;\lor\; x \in A) \\ \equiv & \qquad \text{"logic: use $\;x \in A\;$ on other side of $\;\land\;$"} \\ & x \in A \;\land\; (x \in B \;\lor\; \text{true}) \\ \equiv & \qquad \text{"logic: simplify"} \\ (**) \;\;\; \phantom{\equiv} & x \in A \\ \end{align}

By set extensionality, this proves the theorem.

In essence, the above proof uses (a generalization of) the absorption law from logic to prove the absorption law for sets.

Another way to go from $(*)$ to $(**)$ is \begin{align} & P \land (Q \lor P) \\ \equiv & \qquad \text{"rewrite -- to give both sides of $\;\land\;$ the same shape"} \\ & (P \lor \text{false}) \land (P \lor Q) \\ \equiv & \qquad \text{"extract common disjunct:$\;\lor\;$ distributes over $\;\land\;$"} \\ & P \lor (\text{false} \land Q) \\ \equiv & \qquad \text{"simplify"} \\ & P \\ \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .