Question

Just need a little help understanding how to do these simple set theory proofs

Answer 1

Questions are here

Answer 2

So i'm thinking we can use x as an element of A and show that it is not equal for a counter-example, but I haven't done a proof for these before

Answer 3

\(\overline{A-B} = \overline{A}-\overline{B}\)

Counterexample :
U = {1, 2, 3}
A = {1, 2}
B = {2, 3}

\(\overline{A-B}=?\)
\(\overline{A}-\overline{B}=?\)

Answer 4

So one would be:
A' - B' = {3}?

Answer 5

and (A - B)' = {2,3}

Answer 6

I'm not sure about the first one

Answer 7

{3} is not the same set as {2, 3}

so first statement is false

Answer 8

oh yeah, I see that

Answer 9

so when proving we can use the same method?

Answer 10

Counterexample is for disproving a statement

Answer 11

like in the next one A-B = {1} and B'-A' = {1} is not a valid proof?

Answer 12

We need to use other techniques for proving

Answer 13

Showing one example for which the statement is true is NOT a proof.

Answer 14

Alright

Answer 15

Has to hold for all cases right?

Answer 16

But, Showing one COUNTER example for which the statement is NOT true is sufficient for disproving.

Answer 17

So, we are good with part a proof.
We have proved that the given statement does not hold by providing a counterexample

Answer 18

Any ideas on part b ?

Answer 19

can we use laws of logic? like go LHS = RHS?

Answer 20

Yes, recall below relationship :

\[A-B = A\cap \overline{B}\]

Answer 21

okay so we have to make that look like B' ^ A?

Answer 22

Oh sorry, you said that

Answer 23

\[A-B = A\cap \overline{B}\tag{1}\]

\[\overline{B}-\overline{A} = \overline{B} \cap \overline{\overline{A} } = \overline{B} \cap A\tag{2} \]

Answer 24

from (1) and (2), can we conclude
\(A-B = \overline{B}-\overline{A}\) ?

Answer 25

yes

Answer 26

Okie got it :)

Answer 27

For the second group can we use the same type of counter example?

Answer 28

For the second group, part a looks like a correct statement

Answer 29

So logic laws again?

Answer 30

Kind of looks like a distributive law

Answer 31

yeah lets do part b first because it is easy

Answer 32

alrighty

Answer 33

part b :
\(C\cup (A-B) =(C\cup A)-(C\cup B)\)

Counterexample :
U = {1, 2, 3,4}
A = {1, 2}
B = {1, 3}
C = {1, 4}

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

Answer 34

first one is = {1,2,4)?

Answer 35

yes

Answer 36

second one is {2}?

Answer 37

Yes, they are not same; so, we're done !

Answer 38

Hooray :D

Answer 39

so the logic law one now

Answer 40

we use the A - B = A ^ B' thing again right?

Answer 41

kind of confused here

Answer 42

Isn't it supposed to be A - B = A union B' ?

Answer 43

not intersection?

Answer 44

Yeah try this :

\[C\cap (A-B) = C\cap (A \cap \overline{B})\tag{1}\]
\[(C\cap A) - (C\cap B) \\= (C\cap A)\cap \overline{ (C\cap B)} \\=(C\cap A)\cap (\overline{C}\cup \overline{B}) \\= [(C\cap A)\cap \overline{C}] \cup [(C\cap A)\cap \overline{B}]\\=[\emptyset ]\cup [(C\cap A)\cap \overline{B}]\\=(C\cap A)\cap \overline{B} \]

Answer 45

what can we conclude from (1) and the last line ?

Answer 46

RHS = LHS

Answer 47

so true, thanks ganeshie