Chapter 1: Carry out set theory operations

Discrete mathematical concepts form the foundational language for many ICT operations, including database management, network design, and algorithm development. Set theory, in particular, provides a structured way to handle collections of distinct objects such as IP addresses, user groups, and data packets. Mastering set operations enables ICT technicians to efficiently organize, query, and manipulate data sets critical to system administration and software configuration in Kenyan ICT environments.

1.1 Sets representation

A set is a well-defined collection of distinct objects, and in ICT work almost every group of data is a set: the devices on a network, the user accounts allowed into a system, the ports a firewall leaves open. Before sets can be combined or compared they must be written down in a way that everyone reads in the same manner. This topic introduces the vocabulary and notation of sets, the properties that hold when sets are combined, the rules of order and uniqueness, and the methods used to represent a set.

1.1.1 Introduction to set theory operations

Set theory operations are the rules for combining and comparing sets to form new sets. There are four basic operations: union, intersection, difference and complement. This section only introduces them so that the vocabulary of the topic makes sense. Each operation is worked in full in the topic Set operations.

• Union (A ∪ B): all the elements that are in A, in B, or in both.
• Intersection (A ∩ B): only the elements that are in both A and B.
• Difference (A − B): the elements of A that are not in B.
• Complement (A′): the elements of the universal set that are not in A.

Example: a web design studio keeps two sets of files. Set A holds the files edited today and set B holds the files waiting for review.

A = {logo.png, home.html, style.css}
B = {home.html, about.html}

A ∪ B = {logo.png, home.html, style.css, about.html}, which has four files because home.html is listed once.
A ∩ B = {home.html}, the only file that was edited today and is also waiting for review.
A − B = {logo.png, style.css}, the files edited today that are not waiting for review.

1.1.1.1 Definition of key terms

Set theory has a small vocabulary that every later topic of this chapter uses. The terms below are the ones a learner must be able to use correctly in writing and in speech.

• Set: a well-defined collection of distinct objects. Well-defined means that for any object it is possible to decide whether it belongs to the set or not. The set of tablets in a repair queue is well defined, but "the best tablets" is not, because people disagree on what best means.
• Element (member): each object in a set. The router, the switch and the laptop are the elements of the set of devices on a bench.
• Membership symbols: ∈ means "is an element of" and ∉ means "is not an element of". If A = {laptop, router, switch}, then router ∈ A and printer ∉ A.
• Naming and braces: a set is named with a capital letter, its elements are written in lower case or as they are named, and the elements are enclosed in curly braces { }, separated by commas.
• Cardinality: the number of elements in a set, written n(A). The set A above has n(A) = 3. Counting and calculating with cardinality are covered in Set operations.
• Number sets: ℕ = {1, 2, 3, ...} is the set of natural numbers, ℤ = {..., −2, −1, 0, 1, 2, ...} is the set of integers and ℝ is the set of real numbers. In these notes zero is not placed in ℕ.

1.1.1.2 Set builder notation

Set builder notation describes a set by the rule its members obey instead of listing the members. It is written A = {x | condition on x} and read "A is the set of all x such that the condition holds". The bar | means "such that" (some books write a colon instead).

The notation has three parts: the variable before the bar (here x), the bar itself, and the condition after the bar. The condition often names the number set the variable comes from, for example x ∈ ℕ. The rule must be exact enough that every object either passes or fails it.

Example: B = {x | x ∈ ℕ, x < 6} reads "the set of all natural numbers x such that x is less than 6", so B = {1, 2, 3, 4, 5}.

Example: P = {p | p is a TCP or UDP port number, 0 ≤ p ≤ 1023} is the set of well-known port numbers. It has 1024 elements because both end values are included.

The skill of turning a rule into a list and a list into a rule is practised under Set builder form.

1.1.2 Identification of sets properties

Union and intersection obey three properties: the commutative, associative and distributive properties. Knowing them lets a technician rearrange a database query or a filter without changing its result. To identify a property, take sample sets, work out both sides of the statement separately and compare the two answers.

Commutative property

The order of the two sets in a union or an intersection does not change the result.

A ∪ B = B ∪ A
A ∩ B = B ∩ A

Difference does not have this property: A − B and B − A are usually different sets.

Example 1: let A = {1, 2, 3} and B = {3, 4}. Confirm the property for union and intersection, and show that difference is not commutative.

A ∪ B = {1, 2, 3, 4}
B ∪ A = {3, 4, 1, 2} = {1, 2, 3, 4}
A ∩ B = {3} and B ∩ A = {3}
A − B = {1, 2} but B − A = {4}

Answer: union and intersection are commutative, difference is not.

Example 2: two patch panels carry the device sets C = {D01, D02} and D = {D02, D03}. Confirm the property for union and intersection.

C ∪ D = {D01, D02, D03} and D ∪ C = {D02, D03, D01} = {D01, D02, D03}
C ∩ D = {D02} and D ∩ C = {D02}

Answer: C ∪ D = D ∪ C = {D01, D02, D03} and C ∩ D = D ∩ C = {D02}.

Example 3: the user groups E = {Admin, User} and F = {User, Guest} are combined in both orders.

E ∪ F = {Admin, User, Guest}
F ∪ E = {User, Guest, Admin} = {Admin, User, Guest}

Answer: E ∪ F = F ∪ E = {Admin, User, Guest}.

Associative property

When three sets are joined by the same operation, the way they are grouped does not change the result.

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

Example 1: let A = {1, 2}, B = {2, 3} and C = {3, 4}. Verify the property for union.

(A ∪ B) ∪ C = {1, 2, 3} ∪ {3, 4} = {1, 2, 3, 4}
A ∪ (B ∪ C) = {1, 2} ∪ {2, 3, 4} = {1, 2, 3, 4}

Answer: both groupings give {1, 2, 3, 4}.

Example 2: let A = {1, 2, 3}, B = {2, 3, 4} and C = {3, 4, 5}. Verify the property for intersection.

(A ∩ B) ∩ C = {2, 3} ∩ {3, 4, 5} = {3}
A ∩ (B ∩ C) = {1, 2, 3} ∩ {3, 4} = {3}

Answer: both groupings give {3}.

Example 3: a network installer lists the devices on three floors as X = {D1, D2}, Y = {D2, D3} and Z = {D3, D4}. Verify the property for union.

(X ∪ Y) ∪ Z = {D1, D2, D3} ∪ {D3, D4} = {D1, D2, D3, D4}
X ∪ (Y ∪ Z) = {D1, D2} ∪ {D2, D3, D4} = {D1, D2, D3, D4}

Answer: both groupings give {D1, D2, D3, D4}.

Distributive property

Union distributes over intersection, and intersection distributes over union. Working out one operation "inside" the brackets first gives the same answer as applying it to each set separately and then joining the results.

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

Example 1: let A = {1, 2, 3}, B = {2, 3, 4} and C = {3, 4, 5}. Verify that union distributes over intersection.

B ∩ C = {3, 4}
A ∪ (B ∩ C) = {1, 2, 3} ∪ {3, 4} = {1, 2, 3, 4}
A ∪ B = {1, 2, 3, 4} and A ∪ C = {1, 2, 3, 4, 5}
(A ∪ B) ∩ (A ∪ C) = {1, 2, 3, 4}

Answer: both sides equal {1, 2, 3, 4}.

Example 2: with the same sets, verify that intersection distributes over union.

B ∪ C = {2, 3, 4, 5}
A ∩ (B ∪ C) = {1, 2, 3} ∩ {2, 3, 4, 5} = {2, 3}
A ∩ B = {2, 3} and A ∩ C = {3}
(A ∩ B) ∪ (A ∩ C) = {2, 3} ∪ {3} = {2, 3}

