1.7 Binary Relations

For any binary relation \(R: A \to B \) and subset \(S \subseteq A \), let \( R(S) \) be the image of \(S \) under \(R \). An example of such an image is the doubling function with domain and codomain equal to the real numbers:

such that \(R(\{0,3,11\}) = \{0,6,22\} \). Another example, \(R(\mathbb{Z}) \), is the set of all even integers. For any finite set, we let \(|S| \) denotes the size (number of elements) of \(S \).

Now assume \(R \) is some total function and \(A \) is finite. Fill in the blanks to produce the strongest correct version of the following statements:

1. \(|R(A)| \) ____ \(|B| \)

   Exercise 1

   &nbsp;\(<\)&nbsp;

   &nbsp;\(\leq\)&nbsp;

   &nbsp;\(=\)&nbsp;

   &nbsp;\(\geq\)&nbsp;

   &nbsp;\(>\)&nbsp;
   Note that \(R(A)\subseteq B \).

2. If \(R \) is a surjection, then \(|A| \) ____ \(|B| \).

   Exercise 2

   &nbsp;\(<\)&nbsp;

   &nbsp;\(\leq\)&nbsp;

   &nbsp;\(=\)&nbsp;

   &nbsp;\(\geq\)&nbsp;

   &nbsp;\(>\)&nbsp;

3. If \(R \) is a surjection, then \(|R(A)| \) ____ \(|B| \).

   Exercise 3

   &nbsp;\(<\)&nbsp;

   &nbsp;\(\leq\)&nbsp;

   &nbsp;\(=\)&nbsp;

   &nbsp;\(\geq\)&nbsp;

   &nbsp;\(>\)&nbsp;

4. If \(R \) is an injection, then \(|R(A)| \) ____ \(|A| \).

   Exercise 4

   &nbsp;\(<\)&nbsp;

   &nbsp;\(\leq\)&nbsp;

   &nbsp;\(=\)&nbsp;

   &nbsp;\(\geq\)&nbsp;

   &nbsp;\(>\)&nbsp;

5. If \(R \) is a bijection, then \(|A| \) ____ \(|B| \).

   Exercise 5

   &nbsp;\(<\)&nbsp;

   &nbsp;\(\leq\)&nbsp;

   &nbsp;\(=\)&nbsp;

   &nbsp;\(\geq\)&nbsp;

   &nbsp;\(>\)&nbsp;
   CheckShow Answer