1
$\begingroup$

DISCLAIMER: This was a typo in the third edition of the ebook, the correct statement to prove is: $B \backslash (\bigcap\limits_{i∈I} A_{i}) = \bigcup\limits_{i∈I}(B \backslash A_{i})$

I have been trying to solve Velleman's exercises in his book "how to prove it". However I have hit a snag with this specific proof. I'm used to fully writing it out in predicate form and then proving it. I have managed to solve $B \backslash (\bigcup\limits_{i∈I} A_{i}) ⊆ \bigcup\limits_{i∈I}(B \backslash A_{i}))$ but I'm struggeling to proof it the other way around: $\bigcup\limits_{i∈I}(B \backslash A_{i})) ⊆ B \backslash (\bigcup\limits_{i∈I} A_{i})$.

There is also being given that I is not an empty set.

I have analyzed the givens as follows: $\exists{i}(i \in I \wedge (a \in B \wedge a \notin A_{i}))$

And what I need to prove: $\forall{i}(i \in I \implies a \notin A_i)$ and $a \in B$

But I just don't see any way to show this is indeed true, if possible please provide an answer in predicate style and a direct proof (if that's possible) since I'm trying to learn and understand it. But any help is welcome really.

Note while this may seem simple I have done multiple attempts and can't figure it out. So I'm wondering if it's even correct, rules I have learned so far are Universal instantiation, generalization, same with existential, modus ponens, modus tollens, implication, bijunction, conjunction, negation. I have not seen other rules yet, if it's true I feel like it must be using some rule I'm not aware of.

$\endgroup$
6
  • $\begingroup$ Are $1$ and $I$ supposed to be the same thing here? $\endgroup$
    – jjagmath
    Commented Nov 15, 2023 at 13:31
  • $\begingroup$ Oh sorry my glasses are not up to prescription, I'll adjust it. $\endgroup$ Commented Nov 15, 2023 at 13:44
  • $\begingroup$ Is $I$ finite? If no, is it countable? $\endgroup$
    – Tran Khanh
    Commented Nov 15, 2023 at 13:51
  • $\begingroup$ What is stated in the problem is that I is a set that has all the indexes in it for the set {Ai | i element of I}. What I also know is that I is not empty. I know the rules for all of these to translate them into predicate logic but unlike the other exercises I can't see how to actually prove this statement with them. I suppose given thennature of this book (which keeps it simple) I suppose I is countable yes, but I cant say for sure. $\endgroup$ Commented Nov 15, 2023 at 13:53
  • $\begingroup$ I have a physical copy of the 3rd edition of Velleman on my desk, and the problem is printed correctly (assuming you're talking about Exercise 23(b) in Section 3.4 on p. 142. I have noticed that some pdf versions of the book which are floating around on the internet have very strange errors in their math symbols (e.g. nonsensical symbols substituted for the correct symbols). Your issue might be related to this. $\endgroup$ Commented Nov 15, 2023 at 14:30

2 Answers 2

1
$\begingroup$

The statement as written is wrong. The right statement is $\bigcup_{i\in I}(B\setminus A_i)=B\setminus\bigcap_{i\in I}A_i$. To see that the statement is wrong, consider $B=\{1,2,3,4\},\,A_1=\{1,2\},A_2=\{3,4\}$. Then: $$\bigcup_{i\in I}(B\setminus A_i)=\{1,2,3,4\}$$ $$B\setminus\bigcup_{i\in I}A_i=\emptyset$$

$\endgroup$
1
  • $\begingroup$ Oh I see thank you very much for pointing this out! I was wondering why I could not prove but it was because it simply was not true. The previous edition did have it like you describe here but the third edition had it like like I posed it in question. Thanks again, you're saved me a ton of time trying to prove something that could not be proven. $\endgroup$ Commented Nov 15, 2023 at 14:17
0
$\begingroup$

Proof that $\bigcup\limits_{i∈I}\Big(B \backslash A_{i}\Big) ⊆ B \backslash \Big(\bigcap\limits_{i∈I} A_{i}\Big)$ using set identites below:

$ \begin{array}{llll} \bigcup\limits_{i∈I} \Big( B \backslash A_{i} \Big) & = \bigcup\limits_{i \in I} \Big( B \cap A_i^C \Big) & \text{by definition of set difference} \\ & = B \cap \Big( \bigcup\limits_{i \in I} A_i^C \Big) & \text{by distributive law for sets} \\ & = B \cap \Big( \bigcap\limits_{i \in I} A_i \Big)^C & \text{by DeMorgan's Law for sets} \\ & = B \backslash \Big( \bigcap\limits_{i \in I} A_i \Big) & \text{by definition of set difference} \\ \end{array} $

By definition of equality between sets, we know $\bigcup\limits_{i∈I}\Big(B \backslash A_{i}\Big) \subseteq B \backslash \Big(\bigcap\limits_{i∈I} A_{i}\Big)$ and $B \backslash \Big(\bigcap\limits_{i∈I} A_{i}\Big) \subseteq \bigcup\limits_{i∈I}\Big(B \backslash A_{i}\Big)$. Therefore, $\bigcup\limits_{i∈I}\Big(B \backslash A_{i}\Big) \subseteq B \backslash \Big(\bigcap\limits_{i∈I} A_{i}\Big)$.

$\endgroup$

You must log in to answer this question.

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