Howdy, Stranger!
It looks like you're new here. If you want to get involved, click one of these buttons!
Categories
- All Categories 2.4K
- Chat 503
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718
Options
Exercise 62 - Chapter 3
We claim that there is exactly one graph homomorphism \( \alpha : G \rightarrow H \) such that \( \alpha_{Arrow}(a) = d \).
- What is the other value of \( \alpha_{Arrow}\), and what are the three values of \( \alpha_{Vertex} \)?
- Draw \( \alpha_{Arrow} \) as two lines connecting the cells in the ID column of \(G(Arrow)\) to those in the ID column of \(H(Arrow)\). Similarly, draw \( \alpha_{Vertex} \) as connecting lines.
- Check the source column and target column and make sure that the matches are natural, i.e. that “alpha-then-source equals source-then-alpha” and similarly for “target”.
$$ \begin{matrix} G := & & \begin{array}{c|cc} Arrow & source & target \\ \hline a & 1 & 2 \\ b & 2 & 3 \end{array} & & \begin{array}{c|} Vertex \\ \hline 1 \\ 2 \\ 3 \end{array} \\ H := & \begin{array}{c|cc} Arrow & source & target \\ \hline c & 4 & 5 \\ d & 4 & 5 \\ e & 5 & 5 \end{array} & & \begin{array}{c|} Vertex \\ \hline 4 \\ 5 \end{array} & \end{matrix} $$
Comments
The graph instances are offset so you can more easily complete the exercise.
The graph instances are offset so you can more easily complete the exercise.Since \(\alpha_\mathrm{Arrow}(a)=d\), it must also be the case that \(\alpha_\mathrm{Vertex}(1)=4\) and \(\alpha_\mathrm{Vertex}(2)=5\). Since \(b:2\to3\), \(\alpha_\mathrm{Arrow}(b)\) must start at \(5\), the only such arrow in \(\mathcal{H}\) is \(e\). So, \(\alpha_\mathrm{Arrow}(b)=e\) and \(\alpha_\mathrm{Vertex}(3)=5\).
The first line in \(G(Arrow)\) goes to the middle line of \(H(Arrow)\), the second line of \(G(Arrow)\) goes to the last line of \(H(Arrow)\). The first line of \(G(Vertex)\) goes to the first line of \(H(Vertex)\), the last two lines of \(G(Vertex)\) go to the last line of \(H(Vertex)\).
\(s\circ\alpha_\mathrm{Arrow}(a)=s(d)=4=\alpha_\mathrm{Vertex}(1)=\alpha_\mathrm{Vertex}\circ s(a)\). \(s\circ\alpha_\mathrm{Arrow}(b)=s(e)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ s(b)\). \(t\circ\alpha_\mathrm{Arrow}(a)=t(d)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ t(a)\). \(t\circ\alpha_\mathrm{Arrow}(b)=t(e)=5=\alpha_\mathrm{Vertex}(3)=\alpha_\mathrm{Vertex}\circ t(b)\). So, the matches are natural.
1. Since \\(\alpha_\mathrm{Arrow}(a)=d\\), it must also be the case that \\(\alpha_\mathrm{Vertex}(1)=4\\) and \\(\alpha_\mathrm{Vertex}(2)=5\\). Since \\(b:2\to3\\), \\(\alpha_\mathrm{Arrow}(b)\\) must start at \\(5\\), the only such arrow in \\(\mathcal{H}\\) is \\(e\\). So, \\(\alpha_\mathrm{Arrow}(b)=e\\) and \\(\alpha_\mathrm{Vertex}(3)=5\\). 2. The first line in \\(G(Arrow)\\) goes to the middle line of \\(H(Arrow)\\), the second line of \\(G(Arrow)\\) goes to the last line of \\(H(Arrow)\\). The first line of \\(G(Vertex)\\) goes to the first line of \\(H(Vertex)\\), the last two lines of \\(G(Vertex)\\) go to the last line of \\(H(Vertex)\\). 3. \\(s\circ\alpha_\mathrm{Arrow}(a)=s(d)=4=\alpha_\mathrm{Vertex}(1)=\alpha_\mathrm{Vertex}\circ s(a)\\). \\(s\circ\alpha_\mathrm{Arrow}(b)=s(e)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ s(b)\\). \\(t\circ\alpha_\mathrm{Arrow}(a)=t(d)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ t(a)\\). \\(t\circ\alpha_\mathrm{Arrow}(b)=t(e)=5=\alpha_\mathrm{Vertex}(3)=\alpha_\mathrm{Vertex}\circ t(b)\\). So, the matches are natural.