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

- All Categories 2.3K
- Chat 499
- Study Groups 18
- Petri Nets 9
- Epidemiology 3
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 67
- Azimuth Code Project 110
- Statistical methods 3
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

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

## Comments

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.

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

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\)?`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\\)?`

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

`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')`