Set

3. Introduction

In real life, there are many problems related to data (objects) that are collected based on certain criteria. These collections of data (objects) are defined as sets or himpunan in Indonesian.

3.1 Sets (Himpunan)

A set is a collection of distinct objects that can be clearly defined. The objects within a set are called elements or members of the set. The membership of an element in a set is denoted by the symbol ’∈‘.

Example 1:

Let’s consider the set A = {x, y, z}.

• x ∈ A: x is a member of set A.
• w ∉ A: w is not a member of set A.

Representation of Sets

Sets can be represented in various ways, such as enumeration, standard symbols, set builder notation, and Venn diagrams.

Enumeration

Enumeration means listing all the elements of a set within curly braces. Each member of the set is listed in detail.

Example 2:

a) Set of the first four natural numbers: A = {1, 2, 3, 4}.
b) Set of the first five positive even numbers: B = {4, 6, 8, 10, 12}.
c) Set of the first 100 natural numbers: {1, 2, …, 100}.
d) Set of integers: {…, -2, -1, 0, 1, 2, …}.

Standard Symbols

There are standard symbols commonly used to represent sets, including:

• P: Set of positive integers (P = {1, 2, 3, …}).
• N: Set of natural numbers (N = {1, 2, …}).
• Z: Set of integers (Z = {…, -2, -1, 0, 1, 2, …}).
• Q: Set of rational numbers.
• R: Set of real numbers.
• C: Set of complex numbers.

Set Membership

The symbol ’∈’ is used to indicate the membership of an element in a set, while ’∉’ is used to indicate non-membership.

Cardinality

The cardinality of a set refers to the number of elements it contains. It is represented by ‘n(A)’ or ‘|A|‘. If a set has an infinite number of elements, its cardinality is considered infinite (∞).

Empty Set

An empty set or null set is a set that does not contain any elements. It is denoted by the symbol Ø or {}.

3.7 Subsets

Theorem: For any set A, the following statements hold true: (a) A is a subset of itself (i.e., A ⊆ A). (b) The empty set is a subset of A (∅ ⊆ A). (c) If A ⊆ B and B ⊆ C, then A ⊆ C.

3.8 Equivalent Sets

Definition: Set A is said to be equivalent to set B if and only if the cardinality of both sets is the same. Notation: A ~ B ↔ |A| = |B|

Example 12: Let A = {1, 3, 5, 7} and B = {a, b, c, d}. Then A ~ B because |A| = |B| = 4.

3.9 Disjoint Sets

Definition: Two sets A and B are said to be disjoint if they have no elements in common. Notation: A // B Venn diagram representation:

Example 13: If A = {x | x ∈ P, x < 8} and B = {10, 20, 30, …}, then A // B.

3.10 Power Set

Definition: The power set of a set A is a set that contains all possible subsets of A, including the empty set and A itself.

Notation: P(A) or 2^A If |A| = m, then |P(A)| = 2^m.

Example 14: If A = {1, 2}, then [P(A) = {\emptyset, {1}, {2}, {1, 2}}]

Example 15: The power set of the empty set is [P(\emptyset) = {\emptyset}] and the power set of the set ({\emptyset}) is [P({\emptyset}) = {\emptyset, {\emptyset}}]

Example 16: If (A = {a, b, 5}), then the power set of A is:

[P(A) = {\emptyset, {a}, {b}, {5}, {a, b}, {a, 5}, {b, 5}, {a, b, 5}}]

3.11 Set Operations

a. Intersection b. Union c. Complement d. Difference e. Symmetric Difference f. Cartesian Product

3.11.1 Intersection

Definition: The intersection of sets A and B is a set whose elements are those that belong to both set A and set B. Notation: A ∩ B = { x | x ∈ A and x ∈ B }

Example 17: (i) If (A = {2, 4, 6, 8, 10}) and (B = {4, 10, 14, 18}), then (A ∩ B = {4, 10}) (ii) If (A = {3, 5, 9}) and (B = {-2, 6}), then (A ∩ B = \emptyset)

3.11.2 Union

Definition: The union of sets A and B is a set whose elements are those that belong to either set A or set B. Notation: A ∪ B = { x | x ∈ A or x ∈ B }

