Home Syllabus Schedule Tutorials Notes Ram CT

Tutorial 1: Sets and Functions

Study Rosen chapter 2 and the slides on sets and functions.

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:

∀ x:( x ∈ A ↔ x ∈ B)

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.

Subsets

A is a subset of B iff every element of A is also an element of B, notation: A ⊆ B

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.

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

Quick Test

True or false:

Tuples

Tuples are ordered collections, as opposed to sets, which are unordered. So eg (1,2,3) is a tuple and it is different from (2,1,3). An n-tuple is an ordered collection of n elements (a1,a2,…,an). Also as opposed to sets, tuples can have the same elements, eg (1,1,1) is a perfectly fine 3=tuple. A 2-tuple (a,b) is an ordered pair. Two ordered pairs (a,b) and (c,d) are equal iff a=c and b=d.

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).

Cartesian Products

The Cartesian product of two sets A and B, notation AxB, is the set of all ordered pairs (a,b) where a∈A and b∈B. For instance in the loop above the loop indices are the Cartesian product of {0,1,2}x{0,1}.

Quick Test

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}.

Quick Test

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

Set Operations

Set operations take sets as inputs and produce sets as outputs. Check Rosen for nice Venn diagrams of the following operations: Union, Intersection, difference, complement.

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.

Quick Test

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}.

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:

Functions

A function f from set A to set B, notation f:A→B maps each element a∈A to exactly one element b∈ B.

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.

Notice that not necessarily all elements of B are mapped to. Also notice that an element of B can be mapped to more than once (2 in our example above), but each element of A is mapped to exactly one element of B. We call A the domain and B the codomain . The range is the subset of B that is mapped to, here the range is {1,2,5}.

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²:

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.

Quick Test

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.

Quick Test

For domain R: