Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

4.5: Index Sets and Partitions

( \newcommand{\kernel}{\mathrm{null}\,}\)

ni=1Ai and ni=1Ai

The notion of union can be extended to three sets: ABC={xU(xA)(xB)(xC)}. It is obvious how to generalize it to the union of any number of sets. We use a notation that resembles the summation notation to describe such a union: ni=1Ai=A1A2An. We define

ni=1Ai={xU(xA1)(xA2)(xAn)}. It looks messy! Here is a better alternative:

ni=1Ai={xUxAi for someiN, where 1in}.

In a similar manner, ni=1Ai=A1A2An, and we define

ni=1Ai={xUxAi for alliN, where 1in}

In plain English, ni=1Ai is the collection of all elements in the Ai’s, and ni=1An is the collection of all elements common to all Ai’s.

Example 4.5.1

For i=1,2,3,, let Ai=[i,i]. First, construct several Ai for comparison, because it may help us detect any specific pattern. See Figure below.  It is clear that A1A2. Thus, ni=1Ai=[n,n]=An, and ni=1Ai=[1,1]=A1.

hands-on Exercise 4.5.1

Evaluate ni=1Bi and ni=1Bi, where Bi=[0,2i) for iN.

i=1Ai and i=1Ai

It is obvious that we can also extend the upper bound to infinity. i=1Ai=A1A2={xUxAi for someiN},i=1Ai=A1A2={xUxAi for alliN}. In some situations, we may borrow the idea of partial sums from calculus. We first find the union or intersection of the first n sets, then take the limit as n approaches infinity. Thus, if the limit is well-defined, the

i=1Ai=limnni=1Ai,andi=1Ai=limnni=1Ai.

Example 4.5.2

Let Ai=[i,i]. We have learned from the last example that ni=1Ai=[n,n] and ni=1Ai=[1,1]. Hence, i=1Ai=limn[n,n]=(,),andi=1Ai=[1,1]. Recall that we write (,) instead of [,] because ± are not numbers, they are merely symbols representing infinitely large values.

hands-on Exercise 4.5.2

Evaluate i=1Bi and i=1Bi, where Bi=[0,2i).

Example 4.5.3

Let Bi=(0,112i]. Determine i=1Bi and i=1Bi.

Solution

Once again, we have B1B2. It is easy to check that ni=1Bi=Bn=(0,112n],andni=1Bi=B1=(0,12]. It follows that i=1Bi=limn(0,112n]=(0,1),andi=1Bi=(0,12]. Note that limn(0,112n](0,1] because the endpoint 1 does not belong to any Bi.

hands-on Exercise 4.5.3

Let Ci=[0,11i]. Determine i=1Ci and i=1Ci.

Example 4.5.4

Let Di=(11i,1+1i). Determine i=1Di and i=1Di.

Solution

As the value of i increases, the value of 1i decreases. Hence, the left endpoint 11i increases, and the right endpoint 1+1i decreases.

iDi=(11i,1+1i)1(0,2)[6pt]2(12,32)[6pt]3(23,43)[6pt]4(34,54)

clipboard_e3a0fce0d879650deddb9d02cc5d4d8a9.png

It is clear that D1D2D3. Thus, i=1Di=D1=(0,2), and i=1Di={1}.

hands-on exercise 4.5.4

Let Ei=[i,1+1i). Determine i=1Ei and i=1Ei.

hands-on Exercise 4.5.5

For each positive integer i, define Fi={i,i+1,i+2,,3i}. Determine i=1Fi and i=1Fi.

The next two results are obvious.

Theorem 4.5.1

If A1A2A3, then i=1Ai=A1.

Theorem 4.5.2

If A1A2A3, then i=1Ai=A1.

Indexed Family of Sets

How could we describe the union A2A4A6? Well, we can write ievenAi, which means that union of Ai, where i is even. Since the set of even positive integers is denoted by 2N, another way to describe the same union is i2NAi. It means the union all Ai, where i is taken out from the set 2N. Accordingly, i=0Ai=iNAi,andi=0Ai=iNAi. We can even go one step further, by allowing i to be taken from any set of integers, or any set of real numbers, or even any set of objects. The only restriction is that Ai must exist, and its content must somehow depend on i.

