Union of Indexed Families

Operations with sets are the daily bread for many mathematicians, understanding how the equivalences should be demonstrated is fundamental, so let’s demonstrate a few properties.

In the following video I solve a simple but very instructive exercise of basic operations with sets. Remember that after watching the video I wait for you back in the article to continue learning.

As you could see in the video, it is relatively simple to make operations with sets, but to reinforce what we have learned, we will solve now the following problem:

Suppose B is a set, {Ai | i ∈ I } is an indexed family of sets, and I≠∅. Prove that

B ∩ (∪i∈I Ai ) = ∪i∈I (B ∩ Ai ).

Remember that the first step is to find out what are the hypotheses and what are the conclusion of the problem. In this case, the word “Suppose” clearly indicates the hypotheses, while the word “Prove” shows the conclusion.

Hypothesis

B is a set

Ai = { x | i∈I }

≠ 

Conclusion

B (iI Ai ) = ∪iI (B Ai )

Once we have identified the conclusion, we must ask us how we should demonstrate it. As we have to show that two sets are equal, we must remember the axiom of extensionality – remember that the axioms are always taken as true – which says the following:

Axiom of Extensionality

Two sets are equal if and only if they have the same elements.

That is, we have to prove that each element of one set is an element of the other set. Or as we saw in the video, that each set is a subset of the other. The rewritten conclusion would look like this.

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

Conclusion

B ∩ (∪i∈I Ai ) ⊆ ∪i∈I (B ∩ Ai )

i∈I (B ∩ Ai ) ⊆B ∩ (∪i∈I Ai )

If we can prove both conclusions, we will have proven that the sets are equal and the problem will be solved.


Let’s start by demonstrating the first conclusion.

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

Conclusion

B ∩ (∪i∈I Ai ) ⊆ ∪i∈I (B ∩ Ai )

For this, we will remember the definition of subset, which says the following:

Definition of Subset

A is a subset of B if and only if every element of A is an element of B.

Formally:

A⊆B ↔ ∀x( x∈A → x∈B )

So we have to prove that every element of B ∩ (∪i∈I Ai ) is an element of i∈I (B ∩ Ai ). Rewriting the above we would have:

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

Conclusion

∀x( x∈B∩(∪i∈I Ai ) → x∈∪i∈I(B ∩ Ai) )

And finally we have a logical structure in our conclusion, in this case it is a universal quantifier. It will be very useful to remember the correct way to demonstrate this structure.

To prove a conclusion of the form ∀xP(x):

1. Introduce an arbitrary element “x” to the hypotheses.

2. Prove that the proposition P(x) holds for this arbitrary element.

3. Once P(x) has been demonstrated for the arbitrary “x”, you can conclude that P(x) is true for every element in the universe.

Notice how in this case the proposition P(x) is ( x∈B∩(∪i∈I Ai ) → x∈∪i∈I(B∩Ai) )

Once the first step of the previous table has been completed, we would have the following:

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

Conclusion

 x∈B∩(∪i∈I Ai ) → x∈∪i∈I(B ∩ Ai)

What follows now is to prove P(x), that is, we have to prove the conditional that is in our conclusion. Recall also the correct way to prove a conditional.

To prove a conclusion of the form P → Q

1. Turn proposition P into hypothesis and proposition Q into your new conclusion.

2. Prove proposition Q using the hypotheses (in which P is included).

3. Once Q is demonstrated, you can conclude that the statement P → Q is true.

Making the first step of the strategy to prove conditionals, we would have the following:

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

x∈B∩(∪i∈I Ai )

Conclusion

 x∈∪i∈I(B ∩ Ai)

So now we have to prove that x∈∪i∈I(B∩Ai), and for that we need to remember what that expression means. We have to remember the definition of union for an indexed family.
Remember that a family of sets is simply a set whose elements are other sets. An indexed family is a family of sets, with the only difference that an index is placed on the elements of the indexed family. I show you an example.

F = { {1,2}, {2,3} } is a family.

{ Ai | i∈I }, I={1,2}, Ai={ i, i+1 } is an indexed family.

Notice how the family F and the indexed family are equal, they are only expressed in different ways.

In this case, A1={1,2}, A2={2,3},   { Ai | i∈I } = { A1, A2 } = { {1,2}, {2,3} } = F

Now let’s define the union for an indexed family.

Definition of Union for an Indexed Family of Sets

Let {Ai | i∈I} an indexed family of sets, the union of the family is denoted  ∪i∈I Ai and is defined as:

