INTRODUCTION TO COMPUTER SCIENCE
HANDOUT #2. SET THEORY
K5 & K6, Computer Science Department, Vaên Lang University
Second semester Feb, 2002
Instructor: Traàn Ñöùc Quang
Major themes:
1. The Set Data Model
2. Set Algebra
3. Implementation of Sets
Reading: Sections 7.2, 7.3, 7.4, 7.7, and 7.10.
2.1 THE SET DATA MODEL
The set is the most fundamental concept in mathematics, and this is true in computer
science. The term "set" is not defined explicitly; at a basic level, we can think of a set
as a collection of objects.
Basic notation
• x ∈ S "element x is a member of set S"
• S = {x
1
, x
2
, . . . , x
n
} "elements x
1
, x
2
, . . . , x
n
are members of set S"
• each x
i

• T is a proper superset of S
Region 1
Region 2 Region 3 Region 4
S T
2.3 IMPLEMENTATION OF SETS 13
• S is properly contained in T
• T properly contains S
and is true if S ⊆ T and there is at least one element of T that is not also a mem-
ber of S.
Power Sets
Let S be any set. The power set of S is the set of all subsets of S. We denote the power
set of S by P(S) or 2
S
.
Example: S = {a, b, c, d}
P(S) = {∅, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c},
{a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}
Theorem: If a set S has n members, then P(S) has 2
n
members.
2.3 IMPLEMENTATION OF SETS
I will briefly present list implementation of sets. You could see some other implemen-
tations in Section 7.5.
Note that the set is a general concept, thus we only show the basic set operations.
When the set is a specific model, for example, dictionary or list, we can efficiently
implement those operations.
For simplicity, sets are implemented by a sorted linked list; each element is a cell.
4
6
•

else if (L == NULL) /* M cannot be NULL here */
return assemble(M->element, NULL, M->next);
else if (M == NULL) /* L cannot be NULL here */
return assemble(L->element, L->next, NULL);
/* if we reach here, neither L nor M can be NULL */
else if (L->element == M->element)
return assemble(L->element, L->next, M->next);
else if (L->element < M->element)
return assemble(L->element, L->next, M);
else /* here, M->element < L->element */
return assemble(M->element, L, M->next);
}
2.4 GLOSSARY 15
2.4 GLOSSARY
Concept: Khái niệm, ý niệm. An original idea.
Conceptual design: Thiết kế mức khái niệm.
Set: Tập hợp (tập). See the definition in text.
Collection: commonly used (informally) as a synonym of set.
Set former: Lập tử tập hợp. An operator to form a set.
Empty set: Tập trống, tập rỗng.
Element, member: Phần tử (của tập hợp).
Subset: Tập con.
Superset: Tập cha, tập bao hàm.
Term. Various meanings (1) Thuật ngữ, thuật từ; (2) Học kỳ, dùng chung cho cả quarter
(khoảng 10 đến 15 tuần) và semester (khoảng 20 đến 25 tuần); (3) Hạng thức.
Notation: Ký pháp. A system of signs or symbols to represent words, phrases, num-
bers, quantities, etc. as in mathematics, chemistry, musics, etc.
Equality: Tính bằng nhau; Đẳng thức.
Set Algebra: Đại số tập hợp.
Union: Phép hợp; phần hợp. See the definition in text.