In general, given a nonempty set I, if we could associate with each iI a set Ai, we define the indexed family of sets A as A={AiiI}. We call I the index set, and define iIAi={xxAi for someiI},iIAi={xxAi for alliI}. Let us look at a few examples.

Example 4.5.5

To describe the union A1A3A7A11A23, we first define the index set to be I={1,3,7,11,23}, which is the set of all the subscripts used in the union. Now the union can be conveniently described as iIAi.

Example 4.5.6

Consider five sets A1={1,4,23},A2={7,11,23},A3={3,6,9},A4={5,17,22},A5={3,6,23}. Let I={2,5}, then iIAi=A2A5={7,11,23}{3,6,23}={3,6,7,11,23}. Likewise, iIAi=A2A5={7,11,23}{3,6,23}={23}.

hands-on Exercise 4.5.6

Let J={1,4,5}. Evaluate iJAi and iJAi, where Ais are defined in the last example.

hands-on Exercise 4.5.7

An index set could be a set of any objects. For instance, the sets of numbers in the last example could be the favorite Lotto numbers of five different students. We could index these sets according to the names of the students: AJohn={1,4,23},AMary={7,11,23},AJoe={3,6,9},APete={5,17,22},ALucy={3,6,23}. If I={Mary,Joe,Lucy}, what is iI? How would you interpret its physical meaning?

example 4.5.7

