Discrete Mathematics

Class 9: Relations, Finite Set Cardinality


This week you should finish reading MCS Chapter 4 (section 4.5) and Section 5.1. We will discuss Induction (Section 5.1) next class.

Problem Set 4 is due Friday at 6:29pm. The original version of Problem Set 4, Question 6, asked for a function, when we really meant to ask for a total function (as we defined it in class today, and the book defines it). The problem set is updated now to specify this. If you already answered the original question, you do not need to update your answer, just indicate clearly for which questions the function you defined is partial. Sorry for the confusion!

Problem Set 5 (not yet posted) will be due Friday, 29 September.

Exam 1 will be in-class on Thursday, 5 October. It will cover Classes 1 - 11, Problem Sets 1 - 5, and MCS Chapters 1 - 5.

Total and Partial Functions

A function is a mathematical datatype that associates elements from one set, called the domain, with elements from another set, called a codomain.

$$ f: \textrm{\em domain} \rightarrow \textrm{\em codomain} $$

If the function is total, every element of the domain has one associated codomain element; if the function is partial, there may be elements of the domain that do not have an associated codomain element.

Relation Relationships

Definition review: binary relation, $R$, consists of a domain set, $A$, and a codomain set, $B$, and a subset of $A \times B$ called the graph of $R$.

For each statement below, give the name and at least one example.

  • A binary relation where no element of $A$ has more than one outgoing edge:


  • A binary relation where every element of $A$ has exactly one outgoing edge:


  • A binary relation where every element of $B$ has exactly one incoming edge:


  • A binary relation where every element of $A$ has exactly one outgoing edge and every element of $B$ has exactly one incoming edge:


If there exists a bijective relation between $S$ and $T$ defined by the graph $G$ which of these must be true:

a. there exists some injective relation between $S$ and $T$. b. there exists some bijective relation between $T$ and $S$. c. there exists a total function, $f: S \rightarrow T$. d. $S - T = \emptyset$. e. the number of elements of $S$ is equal to the number of elements of $T$. f. $G - (S \times T) = \emptyset$. g. $(S \times T) - G = \emptyset$. h. $(S \times T) - G \neq \emptyset$.

Relation Practice

The inverse of a relation $R: A \rightarrow B, G \subseteq A \times B$ is defined by reversing all the arrows: $$ R^{-1}: B \rightarrow A, G^{-1} \subseteq B \times A $$

$$ (b, a) \in G^{-1} \iff \fillin\fillin\fillin\fillin $$

What does it mean if $R \equiv R^{-1}$?

Set Cardinality

Finite Cardinality. The book’s definition is: ``If $A$ is a finite set, the cardinality of $A$, written $|A|$, is the number of elements in $A$.”

Does this definition require adding a new fundamental set operation, or is it meaningful with just the set operations we have defined?

Alternate definition: The cardinality of the set $$ N_k = { n | n \in \mathbb{N} \wedge n < k } $$ is $k$. (Next class, we’ll use this to define the cardinality of any set. You should be able to figure out how to do this on your own with what you know now.)