Union/Intersection Relationship (Proof)

[Someone2841]

Below is a attempt at a proof of a distributive property of union/intersections of sets. A critique would be very much appreciated. Thanks in advance!

-----------------
For sets A, B, and C, the formula,
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
is true

Two sets are equal if they contain the same elements. Let x denote an element of set $A \cup (B \cap C)$ and y an element of $(A \cup B) \cap (A \cup C)$. Where X and Y are sets, $X \subset Y$ and $e \in Y$, define the function $f_X(e)$ as

$f_X(e) = \begin{cases} 1, & e \in X \\ 0, & e \notin X \end{cases}$

We want to show that $\forall e \in A \cup B \cup C, f_{A \cup (B \cap C)}(e) = f_{(A \cup B) \cap (A \cup C)}(e)$, since this would imply $e \in A \cup (B \cap C) \iff e \in (A \cup B) \cap (A \cup C)$. First, two basic and easily verifiable properties of $f_X(e)$ are:$\begin{alignat}{0} f_{X \cap Y}(e) = f_X(e)f_Y(e) & \text{(1) - since e must be in X and Y} \\ f_{X \cup Y}(e) = f_X(e) + f_Y(e) - f_X(e)f_Y(e) & \text{(2) - since e may be in X or Y} \end{alignat}$

And now:
$f_{A \cup (B \cap C)}(e)$
$\begin{alignat}{0} =&f_A(e) + f_{B \cap C}(e) - f_A(e)f_{B \cap C}(e) & \text{(1)}\\ =&f_A(e) + f_B(e) f_C(e) - f_A(e)f_B(e)f_C(e) & \text{(0)}\\ =&f_{(A \cup B) \cap (A \cup C)}& \text{(1)} \end{alignat}$

And therefore $e \in A \cup (B \cap C) \iff e \in (A \cup B) \cap (A \cup C)$ and $A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \text{ } \Box$

------

P.S.: This is not a homework assignment; however, it is very much like a homework assignment. Would this type of problem go better in the homework section?

 

[Stephen Tashi]

What constitutes a correct proof depends on the context in which the proof is given. A requirement to prove the distributive law of sets often happens in a course that is trying to teach the fundamentals of logic as well as set theory. In that context, you are expected to show you've mastered the fundamentals of logic. Your proof doesn't give sufficient details of the fundamentals of logic. Instead it asserts some properties about the function f_A(x) without referring to the fundamentals of logic.

For example:

First, two basic and easily verifiable properties of $f_X(e)$ are:
$\begin{alignat}{0} f_{X \cap Y}(e) = f_X(e)f_Y(e) & \text{(1) - since e must be in X and Y} \\ f_{X \cup Y}(e) = f_X(e) + f_Y(e) - f_X(e)f_Y(e) & \text{(2) - since e may be in X or Y} \end{alignat}$

...

And now:
$f_{A \cup (B \cap C)}(e)$
$\begin{alignat}{0} =&f_A(e) + f_{B \cap C}(e) - f_A(e)f_{B \cap C}(e) & \text{(1)}\\ =&f_A(e) + f_B(e) f_C(e) - f_A(e)f_B(e)f_C(e) & \text{(0)}\\ \end{alignat}$

Those arguments are acceptable in an advanced course where the reader is expected to believe the "easily verifiable" properties of your function without a detailed justification, but in an advanced course, the distributive law of union over intersection itself would be considered "easily verifiable".

My guess is that a basic course expects you state the definitions of union and intersection for sets and give a proof that employs the distributive laws of propositional logic. "P or (Q and R)" is logically equivalent to "(P or Q) and (P or R)". Hence \forall x ( x \in A \ or \ (x \in B \ and \ x \in C )) is logically equivalent to \forall x ( (x \in A \ and \ x \in B) \ or \ (x \in A \ and \ x \in C)).

To verify the properties of your function in detail, such logic has to be used. The level of the course determines whether you are expected to show the logic in detail. If you are in a course that emphasizes basic logic, you can't escape doing the basic logic by inventing a function and then skiipping over the detailed logic when deriving its properties. If you are in a more advanced setting then it may be convenient to introduce such a function to simplify the presentation.

 

[Someone2841]

That makes sense. It is illogical to use a function based on assumptions that can themselves prove the relationship and are actually necessary therefor (unless, as you pointed out, it helps with the presentation; here it does not). How's this:

---
For sets A, B, and C, the formula,
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
is true

Definitions of union and intersections of sets:
$X \cup Y = \{e:e \in x \vee e \in y\}$
$X \cap Y = \{e:e \in x \wedge e \in y\}$

Let x denote an element of set A∪(B∩C) and y an element of (A∪B)∩(A∪C), by definition:
$\begin{alignat}{0} & \text{1.} && A \cup (B \cap C) = A \cup \{x: x \in B \wedge x \in C \} = \{x: x \in A \vee ( x \in B \wedge x \in C ) \} \\ & \text{2.} && (A \cup B) \cap (A \cup C) = \{y: y \in A \vee y \in B \} \cap \{y: y \in A \vee y \in C \} = \{y: (y \in A \vee y \in B) \wedge (y \in A \vee y \in C)\} \end{alignat}$

