Problem 4.10 in mcs_2018-unlocked.pdf

[spamegg1]

I'm opening this discussion in response to your email.
I'll update when I have a chance to look over the solution.

To be clear, the Problem is:

Problem 4.10.

Looking at set expressions involving just the operations $\cup$, $\cap$, and complement, Section 4.1.5 explains how to reduce proving the equality of two such expressions to verifying validity of a corresponding ropositional equivalence. The same approach can provide counter-examples to set-theoretic equalities that are not valid.

For example, a counter-example to the equality

$$ A - (B \cup C) = A - B \cup A - C $$

is

$$ A = \{1\}, B = \{1\}, C = \emptyset . $$

Now the left hand expression evaluates to $\{1\} - (\{1\} \cup \emptyset) = \emptyset$, while the right hand expression evaluates to $\emptyset \cup (\{1\} - \emptyset) = \{1\}$.

Explain how, given a set-theoretic equality between two set expressions that is not valid, to construct a counter-example using any truth assignment that falsifies the corresponding propositional equivalence. Conclude that any set equality that is valid in a domain of size one will be valid in all domains.

I cannot find where your solution is. Can you point me to it?

[sci-42ver]

Sorry. The README.md again is too big. I changed now and reviewed my solution by fixing some small errors (I committed to github "update Problem 4.10 and 15.8.2" just now). See

Discrete_Mathematics_and_Algorithm/Discrete_Mathematics_and_Its_Applications/mcs.md

Line 185 in 7313ef6

- Problem 4.10 @#@ (Here @#@ means problems in mcs 2018 whose solution is not certain and not verified)

You can copy the contents into https://stackedit.io/app# to render correctly.

[spamegg1]

I'll post the solution here for easier discussion.

• Problem 4.10 @#@ (Here @#@ means problems in mcs 2018 whose solution is not certain and not verified)

$$ \begin{align*} z&\in A-(B\cup C)&\\ &\iff (z\in A)\land(\neg z\in B\cup C)&(\text{def of }-)\\ &\iff (z\in A)\land(\neg (z\in B\lor z\in C))&(\text{def of }\cup)\\ &\iff (z\in A)\land(z\notin B\land z\notin C)&(\text{De Morgan's laws})\\ &\iff (z\in A)\land(z\in A)\land(z\notin B\land z\notin C)&(a\land a=a)\\ &\iff (z\in A \land z\notin B)\land(z\in A \land z\notin C)&(\text{Associativity and Commutativity})\\ &\iff (A-B)\cap(A-C)&(\text{def of }\cap,-) \end{align*} $$

• Explain how, given a set-theoretic equality between two set expressions that is not valid, to construct a counter-example using any truth assignment that falsifies the corresponding propositional equivalence

Since we get the final expression, it is easy to show the counter-example or directly show the equality "is not valid". If wanting to make connection with the "truth assignment" anyway, we can use $T\land F\neq T\lor F$ where $(\land,\lor)$ corresponds to $(\cap,\cup)$. Or more specifically, let $(z\in A \land z\notin B)=T$ and $(z\in A \land z\notin C)=F$.
We can also use the method implied in the following proof, i.e. .

• Conclude that any set equality that is valid in a domain of size one will be valid in all domains.

Focus on the 2nd to last equation sequence in p107, we only need to care about each propositional literal like $z\in A$ and the above $\neg z\in A=z\notin A$.

Then for "a domain of size one" like ${1}$ which the problem seems to assume including $\varnothing$

we choose $z$ as the only element in that set, i.e. $1$ in the above. Then $1\in{1}=T,1\in\varnothing=F$. So that for each $z\in A$ we can choose $T$ or $F$.

Then all possible truth assignment for the truth table can be tested in "a domain of size one". $\blacksquare$

[spamegg1]

Okay, it's a vague, open-ended "explain" question so I would not take it too seriously.

I'm not sure how your proof $z \in A - (B \cup C) \iff z \in (A-B) \cap (A - C)$ (last line should have $z \in$) is relevant... the question is stated "generally". The wrong set equality was just given as an example of a "broader idea".

So it's just asking "explain in general" not "explain in this particular example". At least that's how I understood it.

The problem is written very poorly, as is quite common in this book. As I understand, the exercises are written with a classroom in mind, so you would explain it to the professor in person.

I think in your explanation you got the right idea. And since it's a vague question it's difficult to give a precise answer. It's an ESSAY question. I would say something like this:

1. Given a set-theoretic equality between two set expressions that is not valid.
2. Use the definitions of set operations to convert the set expressions to propositions.
3. These propositions can be put into, say, Conjunctive Normal Form.
4. So, both propositions will have the form similar to:

$$ (z \in A \vee z \notin B \vee \cdots) \wedge (z \notin C \vee z \in D \vee \cdots) \wedge \ldots (\ldots) $$

where each literal is of the form $z \in X$ or $z \notin X$ for some set variable $X$.

5. We can convert each expression of the form $z \in X$ to a propositional variable like $P$, $Q$ etc.
6. To find a counterexample, we need to find a truth assignment that makes all the conjuncts in one proposition true, and make at least one conjunct in the other proposition false.
7. So we can write down a truth table with all these propositional variables and all the disjunctions $P \vee \neg Q \vee \ldots$ etc. that appear in the two propositions.
8. Then we look for a row in the truth table that makes all disjunctions of one proposition true, and make at least one disjunction of the other proposition false. This may take a while, but we can speed up the process by recognizing patterns, using our intuition, etc.
9. Once we find the row we want, that's the truth assignment which gives us a counterexample.
10. We can convert the propositional variables $P, Q$ etc. back to $z \in X, z \notin Y$ etc. to see which ones should be true or false.
11. Then we can assign a value to $z$, say $z = 1$ to construct the sets we need for our counterexample.

For the second part of the question: (Conclude that any set equality that is valid in a domain of size one will be valid in all domains.)

I would say:

1. The above discussion shows that, if a set equality is not valid, then there is a counterexample in a size-1 domain.
2. So, if a set equality is valid in all size-1 domains, then there are no counterexamples in any size-1 domains.
3. So by the contraposition of 1, the set equality is valid.

[sci-42ver]

Thanks for your patient reply. IMHO that is almost same as my solution but with one structured statement.

I'm not sure how your proof z∈A−(B∪C)⟺z∈(A−B)∩(A−C) (last line should have z∈) is relevant... the question is stated "generally". The wrong set equality was just given as an example of a "broader idea".

That is one warm-up to understand the problem. Normally in my notes, I wrote my process of thinking of the problem, so the proof may be informal in some way.