#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Exercise 21 - Chapter 1

edited July 2018

Answer the following questions for each of the relations below

1: Find two sets A and B and a function f : A → B that is injective but not surjective.

2: Find two sets A and B and a function f : A → B that is surjective but not injective.

Now consider the four relations shown here:

For each relation, answer the following two questions.

3: Is it a function?

4: If not, why not? If so, is it injective, surjective, both, or neither?

In earlier versions of the text the questions were in a different order [ 3, 4, 1, 2].

• Options
1.
1. f1 and f4 are functions. f2 and f3 are not.
2. Letting A and B be the left and right sets. $$\forall a \in A, f1(a) \in B \wedge f4(a) \in B$$. However, for both f3 and f2 $$\exists a \in A \text{ s.t. } f(a) \notin B$$. For f2 it's $$\circ$$, for f3 it's $$\bullet$$.
3. To have an injective, but not surjective, function $$|A| \lt |B|$$. An example of this would be $$A = \{1,2,3\}$$ and $$B = \{1,2,3,4,5,6\}$$ with $$f (a) = 2a$$. for each b in B either there is a (singular) a in A which maps to it or no a maps to it (at most one).
4. To have a surjective, but not injective, function we require the opposite: $$|A| \gt |B|$$. Using the same two sets from part 3, we can define $$g(b) = \lceil \frac{b}{2} \rceil$$. Each of the 3 elements of A will be mapped to, but each by 2 elements of B.

If the sizes of A and B are equal, then we can find functions which are both surjective and injective or functions which are neither. However we cannot find functions which are one or the other.

Comment Source:1. f1 and f4 are functions. f2 and f3 are not. 2. Letting A and B be the left and right sets. \$$\forall a \in A, f1(a) \in B \wedge f4(a) \in B \$$. However, for both f3 and f2 \$$\exists a \in A \text{ s.t. } f(a) \notin B\$$. For f2 it's \$$\circ\$$, for f3 it's \$$\bullet\$$. 3. To have an injective, but not surjective, function \$$|A| \lt |B|\$$. An example of this would be \$$A = \\{1,2,3\\}\$$ and \$$B = \\{1,2,3,4,5,6\\}\$$ with \$$f (a) = 2a\$$. for each b in B either there is a (singular) a in A which maps to it or no a maps to it (at most one). 4. To have a surjective, but not injective, function we require the opposite: \$$|A| \gt |B|\$$. Using the same two sets from part 3, we can define \$$g(b) = \lceil \frac{b}{2} \rceil\$$. Each of the 3 elements of A will be mapped to, but each by 2 elements of B. If the sizes of A and B are equal, then we can find functions which are both surjective and injective or functions which are neither. However we cannot find functions which are one or the other.
• Options
2.
edited April 2018

Nice! It's fun to think about infinite sets, too.

Puzzle. If $$A$$ and $$B$$ are possibly infinite sets, and there's an injection $$f: A \to B$$ and an injection $$g: B \to A$$, is there a bijection between $$A$$ and $$B$$?

Puzzle. If $$A$$ and $$B$$ are possibly infinite sets, and there's a surjection $$f: A \to B$$ and an surjection $$g: B \to A$$, is there a bijection between $$A$$ and $$B$$?

Comment Source:Nice! It's fun to think about infinite sets, too. **Puzzle.** If \$$A\$$ and \$$B\$$ are possibly infinite sets, and there's an injection \$$f: A \to B\$$ and an injection \$$g: B \to A\$$, is there a bijection between \$$A\$$ and \$$B\$$? **Puzzle.** If \$$A\$$ and \$$B\$$ are possibly infinite sets, and there's a surjection \$$f: A \to B\$$ and an surjection \$$g: B \to A\$$, is there a bijection between \$$A\$$ and \$$B\$$?
• Options
3.

possibly a related question on infinite sets is in physics arxiv . org 1208.5424 (s. shelah, etc.) which i think is about whether there are infinite cardinals or sets called p and t (etc.) in between the integers (countable inifnity) and the continuum. the answer there seems to be if there are then there is only one so p=t for all p, t between aleph 0 and the continuum.

i had to look up injective, surjective, recently but I have to look them up again. One means its 1 to 1 (like an isomorphism) , the other is many to 1 (like a homomorphism) if i recall. I like 'self-inverse functions' , and also 'inverse problems' (eg marc kac 'can you tell the shape of a drum by how it sounds')

Comment Source:possibly a related question on infinite sets is in physics arxiv . org 1208.5424 (s. shelah, etc.) which i think is about whether there are infinite cardinals or sets called p and t (etc.) in between the integers (countable inifnity) and the continuum. the answer there seems to be if there are then there is only one so p=t for all p, t between aleph 0 and the continuum. i had to look up injective, surjective, recently but I have to look them up again. One means its 1 to 1 (like an isomorphism) , the other is many to 1 (like a homomorphism) if i recall. I like 'self-inverse functions' , and also 'inverse problems' (eg marc kac 'can you tell the shape of a drum by how it sounds')