Lemma: P∨(Q∧R)⟺(P∨Q)∧(P∨R)
Proof: P∨(Q∧R) is true when 1) P is true or 2) P is false and both Q and R are true. If 1) P is true, then (P∨Q)∧(P∨R) is true; if 2) P is false and both Q and R are true, then (P∨Q)∧(P∨R) is true. Therefore, P∨(Q∧R) ⟹ (P∨Q)∧(P∨R). Conversely, (P∨Q)∧(P∨R) is true when 1) P is true or 2) P is false and both Q and R are true. If 1) P is true, then P∨(Q∧R) is true; if 2) P is false but Q and R are true, then P∨(Q∧R) is true. Therefore, (P∨Q)∧(P∨R) ⟹ P∨(Q∧R). Thus, P∨(Q∧R)⟺(P∨Q)∧(P∨R).

By that lemma, these two statements are true:
$\forall x(x \in A \vee ( x \in B \wedge x \in C ) \iff (x \in A \vee x \in B) \wedge (x \in A \vee x \in C)$
$\forall y(y \in A \vee ( y \in B \wedge y \in C ) \iff (y \in A \vee y \in B) \wedge (y \in A \vee y \in C)$

Since two sets are equal when they contains the same elements, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{ } \Box$

 

[Stephen Tashi]

Evaluating that proof again depends on the context. In the context of a logic course, you would usually have covered the logical equivalence P \vee ( Q \wedge R) \iff (P \vee Q) \wedge (P \vee R) before you began doing a proof about sets. In that case, you need not argue this equivalence; you can refer to it as a previous result. In the context of a more advanced course, the equivalence could be taken as "common knowledge" and not proven.

It isn't clear whether your proof is supposed to demonstrate your ability with logical quantifiers. In "natural language" proofs, we often don't explicity state quantifiers. For example, a statement such as A \cup (B \cap C) = (A \cup B) \cap (A \cup C) is taken to involve universal quantifiers unless otherwise noted.

i.e. Let S(X) represent the property "X is a set".
\forall A, \forall B, \forall C ( (S(A) \wedge S(B) \wedge S(C) ) \implies A \cup (B \cap C) = (A \cup B) \cap (A \cup C) ).In natural language proofs, the method of "universal generalization" is often used (and you've used it). In this method we introduce a symbol that represents a completely general thing. For example we say "Let x be an element" or "Let P be a propositon" or we simply introduce a symbol without even the courtesy of saying "Let...be a...". We make an argument using the symbol as if it were some particular thing. At end we conclude that our argument applies to any such thing because the symbol we used didn't have any special properties that distinguished it.

In most mathematical contexts, this type of argument is taken for granted. In a course on symbolic logic which is trying to teach "universal generalization" you'd be expected to go through the formalities of showing where you used it. (Proofs in such courses are written mostly as strings of symbols .)

To me your proof has strange mixture of natural language and formal language. Some places you are careful to use quantifiers, at other places you treat them informally. You use notation such as A \cup B = \{e: e \in A \vee e \in B \} that is appropriate for a natural language proof. A proof emphasizing the role of definition and basic logic would state definitions as logical equivalences. It would use the definition of "equality" of sets: A = B \iff \forall x (x \in A \iff x \in B) and the definition of union as \forall x ( (x \in A \cup B) \iff x \in A \cup x \in B)

From the point of view of rigorous logic, any definition must be interpretable as a logical equivalence. In natural language we say things like "A positive number is a number greater than 0" instead of saying "x is a positive number iff and only if x is a number greater than 0". However, in more formal logic, you need the later formulation. You need to be able to put any definition in the form of "[The statement to be defined] \iff [A statement involving things previously defined]".

In summary, you need to settle on a particular context for your proof. A valid proof is an argument that will convince an audience of experts. The way it should be written depends on the audience. The audience might be the grader for a logic course, the teacher of a physics course, the editor of math journal or just yourself.

 

[Someone2841]

Thanks for the advice! I'm really just trying to learn to prove and practice proving things (this problem comes from Pugh's book on Real Analysis), so any strangeness comes from a lack of understanding and formal training. I think I get what you mean about the context. At the point which this is proven, something as simple as this may work? (Perhaps overly verbose?)

---

For sets A, B, and C, the formula,
$A∪(B∩C)=(A∪B)∩(A∪C)$
is true

To prove this, it needs to be shown that every element x in A∪(B∩C) is also in (A∪B)∩(A∪C), and vice versa. Every element x in A∪(B∩C) is either in A or in (B and C), and so x is in (A or B) and (A or C) and therefore in (A∪B)∩(A∪C). Conversely, every element y in (A∪B)∩(A∪C) is either in (A or B) and (A or C), and so y is in A or in (B and C) and therefore in A∪(B∩C). Since every x and y is in both A∪(B∩C) and (A∪B)∩(A∪C), A∪(B∩C)=(A∪B)∩(A∪C).


---

This takes for granted the definition of sets and their equality condition, unions, and intersections without formally stating their definition and assumes that $p \vee (q \wedge r) \iff (p \vee q) \wedge (p \vee r)$ is true.