# 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

## 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.

**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.