Set Theory Concepts relevant to probability

What is a Set?

A set is a collection of distinct objects considered as a whole. An object can be anything that is conceivable in the mind.

Each object belonging to a set is called an "element" of the set.

For a group of objects to form a set, it should be possible to verify whether a given object belongs or not belongs to the group.

• {1, 2, 3, 4, 5, ... ∞ }
• {Cat, Dog, Horse, Bull, Tiger}
• {α, β, ♥, γ, ε ♣ }

Denoting a Set

Sets are generally denoted using the Capital Letters of English/Greek alphabets.
• A = {1, 2, 3, 4, 5, ... ∞ }
• Ω = {Cat, Dog, Horse, Bull, Tiger}
• M = {α, β, ♥, γ, ε ♣ }

Elements of a Set and their order

Element : A small part of the total whole.

By an element of the set, we mean each distinct object of the set. They are also called the members of the set.

Any identifiable entity may form the element of a set.
[Numbers, Letters, Points, Birds, Symbols, Things, Equations, Persons etc.]

A set can also form an element of another set.

• N = { {1, 2, 3, ... 10} , {11, 12, 13, ... 20}, {21, 22, 23, ... 30} }

Order of Elements

The elements of the set may be listed in any order. The only thing that matters is "What are the elements?".

Defining/Describing a set

Intensional/Implicit Definition

Such a definition of a set involves defining the set in terms of the necessary and sufficient conditions required to be satisfied for an element to belong to the set.
• "A" is the set of all even numbers divisible by 4.
Commonly written as A = {Even numbers divisible by 4}
• "M" is the set of all models of cars in a city
(Or) M = {Models of cars in a city}
• G is the set of all democratic countries in South Asia
(Or) G = {Democratic countries in South Asia}

The braces "{ }" replace the words "The set of all".

Set Builder Notation

This involves using a variable to represent the elements of the set along with the necessary and sufficient conditions required to be satisfied for an element to belong to the set.
• P = { x : x Z, − 100 ≤ x ≤ 100 and x ÷ 5}
[The symbol ":" is read "such that"]
• V = { x2 − 3x + 4 | x N, x ≤ 12}
[The symbol "|" is read "such that"]

Extensional/Explicit/Enumerative Definition

Such a definition of a set involves listing out all the elements that belong to that set. Such a description/definition of the set is possible/practical only where the elements of the set are finite/small.
• "M" = {Toyota Corolla, Honda City, Benz C Class, Tata Indigo, Maruthi Baleno}
• "G" = {India, Pakistan, Sri Lanka, Pakistan, Maldives}

Ostensive/Abbreviated Definition

Such a definition of a set involves listing out only some of the elements of the set (but not all) to create an understanding on the nature of the elements within the set.
• "A" = {2, 4, 6, 8, ... }
• "T" = {5, 10, 15, ... 245, 250}

Belonging and Not Belonging to a Set

The elements which satisfy the necessary and sufficient conditions in relation to a set are said to belong to the set and those that do not satisfy the conditions are said to be not belonging to the set.

Where A = {Even numbers less than 50 divisible by 4}

• 16 A
[Read as 16 belongs to set A]
• 35 A
[Read as 35 does not belong to set A]

Cardinality of a Set

The cardinality of a set is a numerical figure that represents the number of elements in the set.

It is represented with the name of the set included within two vertical bars as "|D|" (Or) within parentheses following n as "n(D)" indicating the number of elements in the set "D".

• A = {5, 10, 15, 20, ... , 245, 250}
⇒ n(A) = 50 (Or) |A| = 50
• Ω = {α, β, ♥, γ, ε ♣ }
⇒ n(Ω) = 6 (Or) |Ω| = 6
• M = {a, e, i, o, u};
⇒ n(M) = 5 (Or) |M| = 5
• B = {a, b, c, d, e, f, ...., w, x, y, z}
⇒ n(B) = 26 (Or) |B| = 26
• N = {1, 2, 3, ....}
⇒ n(N) = ℵ0 (read aleph nought) (Or) |N| = ℵ0
• A ∪ B = {1, 2, 3, 4, 5, 6, 8, 10}
⇒ n(A ∪ B) = 8 (Or) |A ∪ B| = 8
• K ∩ L ∩ M = {a, o}
⇒ n(K ∩ L ∩ M) = 2 (Or) |K ∩ L ∩ M| = 2
• B − A = {b, c, d, f}
⇒ n(B − A) = 4 (Or) |B − A| = 4
• F = { {1, 2, 3, ... 10} , {11, 12, 13, ... 20}, {21, 22, 23, ... 30} }
⇒ n(F) = 3 (Or) |F| = 3