Let I={xx is a living human being}, and define Bi={xIx is a child of i},Ai={i}Bi for each iI. Then iIAi=,iIAi=I,iIBi=, and iIBi=I{xx's parents are both deceased}. We leave it as an exercise to verify these unions and intersections.

hands-on Exercise 4.5.8

Verify the intersection and union in the last example.

hands-onExercise 4.5.9

If I represents a set of students, and Ai represents the set of friends of student i, interpret the meaning of iIAi and iIAi.

We close this section with yet another generalization of De Morgan’s laws.

Theorem 4.5.3 Extended De Morgan's laws

For any nonempty index set I, we have ¯iIAi=iI¯Ai, and ¯iIAi=iI¯Ai.

Proof 1

Let x¯iIAi, then xiIAi={xxAi for someiI}. This means xAi for every iI. Hence, x¯Ai for each iI. Consequently, xiI¯Ai. This proves that ¯iIAiiI¯Ai.

Next, let xiI¯Ai. Then x¯Ai for each iI. This means xAi for each iI. Then x{xxAi for someiI}=iIAi. Thus, x¯iIAi, proving that iI¯Ai¯iIAi. We proved earlier that ¯iIAiiI¯Ai. Therefore, the two sets must be equal.
The proof of ¯iIAi=iI¯Ai proceeds in a similar manner, and is left as an exercise.

 

Proof 2

We shall prove ¯iIAi=iI¯Ai. We leave out the explanations for you to fill in: x¯iIAi¯xiIAi¯xAi for some ixAi for all ix¯Ai for all ixiI¯Ai. The proof of ¯iIAi=iI¯Ai is left as an exercise.

Partitions of Sets

Definition: Mutually Disjoint

Sets A1,A2,A3, are mutually disjoint (or pairwise disjoint) if and only if no two sets with distinct subscripts have any elements in common.

Specifically, for all j=1,2,3,

AiAj= whenever ij.

Definition: Partition

A finite or infinite collection of non-empty sets  {A1,A2,A3,} is a partition of set A if and only if

(1) A is the union of all the Ai.

(2) The sets {A1,A2,A3,} are mutually disjoint.

Example 4.5.8

Let S={1,2,3,4,5,6,7,8,9,10}.  Which of the following collections of sets are a partition of set S?

(a) A={A1,A2}  with    A1={1,3,5,7,9},A2={2,4,6,8,10}

(b) B={B1,B2,B3}  with  B1={1,2,3,4,5,6,9},B2={7},B3={8,9,10}

(c) C={C1,C2,C3,C4}  with   C1={8,10},C2={3},C3={1,4,9},C4={2,5,6,7},

(d) D={D1,D2,D3,D4}  with   D1={1},D2={2},D3={3},D4={4},D5={5,6,7,8,9,10},

(e) E={E1,E2}  with   E1={1,3,5,7,9},E2={0,2,4,6,8,10}

(f) F={F1,F2,F3}  with   F1={1,2,3,4},F2={5,6,7},F3={9,10}

Solution

(a), (c) & (d)

Summary and Review

  • When dealing with arbitrary intersection or union of intervals, first identify the endpoints, then analyze the sets involved in the operation to determine whether an endpoint should be included or excluded.
  • Intersection and union can be performed on a group of similar sets identified by subscripts belonging to an index set.
  • Consequently, intersection or union can be formed by naming a specific index set.
  • A collection of sets can be a partition of a set if it satisfies two conditions.

Exercises 

Exercise 4.5.1

For each nZ+, define An=(1n,2n). Find n=1An and n=1An.
 

Answer

n=1An=(0,2), n=1An=(1,).

Exercise 4.5.2

For each nZ+, define Bn={mZn2m3n}. Evaluate n=1Bn and n=1Bn.

Exercise 4.5.3

Define Cn={n,n+1,n+2,,2n+1} for each integer n0. Evaluate n=0Cn and n=0Cn.
 

Answer

n=0Cn=, n=0Cn=N{0}.

Exercise 4.5.4

For each nI={1,2,3,,100}, define Dn=[n,2n]Z. Evaluate nIDn and nIDn.

Exercise 4.5.5

For each nN, define En={n,n+1,n+2,,n2}. Evaluate nNEn and nNEn.
 

Answer

nNEn=E1={1,0,1}, nNEn=Z.

Exercise 4.5.6

For each nN, define Fn={mnmZ}. Evaluate nNFn and nNFn.

Exercise 4.5.7

Let I=(0,1), and define Ai=[1,1i] for each iI. For instance A0.5=[1,2] and Aπ4=[1,4π]. Evaluate iIAi and iIAi.
 

Answer

iIAi=[1,), iIAi={1}.

Exercise 4.5.8

Define I=(0,1), and for each iI, let Bi=(i,1i). Evaluate iIBi=(1,) and iIBi.

Exercise 4.5.9

Evaluate x(1,2)(12x,x2) and x(1,2)(12x,x2).
 

Answer

x(1,2)(12x,x2)=[1,1], x(1,2)(12x,x2)=(3.4).

Exercise 4.5.10

Evaluate x(0,1)(x,1x) and x(0,1)(x,1x).

Exercise 4.5.11

Let the universal set be R2. For each r(0,), define Ar={(x,y)y=rx2}; that is, Ar is the set of points on the parabola y=rx2, where r>0. Evaluate r(0,)Ar and r(0,)Ar.
 

Answer

r(0,)Ar={(0,0)}, r(0,)Ar=R×R+{(0,0)}.

Exercise 4.5.12

Prove that ¯iIAi=iI¯Ai for any nonempty index set I.

Exercise 4.5.13

Let Ai=[1i,5i] for iZ+.
Find:
(a) A1=(b)A3=(c)A6=

Answer

(a) A1=[1,5](b)A3=[13,15](c)A6=[16,30]

Exercise 4.5.14

Let Ai=[1i,5i] for iZ+.
Find:
(a) ni=1Ai=(b)ni=1Ai=

Exercise 4.5.15

Let Bi=(0,1i) for iZ+.
Find:
(a) B1=(b)B3=(c)B6=

Answer

(a) B1=(0,1)(b)B3=(0,13)(c)A6=(0,16)

Exercise 4.5.16

Let Bi=(0,1i) for iZ+.
Find:

(a) ni=1Bi=(b)ni=1Bi=

(c) i=1Bi=(d)i=1Bi=


This page titled 4.5: Index Sets and Partitions is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?