Finite Sets and Inclusion-Exclusion Principle in Set Theory

I am a PhD student of mathematics. I have complete MS in math from the University of Pakistan and have been writing online since 2020.

Finite Sets and Inclusion-Exclusion Principle in Set Theory

1. Finite Sets:

1.1. Definition of Finite Sets:

A set K is said to be finite if K is empty or if K contains exactly finite number of elements h.

1.2. Example:

• The English alphabet's set A of letters and the week's set D of days are both finite sets. A specifically has 26 elements, while D only has 7.

2. Infinite Sets:

2.1. Definition of infinite sets:

A set K is said to be infinite if K contains infinite finite number of elements.

2.2. Examples:

• The rational numbers are infinite.
• The real numbers are infinite.
• Let E be the set of even positive integers, and let I be the unit interval, that is,

E = {2, 4, 6...}

and

I = [0, 1] = {x | 0 ≤ x ≤ 1}
Then both E and I are inﬁnite.

3. Countable Finite Sets:

3.1. Definition of Countable Infinite Sets:

If the elements of a set K can be arranged in a sequence or if K is finite, then the set is said to be countable infinite; if not, the set is said to be uncountable.

3.2. Examples:

• The above set E of even integers are countably inﬁnite,
• The unit interval I = [0, 1] is uncountable because there are infinite numbers between o and 1.
Scroll to Continue

3.3. Counting Elements in Finite Sets:

3.3.1. Notation for Represent of Elements in Set:

The number of elements in a set K can be indicated by the notation n(k) or |k |.

3.3.2. Examples:

• If A is the set is defined for the English alphabets, then number of elements in A can be represented by the notation n (A) = 26
• If D is the set is defined for the days of week, then number of elements in D can be represented by the notation n (D) = 7.
• If K is empty set, then number of elements can be represented in K as,n (∅) = 0

4. Important Results of Finite Sets:

• Suppose G and H are ﬁnite disjoint sets. Then G ∪ H is ﬁnite and

n (G ∪ H) = n(G) + n(H)

• Suppose K is the disjoint union of ﬁnite sets G and H. Then K is ﬁnite and

n(K) = n (G) + n(H)

Proof:

In counting the elements of G ∪ H, ﬁrst count those that are in G. There is n (G) of these. The only other elements of G ∪ H are those that are in H but not in G. But since G and H are disjoint, no element of H is in G, so there are n (H) elements that are in H but not in G. Therefore,

n (G ∪ H) = n (G) + n (H).

For any sets G and H, the set G is the disjoint union of G\H and G ∩ H.

So,

n(K) = n(G) + n(H)

• Let G and H be ﬁnite sets. Then

n(G\H) = n(G) − n (G ∩ H)

5. Inclusion–Exclusion Principle:

Definition of Inclusion–Exclusion Principle:

If sets G and H are not disjoint, there is a formula for n (G ∪ H) known as the Inclusion-Exclusion Principle.

Accordingly:

n (G ∪ H) = n(G) + n(H) − n (G ∩ H)

5.1. Results (Inclusion–Exclusion Principle):

• Suppose G and H are ﬁnite sets. Then G ∪ H and G ∩ H are ﬁnite and

n (G ∪ H) = n(G) + n(H) − n (G ∩ H)

• Suppose G, H and L are ﬁnite sets. Then G ∪ H ∪ L is ﬁnite and

n (G ∪ H ∪ L) = n(G) + n(H) + n(L) − n (G ∩ H) − n (G ∩ L) − n (H ∩ C) + n (G ∩ H ∩ L)

5.2. Example (Inclusion–Exclusion Principle):

Suppose a list G contains the 35 students in a mathematics class, and a list H contains the 60 students in an English class and suppose there are 30 names on both lists. Find the number of students:

(a) Only on list G

(b) only on list H

(c) on list G or H (or both)

Solution:

a) Students in list G are 35 and in list H are 60, hence 35-30 = 5 only in list A.

b) Students in list G are 35 and in list H are 60, hence 60-30 = 30 only in list B.

c) By Inclusion–Exclusion Principle

n (G ∪ H) = n(G) + n(H) − n (G ∩ H)

Number of students are in G = n (G) = 35

Number of students are in H = n (H) = 60

Number of students are common in both lists G and H are = n (G ∩ H) = 30

So,

n (G ∪ H) = n(G) + n(H) − n (G ∩ H)

n (G ∪ H) = 35+60-30

n (G ∪ H) = 65

Hence, the students in list G or H or both are 65.