Discrete Mathematics (H) Lecture 4 Notes

Basic Discrete Mathematics Objects

Sets

Introduction to Sets

Definition: Sets

A set is an unordered collection of objects. These objects are called elements or members.

We can represent a set by

• listing the elements, or
• define it by property, e.g.

Important sets:

• Natural numbers:
• Integers:
• Positive integers:
• Rationals:
• Real numbers:
• Complex numbers:

Interval notation: - - - -

Two sets are equal if and only if

Russell’s Paradox

Let , is a set of sets that are not members of themselves. Is or ?

• If , then does not satisfy the condition, so .
• If , then is included in the set , so .

The most common solution of this paradox in modern mathematics is the axiomatic set theory.

Two special sets:

• The universal set is the set of all objects under consideration, denoted as .
• The empty set is the set that contains no elements, denoted as or .

Venn Diagrams and Subsets

Definition: Subsets

A set is called a subset of iff every element of is also an element of , denoted as .

Definition: Proper Subsets

If , but , then we say is a proper subset of , denoted by .

Theorem: Empty Set

.

Proof: we substitute into the definition of subset relation Since the premise is always false, the statements holds.

Theorem: Reflexivity of Subset Relation

.

Proof: we substitute into the definition of subset relation This trivially holds.

The set relations can be visualized by using Venn diagrams, e.g. :

Cardinality

Definition: Cardinality

Let be a set. If there are exactly distinct elements in where is a nonnegative integer, we say that is a finite set and is the cardinality of , denoted by .

A set if infinite if it is not finite.

Power Set

Definition: Power Set

Given a set , the power set of is the set of all subsets of the set , denoted by .

Example

We can observe that .

Tuples

Definition: Tuple

The ordered n-tuple is the ordered collection that has its -th element. A -tuple is also called as an ordered pair.

Definition: Cartesian Product

Let and be sets. The Cartesian product of and , denoted as , is the set of all ordered pairs , where and . Hence We can easily generalize the Cartesian product to sets as follows:

It easy to observe that

Definition: Relations

A subset of the Cartesian product is called a relation from the set to the set .

Set Operations

Definition: Union

Let and be sets. The union of the sets amd , denoted by , is the set .

Definition: Intersection

The intersection of the set and , denoted by , is the set .

Definition: Complement

If is a set, then the complement of the set w.r.t. the universal set , denoted is the set , .

Definition: Difference

Let and be sets. The difference of and , denoted by , is the set containing the elements of that are not in , i.e. .

Definition: Disjoint Sets

Two sets and are called disjoint if their intersection is empty, i.e. .

Theorem: The Principle of Inclusion and Exclusion

This is very similar to the principle of inclusion and exclusion in probability.

Set Identities

Identity Laws

Domination Laws

Idempotent Laws

Identity Laws

Complementation Laws

Commutative Laws

Associative Laws

Distributive Laws

Associative Laws

Absorbtion Laws

Complement Laws

The set identities are extremely similar to that ones of logic. The proofs for them are also very close to the ones of logic.

For example, to prove .

• Proof by membership tables
• Proof by equivalence
• Proof by logical equivalences

Proof by membership tables:

1	1	0	0	0	0
1	0	0	1	1	1
0	1	1	0	1	1
0	0	1	1	1	1

Proof by equivalence: showing that

Proof by logical equivalences:

### Generalized Unions and Intersections The union of a collection of sets is the set that contains those elements that are members of at least one set in the collection .

The intersection of a collection of sets is the set that contains those elements that are members of all sets in the collection .

Computer Representation of Sets

A naive way to represent sets in computers is to explicitly store all the elements in a list. But this will make common set operations like lookup/insertion/deletion inefficient. A better solution is to assign a bit in a bit string to each element in the universal set and set the bit to 1 if the element is in the set, otherwise 0. By using this representation, each set of cardinality can be represented as a bit string . And the common set operations can be implemented easily and efficiently. The only problem is that this representation can waste memory.

Functions

Definition: Functions

Let and be two sets. A function from to , denoted by , is an assignment of exactly one element of to each element of . We write if is the unique element of assigned by the function to the element of .

To represent a function, we can either

• explicitly state the assignments between elements of the two sets, or
• by a formula.

Definition: Important Sets of Functions

Let be a function from to . We say that is the domain of and is the codomain of . If , is called the image of and is a preimage of . The range of is the set of all images of elements of , denoted by . We also say maps to .

Example

For a function:

• is the image of
• is a preimage of
• the domain of is
• the codomain of is
• the range of is

Definition: Image of a Subset

For a function and , the image of is a subset of that consists of the images of the elements of , denoted by , .

Definition: Injective Function

A function is called one-to-one or injective, iff implies for all in the domain of . In the case, is called an injection. Alternatively, a function is one-to-one iff whenever .

Definition: Surjective Function

A function is called onto or surjective, iff for every there is an element s.t. . In this case, is called a surjection. Alternatively, a function is onto iff all codomain elements are covered, i.e. .

Definition: Bijective Function

A function is called bijective, iff it is both injective and surjective.

Properties to prove	Method to prove
To show is injective	Show that
To show is not injective	Show that
To show is surjective	Show that
To show is not surjective	Show that

Tip

For a function with , is injective iff is surjective.

Proof.

• Only if: suppose that is injective. Let be elements of . Then for . Therefore, . But and . Therefore, .
• If: suppose that is surjective. Let be a listing of the elements of . Suppose that for some . Then, . But , a contradiction.

But note that this conclusion cannot be straightforwardly generalize to functions with infinite domain and codomain.

Let and be functions from to . Then and are also functions from to defined for all by

Definition: Inverse Function

Let be a bijection. The inverse of is the function that assigns to an element belonging to the unique element in s.t. , denoted by . Hence, when . In this case, is called an invertible function.

Caution

If is not a bijection, it is impossible to define the inverse function of .

Definition: Composition of Functions

Let be a function from to and let be a function from to . The composition of the functions and , denoted by , is defined by .

Suppose that is a bijection from to . Then and , where denote the identity functions on the sets and , respectively.