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
Elementary class
(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!
== Examples == === A basic elementary class === 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 :<math>\forall x\forall y( (f(x)=f(y)) \to (x=y) )</math>. === An elementary, basic pseudoelementary class that is not basic elementary === 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>", :<math>\rho_3={}</math> "<math>\exist x_1\exist x_2\exist x_3((x_1 \not =x_2) \land (x_1 \not =x_3) \land (x_2 \not =x_3))</math>", 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 :<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 finite σ-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 [[Gödel's_completeness_theorem|completeness]] and [[compactness theorem|compactness]] theorems.
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)