Meta tags:

Headings (most frequently used words):

elementary, equivalence, contents, elementarily, equivalent, structures, substructures, and, extensions, tarski, vaught, test, embeddings, references,

Text of the page (most frequently used words):
elementary (35), and (34), the (33), theory (27), order (19), substructure (18), model (16), first (15), logic (13), #tarski (12), are (12), with (11), #elementarily (11), equivalent (11), models (10), only (10), this (9), mathematics (9), theorem (9), edit (9), for (9), equivalence (8), set (8), list (8), logical (8), signature (8), displaystyle (8), structures (8), wikipedia (7), non (7), formula (7), every (7), structure (7), that (7), vaught (7), page (6), from (6), mathematical (6), function (6), same (6), all (5), truth (5), predicate (5), complete (5), proof (5), skolem (5), true (5), free (5), large (5), its (5), embeddings (5), then (5), can (5), test (5), one (5), contents (4), search (4), text (4), citations (4), history (4), recursive (4), calculus (4), standard (4), formal (4), elements (4), numbers (4), variable (4), propositional (4), infinite (4), löwenheim (4), embedding (4), any (4), two (4), called (4), article (4), hide (4), move (4), sidebar (4), view (3), articles (3), category (3), related (3), type (3), problem (3), theories (3), arithmetic (3), finite (3), atomic (3), systems (3), boolean (3), example (3), symbol (3), rank (3), language (3), relation (3), extension (3), axiom (3), gödel (3), new (3), foundations (3), general (3), cardinality (3), countable (3), element (3), paradox (3), isbn (3), cambridge (3), substructures (3), references (3), into (3), such (3), extensions (3), has (3), links (3), tools (3), main (3), languages (2), toggle (2), table (2), contact (2), about (2), privacy (2), policy (2), terms (2), use (2), was (2), categories (2), lacking (2), february (2), 2023 (2), short (2), description (2), wikidata (2), portal (2), sets (2), abstract (2), turing (2), primitive (2), computable (2), church (2), validity (2), schema (2), kripke (2), semantics (2), diagram (2), submodel (2), spectrum (2), ordinal (2), hilbert (2), axiomatic (2), rule (2), inference (2), consequence (2), euclidean (2), real (2), second (2), peano (2), constant (2), sentence (2), ground (2), definition (2), von (2), neumann (2), grothendieck (2), binary (2), number (2), isomorphism (2), domain (2), map (2), maps (2), universe (2), monadic (2), point (2), argument (2), theorems (2), information (2), 978 (2), university (2), press (2), hodges (2), wilfrid (2), encyclopedia (2), 1993 (2), most (2), important (2), also (2), cardinals (2), over (2), there (2), sufficient (2), condition (2), gives (2), writes (2), both (2), variables (2), holds (2), varphi (2), dots (2), more (2), which (2), other (2), usual (2), they (2), unbounded (2), dense (2), because (2), linear (2), parameters (2), solution (2), when (2), learn (2), help (2), appearance (2), upload (2), file (2), changes (2), read (2), log (2), create (2), account (2), donate (2), menu (2), add, topic, mobile, cookie, statement, statistics, developers, code, conduct, legal, safety, contacts, disclaimers, available, under, additional, may, apply, using, site, you, agree, registered, trademark, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, rendered, parsoid, last, edited, march, 2026, utc, hidden, matches, retrieved, https, org, index, php, title, elementary_equivalence, oldid, 1344446394, supertask, philosophy, object, logicism, timeline, concrete, automated, proving, algebraic, machine, recursion, lambda, kolmogorov, complexity, versus, undecidable, decidable, decision, computably, enumerable, thesis, encoding, computability, ultraproduct, value, transfer, principle, semantic, strength, satisfiability, categorical, saturated, prime, interpretation, self, verifying, reverse, analysis, impossibility, zfc, independence, deductive, sequent, natural, deduction, principia, mathematica, geometry, minimal, axioms, canonical, algebras, axiomatization, robinson, term, substitution, string, quantifier, functional, connective, metalanguage, bound, open, closed, grammar, formation, conservative, expression, automata, arity, alphabet, syntax, constructive, ackermann, bernays, naive, morse, kelley, platek, continuum, hypothesis, choice, zermelo, fraenkel, operation, aleph, inaccessible, cardinal, enumeration, numbering, schröder, bernstein, jection, sur, image, codomain, constructible, universal, fuzzy, ultrafilter, transitive, singleton, inhabited, empty, uncountable, types, operations, identities, power, cartesian, product, complement, union, intersection, partition, forcing, extensionality, class, hereditary, quantifiers, fixed, higher, many, valued, tables, connectives, functions, algebra, venn, square, opposition, syllogism, soundness, equiconsistency, consistency, proposition, tautology, classical, traditional, logics, russell, lindström, halting, compactness, diagonal, cantor, banach, undefinability, incompleteness, completeness, paradoxes, lemma, monk, donald, 1976, graduate, texts, york, heidelberg, berlin, springer, verlag, 387, 90170, 1997, 521, 58713, shorter, 1990, 1973, studies, 3rd, elsevier, 444, 88054, keisler, jerome, chang, chen, chung, applications, milner, appearing, vol, 136, issues, 1994, 243, 252, discrete, combinatorics, whose, play, role, see, critical, induces, between, strong, homomorphism, let, exists, necessary, useful, constructing, criterion, downward, upward, arbitrarily, says, succeq, preceq, interpreted, consisting, together, appears, 1957, follows, formulas, generally, isomorphic, obtained, via, thus, contain, objects, than, just, etc, yet, consider, since, interpret, ensure, shown, łoś, orderings, ordering, rational, without, have, used, study, including, passes, evaluated, prove, ehrenfeucht, fraïssé, games, often, needs, stronger, case, branch, satisfy, sentences, includes, how, remove, message, please, precise, introducing, improve, but, sources, remain, unclear, lacks, inline, external, reading, concept, item, projects, printable, version, download, pdf, print, export, switch, legacy, parser, get, shortened, url, cite, permanent, link, what, here, actions, english, talk, svenska, português, 한국어, 日本語, italiano, français, esperanto, deutsch, čeština, বাংলা, top, personal, special, pages, recent, community, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
elementary equivalence wikipedia jump to content main menu main menu move to sidebar hide navigation main page contents current events random article about wikipedia contact us contribute help learn to edit community portal recent changes upload file special pages search search appearance donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 elementarily equivalent structures 2 elementary substructures and elementary extensions 3 tarski vaught test 4 elementary embeddings 5 references toggle the table of contents elementary equivalence 11 languages বাংলা čeština deutsch esperanto français italiano 日本語 한국어 português svenska 中文 edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia concept in model theory this article includes a list of references related reading or external links but its sources remain unclear because it lacks inline citations please help improve this article by introducing more precise citations february 2023 learn how and when to remove this message in model theory a branch of mathematical logic two structures m and n of the same signature σ are called elementarily equivalent if they satisfy the same first order σ sentences if n is a substructure of m one often needs a stronger condition in this case n is called an elementary substructure of m if every first order σ formula φ a 1 a n with parameters a 1 a n from n is true in n if and only if it is true in m if n is an elementary substructure of m then m is called an elementary extension of n an embedding h n m is called an elementary embedding of n into m if h n is an elementary substructure of m a substructure n of m is elementary if and only if it passes the tarski vaught test every first order formula φ x b 1 b n with parameters in n that has a solution in m also has a solution in n when evaluated in m one can prove that two structures are elementarily equivalent with the ehrenfeucht fraïssé games elementary embeddings are used in the study of large cardinals including rank into rank elementarily equivalent structures edit two structures m and n of the same signature σ are elementarily equivalent if every first order sentence formula without free variables over σ is true in m if and only if it is true in n i e if m and n have the same complete first order theory if m and n are elementarily equivalent one writes m n a first order theory is complete if and only if any two of its models are elementarily equivalent for example consider the language with one binary relation symbol the model r of real numbers with its usual order and the model q of rational numbers with its usual order are elementarily equivalent since they both interpret as an unbounded dense linear ordering this is sufficient to ensure elementary equivalence because the theory of unbounded dense linear orderings is complete as can be shown by the łoś vaught test more generally any first order theory with an infinite model has non isomorphic elementarily equivalent models which can be obtained via the löwenheim skolem theorem thus for example there are non standard models of peano arithmetic which contain other objects than just the numbers 0 1 2 etc and yet are elementarily equivalent to the standard model elementary substructures and elementary extensions edit n is an elementary substructure or elementary submodel of m if n and m are structures of the same signature σ such that for all first order σ formulas φ x 1 x n with free variables x 1 x n and all elements a 1 a n of n φ a 1 a n holds in n if and only if it holds in m n φ a 1 a n if and only if m φ a 1 a n displaystyle n models varphi a_ 1 dots a_ n text if and only if m models varphi a_ 1 dots a_ n this definition first appears in tarski vaught 1957 1 it follows that n is a substructure of m if n is a substructure of m then both n and m can be interpreted as structures in the signature σ n consisting of σ together with a new constant symbol for every element of n then n is an elementary substructure of m if and only if n is a substructure of m and n and m are elementarily equivalent as σ n structures if n is an elementary substructure of m one writes n displaystyle preceq m and says that m is an elementary extension of n m displaystyle succeq n the downward löwenheim skolem theorem gives a countable elementary substructure for any infinite first order structure in at most countable signature the upward löwenheim skolem theorem gives elementary extensions of any infinite first order structure of arbitrarily large cardinality tarski vaught test edit the tarski vaught test or tarski vaught criterion is a necessary and sufficient condition for a substructure n of a structure m to be an elementary substructure it can be useful for constructing an elementary substructure of a large structure let m be a structure of signature σ and n a substructure of m then n is an elementary substructure of m if and only if for every first order formula φ x y 1 y n over σ and all elements b 1 b n from n if m displaystyle models displaystyle exists x φ x b 1 b n then there is an element a in n such that m displaystyle models φ a b 1 b n 2 elementary embeddings edit an elementary embedding of a structure n into a structure m of the same signature σ is a map h n m such that for every first order σ formula φ x 1 x n and all elements a 1 a n of n n displaystyle models φ a 1 a n if and only if m displaystyle models φ h a 1 h a n every elementary embedding is a strong homomorphism and it induces an isomorphism between n and an elementary substructure of m elementary embeddings are the most important maps in model theory in set theory elementary embeddings whose domain is v the universe of set theory play an important role in the theory of large cardinals see also critical point references edit e c milner the use of elementary substructures in combinatorics 1993 appearing in discrete mathematics vol 136 issues 1 3 1994 pp 243 252 wilfrid hodges model theory encyclopedia of mathematics and its applications 42 cambridge university press 1993 theorem 2 5 1 page 55 chang chen chung keisler h jerome 1990 1973 model theory studies in logic and the foundations of mathematics 3rd ed elsevier isbn 978 0 444 88054 3 hodges wilfrid 1997 a shorter model theory cambridge cambridge university press isbn 978 0 521 58713 6 monk j donald 1976 mathematical logic graduate texts in mathematics new york heidelberg berlin springer verlag isbn 0 387 90170 1 v t e mathematical logic general axiom list cardinality first order logic formal proof formal semantics foundations of mathematics information theory lemma logical consequence model theorem theory type theory theorems list paradoxes gödel s completeness incompleteness theorems tarski s undefinability banach tarski paradox cantor s theorem paradox diagonal argument compactness halting problem lindström s löwenheim skolem russell s paradox logics traditional classical logic logical truth tautology proposition inference logical equivalence consistency equiconsistency argument soundness validity syllogism square of opposition venn diagram propositional boolean algebra boolean functions logical connectives propositional calculus propositional formula truth tables many valued logic 3 finite predicate first order list second order monadic higher order fixed point free quantifiers predicate monadic predicate calculus set theory set hereditary class ur element ordinal number extensionality forcing relation equivalence partition set operations intersection union complement cartesian product power set identities types of sets countable uncountable empty inhabited singleton finite infinite transitive ultrafilter recursive fuzzy universal universe constructible grothendieck von neumann maps cardinality function map domain codomain image in sur bi jection schröder bernstein theorem isomorphism gödel numbering enumeration large cardinal inaccessible aleph number operation binary theories zermelo fraenkel axiom of choice continuum hypothesis general kripke platek morse kelley naive new foundations tarski grothendieck von neumann bernays gödel ackermann constructive formal systems list language syntax alphabet arity automata axiom schema expression ground extension by definition conservative relation formation rule grammar formula atomic closed ground open free bound variable language metalanguage logical connective predicate functional variable propositional variable proof quantifier rank sentence atomic spectrum signature string substitution symbol function logical constant non logical variable term theory list example axiomatic systems list of true arithmetic peano second order elementary function primitive recursive robinson skolem of the real numbers tarski s axiomatization of boolean algebras canonical minimal axioms of geometry euclidean elements hilbert s tarski s non euclidean principia mathematica proof theory formal proof natural deduction logical consequence rule of inference sequent calculus theorem systems axiomatic deductive hilbert list complete theory independence from zfc proof of impossibility ordinal analysis reverse mathematics self verifying theories model theory interpretation function of models model atomic equivalence finite prime saturated spectrum submodel non standard model of non standard arithmetic diagram elementary categorical theory model complete theory satisfiability semantics of logic strength theories of truth semantic tarski s kripke s t schema transfer principle truth predicate truth value type ultraproduct validity computability theory church encoding church turing thesis computably enumerable computable function computable set decision problem decidable undecidable p np p versus np problem kolmogorov complexity lambda calculus primitive recursive function recursion recursive set turing machine type theory related abstract logic algebraic logic automated theorem proving category theory concrete abstract category category of sets history of logic history of mathematical logic timeline logicism mathematical object philosophy of mathematics supertask mathematics portal retrieved from https en wikipedia org w index php title elementary_equivalence oldid 1344446394 categories equivalence mathematics mathematical logic model theory hidden categories articles with short description short description matches wikidata articles lacking in text citations from february 2023 all articles lacking in text citations this page was last edited on 20 march 2026 at 14 15 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mobile view search search toggle the table of contents elementary equivalence 11 languages add topic