SET and Relation flash cards

1. 1.If $n(A)=p$ and $n(B)=q$, find the number of relations from $A$ to $B$ and the number of functions from $A$ to $B$.

   Relations $=2^{pq}$ (subsets of $A\times B$); Functions $=q^{p}$.

   Hint: Relations count subsets of $A\times B$; functions assign one image to each element of $A$.

2. 2.State the general formula for $n(A\cup B\cup C)$ using the inclusion-exclusion principle.

   $n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C)$.

   Hint: Add singles, subtract pairwise, add back the triple intersection.

3. 3.For a function $f:A\to B$, define one-one (injective), onto (surjective), and bijective in terms of counting.

   One-one: $f(x_1)=f(x_2)\Rightarrow x_1=x_2$; onto: range $=B$ (every element of $B$ has a pre-image); bijective: both hold, so $f^{-1}$ exists, and for finite sets $n(A)=n(B)$.

   Hint: Think distinct inputs vs distinct outputs, and whether every element of $B$ is covered.

4. 4.If $f(x)$ has domain $D_1$ and $g(x)$ has domain $D_2$, what is the domain of $(f+g)(x)$, $(fg)(x)$, and $\left(\dfrac{f}{g}\right)(x)$?

   For $f+g$ and $fg$: domain $=D_1\cap D_2$; for $f/g$: domain $=D_1\cap D_2$ excluding points where $g(x)=0$.

   Hint: Intersection of domains, plus an extra restriction for division.

5. 5.For a relation $R$ on set $A$, state the conditions for $R$ to be reflexive, symmetric, and transitive (an equivalence relation).

   Reflexive: $(a,a)\in R\ \forall a\in A$; Symmetric: $(a,b)\in R\Rightarrow (b,a)\in R$; Transitive: $(a,b)\in R$ and $(b,c)\in R\Rightarrow (a,c)\in R$.

   Hint: Same element, swap, chain.

6. 6.Let $A=\{1,2,3,4\}$. How many equivalence relations on $A$ contain the pair $(1,2)$?

   Since $(1,2)$ forces $1$ and $2$ into the same block, the count equals the number of partitions of the effectively $3$-element collection $\{\{1,2\},3,4\}$. This is the Bell number $B_3=5$: namely $\{1,2,3,4\}$, $\{1,2,3\}\{4\}$, $\{1,2,4\}\{3\}$, $\{1,2\}\{3,4\}$, and $\{1,2\}\{3\}\{4\}$. So there are 5 such equivalence relations.

   Hint: Merge $1$ and $2$ into one unit and count partitions of the reduced set.

7. 7.How many equivalence relations on $\{1,2,3,4\}$ contain both $(1,2)$ and $(2,3)$?

   Transitivity and symmetry force $1,2,3$ into one block, so we are really partitioning $\{\{1,2,3\},4\}$, a $2$-element collection. The number of partitions of a $2$-element set is $B_2=2$: either $\{1,2,3,4\}$ as one block, or $\{1,2,3\}\{4\}$ as two blocks. Hence the answer is 2.

   Hint: First find the smallest block forced by both pairs via transitivity.

8. 8.What is the total number of equivalence relations that can be defined on a $5$-element set?

   Equivalence relations on a set correspond bijectively to its set partitions, so the count is the Bell number $B_5$. Using $B_5=\sum_k S(5,k)=1+15+25+10+1$, we get $B_5=52$. So there are 52 equivalence relations.

   Hint: Equivalence relations correspond exactly to partitions of the set.

9. 9.How many equivalence relations on $\{1,2,3,4,5\}$ have exactly $3$ equivalence classes?

   This equals the Stirling number of the second kind $S(5,3)$, the number of ways to partition a $5$-set into $3$ nonempty blocks. Using the recurrence $S(5,3)=3\cdot S(4,3)+S(4,2)=3(6)+7$, we get $S(5,3)=25$. So there are 25 such equivalence relations.

   Hint: Count partitions of the $5$-set into exactly $3$ nonempty blocks.

10. 10.How many equivalence relations on $\{1,2,3,4\}$ have exactly $2$ equivalence classes?

    This equals $S(4,2)$, the number of ways to split a $4$-element set into $2$ nonempty unordered blocks. Splitting by block-size pattern: a $1{+}3$ split gives $4$ partitions (choice of singleton), and a $2{+}2$ split gives $\binom{4}{2}/2=3$ partitions (dividing by $2$ since the two blocks are unordered). Total $4+3=7$, matching $S(4,2)=2^{3}-1=7$. So there are 7 such equivalence relations.

    Hint: Use $S(4,2)=2^{n-1}-1$ or split by block sizes $1{+}3$ and $2{+}2$.

11. 11.Define a relation on $\mathbb{Z}$ by $a\,R\,b$ iff $5\mid (a-b)$. Show $R$ is an equivalence relation and state how many equivalence classes it has.

    Reflexive: $5\mid(a-a)=0$. Symmetric: if $5\mid(a-b)$ then $5\mid(b-a)=-(a-b)$. Transitive: if $5\mid(a-b)$ and $5\mid(b-c)$ then $5\mid[(a-b)+(b-c)]=(a-c)$. So $R$ is an equivalence relation, and its classes are exactly the residue classes mod $5$: $[0],[1],[2],[3],[4]$, giving 5 equivalence classes.

    Hint: Check the three defining properties directly using divisibility.

Open the interactive deck for the other 74 cards, with self-grading so the ones you keep missing come back.