Each element of the set F is a set.
Since there are three sets which form elements of the set F, the cardinality of set F is 3.
The elements of those sets should not be counted in finding the cardinality of F.

Empty/Null Set

A set whose cardinality is Zero i.e. a set without any elements is an empty or null set.

It is represented as {} or by the symbol Φ

M = {Odd number divisible by 2} ⇒ M = Φ (Or) M = {}

M = Φ ≠ M = {Φ}

Whereas M = Φ represents a Null set, M = {Φ} is a set with only one element Φ

This can be better understood if they are represented as M = {} and M = {Φ}

Sets with infinite Cardinality

To express the cardinality for a set, the number of elements in the set should be countable.

We use the term ∞ to express the boundaries of of some common number sets.

• Set of Natural numbers, N = {1, 2, 3, ... ∞ }
• Set of Whole numbers, W = {0, 1, 2, 3, ... ∞ }
• Set of Integers, Z = {− ∞, ... − 3, − 2, − 1, 0, 1, 2, 3, ... ∞ }
• Set of Real Numbers, R = {− ∞, ... − 2, − 3/2, − 1, 0, 1, 3/2, 2, ... ∞ }

The infinite (∞) symbol here is used to define the boundaries and not the infiniteness of the cardinality of these sets.

Finite, Countably infinite, Uncountable

The Cardinality of the set of Natural numbers is represented by ℵ0 (read aleph null).

Finite sets

Any set with a cardinality less than the cardinality of the set of Natural numbers is a finite set.

A set P is said to be finite if n(P) < n(N) or |P| ℵ0

Countably infinite sets

Any set with a cardinality equal to the cardinality of the set of Natural numbers is a countably infinite set.

A set M is said to be infinite if |M| = n(N) or n(M) = ℵ0

uncountable sets

Any set with a cardinality greater than the cardinality of the set of Natural numbers is said to be an uncountable set.

A set S is said to be uncountable if n(S) > |N| or |S| > ℵ0

continuum
Real numbers set is also called continuum. The Cardinality of the continuum, represented by C, is greater than the cardinality of the natural number set i.e. C > ℵ0

Union of sets

The union of two or more sets is the set whose elements are all the elements that belong to any of the sets, but nothing else.

The symbol is used to indicate union.

1. A = {1, 2, 3, 4, 5}; B = {2, 4, 6, 8, 10}

A ∪ B = {x / x ∈ A or x ∈ B}
⇒ A ∪ B = {1, 2, 3, 4, 5, 6, 8, 10}

2. K = {a, e, i, o, u}; L = {a, b, c, d, e, o}; M = {a, o, p, q, r, s, t, u}

K ∪ L ∪ M = {x / x ∈ K or x ∈ L or x ∈ M}
⇒ K ∪ L ∪ M = {a, b, c, d, e, i, o, p, q, r, s, t, u}

Properties of union of sets

Commutative Law

1. For any two sets "A" and "B",

A ∪ B = B ∪ A

2. For any three sets "A", "B" and "C",

A ∪ B ∪ C = B ∪ A ∪ C = B ∪ C ∪ A

Associative Law

1. For any three sets "A", "B" and "C",

A ∪ (B ∪ C) = (A ∪ B) ∪ C

Identity Law

1. For any set "A",

A ∪ A = A

Complements Law

1. For any set "A",

A ∪ Φ = A

Intersection of Sets - Disjoint Sets

The intersection of two or more sets is the set whose elements are all the elements that are common to all of the sets, but nothing else.

The symbol is used to indicate intersection.

1. A = {1, 2, 3, 4, 5}; B = {2, 4, 6, 8, 10}

A ∩ B = {x / x ∈ A and x ∈ B}
⇒ A ∩ B = {2, 4}

