Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Chris Eagle Aug 27 '12 at 6:48

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.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.