I’m learning for a test and I think there will be some task similar to this one. I’d like to know if I did it correct and if not can you please say how to do it correctly?

Let Ω\Omega be a set, let II be an index-set and let A⊆ΩA \subseteq

\Omega and Ai⊆ΩA_{i} \subseteq \Omega for all i∈Ii \in I.

Show that (⋃i∈IAi)c=⋂i∈IAic\left(\bigcup_{i \in I}A_{i}\right )^{c}=\bigcap_{i \in

I}{A_{i}}^{c}

We defined this in our readings:

Complement: Ac≡ˉA={x∈Ω;(x∉A)}A^{c} \equiv \bar{A}= \left\{x \in \Omega; (x \notin A)\right\}

and ¯⋃i∈IAi=⋂i∈I¯Ai\overline{\bigcup_{i \in I}A_{i}}=\bigcap_{i \in

I}\overline{A_{i}}

I did it like this:

(⋃i∈IAi)c=¯⋃i∈IAi=⋂i∈I¯Ai=⋃i∈IAic\left(\bigcup_{i \in I}A_{i}\right)^{c}=\overline{\bigcup_{i \in I}A_{i}}=\bigcap_{i \in

I}\overline{A_{i}}=\bigcup_{i \in I}{A_{i}}^{c}

=================

The first image you inserted, ¯⋃iâˆˆIAi=⋂iâˆˆI¯Ai\overline{\bigcup_{iâˆˆI} A_i} = \bigcap_{i âˆˆ I} \overline{A_i} â€“ is that really supposed to be a definition? Or is that a proposition already proved in your readings? It would be really weird if that was a definition. If itâ€™s not, my guess is that you are supposed to produce or reproduce the proof of that proposition, so you cannot use it itself in doing so. The task certainly is not supposed to be to merely recognise AcA^c and ¯A\overline A as being diferent notations for the same thing.

– k.stm

2 days ago

It wasn’t proved but our professor wrote it exactly like that on the table and he said what we had in readings is allowed to be used. So I just used it 😛 How would you do it if it wasn’t allowed? Is it possible?

– cnmesr

2 days ago

Sure it is. I propose you give it a try to explicitly prove the proposition. And a little advice: Commit to one of the notations, either AcA^c or ¯A\overline A, for set-theoretic complements. Otherwise, you might confuse yourself and your writing becomes less clear. If you canâ€™t manage to prove it yourself, look up â€œde Morganâ€™s lawsâ€.

– k.stm

2 days ago

Please note that in the linked duplicate, C(∗)C(*) is taken to mean (∗)c(*)^c. I reopened the question after adding the tag “proof verification”, since your question is not asking “how” to prove it, but rather verification of your work.

– amWhy

2 days ago

See also this post and other questions linked there

– Martin Sleziak

2 days ago

=================

4 Answers

4

=================

Here is a basic beginner’s guide on how to solve this question.

So you want to show (∪i∈IAi)c=∩i∈IAci(\cup_{i\in I} A_{i})^{c} = \cap_{i \in I} A_{i}^{c}.

Notice that the thing on either side of the == is a set. So you are trying to show two sets are equal. If you want to show B=CB = C for sets BB and CC, the standard way to approach this is to show B⊆CB \subseteq C and C⊆BC \subseteq B. If you show they are subsets of each other, then that’s good enough to show they are equal.

Okay, so we need to show then two statements:

(∪i∈IAi)c⊆∩i∈IAci(\cup_{i\in I} A_{i})^{c} \subseteq \cap_{i \in I} A_{i}^{c}

∩i∈IAci⊆(∪i∈IAi)c\cap_{i \in I} A_{i}^{c} \subseteq (\cup_{i\in I} A_{i})^{c}.

I’ll show you how to do 1, and you will have to do 2 yourself, but the way to do 2 is very similar to the way to do 1 so if you understand what I’m about to say, then you’ll be able to do 2. Feel free to ask me questions in the comments about your attempt.

Okay, so I want to prove (∪i∈IAi)c⊆∩i∈IAci(\cup_{i\in I} A_{i})^{c} \subseteq \cap_{i \in I} A_{i}^{c}. To show this, I will need to let xx be any element of the left hand side (∪i∈IAi)c(\cup_{i\in I} A_{i})^{c}, and I will need to show it is in the right hand side ∩i∈IAci\cap_{i \in I} A_{i}^{c}.

Alright, then let x∈(∪i∈IAi)cx \in (\cup_{i\in I} A_{i})^{c} be any arbitrary element. To show it is in ∩i∈IAci\cap_{i \in I} A_{i}^{c}, let’s start by inspecting what it means for xx to be in (∪i∈IAi)c(\cup_{i\in I} A_{i})^{c}.