Example 19: a. If (A = {2, 5, 8}) and (B = {7, 5, 22}), then (A ∪ B = {2, 5, 7, 8, 22}) b. (A ∪ \emptyset = A) c. If (A = {2, 3, 5, 7, 9}) and (D = {Anto, 14, L}), then (A ∪ D = {2, 3, 5, 7, 9, Anto, 14, L})

3.11.3 Complement

Definition: The complement of a set A with respect to a universal set U is a set whose elements are those in U but not in A. Notation: (A’ = { x | x ∈ U, x ∉ A })

Example 20: If (U = {1, 2, 3, …, 9}) and (A = {1, 3, 7, 9}), then (A’ = {2, 4, 6, 8})

3.11.4 Difference

Definition: The difference between two sets A and B is a set whose elements are those in A but not in B. Notation: (A - B = { x | x ∈ A and x ∉ B })

Example 22: (i) If (A = {1, 2, 3, …, 10}) and (B = {2, 4, 6, 8, 10}), then (A - B = {1, 3, 5, 7, 9}) and (B - A = \emptyset) (ii) ({1, 3, 5} - {1, 2, 3} = {5}) (iii) ({1, 2, 3} - {1, 3, 5} = {2})

3.11.5 Symmetric Difference

Definition: The symmetric difference between sets A and B is a set whose elements are in either A or B but not in both. Notation: (A ⊕ B = (A ∪ B) - (A ∩ B)) (A ⊕ B = (A - B) ∪ (B - A))

Example 24: If (A = {2, 4, 6}) and (B = {2, 3, 5}), then (A ⊕ B = {3, 4, 5, 6})

Theorem: The symmetric difference satisfies the following properties: (a) (A ⊕ B = B ⊕ A) (commutative law) (b) ((A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)) (associative law)

3.12 Cartesian Product

Definition: The Cartesian product of sets A and B, denoted as (A × B), is the set of all ordered pairs where the first element comes from set A and the second element comes from set B.

Example 26: Let (C = {1, 2, 3}) and (D = {a, b}), then (C × D = {(1, a), (1,b), (2, a), (2, b), (3, a), (3, b)})

Properties:

• If A and B are finite sets, then (|A × B| = |A| \cdot |B|).
• Ordered pairs are distinct, meaning ((a, b)) is different from ((b, a)) unless (a = b).
• Cartesian product is not commutative, i.e., (A × B ≠ B × A) unless either A or B is empty.
• If A = ∅ or B = ∅, then (A × B = B × A = ∅).

Example 27: Suppose (A = {\text{soto}, \text{gado-gado}, \text{nasi goreng}, \text{mie rebus}})
(B = {\text{coca-cola}, \text{teh}, \text{es dawet}}) How many combinations of food and drink can be arranged from these two sets?

Answer: (4 \times 3 = 12)
Thus, {(s, c), (s, t), (s, d), (g, c), (g, t), (g, d), (n, c), (n, t), (n, d), (m, c), (m, t), (m, d)}.

Example 28: List all members of the following sets: (a) (P(\emptyset))
(b) ∅ × (P(\emptyset))
(c) {\emptyset} × (P(\emptyset))
(d) (P(P({3})))

Solution: (a) (P(\emptyset) = {\emptyset})
(b) ∅ × (P(\emptyset) = ∅)
(Note: if A = ∅ or B = ∅, then (A × B = ∅))

(c) {\emptyset} × (P(\emptyset) = {\emptyset} × {\emptyset} = {(\emptyset, \emptyset))}
(d) (P(P({3})) = P({\emptyset, {3}}) = {\emptyset, {\emptyset}, {{3}}, {\emptyset, {3}}})

3.13 Laws of Sets

Identity Laws:

• (A ∪ ∅ = A)
• (A ∩ U = A)

Null/Dominance Laws:

• (A ∩ ∅ = ∅)
• (A ∪ U = U)

Complement Laws:

• (A ∪ A’ = U)
• (A ∩ A’ = ∅)

Idempotent Laws:

• (A ∩ A = A)
• (A ∪ A = A)

Involution Law:

