cs160 Tutorial 1

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:

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.

venn

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.

Bit String

A bit string a sequence of zero or more bits, where a bit is represented by 0 or 1. A bit string's length is the number of bits in the string.

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}

Power Set

The power set of a set, S, is a new set containing all the subsets of that set. P(S) is the notation for the power set S. A power set is useful when testing all combinations of elements of a set to see if they satisfy some particular property.

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.

Quick Test

True or false:

1. {1,2,3} = {1,3,2}
false
true

2. N is finite
false
true

3. | {1,1,1} | = 1
false
true

4. ∀ set A:(A⊆A)
false
true

5. ∀ set A:(A⊂A)
false
true

6. What is the set of bit strings s of size 4?
{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}
{0000, 0001,0010, 0011, 0100}

S = {10, 20, 30, 40}

7. What is the powerset, P(S)?
{{10}, {20}, {30}, {40}, {10, 20}, {10, 30}, {10, 40}, {20, 30}, {20, 40}, {30, 40}, {10, 20, 30}, {10, 20, 40}, {10, 30, 40}, {20, 30, 40}, {10, 20, 30, 40}}
{{}, {10}, {20}, {30}, {40}, {10, 20}, {10, 30}, {10, 40}, {20, 40}, {10, 20, 30}, {10, 20, 40}, {10, 30, 40}, {10, 20, 30, 40}}
{{}, {10}, {20}, {30}, {40}, {10, 20}, {10, 30}, {10, 40}, {20, 30}, {20, 40}, {30, 40}, {10, 20, 30}, {10, 20, 40}, {10, 30, 40}, {20, 30, 40}, {10, 20, 30, 40}}

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

8. How many elements does P(A) have?
16
32
64

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}

9. How many elements does AxB have?
5
6
8

10. Is (a,a) an element of AxB?
no
yes

11. Is (1,a) an element of AxB?
no
yes

12. Is (2,c) an element of BxA?
no
yes

13. Is (2,2) an element of AxA?
no
yes

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}

14. (1,p,a) is an element of
AxBxC
BxCxA
AxCxB

15. (p,p,1) is an element of
AxBxC
BxCxA
CxCxA

16. The number of elements in AxBxC is
7
12
8

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:

17. A∪∅ = A∩A = A∪A =
{1,2,3,4,5}
{2,4,6,8}

COMMUTATIVE LAWS:

18. A ∪ B = B ∪ A =
{1,2,3,4,5,6,8}
{2,4,6,8}

19. A ∩ B = B ∩ A =
{1,2,3,4,5}
{2,4}

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:

20. A∪(B∪C) = (A∪B)∪C =
{1,2,3,4,5}
{1,2,3,4,5,6,7,8}

21. A∩(B∩C) = (A∩B)∩C =
{2,4}
{4}

DISTRIBUTIVE LAWS:

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

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

COMPLEMENT LAWS:

24. A∪(U-A) =
{1,2,3,4,5}
{1,2,3,4,5,6,7,8,9}

25. A∩(U-A) =
{}
{1,2,3,4,5,6,7,8,9}

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.

floor
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 x2:

square

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

26. Is floor 1to1?
no
yes

27. Is increment: x→(x+1) 1to1?
no
yes

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:

28. Is floor increasing?
no
yes

29. Is floor strictly increasing?
no
yes

29. Is increment increasing?
no
yes

31. Is increment strictly increasing?
no
yes

32. Is square increasing?
no
yes

33. For domain N, is square increasing?
no
yes

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