A set is an **unordered** collection of
**unique** objects or elements or
members. Notation S = {a,b,c} means: S is the set with elements a,b and
c and, because sets are unordered, {a,b,c} = {a,c,b}. Also,
a ∈ S stands for a is an element of S.
Every element of a set is unique, so there is no need to have the same
element occur more than once in a set. For example {a,a,b,c} is the same set
as {a,b,c}. In general we avoid repeating the same elements when we write down sets.

A finite set contains a finite number of elements. We can fully
enumerate, ie write all elements of, a finite set, eg Vowels =
{a,e,i,o,u} or OddDigs = {1,3,5,7,9}. The **cardinality**
of a finite set
is the number of elements in it. In the two cases above the
cardinality is 5. Notation **|S|**: the cardinality of S.

An infinite set of elements cannot be fully enumerated. To define
infinite sets we use a **set builder**: {x |
characteristic A} which means: all elements x that have characteristic
A. We also use a … notation, meaning "and so on".
For example N, the infinite set of natural numbers is often denoted as
N = {0,1,2, …}. Here are some more interesting sets:

- Booleans: {false, true} or {F,T} or even {0,1}
- Numbers
- N = {0,1,2, …} Natural numbers. Notice that we consider 0 to be an element of N.
- Z = {… ,-2,-1,0,1,2, …} Integers.
- Q = {p/q | p ∈ Z and q ∈ Z and q ≠ 0} Rationals
- R, Real numbers, the set of numbers on the real number line.

N^{+} is sometimes used for the positive integers,
N^{+} = {1,2,3, …}.
In Mathematics, the Integers, Rationals and Reals are truely infinite sets.
In Computer Science we think about the representation of numbers in a computer.
For example, integers in Java (byte, short, int, and long) have finite representations,
ie they are represented by a fixed number of bits (byte: 8, short: 16, int: 32, and
long: 64) and are therefore are finite sets. When we talk about eg Integers
in this course, we mean the Mathematics Integers.
Q and R are not the same (eg √2 is not in Q).
The irrational numbers are the real numbers in R that are not in Q,
notation: R-Q.

Two sets are equal, notation A=B, if and only if they have the same
elements. Notation:

Do not be intimidated or put off by notation. As a Computer Scientist you will encounter many forms of notation in your career. ∀ means: for all, ∀ x ∈ S means: for all x in S, ∀ x ∈ S: P means for all x in S such that P holds. P↔Q means P if and only if Q, or if P then Q and if Q then P. Alternative notation P iff Q. We will come back to these concepts later.

A is a proper subset of B, notation A ⊂ B, if B has elements A does not have, in other words if B is not a subset of A, notation B ⊄ A.

Venn diagrams are geometrical representations of sets, which allow us to reason about subset relationships. Here is a Venn diagram of N, Z, Q and R.

Here U stands for the Universal set, the set of all objects under consideration. The rest of the Venn diagram says in a geometrical way, N ⊂ Z ⊂ Q ⊂ R.

A special set is the empty set: notation ∅, which contains no elements and is thus a subset of all sets, even the empty set.

A set composed of all bit strings of length x, contains all unique bit combinations of 0 and 1 that are of length x.

For example, a set of bit strings s of length 3, is {000, 001, 010, 011, 100, 101, 110, 111}

For example, the power set of the set S = {a, b, c} is P(S) = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

A set with n elements will have 2 to the nth power elements in its power set.

Before we move to tuples, let us do some quick self check exercises.

True or false:

S = {10, 20, 30, 40}

A = {a, b, c, d, e, f}

Tuples are useful to us because eg a Java method with multiple arguments uses an n-tuple to represent the argument list, and user defined lists can be modeled with n-tuples. Also, loop indices are tuples, eg in

for (i=0;i<3;i++) for (j=0;j<2;j++) body(i,j);Here, body gets called with (i,j)-tuples (0,0), (0,1), (1,0), (1,1), (2,0), and (2,1).

A={1,2} and B={a,b,c}

The Cartesian product of the sets A1,A2,…,An, denoted A1xA2x…xAn is the set of ordered n-tuples (a1,a2,…,an) where ai∈Ai, ∀i ∈ {1…n}.

**Set Union**, notation: A∪B, is the set
containing all elements in A or B.

**Set Intersection**, notation A∩B, is the set
containing all elements in both A and B.

Two sets are **disjoint** if their
intersection is empty

**Set Difference**, notation: A-B, is the set of elements in A
but not in B. This is also called the complement of B with respect to A.

**Set Complement** of A, notation U-A, is the complement of A wrt the Universal
set U.
Study the set identities below, using Venn diagrams to
convince your self of their validity in general.

IDENTITIES:

COMMUTATIVE LAWS:

Using U = {1,2,3,4,5,6,7,8,9}, A={1,2,3,4,5}, B={2,4,6,8}, C={3,4,5,6,7}.

ASSOCIATIVE LAWS:

DISTRIBUTIVE LAWS:

COMPLEMENT LAWS:

For instance if A={2.4, 1.6, 5.0,2.3} and B={1,2,3,4,5}, the floor function maps 2.4 → 2, 1.6 → 1, 5.0 → 5, and 2.3 →2.

In Java we would write for floor: int floor(double x){ … } and in that case the domain would be all double values, the codomain would be all int values.

The ** identity ** function Fid maps each element to itself: Fid(x)=x
∀ x ∈ A.

The ** square ** function maps each element x to x^{2}:

A function is ONE-TO-ONE (1to1) if for all elements in the range there is only one element in the domain, so for a 1 to 1 function f, if f(a)=f(b) then a=b for all a and b in the domain. The square function above is 1 to 1.

A function is **increasing** if when x<y, f(x)≤f(y) and **strictly increasing**
if when x<y, f(x)<f(y). All elements of the domain and codomain of these
functions must be comparable, eg N, Z, Q or R.

Increasing functions are important to us, because the run time of a
program is often an increasing function of the size of its input.