Cyclic order: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Peter Schmitt
(new)
 
imported>Peter Schmitt
(edits)
Line 1: Line 1:
{{subpages}}
The typical example of a '''cyclic order''' are people seated at a (round) table:
The typical example of a '''cyclic order''' are people seated at a (round) table:
Each person has a right-hand and a left-hand neighbour, and no position is distinguished from the others.
Each person has a right-hand and a left-hand neighbour, and no position is distinguished from the others.
The seating order can be described by listing the persons, starting from any arbitrary position, in clockwise (or counterclockwise) order.
The seating order can be described by listing the persons, starting from any arbitrary position, in clockwise (or counterclockwise) order.


The abstract concept analogous to this situation is, described in mathematical terms, as follows:
== Mathematical formulation ==
 
The abstract concept analogous to sitting around a table can be described in mathematical terms as follows:


On a finite set ''S'' of ''n'' elements, consider a function σ that defines for each element ''s'' its successor σ(''s'').
On a finite set ''S'' of ''n'' elements, consider a function σ that defines for each element ''s'' its successor σ(''s'').
<br>
<br>
This describes a cyclic order if (and only if) for some element ''s'' the orbit under &sigma; is the whole set ''S'':
This gives rise to a cyclic order if (and only if) for some element ''s'' the orbit under &sigma; is the whole set ''S'':
: <math>
: <math>
           S = \{ \sigma^k (s)  \mid k=1,\dots,n \}
           S = \{ \sigma^k (s)  \mid k=1,\dots,n \}
   </math>
   </math>
The '''reverse cyclic order''' is given by &sigma;<sup>&minus;1</sup> (where &sigma;<sup>&minus;1</sup>(''s'') is the element preceding ''s'').
'''Remarks:'''
'''Remarks:'''
# If this holds for one element then it holds for all elements.
# If the condition holds for one element then it holds for all elements.
# All cyclic orders of ''n'' elements are isomorphic.
# All cyclic orders of ''n'' elements are isomorphic.
# Cyclic orders cannot be considered as [[order relation]]s because both ''s''<''t'' and ''t''<''s'' would hold for any two distinct elements ''s'' and ''t''.
# Cyclic orders cannot be considered as [[order relation]]s because both ''s''&nbsp;<&nbsp;''t'' and ''t''&nbsp;<&nbsp;''s'' would hold for any two distinct elements ''s'' and ''t''.
# Cyclic orders occur naturally in number theory ([[residue set]]s and group theory ([[cyclic group]]s, [[permutation]]s).
# Cyclic orders occur naturally in number theory ([[residue set]]s and group theory ([[cyclic group]]s, [[permutation]]s).


== Examples ==
== Examples ==


(Alice, Bob, Celia, Don), (Bob, Celia, Don, Alice), (Celia, Don, Alice, Bob), and (Don, Alice, Bob, Celia) describe the same cyclic (seating) order.
* (Alice, Bob, Celia, Don), (Bob, Celia, Don, Alice), (Celia, Don, Alice, Bob), and (Don, Alice, Bob, Celia) all describe the same cyclic (seating) order. <br> (Alice, Don, Celia, Bob) describes the reverse cyclic order, and (Alice, Celia, Bob, Don) describes a different cyclic order.
<br>
(Alice, Don, Celia, Bob) describes the reverse cyclic order, and (Alice, Celia, Bob, Don) describe a different cyclic order.


The hours on a clock are in cyclic order: one o'clock follows twelve o'clock.
* The hours on a clock are in cyclic order: one o'clock follows twelve o'clock.

Revision as of 13:33, 5 January 2011

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

The typical example of a cyclic order are people seated at a (round) table: Each person has a right-hand and a left-hand neighbour, and no position is distinguished from the others. The seating order can be described by listing the persons, starting from any arbitrary position, in clockwise (or counterclockwise) order.

Mathematical formulation

The abstract concept analogous to sitting around a table can be described in mathematical terms as follows:

On a finite set S of n elements, consider a function σ that defines for each element s its successor σ(s).
This gives rise to a cyclic order if (and only if) for some element s the orbit under σ is the whole set S:

The reverse cyclic order is given by σ−1 (where σ−1(s) is the element preceding s).

Remarks:

  1. If the condition holds for one element then it holds for all elements.
  2. All cyclic orders of n elements are isomorphic.
  3. Cyclic orders cannot be considered as order relations because both s < t and t < s would hold for any two distinct elements s and t.
  4. Cyclic orders occur naturally in number theory (residue sets and group theory (cyclic groups, permutations).

Examples

  • (Alice, Bob, Celia, Don), (Bob, Celia, Don, Alice), (Celia, Don, Alice, Bob), and (Don, Alice, Bob, Celia) all describe the same cyclic (seating) order.
    (Alice, Don, Celia, Bob) describes the reverse cyclic order, and (Alice, Celia, Bob, Don) describes a different cyclic order.
  • The hours on a clock are in cyclic order: one o'clock follows twelve o'clock.