187 – Midterm 1

Here is the midterm.

Solutions follow.

Problem 1 concerns lists. We are given a collection of 5 objects, $\{0,1,2,3,4\},$ and we want to find:

1. The number of lists of length 2 where the entries come from these objects, and repetitions are allowed. We have that for each entry we can use 5 possible objects, for a total of $5\times 5=25$ lists.
2. The number of lists of length 2 where the entries come from these objects, and repetitions are required. Now, once we select the first entry (there are 5 possible ways of doing this), the second entry is completely determined. So we only have $5$ lists.
3. The number of lists of length 2 where the entries come from these objects, and repetitions are not allowed. There are two ways of counting: Either we simply notice that this is the total number of lists of length 2 (25), except for those that have repetitions (5), for a total of $25-5=20,$ or else we note that whatever first entry we choose (5 possibilities), this eliminates one of the 5 possible objects from being the second entry (so now we only have 4 possibilities for this entry), for a total of $5\times 4=20.$

The extra credit problem asked for the number of lists of length 3 whose entries come from $\{0,1,2,3,4\}$ and repetitions are required. Again, there are two ways of counting. The easiest way is simply to count of lists of length 3 ($5^3$) and subtract from them those lists that do not have repetitions ($5\times4\times 3$) for a total of $5^3-5\times 4\times 3=125-60=65$ lists. The second way counts the lists directly, but this is a bit more complicated. There are 5 possibilities for the first entry. If the second entry is the same, the third entry is arbitrary (so this gives us $5\times1\times 5=25$ lists so far). If the second entry is different (4 possibilities) then the last entry is either the same as the first or the second (2 possibilities), for a total of $5\times 4\times 2=40$ lists. Hence, the total number of lists we are looking for is $25+40=65.$

Problem 2 asks us to explain in what sense the statement $(\varphi\Leftrightarrow\psi)$ is equivalent to the statement $((\lnot\varphi)\Leftrightarrow(\lnot\psi)),$ and to prove that this is the case.

Two statements are equivalent precisely when they have the same truth values, i.e., they are both true in precisely the same cases and both are false in precisely the same cases. To see that this is the case, the easiest method is to compare the truth tables for both statements and see that they are the same. This is indeed the case: Both statements are true precisely when latex \varphi\$ and $\psi$ have the same truth value (be it true or false).

There is another way in which the equivalence can be analyzed. The statement $(A\Leftrightarrow B)$ is known to be equivalent to the conjunction $(A\Rightarrow B)\land(B\Rightarrow A).$ Let’s analyze when this conjunction holds, which is the same as saying that both implications must be true. Note that $(A\Rightarrow B)$ holds if $B$ is true. However, if $B$ is false, then the implication only holds if $A$ is also false. This is to say, $(\lnot B\Rightarrow\lnot A).$ This statement is called the contrapositive of $(A\Rightarrow B),$ and our analysis just showed that the two are equivalent.

In the case that interests us, we see that $(\varphi\Leftrightarrow\psi)$ is equivalent to $(\varphi\Rightarrow\psi)\land(\psi\Rightarrow\varphi)$ which is equivalent, considering the contrapositives of both implications, to $(\lnot\psi\Rightarrow\lnot\varphi)\land(\lnot\varphi\Rightarrow\lnot\psi),$ which is equivalent to $(\lnot\psi\Leftrightarrow\lnot\varphi),$ which in turn is equivalent to $(\lnot\varphi\Leftrightarrow\lnot\psi),$ as we wanted to see.

There is yet another way in which one can make sense of two statements $C$ and $D$ being equivalent, namely, that we can prove $D$ from $C$ and also prove $C$ from $D.$ A careful study of this sense would lead us to study provability in the context of mathematical logic.

Problem 3 asks us to show that if $A,B,C$ are sets and $x$ is an element such that $x\in(A\triangle B)$ and $x\in C,$ then also $x\in\bigl((A\cap C)\triangle(B\cap C)\bigr).$

To prove this, recall that $A\triangle B=(A\setminus B)\cup(B\setminus A).$ If $x$ belongs to this symmetric difference, then there are two possibilities: Either $x\in A\setminus B,$ or else $x\in B\setminus A.$

1. Assume that $x\in A\setminus B,$ and recall that this means that $x\in A$ but $x\notin B.$ Then (since we are also given that $x\in C$) we have that $x\in A\cap C$ (by definition of $\cap$) and $x\notin B\cap C$ (again, by definition of $\cap$). But then $x\in (A\cap C)\setminus (B\cap C)$ and therefore $x\in\bigl( (A\cap C)\setminus (B\cap C) \bigr)\cup \bigl( (B\cap C)\setminus (A\cap C) \bigr)$ (by definition of $\cup$), i.e., $x\in \bigl((A\cap C)\triangle(B\cap C)\bigr),$ by definition of $\triangle.$
2. Assuming that $x\in B\setminus A$ leads us to the same conclusion by essentially the same argument.

Since in both cases we have reached the desired conclusion, we are done.

Problem 4 asks to show that if $a|b$ and $x$ is divisible by $b,$ then $a$ is a factor of $x.$

The problem essentially asked us to remember that “$c$ is divisible by $d$” means the same as $d|c$ and that “$d$ is a factor of $c$.” All three statements mean that $c,d$ are integers and there is an integer $e$ such that $de=c.$

We are given that $a|b$ and $b|x.$ There are then integers $y$ and $z$ such that $ay=b$ and $bz=x.$ Then, multiplying the first equation by $z,$ we get $(ay)z=bz=x.$ But $(ayz)=a(yz),$ and it follows that there is an integer $t$ (namely, $t=yz$) such that $at=x.$ This is the definition of $a|x,$ which is what we needed to prove.

Problem 5 asks us to count the number of positive divisors of $3\times 4\times 5\times 6\times 7.$

To find this number, note that $3\times 4\times 5\times 6\times 7=2^3\times 3^2\times 5^1\times 7^1$ and therefore any divisor will have the form $2^a\times 3^b\times 5^c\times 7^d$ where $a,b,c,d$ are integers with $0\le a\le3,$ $0\le b\le 2,$ $0\le c\le 1,$ and $0\le d\le 1.$

This means that the number of divisors is the same as the number of  lists $(a,b,c,d)$ with $a,b,c,d$ as explained. There are 4 possibilities for $a,$ 3 for $b,$ 2 for $c,$ and 2 for $d,$ for a total of $4\times 3\times 2\times 2=48$ lists, and therefore 48 is the number of positive divisors of $3\times 4\times 5\times 6\times 7.$