2. K = {a, e, i, o, u}; L = {a, b, c, d, e, o}; M = {a, o, p, q, r, s, t, u}

K ∩ L ∩ M = {x / x ∈ K and x ∈ L and x ∈ M}
⇒ K ∩ L ∩ M = {a, o}

Disjoint sets

Two or more sets are said to be disjoint if they have no element in common i.e. if their intersection set is an empty set (a null set).
1. A = {1, 3, 5, 7, ... }; B = {2, 4, 6, 8, 10, ...}

A ∩ B = {} (Or) A ∩ B = Φ
⇒ A and B are disjoint sets.

2. K = {a, e, i, o, u}; L = {a, b, c, d, e}; M = {p, q, r, s, t, u}

K ∩ L ∩ M = {} (Or) K ∩ L ∩ M = Φ
⇒ K, L and M are disjoint sets.

Properties of intersection of sets

Commutative Law

1. For any two sets "A" and "B",

A ∩ B = B ∩ A

2. For any three sets "A", "B" and "C",

A ∩ B ∩ C = B ∩ A ∩ C = B ∩ C ∩ A

Associative Law

1. For any three sets "A", "B" and "C",

A ∩ (B ∩ C) = (A ∩ B) ∩ C

Identity Law

1. For any set "A",

A ∩ A = A

Complements Law

1. For any set "A",

A ∩ Φ = Φ

Complements of Sets : Relative - Absolute

In many cases, we consider (assume) the given set or sets as the subsets of a universal set represented by "U".

Complements of sets are of two types.

Relative Complements of Sets

Relative complement of a set in relation to a second set is the set of elements which are present only in the second set but not in the first.

Where "A" and "B" are two sets, the relative complement of "A" in "B" is the set theoretic difference of "B" and "A" i.e. the set of elements present in "B" but not in "A".

It is written as "B − A"

Example

A = {a, e, i, o, u}; B = {a, b, c, d, e, f, ...., w, x, y, z}
 ⇒ B − A Complement of A in B = {x / x ∈ B and x ∉ A} = {a, b, c, d, e, f, ...., w, x, y, z} − {a, e, i, o, u} = {b, c, d, f, ...., w, x, y, z}

It is not a requirement that all the elements of the first set should be present in the second i.e. the first set need not be a subset of the second.

A = {a, e, i, o, u}; B = {a, b, c, d, e, f}

 ⇒ B − A Complement of A in B = {x / x ∈ B and x ∉ A} = {a, b, c, d, e, f} − {a, e, i, o, u} = {b, c, d, f}

1. A − A = Φ
2. A − Φ = A
3. Φ − A = Φ

Absolute Complements of Sets

For a set which is a subset of a universal set, the absolute complement is the relative complement of the set in the Universe. It is the set of all the elements in the universal set that are not present in it.

The absolute complement of a set "A" is the relative complement of "A" in "U" (where "U" is the universal set).

It is represented as "Ac" or A' ["Ac" or A' = U − A]

Example

U = {1, 2, 3, 4, 5, 6, ... }; O = {1, 3, 5, 6, 7, .... }
 ⇒ Oc Complement of O = {x / x ∈ U and x ∉ A} = {1, 2, 3, 4, 5, 6, ... } − {1, 3, 5, 7, 9, ...} = {2, 4, 6, 8, 10, ...}

1. A ∪ Ac = A
2. A ∩ Ac = Φ
3. Φc= U
4. Uc= Φ

Absolute : Relative Complements

For two sets "A" and "B"
1. A − B = A ∩ Bc
2. (A − B)c = Ac ∪ B

Set theory - Distibutive Laws

For three sets "A", "B" and "C"
1. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
2. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Set Theory - De Morgans Laws

For two sets "A" and "B"
1. n(A ∪ B) = n (A) + n (B) − n(A ∩ B)
2. (A ∪ B)c = Ac ∩ Bc
3. (A ∩ B)c = Ac ∪ Bc
For three sets "A", "B" and "C"
1. n(A ∪ B ∪ C) = n (A) + n (B) + n (C) − n(A ∩ B) − n(B ∩ C) − n(A ∩ C) + n(A ∩ B ∩ C)
 ... 161718 ...