patternMinor
What is a quotient structure?
Viewed 0 times
quotientstructurewhat
Problem
I was reading a paper here, and it mentioned "quotient structure" in the following sentence (third page, second paragraph of the paper)
In order to obtain a representation of terms truly isomorphic to
λ-terms, we need to build a quotient structure, quotient the set of
raw terms with respect to alpha-equivalence. This construction based
on a quotient corresponds very closely to the of presentation from
standard textbooks on λ-calculus.
I am hoping that someone could point me a good tutorial on quotient structures.
In order to obtain a representation of terms truly isomorphic to
λ-terms, we need to build a quotient structure, quotient the set of
raw terms with respect to alpha-equivalence. This construction based
on a quotient corresponds very closely to the of presentation from
standard textbooks on λ-calculus.
I am hoping that someone could point me a good tutorial on quotient structures.
Solution
The idea is that two expressions which are α-equivalent are not meaningfully different. λx.λy.x and λz.λy.z are technically different expressions. They are α-equivalent, though, they intuitively represent the same thing. In most circumstances, differentiating between them is useless at best, counter-productive at most.
The quotient set is a formal definition that allows to say “we consider α-equivalent expressions to actually be the same”. So what is this formal definition?
Equivalence relation
First of all, an equivalence relation ~ on a set S is a binary relation that is:
Examples:
Equivalence class and quotient set
Now, given S and ~, and a in S, the equivalence class of a for ~ is the set [a] of all x in S such that x ~ a.
By reflexivity, it is clear that each x in S is in [x].
Moreover, using symmetry and transitivity, you can show that if x in [y], then [y] = [x]. So each x is in a single equivalence class, two distinct equivalence classes do not intersect.
Given S and ~, the set {[x] | x in S} of every equivalent class is a partition of S. This partition is called quotient set of S by ~ (usually noted S/~).
Example:
For the relation = (mod 5) on Z, the equivalence classes are [0], [1], [2], [3], [4]. Each integer is equal to a single 0 ≤ n ≤ 4 modulo 5.
Usually, one doesn’t bother writing the [ ] when it’s not necessary.
The quotient set is a formal definition that allows to say “we consider α-equivalent expressions to actually be the same”. So what is this formal definition?
Equivalence relation
First of all, an equivalence relation ~ on a set S is a binary relation that is:
- reflexive: for every x in S, x ~ x.
- symmetric: for x, y in S, if x ~ y, then y ~ x.
- transitive: for x, y, z in S, if x ~ y and y ~ z, then x ~ z.
Examples:
- For any set, = is an equivalence relation.
- a = b (mod n) is an equivalence relation.
- α-equivalence is an equivalence relation.
Equivalence class and quotient set
Now, given S and ~, and a in S, the equivalence class of a for ~ is the set [a] of all x in S such that x ~ a.
By reflexivity, it is clear that each x in S is in [x].
Moreover, using symmetry and transitivity, you can show that if x in [y], then [y] = [x]. So each x is in a single equivalence class, two distinct equivalence classes do not intersect.
Given S and ~, the set {[x] | x in S} of every equivalent class is a partition of S. This partition is called quotient set of S by ~ (usually noted S/~).
Example:
For the relation = (mod 5) on Z, the equivalence classes are [0], [1], [2], [3], [4]. Each integer is equal to a single 0 ≤ n ≤ 4 modulo 5.
Usually, one doesn’t bother writing the [ ] when it’s not necessary.
Context
StackExchange Computer Science Q#70858, answer score: 6
Revisions (0)
No revisions yet.