patternMinor
Is "represents" a symmetric relation in the provided answer to TAOCP exercise 1.1.9?
Viewed 0 times
symmetrictheanswertaocpexerciseprovidedrelationrepresents
Problem
In exercise 1.1.9 of volume 1 of The Art of Computer Programming, the reader is asked to
formulate a set-theoretic definition for the concept "$C_2$ is a representation of $C_1$"
where $C_1$ and $C_2$ are computational methods described in the previous few pages (reproduced here so the question can be answered without needing the book).
Let us formally define a computational method to be a quadruple $(Q,I,\Omega,f)$, in which $Q$ is a set containing subsets $I$ and $Ω$, and $f$ is a function from $Q$ into itself. [...] The four quantities $Q$, $I$, $\Omega$, $f$ are intended to represent repectively the state of the computation, the input, the output, and the computational rule.
When I looked at the answer in the back, this definition was proposed:
For example we can say $C_2$ represents $C_1$ if there is a function $g$ from $I_1$ into $I_2$, a function $h$ from $Q_2$ into $Q_1$, and a function $j$ from $Q_2$ into the positive integers, satisfying the following conditions:
Later on, discussing this definition, Knuth writes (emphasis mine):
The relation "$C_2$ represents $C_1$" generates an equivalence relation in which two computational methods apparently are equivalent if and only if they compute isomorphic functions of their inputs ...
To be an equivalence relation, a relation must be symmetric. That is, for a relation $R$, $(a, b) \in R$ implies $(b, a) \in R$. I don't believe this is true of the given definition.
Consider the computational methods $C_1$ and $C_2$, where
\begin{align*}
C_2 &= \{Q_2, I_2, \Omega_2, f_2\}\\
C_1 &= \{Q_1, I_1, \Omega_1, f_1\}\\\\
I_2 &= \{a_1, a_2\}\\
\Omega_2 &= \{b_1, b_2\}\\
Q_2 &= I_2 \cup \Omega_2\\
f_2 &= \{(a_1, b
formulate a set-theoretic definition for the concept "$C_2$ is a representation of $C_1$"
where $C_1$ and $C_2$ are computational methods described in the previous few pages (reproduced here so the question can be answered without needing the book).
Let us formally define a computational method to be a quadruple $(Q,I,\Omega,f)$, in which $Q$ is a set containing subsets $I$ and $Ω$, and $f$ is a function from $Q$ into itself. [...] The four quantities $Q$, $I$, $\Omega$, $f$ are intended to represent repectively the state of the computation, the input, the output, and the computational rule.
When I looked at the answer in the back, this definition was proposed:
For example we can say $C_2$ represents $C_1$ if there is a function $g$ from $I_1$ into $I_2$, a function $h$ from $Q_2$ into $Q_1$, and a function $j$ from $Q_2$ into the positive integers, satisfying the following conditions:
- a) If $x$ is in $I_1$ then $h(g(x)) = x$
- b) If $q$ is in $Q_2$ then $f_1(h(q)) = h(f_2^{[j(q)]}(q))$, where $f_2^{[j(q)]}$ means that the function $f_2$ is to be iterated $j(q)$ times.
- c) If $q$ is in $Q_2$ then $h(q)$ is in $\Omega_1$ if and only if $q$ is in $\Omega_2$
Later on, discussing this definition, Knuth writes (emphasis mine):
The relation "$C_2$ represents $C_1$" generates an equivalence relation in which two computational methods apparently are equivalent if and only if they compute isomorphic functions of their inputs ...
To be an equivalence relation, a relation must be symmetric. That is, for a relation $R$, $(a, b) \in R$ implies $(b, a) \in R$. I don't believe this is true of the given definition.
Consider the computational methods $C_1$ and $C_2$, where
\begin{align*}
C_2 &= \{Q_2, I_2, \Omega_2, f_2\}\\
C_1 &= \{Q_1, I_1, \Omega_1, f_1\}\\\\
I_2 &= \{a_1, a_2\}\\
\Omega_2 &= \{b_1, b_2\}\\
Q_2 &= I_2 \cup \Omega_2\\
f_2 &= \{(a_1, b
Solution
I slept on it and remembered there was another wording issue that was bugging me: "generates an equivalence relation". I wasn't familiar with it and assumed it just meant "is an equivalence relation". Turns out I was wrong. It has a very specific meaning that Wikipedia describes thusly:
Given any binary relation $A \subset X \times X$ on $X$, the equivalence relation generated by $A$ is the intersection of the equivalence relations on $X$ that contain $A$.
In short, no, "represents" isn't a symmetric relation, nor did Knuth claim it is; he claimed that an equivalence relation could be constructed from it, which is true. Apparently my "knowledge of high school algebra", listed as the primary prerequisite to reading, is lacking.
Given any binary relation $A \subset X \times X$ on $X$, the equivalence relation generated by $A$ is the intersection of the equivalence relations on $X$ that contain $A$.
In short, no, "represents" isn't a symmetric relation, nor did Knuth claim it is; he claimed that an equivalence relation could be constructed from it, which is true. Apparently my "knowledge of high school algebra", listed as the primary prerequisite to reading, is lacking.
Context
StackExchange Computer Science Q#115874, answer score: 3
Revisions (0)
No revisions yet.