Answer: both sides equal {2, 3}.

Example 3: a web design studio records the skills of three developers as X = {HTML, CSS}, Y = {CSS, JavaScript} and Z = {JavaScript, SQL}. Verify that union distributes over intersection.

Y ∩ Z = {JavaScript}
X ∪ (Y ∩ Z) = {HTML, CSS, JavaScript}
X ∪ Y = {HTML, CSS, JavaScript} and X ∪ Z = {HTML, CSS, JavaScript, SQL}
(X ∪ Y) ∩ (X ∪ Z) = {HTML, CSS, JavaScript}

Answer: both sides equal {HTML, CSS, JavaScript}.

1.1.3 Order and uniqueness

A set is a collection of distinct elements in which the order carries no meaning. This separates a set from a list or an array, which keeps its elements in positions and may repeat a value. In Python the same idea appears in the data types: the list ["admin", "user", "admin"] has three entries in a fixed order, but set(["admin", "user", "admin"]) has only two elements and gives no promise about the order in which they are printed.

Order irrelevance in sets

Writing the elements of a set in a different order gives the same set. Two sets are the same set when they contain exactly the same elements, however the elements are arranged.

Example 1: are A = {User1, User2} and B = {User2, User1} the same set? Both contain User1 and User2 and nothing else, so A = B.

Example 2: are G = {10, 20, 30} and H = {30, 10, 20} the same set? Each contains 10, 20 and 30, so G = H.

Example 3: are I = {Admin, Guest} and J = {Guest, Admin} the same set? Each contains the same two roles, so I = J.

Uniqueness of elements in sets

An element is either in a set or not in it, so a repeated value is counted once. When a list of values is turned into a set, the repeats disappear.

Example 1: simplify A = {User1, User2, User1}. The duplicate User1 is removed, so A = {User1, User2}.

Example 2: simplify B = {192.168.1.1, 192.168.1.2, 192.168.1.1}. The duplicate address is removed, so B = {192.168.1.1, 192.168.1.2}.

Example 3: simplify D = {10, 20, 10, 30, 20}. Each value is kept once, so D = {10, 20, 30}.

Example 4: a firewall log has six entries, from the addresses 10.0.0.5, 10.0.0.7, 10.0.0.5, 10.0.0.9, 10.0.0.7 and 10.0.0.5. As a list it has six entries. As a set of distinct source addresses it is {10.0.0.5, 10.0.0.7, 10.0.0.9}, which has three elements.

1.1.4 Methods of set representation

A set can be represented in several ways, and the best choice depends on what the reader needs. Four methods of set representation are used here: roster form, set builder form, statement form and tabular form. Finite and infinite sets also need different handling, because only a finite set can be listed to the end.

1.1.4.1 Roster form

Roster form, also called the listing method, writes every element of the set between curly braces, separated by commas. The order does not matter and no element is written twice. It is the clearest method for small sets.

• The servers that are running are S = {S1, S2, S3}.
• The user roles on a system are R = {Admin, User, Guest}.
• The addresses given out by a router are I = {10.0.0.1, 10.0.0.2, 10.0.0.3}.
• The tables of a small database are T = {Customers, Orders, Products}.
• The programming languages a team supports are L = {Python, Java, C++}.

1.1.4.2 Set builder form

Set builder form defines a set by a property that every member satisfies, and it is the only practical method when the set is too large to list. The notation was introduced under Set builder notation; this section uses it to write real sets and to move between the forms.

• All addresses of the subnet from 192.168.1.0 to 192.168.1.255 are A = {x | x = 192.168.1.i, i a whole number, 0 ≤ i ≤ 255}.
• The even port numbers from 0 to 1024 are B = {p | p is even, 0 ≤ p ≤ 1024}.
• The users with an access level above 3 are C = {u | access level of u > 3}.
• The usernames that start with "admin" are D = {u | u starts with "admin"}.
• The devices whose MAC address ends in FF are E = {d | MAC address of d ends with FF}.