• ((A’)’ = A)

Absorption Laws:

• (A ∪ (A ∩ B) = A)
• (A ∩ (A ∪ B) = A)

Commutative Laws:

• (A ∪ B = B ∪ A)
• (A ∩ B = B ∩ A)

Associative Laws:

• (A ∪ (B ∪ C) = (A ∪ B) ∪ C)
• (A ∩ (B ∩ C) = (A ∩ B) ∩ C)

Distributive Laws:

• (A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C))
• (A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C))

De Morgan’s Laws:

• ((A ∪ B)’ = A’ ∩ B’)
• ((A ∩ B)’ = A’ ∪ B’)

0/1 Laws:

• (U’ = ∅)
• (\emptyset’ = U)

3.14 Principle of Inclusion-Exclusion

The Principle of Inclusion and Exclusion is an extension of Venn diagrams. It helps determine the total number of elements in the union of two or more sets by considering their intersections.

Example 29: Suppose there are 20 students attending a training on hardware engineering and 30 students attending a training on software engineering. How many students in total are attending either hardware engineering or software engineering training?

To answer this, let’s use the Principle of Inclusion-Exclusion.

Explanation: If we denote:

• A = set of students attending hardware engineering training
• B = set of students attending software engineering training

Then, we want to find (|A ∪ B|), which represents the total number of students attending either training.

The Principle of Inclusion-Exclusion states:

[|A ∪ B| = |A| + |B| - |A ∩ B|]

Example 30: How many integers between 1 and 100 are divisible by 3 or 5?

Solution: Let:

• (|A|) = number of integers between 1 and 100 divisible by 3
• (|B|) = number of integers between 1 and 100 divisible by 5
• (|A ∩ B|) = number of integers between 1 and 100 divisible by both 3 and 5

Using the Principle of Inclusion-Exclusion:

[|A ∪ B| = |A| + |B| - |A ∩ B|]

Example 31: Among integers between 101 and 600 (inclusive), how many numbers are not divisible by 4 or 5, but not both?

This can also be solved using the Principle of Inclusion-Exclusion, similar to Example 30.

3.15 Multisets

A multiset is a set where elements are allowed to repeat (not necessarily distinct). Examples include {1, 1, 1, 2, 2, 3}, {2, 2, 2}, {2, 3, 4}, and {}.

The multiplicity of an element in a multiset is the number of times that element appears in the multiset. For example, in the multiset M = {0, 1, 1, 1, 0, 0, 0, 1}, the multiplicity of 0 is 4.

Sets are a special case of multisets where each element’s multiplicity is either 0 or 1.

The cardinality of a multiset is defined as the cardinality of its equivalent set, assuming all elements in the multiset are distinct.

3.16 Operations Between Two Multisets

Let P and Q be multisets:

• ( P \cup Q ) is a multiset where the multiplicity of each element is equal to the maximum multiplicity of that element in sets P and Q.
  • Example: ( P = { a, a, a, c, d, d } ) and ( Q = { a, a, b, c, c } ), ( P \cup Q = { a, a, a, b, c, c, d, d } )
• ( P \cap Q ) is a multiset where the multiplicity of each element is equal to the minimum multiplicity of that element in sets P and Q.
  • Example: ( P = { a, a, a, c, d, d } ) and ( Q = { a, a, b, c, c } ), ( P \cap Q = { a, a, c } )

3.17 Operations Between Two Multisets

• ( P - Q ) is a multiset where the multiplicity of each element is equal to:
  • the multiplicity of that element in set P minus the multiplicity of that element in set Q, if the difference is positive
  • 0 if the difference is zero or negative.
  • Example: ( P = { a, a, a, b, b, c, d, d, e } ) and ( Q = { a, a, b, b, b, c, c, d, d, f } ), then ( P - Q = { a, e } )

3.18 Operations Between Two Multisets

• ( P + Q ), defined as the sum of two multisets, is a multiset where the multiplicity of each element is equal to the sum of the multiplicities of that element in sets P and Q.
  • Example: ( P = { a, a, b, c, c } ) and ( Q = { a, b, b, d } ), ( P + Q = { a, a, a, b, b, b, c, c, d } )