Java Reference
In-Depth Information
f1, 4g A set composed of the members 1 and 4
fxjx is a positive integerg A set definition using a
setformer
Example: the set of all positive integers
x 2
P
x is a member of set
P
x 2
P
x is not a member of set
P
; The null or empty set
j
P
j Cardinality: size of set
P
or number of members for set
P
P
Q
,
Q
P
Set
P
is included in set
Q
,
set
P
is a subset of set
Q
,
set
Q
is a superset of set
P
P
[
Q
Set Union:
all elements appearing in
P
OR
Q
P
\
Q
Set Intersection:
all elements appearing in
P
AND
Q
P
Q
Set difference:
all elements of set
P
NOT in set
Q
Figure2.1
Set notation.
jPj = 3 (because P has three members) and jQj = 2 (because Q has two members).
The union of P and Q, written P[Q, is the set of elements in either P or Q, which
is f2, 3, 5, 10g. The intersection of P and Q, written P \ Q, is the set of elements
that appear in both P and Q, which is f5g. The set difference of P and Q, written
P Q, is the set of elements that occur in P but not in Q, which is f2, 3g. Note
that P [ Q = Q [ P and that P \ Q = Q \ P, but in general P Q 6= Q P.
In this example, Q P = f10g. Note that the set f4; 3; 5g is indistinguishable
from set P, because sets have no concept of order. Likewise, set f4; 3; 4; 5g is also
indistinguishable from P, because sets have no concept of duplicate elements.
The powerset of a set S is the set of all possible subsets for S. Consider the set
S = fa;b;cg. The powerset of S is
f;; fag; fbg; fcg; fa;bg; fa;cg; fb;cg; fa;b;cgg:
A collection of elements with no order (like a set), but with duplicate-valued el-
ements is called a bag.
1
To distinguish bags from sets, I use square brackets []
around a bag's elements. For example, bag [3, 4, 5, 4] is distinct from bag [3, 4, 5],
while set f3; 4; 5; 4g is indistinguishable from set f3; 4; 5g. However, bag [3, 4, 5,
4] is indistinguishable from bag [3, 4, 4, 5].
1
The object referred to here as a bag is sometimes called a multilist.
But, I reserve the term
multilist for a list that may contain sublists (see Section 12.1).
