Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Canonical form
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Definition== Given a set ''S'' of objects with an [[equivalence relation]] ''R on S'', a canonical form is given by designating some objects of ''S'' to be "in canonical form", such that every object under consideration is equivalent to exactly one object in canonical form. In other words, the canonical forms in ''S'' represent the equivalence classes, once and only once. To test whether two objects are equivalent, it then suffices to test equality on their canonical forms. A canonical form thus provides a [[classification theorem]] and more, in that it not only classifies every class, but also gives a distinguished (canonical) [[representative (mathematics)|representative]] for each object in the class. Formally, a canonicalization with respect to an equivalence relation ''R'' on a set ''S'' is a mapping ''c'':''S''β''S'' such that for all ''s'', ''s''<sub>1</sub>, ''s''<sub>2</sub> β ''S'': #''c''(''s'') = ''c''(''c''(''s'')) ([[idempotence]]), #''s''<sub>1</sub> ''R'' ''s''<sub>2</sub> if and only if ''c''(''s''<sub>1</sub>) = ''c''(''s''<sub>2</sub>) (decisiveness), and #''s'' ''R'' ''c''(''s'') (representativeness). Property 3 is redundant; it follows by applying 2 to 1. In practical terms, it is often advantageous to be able to recognize the canonical forms. There is also a practical, algorithmic question to consider: how to pass from a given object ''s'' in ''S'' to its canonical form ''s''*? Canonical forms are generally used to make operating with equivalence classes more effective. For example, in [[modular arithmetic]], the canonical form for a residue class is usually taken as the least non-negative integer in it. Operations on classes are carried out by combining these representatives, and then reducing the result to its least non-negative residue. The uniqueness requirement is sometimes relaxed, allowing the forms to be unique up to some finer equivalence relation, such as allowing for reordering of terms (if there is no natural ordering on terms). A canonical form may simply be a convention, or a deep theorem. For example, polynomials are conventionally written with the terms in descending powers: it is more usual to write ''x''<sup>2</sup> + ''x'' + 30 than ''x'' + 30 + ''x''<sup>2</sup>, although the two forms define the same polynomial. By contrast, the existence of [[Jordan canonical form]] for a matrix is a deep theorem.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)