Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
mNo edit summary
No edit summary
 
(364 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
In the branch of [[mathematical logic]] called [[model theory]], an '''elementary class''' (or '''axiomatizable class''') is a [[class (set theory)|class]] consisting of all [[structure (mathematical logic)|structures]] satisfying a fixed [[first-order logic|first-order]] [[theory (mathematical logic)|theory]].
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


== Definition ==
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


A [[class (set theory)|class]] ''K'' of [[structure (mathematical logic)|structures]] of a [[signature (logic)|signature]] σ is called an '''elementary class''' if there is a [[first-order logic|first-order]] [[theory (mathematical logic)|theory]] ''T'' of signature σ, such that ''K'' consists of all models of ''T'', i.e., of all σ-structures that satisfy ''T''. If ''T'' can be chosen as a theory consisting of a single first-order sentence, then ''K'' is called a '''basic elementary class'''.
Registered users will be able to choose between the following three rendering modes:


More generally, ''K'' is a [[pseudoelementary class|pseudo-elementary class]] if there is a first-order theory ''T'' of a signature that extends σ, such that ''K'' consists of all σ-structures that are [[reduct]]s to σ of models of ''T''. In other words, a class ''K'' of σ-structures is pseudo-elementary [[iff]] there is an elementary class ''K<nowiki>'</nowiki>'' such that ''K'' consists of precisely the reducts to σ of the structures in ''K<nowiki>'</nowiki>''.
'''MathML'''
:<math forcemathmode="mathml">E=mc^2</math>


For obvious reasons, elementary classes are also called '''axiomatizable in first-order logic''', and basic elementary classes are called '''finitely axiomatizable in first-order logic'''. These definitions extend to other logics in the obvious way, but since the first-order case is by far the most important, '''axiomatizable''' implicitly refers to this case when no other logic is specified.
<!--'''PNG''' (currently default in production)
:<math forcemathmode="png">E=mc^2</math>


== Conflicting and alternative terminology ==
'''source'''
:<math forcemathmode="source">E=mc^2</math> -->


While the above is nowadays standard terminology in [[model theory|"infinite" model theory]], the slightly different earlier definitions are still in use in [[finite model theory]], where an elementary class may be called a '''Δ-elementary class''', and the terms '''elementary class''' and '''first-order axiomatizable class''' are reserved for basic elementary classes (Ebbinghaus et al. 1994, Ebbinghaus and Flum 2005). Hodges calls elementary classes [[axiomatizable class]]es, and he refers to basic elementary classes as '''definable classes'''. He also uses the respective synonyms '''EC class''' and '''EC<math>_\Delta</math> class''' (Hodges, 1993).
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


There are good reasons for this diverging terminology. The [[signature (logic)|signature]]s that are considered in general model theory are often infinite, while a single [[first-order logic|first-order]] [[sentence (mathematical logic)|sentence]] contains only finitely many symbols. Therefore basic elementary classes are atypical in infinite model theory. Finite model theory, on the other hand, deals almost exclusively with finite signatures. It is easy to see that for every finite signature σ and for every class ''K'' of σ-structures closed under isomorphism there is an elementary class <math>K'</math> of σ-structures such that ''K'' and <math>K'</math> contain precisely the same finite structures. Hence elementary classes are not very interesting for finite model theorists.
==Demos==


== Easy relations between the notions ==
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:


Clearly every basic elementary class is an elementary class, and every elementary class is a pseudo-elementary class. Moreover, as an easy consequence of the [[compactness theorem]], a class of σ-structures is basic elementary if and only if it is elementary and its complement is also elementary.


== Examples ==
* accessibility:
=== A basic elementary class ===
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
Let σ be a signature consisting only of a [[unary function]] symbol ''f''. The class ''K'' of σ-structures in which ''f'' is [[injection (mathematics)|one-to-one]] is a basic elementary class. This is witnessed by the theory ''T'', which consists only of the single sentence
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
:<math>\forall x\forall y( (f(x)=f(y)) \to (x=y) )</math>.
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


=== An elementary, basic pseudoelementary class that is not basic elementary ===
==Test pages ==
Let σ be an arbitrary signature. The class ''K'' of all infinite σ-structures is elementary. To see this, consider the sentences


:<math>\rho_2={}</math> "<math>\exist x_1\exist x_2(x_1 \not =x_2)</math>",
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


:<math>\rho_3={}</math> "<math>\exist x_1\exist x_2\exist x_3((x_1 \not =x_2) \and (x_1 \not =x_3) \and (x_2 \not =x_3))</math>",
*[[Inputtypes|Inputtypes (private Wikis only)]]
 
*[[Url2Image|Url2Image (private Wikis only)]]
and so on. (So the sentence <math>\rho_n</math> says that there are at least ''n'' elements.) The infinite σ-structures are precisely the models of the theory
==Bug reporting==
 
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
:<math>T_\infty=\{\rho_2, \rho_3, \rho_4, \dots\}</math>.
 
But ''K'' is not a basic elementary class. Otherwise the infinite σ-structures would be precisely those that satisfy a certain first-order sentence τ. But then the set
<math>\{\neg\tau, \rho_2, \rho_3, \rho_4, \dots\}</math> would be inconsistent. By the [[compactness theorem]], for some natural number ''n'' the set <math>\{\neg\tau, \rho_2, \rho_3, \rho_4, \dots, \rho_n\}</math> would be inconsistent. But this is absurd, because this theory is satisfied by any σ-structure with <math>n+1</math> or more elements.
 
However, there is a basic elementary class ''K<nowiki>'</nowiki>'' in the signature σ' = σ <math>\cup</math> {''f''}, where ''f'' is a unary function symbol, such that ''K'' consists exactly of the reducts to σ of σ'-structures in ''K<nowiki>'</nowiki>''. ''K<nowiki>'</nowiki>'' is axiomatised by the single sentence <math>(\forall x\forall y(f(x) = f(y) \rightarrow x=y) \land \exists y\neg\exists x(y = f(x))),</math>, which expresses that ''f'' is injective but not surjective. Therefore ''K'' is elementary and what could be called basic pseudo-elementary, but not basic elementary.
 
=== Pseudo-elementary class that is non-elementary ===
Finally, consider the signature σ consisting of a single unary relation symbol ''P''. Every σ-structure is [[partition of a set|partitioned]] into two subsets: Those elements for which ''P'' holds, and the rest. Let ''K'' be the class of all σ-structures for which these two subsets have the same [[cardinality]], i.e., there is a bijection between them. This class is not elementary, because a σ-structure in which both the set of realisations of ''P'' and its complement are countably infinite satisfies precisely the same first-order sentences as a σ-structure in which one of the sets is countably infinite and the other is uncountable.
 
Now consider the signature <math>\sigma'</math>, which consists of ''P'' along with a unary function symbol ''f''. Let <math>K'</math> be the class of all <math>\sigma'</math>-structures such that ''f'' is a bijection and ''P'' holds for ''x'' [[iff]] ''P'' does not hold for ''f(x)''. <math>K'</math> is clearly an elementary class, and therefore ''K'' is an example of a pseudo-elementary class that is not elementary.
 
=== Non-pseudo-elementary class===
Let σ be an arbitrary signature. The class ''K'' of all finite σ-structures is not elementary, because (as shown above) its complement is elementary but not basic elementary. Since this is also true for every signature extending σ, ''K'' is not even a pseudo-elementary class.
 
This example demonstrates the limits of expressive power inherent in [[first-order logic]] as opposed to the far more expressive [[second-order logic]]. Second-order logic, however, fails to retain many desirable properties of first-order logic, such as the compactness theorem.
 
== References ==
 
* {{Citation | last1=Chang | first1=Chen Chung | last2=Keisler | first2=H. Jerome | author2-link=Howard Jerome Keisler | title=Model Theory | origyear=1973 | publisher=[[Elsevier]] | edition=3rd | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-88054-3 | year=1990}}
* {{Citation | last1=Ebbinghaus | first1=Heinz-Dieter | last2=Flum | first2=Jörg | title=Finite model theory | origyear=1995 | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-3-540-28787-2 | year=2005 | pages=360}}
* {{Citation | last1=Ebbinghaus | first1=Heinz-Dieter | last2=Flum | first2=Jörg | last3=Thomas | first3=Wolfgang | title=Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-0-387-94258-2 | year=1994}}
* {{Citation | last1=Hodges | first1=Wilfrid | author1-link=Wilfrid Hodges | title=A shorter model theory | publisher=[[Cambridge University Press]] | isbn=978-0-521-58713-6 | year=1997}}
* {{Citation | last1=Poizat | first1=Bruno | title=A Course in Model Theory: An Introduction to Contemporary Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-98655-5 | year=2000}}
 
{{DEFAULTSORT:Elementary Class}}
[[Category:Model theory]]
 
[[de:Elementare Klasse]]
[[nl:Elementaire klasse]]

Latest revision as of 23:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"