Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
mNo edit summary
Replaced content with "<br><br>Here's more info on [http://kanarea.dothome.co.kr/xe/?document_srl=226691 Nebraska Speed Dating] look at our web site."
Line 1: Line 1:
'''Burnside's lemma''', sometimes also called '''Burnside's counting theorem''', the '''Cauchy–Frobenius lemma''' or the '''orbit-counting theorem''', is a result in [[group theory]] which is often  useful in taking account of [[symmetry]] when counting mathematical objects.  Its various eponyms include [[William Burnside]], [[George Pólya]], [[Augustin Louis Cauchy]], and [[Ferdinand Georg Frobenius]]. The result is not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order', attributing it instead to {{harvtxt|Frobenius|1887}}.<ref>{{harvnb|Burnside|1897|loc=§119}}</ref>
{{DISPLAYTITLE:G<sub>δ</sub> set}}
In the mathematical field of [[topology]], a '''G<sub>δ</sub> set''' is a [[subset]] of a [[topological space]] that is a countable intersection of open sets. The notation originated in [[Germany]] with ''G'' for ''[[wikt:Gebiet#German|Gebiet]]'' (''[[German language|German]]'': area, or neighborhood) meaning [[open set]] in this case and δ for ''[[wikt:Durchschnitt#German|Durchschnitt]]'' (''German'': [[intersection (set theory)|intersection]]).  
The term '''inner limiting set''' is also used.  G<sub>δ</sub> sets, and their dual [[F-sigma set|F<sub>&sigma;</sub> sets]], are the second level of the [[Borel hierarchy]].


In the following, let ''G'' be a [[finite set|finite]] [[group (mathematics)|group]] that [[Group action|acts]] on a [[Set (mathematics)|set]] ''X''. For each ''g'' in ''G'' let ''X<sup>g</sup>'' denote the set of [[element (mathematics)|element]]s in ''X'' that are [[fixed point (mathematics)|fixed by]] ''g''. Burnside's lemma asserts the following formula for the number of [[orbit (group theory)|orbit]]s, denoted |''X''/''G''|:<ref>{{harvnb|Rotman|1995|loc=Chapter 3}}</ref>
==Definition==
In a topological space a '''G<sub>δ</sub> set''' is a [[countable]] [[intersection (set theory)|intersection]] of [[open set]]s. The G<sub>δ</sub> sets are exactly the level <math>\mathbf{\Pi}^0_2</math> sets of the [[Borel hierarchy]].


:<math>|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|.</math>
==Examples==
* Any open set is trivially a G<sub>δ</sub> set


Thus the number of orbits (a [[natural number]] or [[Extended real number line|+∞]]) is equal to the [[mean|average]] number of points fixed by an element of ''G'' (which is also a natural number or infinity). If ''G'' is infinite, the division by |''G''| may not be well-defined; in this case the following statement in [[cardinal arithmetic]] holds:
* The [[irrational numbers]] are a G<sub>δ</sub> set in '''R''', the real numbers, as they can be written as the intersection over all [[rational number|rational]] numbers  ''q'' of the [[complement (set theory)|complement]] of {''q''} in '''R'''. Note that the set of [[Rational number|rational]] numbers is not a G<sub>δ</sub> set in '''R'''.


:<math>|G| |X/G| = \sum_{g \in G}|X^g|.</math>
* The rational numbers '''Q''' are '''not''' a G<sub>δ</sub> set. If we were able to write '''Q''' as the intersection of open sets ''A<sub>n</sub>'', each ''A<sub>n</sub>'' would have to be  [[dense set|dense]] in '''R''' since '''Q''' is dense in '''R'''.  However, the construction above gave the irrational numbers as a countable intersection of open dense subsets.  Taking the intersection of both of these sets gives the [[empty set]] as a countable intersection of open dense sets in '''R''', a violation of the [[Baire category theorem]].


== Example application ==
* The zero-set of a derivative of an everywhere differentiable real-valued function on '''R''' is a  G<sub>δ</sub> set; it can be a dense set with empty interior, as shown by  [[Pompeiu derivative#Pompeiu's construction|Pompeiu's construction]].
The number of rotationally distinct colourings of the faces of a [[Cube (geometry)|cube]] using three colours can be determined from this formula as follows.


Let ''X'' be the set of 3<sup>6</sup> possible face colour combinations that can be applied to a cube in one particular orientation, and let the rotation group ''G'' of the cube act on ''X'' in the natural manner. Then two elements of ''X'' belong to the same orbit precisely when one is simply a rotation of the other. The number of rotationally distinct colourings is thus the same as the number of orbits and can be found by counting the sizes of the [[fixed set]]s for the 24 elements of ''G''.
A more elaborate example of a G<sub>δ</sub> set is given by the following theorem:


[[Image:Face colored cube.png|thumb|Cube with coloured faces]]
'''Theorem:''' The set <math>D=\left\{f \in C([0,1]) : f \text{ is not differentiable at any point of } [0,1] \right\}</math> is dense in <math>C([0,1])</math> and contains a G<sub>δ</sub> subset of the metric space <math>C([0,1])</math><ref name="Negrepontis 1997">{{cite book|last1=Νεγρεπόντης|first1=Σ.|last2=Ζαχαριάδης|first2=Θ.|last3=Καλαμίδας|first3=Ν.|last4=Φαρμάκη|first4=Β.|title=Γενική Τοπολογία και Συναρτησιακη Ανάλυσγη|year=1997|publisher=Εκδόσεις Συμμετρία|location=Αθήνα, Ελλάδα|isbn=960-266-178-Χ|pages=55–64|url=http://www.simmetria.gr/eshop/?149,%CD%C5%C3%D1%C5%D0%CF%CD%D4%C7%D3-%D3.-%C6%C1%D7%C1%D1%C9%C1%C4%C7%D3-%C8.-%CA%C1%CB%C1%CC%C9%C4%C1%D3-%CD.-%D6%C1%D1%CC%C1%CA%C7-%C2.-%C3%E5%ED%E9%EA%DE-%D4%EF%F0%EF%EB%EF%E3%DF%E1-%EA%E1%E9-%D3%F5%ED%E1%F1%F4%E7%F3%E9%E1%EA%DE-%C1%ED%DC%EB%F5%F3%E7|accessdate=3 April 2011|language=Greek|chapter=2, Πλήρεις Μετρικοί Χώροι}}</ref>
* one  identity element which leaves all 3<sup>6</sup> elements of ''X'' unchanged
* six  90-degree face rotations, each of which leaves 3<sup>3</sup> of the elements of ''X'' unchanged
* three  180-degree face rotations, each of which leaves 3<sup>4</sup> of the elements of ''X'' unchanged
* eight  120-degree vertex rotations, each of which leaves 3<sup>2</sup> of the elements of ''X'' unchanged
* six  180-degree edge rotations, each of which leaves 3<sup>3</sup> of the elements of ''X'' unchanged


A detailed examination of these automorphisms may be found
==Properties==
[[Cycle index#The cycle index of the face permutations of a cube|here]].


The average fix size is thus
The notion of G<sub>δ</sub> sets in [[Metric space|metric]] (and [[Topological space|topological]]) spaces is strongly related to the notion of [[Complete metric space|completeness]] of the metric space as well as to the [[Baire category theorem]]. This is described by the [[Mazurkiewicz]] theorem:


: <math> \frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57. </math>
'''Theorem''' ([[Mazurkiewicz]]): Let <math>(\mathcal{X},\rho)</math> be a complete metric space and <math>A\subset\mathcal{X}</math>. Then the following are equivalent:
# <math>A</math> is a G<sub>δ</sub> subset of <math>\mathcal{X}</math>
# There is a [[Metric (mathematics)|metric]] <math>\sigma</math> on <math>A</math> which is [[Metric_(mathematics)#Equivalence_of_metrics|equivalent]] to <math>\rho | A</math> such that <math>(A,\sigma)</math> is a complete metric space.


Hence there are 57 rotationally distinct colourings of the faces of a cube in three colours. In general, the number of rotationally distinct colorings of the faces of a cube in ''n'' colors is given by
A key property of <math>G_\delta</math> sets is that they are the possible sets at which a function from a topological space to a metric space is [[continuous function|continuous]]. Formally: The set of points where a function <math>f</math> is continuous is a <math>G_\delta</math> set. This is because continuity at a point <math>p</math> can be defined by a <math>\Pi^0_2</math> formula, namely: For all positive integers <math>n</math>, there is an open set <math>U</math> containing <math>p</math> such that <math>d(f(x),f(y)) < 1/n</math> for all <math>x, y</math> in <math>U</math>. If a value of <math>n</math> is fixed, the set of <math>p</math> for which there is such a corresponding open <math>U</math> is itself an open set (being a union of open sets), and the [[universal quantifier]] on <math>n</math> corresponds to the (countable) intersection of these sets. In the real line, the converse holds as well; for any G<sub>δ</sub> subset ''A'' of the real line, there is a function ''f'': '''R''' → '''R''' which is continuous exactly at the points in ''A''. As a consequence, while it is possible for the irrationals to be the set of continuity points of a function (see the [[popcorn function]]), it is impossible to construct a function which is continuous only on the rational numbers.


: <math> \frac{1}{24}\left(n^6+3n^4 + 12n^3 + 8n^2\right). </math>
===Basic properties===
* The [[complement (set theory)|complement]] of a G<sub>δ</sub> set is an [[Fσ set|F<sub>σ</sub>]] set.


== Proof ==
* The intersection of countably many G<sub>δ</sub> sets is a G<sub>δ</sub> set, and the union of ''finitely'' many G<sub>δ</sub> sets is a G<sub>δ</sub> set; a countable union of G<sub>δ</sub> sets is called a G<sub>δσ</sub> set.


The first step in the proof of the lemma is to re-express the sum over the group elements ''g''&nbsp;∈&nbsp;''G'' as an equivalent sum over the set elements ''x''&nbsp;∈&nbsp;''X'':
* In [[metrizable]] spaces, every [[closed set]] is a G<sub>δ</sub> set and, dually, every open set is an F<sub>σ</sub> set.


:<math>\sum_{g \in G}|X^g| = |\{(g,x)\in G\times X \mid g.x = x\}| = \sum_{x \in X} |G_x|.</math>
* A [[topological subspace|subspace]] ''A'' of a [[topologically complete]] space ''X'' is itself topologically complete if and only if ''A'' is a G<sub>δ</sub> set in ''X''.


(Here ''X<sup>g</sup>''&nbsp;=&nbsp;{''x''&nbsp;∈&nbsp;''X''&nbsp;|&nbsp;''g.x''&nbsp;=&nbsp;''x''} is the subset of all points of ''X'' fixed by ''g''&nbsp;∈&nbsp;''G'', whereas ''G<sub>x</sub>''&nbsp;=&nbsp;{''g''&nbsp;∈&nbsp;''G''&nbsp;|&nbsp;''g.x''&nbsp;=&nbsp;''x''} is the [[Orbit-stabilizer theorem#Orbits and stabilizers|stabilizer subgroup]] of G that fixes the point ''x''&nbsp;∈&nbsp;''X''.)
* A set that contains the intersection of a countable collection of [[dense set|dense]] open sets is called '''[[comeagre set|comeagre]]''' or '''residual.''' These sets are used to define [[generic property|generic properties]] of topological spaces of functions.


The [[Orbit-stabilizer theorem#Orbits and stabilizers|orbit-stabilizer theorem]] says that there is a natural [[bijection]] for each ''x''&nbsp;∈&nbsp;''X'' between the orbit of ''x'', ''G.x''&nbsp;=&nbsp;{''g.x''&nbsp;|&nbsp;''g''&nbsp;∈&nbsp;''G''}&nbsp;⊆&nbsp;''X'', and the set of left cosets ''G/G<sub>x</sub>'' of its stabilizer subgroup ''G<sub>x</sub>''. With [[Lagrange's theorem (group theory)|Lagrange's theorem]] this implies
The following results regard [[Polish space]]s<ref name="Fremlin 2003">{{cite book|last=Fremlin|first=D.H.|title=Measure Theory, Volume 4|year=2003|publisher=Digital Books Logistics|location=Petersburg, England|isbn=0-9538129-4-4|pages=334–335|url=http://www.essex.ac.uk/maths/people/fremlin/mt.htm|accessdate=1 April 2011|chapter=4, General Topology}}</ref>:


:<math>|G.x| = [G\,:\,G_x] = |G| / |G_x|.</math>
* Let <math>(\mathcal{X},\mathcal{T})</math> be a [[Polish space|Polish topological space]] and let <math>G\subset\mathcal{X}</math> be a G<sub>δ</sub> set (with respect to <math>\mathcal{T}</math>). The <math>G</math> is a Polish space with respect to the [[subspace topology]] on it.


Our sum over the set ''X'' may therefore be rewritten as
* Topological characterization of Polish spaces: If <math>\mathcal{X}</math> is a [[Polish space]] then it is [[Homeomorphism|homeomorphic]] to a G<sub>δ</sub> subset of a [[Compact space|compact]] [[metric space]].


:<math>\sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|G. x|} = |G| \sum_{x \in X}\frac{1}{|G. x|}.</math>
==G<sub>δ</sub> space==
A [[Gδ space|'''G<sub>δ</sub> space''']] is a topological space in which every [[closed set]] is a G<sub>δ</sub> set ([http://www.jstor.org/stable/2317335 Johnson, 1970]).{{Citation needed|date=August 2008}} A [[normal space]] which is also a G<sub>δ</sub> space is '''[[perfectly normal space|perfectly normal]]'''.  Every metrizable space is perfectly normal, and every perfectly normal space is [[completely normal]]: neither implication is reversible.


Finally, notice that ''X'' is the disjoint union of all its orbits in ''X/G'', which means the sum over ''X'' may be broken up into separate sums over each individual orbit.
==See also==
* [[Fσ set|F<sub>σ</sub> set]], the [[duality (mathematics)|dual]] concept; note that "G" is German (''[[wikt:Gebiet#German|Gebiet]]'') and "F" is French (''[[wikt:fermé#French|fermé]]'').


:<math>\sum_{x \in X}\frac{1}{|G. x|} = \sum_{A\in X/G} \sum_{x\in A} \frac{1}{|A|} = \sum_{A\in X/G} 1 = |X/G|.</math>
==References==
 
* [[John L. Kelley]], ''General topology'', [[Van Nostrand Reinhold|van Nostrand]], 1955.  P.134.
Putting everything together gives the desired result:
* {{Cite book | last1=Steen | first1=Lynn Arthur | author1-link=Lynn Arthur Steen | last2=Seebach | first2=J. Arthur Jr. | author2-link=J. Arthur Seebach, Jr. | title=[[Counterexamples in Topology]] | origyear=1978 | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=[[Dover Publications|Dover]] reprint of 1978 | isbn=978-0-486-68735-3 | mr=507446  | year=1995 | postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}} P. 162.
 
* {{Cite book | last=Fremlin | first=D.H. | title=Measure Theory, Volume 4 | origyear=2003 | publisher=Digital Books Logostics | location=Petersburg, England | isbn=0-9538129-4-4  | year=2003 | url=http://www.essex.ac.uk/maths/people/fremlin/mt.htm|accessdate=1 April 2011|chapter=4, General Topology | postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}} P. 334.
:<math>\sum_{g \in G}|X^g| = |G| \cdot |X/G|.</math>
* Roy A. Johnson (1970). "A Compact Non-Metrizable Space Such That Every Closed Subset is a G-Delta". ''The American Mathematical Monthly'', Vol. 77, No. 2, pp.&nbsp;172–176. [http://www.jstor.org/stable/2317335 on JStor]
 
==History: the lemma that is not Burnside's==
[[William Burnside]] stated and proved this lemma, attributing it to {{harvnb|Frobenius|1887}} in his 1897 book on finite groups. But, even prior to Frobenius, the formula was known to [[Cauchy]] in 1845. In fact, the lemma was apparently so well known that Burnside simply omitted to attribute it to Cauchy. Consequently, this lemma is sometimes referred to as '''the lemma that is not Burnside's'''.<ref>{{harvnb|Neumann|1979}}</ref> (see also [[Stigler's law of eponymy]]). This is less ambiguous than it may seem: Burnside contributed many lemmas to this field.
 
== See also ==
* [[Pólya enumeration theorem]]


==Notes==
==Notes==
{{reflist}}
<references />


== References ==
{{DEFAULTSORT:Gδ Set}}
*Burnside, William (1897) ''[http://www.gutenberg.org/ebooks/40395 Theory of Groups of Finite Order]'', [[Cambridge University Press]], at [[Project Gutenberg]] and [https://archive.org/details/theorygroupsfin00burngoog here] at [[Archive.org]].  (This is the first edition; the introduction to the second edition contains Burnside's famous ''volte face'' regarding the utility of [[representation theory]].)
[[Category:General topology]]
* {{citation | last=Frobenius |first=Ferdinand Georg |authorlink=Ferdinand Georg Frobenius |title=Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul |journal=Crelle |volume=CI |year=1887 |page=288}}.
[[Category:Descriptive set theory]]
* {{Citation | last1=Neumann | first1=Peter M. | author1-link=Peter M. Neumann | title=A lemma that is not Burnside's | mr=562002 | year=1979 | journal=The Mathematical Scientist | issn=0312-3685 | volume=4 | issue=2 | pages=133–141}}.
* {{citation | last=Rotman |first=Joseph |title=An introduction to the theory of groups |publisher=Springer-Verlag |year=1995 |isbn=0-387-94285-8}}.


[[Category:Lemmas]]
[[ja:Gδ集合]]
[[Category:Group theory]]
[[pl:Zbiór typu G-delta]]

Revision as of 02:53, 11 August 2014

In the mathematical field of topology, a Gδ set is a subset of a topological space that is a countable intersection of open sets. The notation originated in Germany with G for Gebiet (German: area, or neighborhood) meaning open set in this case and δ for Durchschnitt (German: intersection). The term inner limiting set is also used. Gδ sets, and their dual Fσ sets, are the second level of the Borel hierarchy.

Definition

In a topological space a Gδ set is a countable intersection of open sets. The Gδ sets are exactly the level sets of the Borel hierarchy.

Examples

  • Any open set is trivially a Gδ set
  • The irrational numbers are a Gδ set in R, the real numbers, as they can be written as the intersection over all rational numbers q of the complement of {q} in R. Note that the set of rational numbers is not a Gδ set in R.
  • The rational numbers Q are not a Gδ set. If we were able to write Q as the intersection of open sets An, each An would have to be dense in R since Q is dense in R. However, the construction above gave the irrational numbers as a countable intersection of open dense subsets. Taking the intersection of both of these sets gives the empty set as a countable intersection of open dense sets in R, a violation of the Baire category theorem.
  • The zero-set of a derivative of an everywhere differentiable real-valued function on R is a Gδ set; it can be a dense set with empty interior, as shown by Pompeiu's construction.

A more elaborate example of a Gδ set is given by the following theorem:

Theorem: The set is dense in and contains a Gδ subset of the metric space [1]

Properties

The notion of Gδ sets in metric (and topological) spaces is strongly related to the notion of completeness of the metric space as well as to the Baire category theorem. This is described by the Mazurkiewicz theorem:

Theorem (Mazurkiewicz): Let be a complete metric space and . Then the following are equivalent:

  1. is a Gδ subset of
  2. There is a metric on which is equivalent to such that is a complete metric space.

A key property of sets is that they are the possible sets at which a function from a topological space to a metric space is continuous. Formally: The set of points where a function is continuous is a set. This is because continuity at a point can be defined by a formula, namely: For all positive integers , there is an open set containing such that for all in . If a value of is fixed, the set of for which there is such a corresponding open is itself an open set (being a union of open sets), and the universal quantifier on corresponds to the (countable) intersection of these sets. In the real line, the converse holds as well; for any Gδ subset A of the real line, there is a function f: RR which is continuous exactly at the points in A. As a consequence, while it is possible for the irrationals to be the set of continuity points of a function (see the popcorn function), it is impossible to construct a function which is continuous only on the rational numbers.

Basic properties

  • The intersection of countably many Gδ sets is a Gδ set, and the union of finitely many Gδ sets is a Gδ set; a countable union of Gδ sets is called a Gδσ set.
  • A set that contains the intersection of a countable collection of dense open sets is called comeagre or residual. These sets are used to define generic properties of topological spaces of functions.

The following results regard Polish spaces[2]:

Gδ space

A Gδ space is a topological space in which every closed set is a Gδ set (Johnson, 1970).Potter or Ceramic Artist Truman Bedell from Rexton, has interests which include ceramics, best property developers in singapore developers in singapore and scrabble. Was especially enthused after visiting Alejandro de Humboldt National Park. A normal space which is also a Gδ space is perfectly normal. Every metrizable space is perfectly normal, and every perfectly normal space is completely normal: neither implication is reversible.

See also

References

  • John L. Kelley, General topology, van Nostrand, 1955. P.134.
  • 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 P. 162.
  • 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 P. 334.
  • Roy A. Johnson (1970). "A Compact Non-Metrizable Space Such That Every Closed Subset is a G-Delta". The American Mathematical Monthly, Vol. 77, No. 2, pp. 172–176. on JStor

Notes

  1. 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
  2. 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534

ja:Gδ集合 pl:Zbiór typu G-delta