0
$\begingroup$

I used to learn it in a different way; \begin{align} x\in A\cup (B\cap C)&\implies x\in A \textrm{ or } (x\in B \textrm{ and } x\in C)\tag{1}\\ &\implies (x\in A \textrm{ or } x\in B) \textrm{ and } (x\in A \textrm{ or } x\in C)\tag{2}\\ &\implies x\in (A\cup B)\cap (A\cup C)\tag{3} \end{align} using the different rules.

This <link> on page 2 has shown another way which questioned me a lot but I will try to make short questions.

It starts to assume that $x\in A\cup (B\cap C)$, that is, assuming with two cases, $x\in A$ and $x\in B\cap C$. The first case seems no problem to me when knowing about or-introduction. But the last case doesn't really make sense to me. For example, if $x\in B\cap C$ then it means that $x$ is both in $B$ and $C$, so how can $x$ be in $A\cup B$ while ignoring the set $C$? I mean, where is the set $C$ if $x$ is in $A\cup B$? The same way, where the set $B$ is if $x\in A\cap C$.

How exactly is this proof technique structured? The proof above shows clearly what happens from $(1)$ to $(2)$, and from $(2)$ to $(3)$. This is the only thing that makes sense to me. But not like this link. It doesn't look like how it is implied but I feel like it's just checking if it's verified or that it only looks at the right side to make the left side imply.

$\endgroup$
  • $\begingroup$ $x\in A\cup(B\cap C)$ means $x\in A$ or $x\in B\cap C$. I'm guessing you meant the or there, correct? $\endgroup$ – Daniel W. Farlow Jul 16 '15 at 22:58
  • $\begingroup$ @DanielW.Farlow I understand what it means. I used "and" to the cases. Should I write "or" instead? $\endgroup$ – UnknownW Jul 16 '15 at 23:00
  • $\begingroup$ I am referring the first sentence of your paragraph starting, "It starts to assume ..." $\endgroup$ – Daniel W. Farlow Jul 16 '15 at 23:01
  • $\begingroup$ @DanielW.Farlow What I meant is that it shows the cases (i) $x\in A$, (ii) $x\in B\cap C$. Is it wrong to say "and" between the cases while knowing that it's not $x\in A\cap (B\cap C)$ I am talking about? $\endgroup$ – UnknownW Jul 16 '15 at 23:05
1
$\begingroup$

It starts to assume that $x∈A∪(B∩C)$ , that is, assuming with two cases, $x∈A$ and $x∈B∩C$ . The first case seems no problem to me when knowing about or-introduction. But the last case doesn't really make sense to me. For example, if $x∈B∩C$ then it means that $x$ is both in $B$ and $C$ , so how can $x$ be in $A∪B$ while ignoring the set $C$ ? I mean, where is the set $C$ if $x$ is in $A∪B$ ? The same way, where the set $B$ is if $x∈A∩C$ .

It's not ignored, it's just examined in parallel.   If you can start with premise $Z$, then prove $X$ by one path, and in parallel prove $Y$ by another, then you have proven the conjunction $X\wedge Y$.   (If $Z\vdash X$ and $Z\vdash Y$, then $Z\vdash X\wedge Y\;$.)

$$ \cfrac{ \cfrac{ \cfrac{ \cfrac{ \cfrac{ \cfrac{ x\in B\cap C }{x\in B \wedge x\in C} }{x\in B} }{x\in A\vee x\in B} }{x\in A\cup B} \quad \cfrac{ \cfrac{ \cfrac{ \cfrac{ x\in B\cap C }{x\in B \wedge x\in C} }{x\in C} }{x\in A\vee x\in C} }{x\in A\cup C} }{x\in A\cup B \wedge x\in A\cup C} }{x\in (A\cup B)\cap(A\cup C)} $$

$\endgroup$
2
$\begingroup$

It uses the Implies-subset relation which states that (by definition)

$$[A\subseteq B]\iff\forall x[x\in A\implies x\in B]$$

In addition we have:

$$[x\in A\cap B]\iff[x\in A\wedge x\in B]$$

($\wedge$ means "and") and

$$[x\in A\cup B]\iff[x\in A\vee x\in B]$$

and of course, $\vee$ means "or" (which is $x\in A$, $x\in B$ or both)

$\endgroup$
1
$\begingroup$

The last step (i.e., the "second case") makes sense, but it could be worded more clearly. To keep it firmly in mind, here it is:

In the second case (i.e., the case "$x\in B$ and $x\in C$"), we have $x\in A\cup B$ and $x\in A\cup C$, by the definition of a union. As before, by the definition of an intersection, it follows that $x\in (A\cup B)\cap (A\cup C)$.

Okay, let's dissect this and see how it makes sense. First, the author begins the proof with "Let $x\in A\cup (B\cap C)$." Since the second case is all about what happens when $x\in B\cap C$, you clearly have that $x\in A\cup B$ and $x\in A\cup C$ by the definition of a union (the size of $A$ and whether or not its elements intersect with those of $B$ and $C$ does not matter since you are considering the union). What you need, namely $x\in(A\cup B)\cap(A\cup C)$, simply follows from this observation.

If $x\in B\cap C$ then it means that $x$ is both in $B$ and $C$, so how can $x$ be in $A\cup B$ while ignoring the set $C$?

You are not ignoring the set $C$--you are simply stating that $x$ is in both $A\cup B$ and $A\cup C$ (<-- $C$ is not being ignored there). Does that make sense?


For what it's worth, the way you structured your own proof is much cleaner and elegant in my opinion. I would have done likewise. The proof in the PDF is verbose and convoluted.

$\endgroup$
1
$\begingroup$

Suppose $x \in A \cup (B \cap C)$. We have two cases here: $$x \in A \;\mathrm{or}\; x \in B \cap C$$

You already know the case where $x \in A$ so I will leave that. Let's assume that $x \in B \cap C$. So, we have $$x \in B \; \mathrm{and} \; x \in C$$

So, $$x \in B \subseteq A \cup B$$ and also $$x \in C \subseteq A \cup C$$ Hence, $$x \in (A \cup B) \cap (A \cup C)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.