Since x∈(∪i∈IAi)cx \in (\cup_{i\in I} A_{i})^{c}, that means xx is not in ∪i∈IAi\cup_{i\in I} A_{i}. Okay, but if xx is not in that union, then that means it is not in any AiA_{i} for any ii (since if it was on one of them, it would be in the union). But if xx is not in AiA_{i} for any ii, then that means xx is in AciA_{i}^{c} for every ii. But if x∈Acix \in A_{i}^{c} for every ii, then that means x∈∩i∈IAcix \in \cap_{i \in I} A_{i}^{c}. But this is what we wanted to show! So we are done with this part.

Now you have to prove statement 2. If you have any questions, feel free to ask me in the comments.

Let x∈⋂i∈IAci⇒xx \in \bigcap_{i \in I} A_{i}^{c} \Rightarrow x isn’t in AiA_{i} but could be because of ⋂i∈I\bigcap_{i \in I}. For the right side, xx cannot be in ⋃i∈IAi\bigcup_{i \in I}A_{i} and if we now take its intersection, it won’t be in any AiA_{i} again because left side it’s not in AiA_{i} and right side it’s not in AiA_{i} either. ?

– cnmesr

2 days ago

@cnmesr So if I understand your first sentence, then the idea in the first sentence is right. If x∈∩i∈IAcix \in \cap_{i \in I} A_{i}^{c}, then xx is in AciA_{i}^{c} for every ii, since that’s what intersection means, right? That means xx is not in AiA_{i} for any ii, since it is in the complement for every ii. But if xx is not in AiA_{i} for any ii, what does that tell you about xx and the set ∪i∈IAi\cup_{i \in I} A_{i}? Is xx in this set or not?

– user46944

2 days ago

xx is not in the set ⋃i∈IAi\bigcup_{i \in I}A_{i}

– cnmesr

2 days ago

..and because on both sides x is not in AiA_{i} for every ii we get true statement?

– cnmesr

2 days ago

@cnmesr Your first comment is right, xx is not in ∪i∈IAi\cup_{i \in I} A_{i}, so that means x∈(∪i∈IAi)cx \in (\cup_{i \in I} A_{i})^{c}.

– user46944

2 days ago

Ok, let’s make things a little more clear: you have a set Ω\Omega and a family of subsets of Ω\Omega indexed by II: {Ai}i∈I\{A_i\}_{i\in I}.

You want to prove that (⋃i∈IAi)c=⋂i∈IAci\left(\bigcup_{i\in I}A_i\right)^c=\bigcap_{i\in I}A_i^c.

You don’t actually need any other A⊆ΩA\subseteq \Omega, I think…

Let’s introduce some notation: U:=⋃i∈IAiU:=\bigcup_{i\in I}A_i, V:=⋂i∈IAciV:=\bigcap_{i\in I}A_i^c. Thus, the claim is that Uc=WU^c=W.

We say that x∈Ucx\in U^c iff x∉Ux\notin U, i.e., if x∉Aix\notin A_i, for every i∈Ii\in I (from the fact that y∈Uy\in U if there is some i0∈Ii_0\in I – not nec. unique – such that y∈Ai0y\in A_{i_0}; recall then how quantifiers behave under negation). This means exactly that x∈Acix\in A_i^c for every i∈Ii\in I, thus, by definition of the intersection, you get x∈Vx\in V. Hence: U⊆VU\subseteq V. Every implication is actually an equivalence (an iff), thus V⊆UV\subseteq U, too.

What you did is correct. But since you asked in a comment how to prove the result without using the proposition provided by your professor (which does all the work for you!), you can do it as follows. You should prove that the elements of (⋃i∈IAi)c\left(\bigcup_{i \in I}A_{i}\right )^{c} are precisely the elements of ⋂i∈IAic\bigcap_{i \in I}{A_{i}}^{c}, because in that case the sets are equal. So you can start by saying suppose that x∈(⋃i∈IAi)cx\in \left(\bigcup_{i \in I}A_{i}\right )^{c}, and then you will have to show that xx is also an element of ⋂i∈IAic\bigcap_{i \in

I}{A_{i}}^{c}. And after that you have the do the same in the opposite direction. I’ll show how to do one direction. Then you can try the other one yourself.

So we start by saying suppose that x∈(⋃i∈IAi)cx\in \left(\bigcup_{i \in I}A_{i}\right )^{c}. This means by definition that x≠⋃i∈IAix\neq \bigcup_{i \in I}A_{i}. We have, also by definition, that

⋃i∈IAi={x∈Ω:x∈Ai for some i∈I}\bigcup_{i \in I}A_{i} = \{x\in \Omega:x\in A_i\text{ for some }i\in I\} and since xx is not an element of this set, there can be no AiA_i that contains xx (for otherwise xx would be an element of the set). Therefore, for all ii we have that x∉Aix\notin A_i, which, by definition, means that x∈Aicx\in A_i{}^c for all ii. Now, since, again by definition,

⋂i∈IAic={x∈Ω:x∉Ai for all i∈I}\bigcap_{i \in I}{A_{i}}^{c} = \{x\in\Omega : x\notin A_i \text{ for all } i\in I\}

it follows that x∈⋂i∈IAicx\in \bigcap_{i \in I}{A_{i}}^{c}.

