1
$\begingroup$

I'm doing some of the exercises in Susanna Epp's Discrete Mathematics with Applications, Fourth Edition and there's one answer to the exercises that I don't understand. In Exercise 1.3, No. 9.c:

What fraction of the relations from { 0, 1 } to { 1 } are functions?

And the answer is 1/4 (one-over-four). Can anyone tell me how to get to that answer?

To be honest, I barely understand the question.

  • 0
    Do you know what a relation is? Do you know what a function is? If yes, then write down all the relations from $\{ 0,1 \}$ to $\{1 \}$, work out which are functions, and count.2012-08-27

3 Answers 3

2

A relation on two sets is simply any subset of the Cartesian Product. The Cartesian Product here has 4 subsets each of which is a relation : $\varnothing, \{(0,1)\}, \{(1,1)\}, \{(0,1),(1,1)\}$. Out of these only the last one is a function since a function is a relation which maps 'all' elements of the domain to some element in the range (namely $1$ in this case).

2

Let $A$ and $B$ be sets. In our case, $A=\{0,1\}$ and $B=\{1\}$. But let us be general for a while.

A relation from $A$ to $B$ is any subset of the set of all ordered pairs $(a,b)$, where $a\in A$ and $b\in B$. In our case, there are only $2$ such ordered pairs, namely $(0,1)$ and $(1,1)$. So the set of ordered pairs is the set $\{(0,1),(1,1)\}$.

This is a two-element set. So it has $2^2$ subsets. We can list them all explicitly: they are $\emptyset,\quad \{(1,0)\},\quad \{(1,1)\}, \quad \{(0,1),(1,1)\}.$

Which of these $4$ sets of ordered pairs are functions from $A$ to $B$? Formally, a function from $A$ to $B$ is a set $F$ of ordered pairs $(a,b)$ such that for any $a\in A$, there is a unique $b\in B$ such that $(a,b)\in F$.

Here there is no uniqueness issue, since $B$ has only one element. But for every $a$ in $A$, we must have a $b$ such that $(a,b)\in F$. So that must hold for $a=0$, and also for $a=1$. The only set of ordered pairs that qualifies is $\{(0,1),(1,1)\}$: one set of ordered pairs, out of the $4$ sets of ordered pairs available.

0

A relation on $\{0,1\}$ to $\{1\}$ is a subset of $\{0,1\} \times \{1\} = \{(0,1), (1,1)\}$.

The four subsets are

1) $\emptyset$

2) $\{(0,1)\}$

3) $\{(1,1)\}$

4) $\{(0,1), (1,1)\}$

All of these are functions.

Probably the question is asking for how many functions from $\{0,1\} \rightarrow \{1\}$. Only 4) has the property that the domain is all of $\{0,1\}$.


Alternatively, instead of listing out all the possible relations, you can also use some combinatorics. Let $|A|$ denote the number of elements in the finite set $A$. $|A \times B| = |A| \times |B|$. Hence $\{0,1\} \times \{1\}$ has $2 \cdot 1 = 2$ elements. Let $\mathscr{P}(A)$ denote the set of all subsets of a finite set $A$. By some combinatorics, $|P(\mathscr{A})| = 2^{|A|}$. So there are $2^2 = 4$ subsets of $\{0,1\} \times \{1\}$, i.e. there are four relations from $\{0,1\} \rightarrow \{1\}$. Now the number of function $A \rightarrow B$ is $|B|^{|A|}$. The number of functions $\{0,1\} \rightarrow \{1\}$ is $1^{2} = 1$. Thus the ratio is $\frac{1}{4}$.