Stuck solving algebraic proof

K

kory

Junior Member
Joined
Mar 8, 2021
Messages
66
I'm trying to solve an Algebraic proof by using set identities. I'm not sure if I should have started off using the Double Complement Law so early, but it seemed like the only logical solution. Maybe someone else has a better solution.

For all sets A & B:
[MATH] (A^c \cup B^c)^c \cup (A \cap B^c) = A [/MATH]
So far I have:
[MATH](A^c \cup B^c)^c \cup (A \cap B^c)=(A^c[/MATH][MATH]^c \cap B^c[/MATH][MATH]^c)[/MATH][MATH]\cup (A \cap B^c)[/MATH] using DeMorgan's Law
[MATH]=(A \cap B) \cup (A \cap B^c)[/MATH] using Double Complement Law

I need to get to
[MATH]=(A^c)[/MATH][MATH]^c[/MATH] Double Complement Law
[MATH]A[/MATH]
or
[MATH]=(A^c[/MATH][MATH]^c)[/MATH] Double Complement Law
[MATH]A[/MATH]
 
what law allows you do combine the two Bs like that at [MATH]A \cap (B \cup B ^c) [/MATH] ?
how did you get rid of the [MATH] ^c[/MATH]and why didnt you use [MATH]A \cap (A \cup B) [/MATH] to get to [MATH]A[/MATH] instead?
 
1618592915263.png

Not sure what you mean by the last two questions.

[MATH](A \cap B) \cup (A \cap B^c)[/MATH][MATH]=A \cap (B \cup B^c)\quad[/MATH][MATH]=A \cap \mathbb{U}[/MATH][MATH]=A[/MATH]
Note [MATH]B \cup B^c[/MATH] contains every element in the universe, because every element is either in B or it is not in B (in the complement of B)
I.e. the Universe [MATH]\mathbb{U} \subseteq (B \cup B^c)[/MATH] and by definition [MATH](B \cup B^c) \subseteq \mathbb{U}\quad \therefore (B \cup B^c)=\mathbb{U}[/MATH]Every set A is a subset of the Universe, [MATH]A \subseteq \mathbb{U}[/MATH] therefore [MATH]A \cap \mathbb{U} = A[/MATH]
 
Ok, I think i'm starting to get it. It's the C's in the Associative Law and Distributive Law that throw me off when working with only As and Bs
 
Yes, those letters can stand for anything. In the distributive law, I am taking C to be [MATH] B^c[/MATH]
 
Can you take a look at another proof that I've been working on to see if I'm on the right path?

Prove the following statement using an Element Proof:
For all sets [MATH]A,B,[/MATH] and [math]C[/math],
if [MATH]A \subseteq B[/MATH] [math] and[/math] [math] A \subseteq C[/math] then [math]A \subseteq B \cap C [/math]
My proof:
Suppose that A, B, and C are particular but arbitrarily chosen sets such that [math] A \subseteq B[/math] and [math] A \subseteq C[/math]since [math] A \subseteq B[/math] then [math]x \in A[/math] and [math]x \in B[/math]since [math] A \subseteq C[/math] then [math]x \in A[/math] and [math]x \in C[/math]By definition of intersection, [math]x \in B \cap C \to x \in B[/math] and [math]x \in C[/math]therefor, By Transitivity [math] x \in A \land x \in C \to A \subseteq B \cap C[/math]
what do you think?
 
A few points:
"since [math] A \subseteq B[/math] then [math]x \in A[/math] and [math]x \in B[/math]"
You haven't said what x is.
"By definition of intersection, [math]x \in B \cap C \to x \in B[/math] and [math]x \in C[/math]"
We are interested in using the implication the other way around. We want to show that something belongs to [MATH]B \cap C[/MATH]"therefor, By Transitivity [math] x \in A \land x \in C \to A \subseteq B \cap C[/math]"
Not sure what you meant by that.

Prove:
For all sets [MATH]A,B,[/MATH] and [math]C[/math]if [MATH]A \subseteq B[/MATH] and [math] A \subseteq C[/math] then [math]A \subseteq B \cap C [/math]
Proof
1. If [MATH]A=\emptyset[/MATH], then trivially [math]A \subseteq B \cap C [/math] (the empty set is a subset of all sets, so certainly is a subset of [MATH]B \cap C[/MATH]).
2. [MATH]A≠\emptyset[/MATH], then [MATH]\exists \,x \in A[/MATH](Now restate the problem in terms of elements)
[MATH]\boxed{\text{We want to prove:}\\ \text{given that } A \subseteq B \text{ and } A \subseteq C \text{, then } \forall x \in A,\; x \in B \cap C}[/MATH][MATH]A \subseteq B[/MATH] and [math] A \subseteq C[/math]Consider arbitrary [MATH]x \in A[/MATH], then [MATH] A \subseteq B \rightarrow x \in B[/MATH] [MATH] \qquad \qquad \qquad \qquad \qquad \text{ and } A \subseteq C \rightarrow x \in C[/MATH][MATH]\therefore x \in B \land x \in C[/MATH][MATH]\rightarrow x \in B \cap C \qquad [/MATH] (definition of intersection)
So, [MATH]x \in A \rightarrow x \in B \cap C[/MATH]i.e. [MATH]A \subseteq B \cap C[/MATH]
 
Just when I think I'm getting it, you throw me right back to the drawing table...
 
You must log in or register to reply here.
Top