So we have now proved that all elements of (⋃i∈IAi)c\left(\bigcup_{i \in I}A_{i}\right )^{c} are also elements of ⋂i∈IAic\bigcap_{i \in I}{A_{i}}^{c}. If you can now show that the opposite statement also holds, then you have proven that the sets are equal. This second part of the proof is very similar to the part that I have shown you, so it would be a good exercise to try it yourself.

By definition we have ⋃i∈IAi={x∈Ω:∃i∈I(x∈Ai)}\bigcup_{i \in I}A_{i}=\{x\in\Omega:\exists i\in I(x\in A_i)\}

and ⋂i∈IAci={x∈Ω:∀i∈I(x∉Ai)}\bigcap_{i \in I}{A_{i}^c}=\{x\in\Omega:\forall i\in I(x\notin A_i)\}

By the definition of equality of sets we have (⋃i∈IAi)c=⋂i∈IAic\left(\bigcup_{i \in I}A_{i}\right )^{c}=\bigcap_{i \in I}{A_{i}}^{c} if and only if (⋃i∈IAi)c⊆⋂i∈IAic and ⋂i∈IAic⊆(⋃i∈IAi)c\left(\bigcup_{i \in I}A_{i}\right )^{c}\subseteq\bigcap_{i \in

I}{A_{i}}^{c} \text{ and }\bigcap_{i \in

I}{A_{i}}^{c}\subseteq\left(\bigcup_{i \in I}A_{i}\right )^{c}

Let x∈(⋃i∈IAi)cx\in\left(\bigcup_{i \in I}A_{i}\right )^{c}. By the defintion of compliment of a set we have x∉⋃i∈IAix\notin \bigcup_{i \in I}A_{i}. Since x∉⋃i∈IAix\notin \bigcup_{i \in I}A_{i}, by the definition of ⋃i∈IAi\bigcup_{i \in I}A_{i} and the axiom of specification we have x∈Ωx\in\Omega and x∉Aix\notin A_i for all i∈Ii\in I. Since x∈Ωx\in\Omega and x∉Aix\notin A_i for any i∈Ii\in I, we have x∈Ωx\in\Omega and x∈Acix\in A_i^c for all i∈Ii\in I. Therefore by the definition of ⋂i∈IAic\bigcap_{i \in

I}{A_{i}}^{c} we have x∈⋂i∈IAicx\in\bigcap_{i \in

I}{A_{i}}^{c}. We thus have x∈⋂i∈IAicx\in\bigcap_{i \in

I}{A_{i}}^{c} whenever x∈(⋃i∈IAi)cx\in\left(\bigcup_{i \in I}A_{i}\right )^{c}. Hence (⋃i∈IAi)c⊆⋂i∈IAic\left(\bigcup_{i \in I}A_{i}\right )^{c}\subseteq\bigcap_{i \in

I}{A_{i}}^{c}.

Now suppose conversely that we have x∈⋂i∈IAicx\in\bigcap_{i \in

I}{A_{i}}^{c}. By the definition of ⋂i∈IAic\bigcap_{i \in

I}{A_{i}}^{c} we have x∈Ωx\in\Omega and x∈Acix\in A_i^c for all i∈Ii\in I. In other words, we have x∈Ωx\in \Omega and x∉Aix\notin A_i for any i∈Ii\in I. Again using the axiom of specification and the definition of ⋃i∈IAi\bigcup_{i \in I}A_{i} we have x∉⋃i∈IAix\notin\bigcup_{i \in I}A_{i}. Since x∉⋃i∈IAix\notin\bigcup_{i \in I}A_{i}, we have x∈(⋃i∈IAi)cx\in\left(\bigcup_{i \in I}A_{i}\right )^{c}. Since x∈(⋃i∈IAi)cx\in\left(\bigcup_{i \in I}A_{i}\right )^{c} whenever x∈⋂i∈IAicx\in\bigcap_{i \in I}{A_{i}}^{c}, we have ⋂i∈IAic⊆(⋃i∈IAi)c\bigcap_{i \in

I}{A_{i}}^{c}\subseteq\left(\bigcup_{i \in I}A_{i}\right )^{c}.

Since (⋃i∈IAi)c⊆⋂i∈IAic\left(\displaystyle\bigcup_{i \in I}A_{i}\right )^{c}\subseteq\displaystyle\bigcap_{i \in

I}{A_{i}}^{c} and ⋂i∈IAic⊆(⋃i∈IAi)c\displaystyle\bigcap_{i \in

I}{A_{i}}^{c}\subseteq\left(\displaystyle\bigcup_{i \in I}A_{i}\right )^{c}, we have \left(\displaystyle\bigcup_{i \in I}A_{i}\right )^{c}=\displaystyle\bigcap_{i \in I}{A_{i}}^{c}\left(\displaystyle\bigcup_{i \in I}A_{i}\right )^{c}=\displaystyle\bigcap_{i \in I}{A_{i}}^{c}.