(iI Ai ) = { x | ∃i∈I(x∈Ai) }

That is, the union of an indexed family will be the set of all “x” such that “xbelongs to at least one set within the family.
We have to prove (see conclusion above) that x∈∪i∈IB∩Ai, and according to the definition of union, we have to prove that ∃i∈I(x∈B∩Ai).

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

x∈B∩(∪i∈I Ai )

Conclusion

∃i∈I(x∈B∩Ai)

And now that we know exactly what we have to prove, let’s use the hypotheses to solve the problem. We see that the first four hypotheses are not so relevant, the key is in the last proposition, which says that x∈B∩(∪i∈I Ai).

Since x belongs to the intersection of two sets, x belongs to both sets. So we have:

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

x∈B

x(∪i∈I Ai )

Conclusion

∃i∈I(x∈B∩Ai)

And now our last proposition shows us a union of family again. At this point we can easily understand this expression and write …

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

x∈B

∃i∈I(x∈Ai)

Conclusion

∃i∈I(x∈B∩Ai)

If this last step was difficult for you, review the definition of union of family again.

Now we have the hypothesis “∃i∈I (x∈ Ai)” and remember that whenever we have an existential quantifier in the hypotheses, we can introduce an element with the property stated in the proposition.

That is, we can enter an element j, where j∈I and x∈Aj. So we have …

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

x∈B

j∈I

x∈Aj

Conclusion

∃i∈I(x∈B∩Ai)

And we have worked our hypotheses properly, now let’s look for ways to prove our conclusion. We have to propose an element that complies with the conclusion, that is:

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

x∈B

j∈I

x∈Aj

i=…

Conclusion

i∈I

x∈B∩Ai

And rewriting the last conclusion using the definition of intersection, it would look like this

Hypothesis

B is a set

{Ai | i∈I } is an indexed family

I ≠∅

x arbitrary

x∈B

j∈I

x∈Aj

i=…

Conclusion

i∈I

x∈B

xAi

If we can give a value to i that fulfill all three conclusions, we will have solved the problem.

In this case the solution is very simple because the only variable that could work is j. If we do i = j, we see that it is clearly fulfilled (see hypotheses) that i∈I, x∈B and that x∈Ai.

Once our conclusions are resolved, we can write the final proof, which would look like this:

Proof of: B ∩ (∪i∈I Ai) ⊆ x∈ ∪i∈I (B ∩ Ai)

Let x be an arbitrary element, suppose that x∈B∩(∪i∈IAi). So that x∈B and x∈ (∪i∈I Ai), therefore, we can choose j∈I such that x∈Aj. Since x∈B and x∈ Aj, x∈B∩ Aj, so that x∈ ∪i∈I (B ∩ Ai). Therfore, if x∈B ∩ (∪i∈I Ai), then x∈ ∪i∈I (B ∩ Ai). And since the element x was arbitrary, B ∩ (∪i∈I Ai) ⊆ x∈ ∪i∈I (B ∩ Ai).

And we have solved half of the problem, if you still think that you need to practice these concepts a little more, try to prove the rest of the problem, that is, show that:

 

i∈I (B ∩ Ai ) ⊆ B ∩ (∪i∈I Ai)

You have to follow exactly the same strategies, obviously making small adjustments. Here is the final proof in case you want to confirm your results.

Proof of: ∪i∈I (B ∩ Ai) ⊆ B ∩ (∪i∈I Ai)

Let x be an arbitrary element, suppose x∈∪i∈I(B ∩ Ai). So we can choose j∈I such that x∈B∩Aj, this means that x∈B and x∈Aj, since x∈Aj, x∈∪i∈I Ai
so x∈ B∩(∪i∈ I Ai). Therefore, if x∈∪i∈I(B∩Ai), then x∈B∩(∪i∈I Ai). Since the element x was arbitrary, i∈I(B∩Ai) ⊆ B∩(∪i∈I Ai).

And now that we have proved that i∈I(B∩Ai) ⊆ B∩(∪i∈IAi) and that B∩(∪i∈IAi) ⊆ ∪i∈I (B∩Ai), we can conclude that B∩(∪i∈I Ai) = ∪i∈I(B∩Ai), as required.

I hope these problems have helped you to understand a little more the incredible set theory, if you have any questions write it in the comments of my YouTube channel.

We are done for today, I hope you have an excellent day and that you continue to enjoy mathematics.

Big hug and see you soon!