To change from set builder form to roster form, work through the rule and list every member that passes it. For {x | x ∈ ℕ, 3 ≤ x ≤ 7} the members are 3, 4, 5, 6 and 7, so the roster form is {3, 4, 5, 6, 7}. To change the other way, find the rule shared by the members. For {2, 4, 6, 8, 10} the rule is "x = 2n for n = 1 to 5", so the set builder form is {x | x = 2n, n ∈ ℕ, n ≤ 5}.

1.1.4.3 Finite

A finite set is represented by listing all of its elements. When the set is long and its pattern is obvious, the middle elements may be replaced by three dots, as long as the first elements and the last element are shown. This is the representation of a finite set; the meaning of the term is given under Finite Set in Types of sets.

Example: a cyber café has thirty terminals named T1 to T30. The set of terminals is C = {T1, T2, T3, ..., T30}. The dots stand for T4 to T29, and the last element T30 closes the list, which tells the reader that the set ends.

The same set in set builder form is {x | x ∈ ℕ, x ≤ 30}, with each x standing for a terminal number.

1.1.4.4 Infinite

An infinite set cannot be listed to the end. It is represented either by writing the first elements followed by three dots with no last element, or by set builder form. The dots are allowed only when the pattern is so clear that the reader can continue it without doubt.

• The natural numbers are ℕ = {1, 2, 3, ...}.
• The even natural numbers are {2, 4, 6, ...}.
• The multiples of 5 are {x | x = 5n, n ∈ ℕ}.
• The real numbers between 0 and 1 are {x | x ∈ ℝ, 0 < x < 1}.
• The ticket numbers of a support desk that numbers its tickets 1, 2, 3 and never stops are {1, 2, 3, ...}.

The set of real numbers between 0 and 1 cannot be written with dots, even at the start, because no number is "next" after 0: between any two real numbers there is another one. Only set builder form or statement form can describe it.

1.1.4.5 Statement form

Statement form describes the set in words inside the braces. It is useful for quick notes, but the sentence must be exact so that two readers build the same set from it.

• A = {the vowels in the word NETWORK} gives the roster form {E, O}.
• B = {the primary colours of light used by a screen} gives {red, green, blue}.
• C = {the prime numbers less than 20} gives {2, 3, 5, 7, 11, 13, 17, 19}.
• D = {the servers in a rack that are switched on} is exact only if the rack and the time of reading are known, because the members change when a server is switched off.
• E = {the days of the week whose names start with T} gives {Tuesday, Thursday}.

A statement such as "the good users of a system" is not accepted, because "good" is a matter of opinion and the set is not well defined.

1.1.4.6 Tabular form

Tabular form shows the elements of a set in a table. Each row holds one element, and extra columns hold facts about it. A second use is a membership table with one row per element and one column per set, where 1 means that the element belongs to the set and 0 means that it does not.

Example: a technician lists five devices D1 to D5. Set W holds the wired devices and set S holds the devices with a static IP address.

Reading the columns gives W = {D1, D2, D4} and S = {D2, D3, D4}. Reading across the rows shows that D2 and D4 are in both sets and D5 is in neither. A database table works the same way: each row is one element, and the rows must differ from each other for the table to behave as a set.

Chapter Summary

This chapter introduced the fundamental concepts of set theory operations, beginning with how sets are represented and the key properties that define them, including order and uniqueness. Various methods of set representation were explored, such as roster form and set builder form, along with distinctions between finite and infinite sets. The chapter then discussed the different types of sets and their applications in mathematical contexts. Central to the chapter were the main set operations, including the determination of cardinality, union, intersection, difference, and complement of sets. The use of Venn diagrams was presented as a visual tool to illustrate these operations and relationships between sets. Overall, the chapter provided a comprehensive foundation for understanding and performing essential set theory operations in discrete mathematics.