|
Omega-categorical
In mathematical logic, an omega-categorical theory is a theory that has exactly one countably infinite model up to isomorphism. Omega-categoricity is the special case κ = \aleph_0 = ω of κ-categoricity, and omega-categorical theories are also referred to as ω-categorical. The notion is most important for countable first-order theories. Equivalent conditions for omega-categoricity Many conditions on a theory are equivalent to the property of omega-categoricity. In 1959 Erwin Engeler, Czesław Ryll-Nardzewski and Lars Svenonius, proved several independently.Rami Grossberg, José Iovino and Olivier Lessmann''A primer of simple theories''/ref> Despite this, the literature still widely refers to the Ryll-Nardzewski theorem as a name for these conditions. The conditions included with the theorem vary between authors.Hodges, Model Theory, p. 341.Rothmaler, p. 200. Given a countable complete first-order theory ''T'' with infinite models, the following are equiva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rado Graph
In the mathematics, mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a Countable set, countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of . The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other. Every finite or countably infinite graph is an induced subgraph of the Rado graph, and can be found as an induced subgraph by a greedy algorithm that builds ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cantor's Isomorphism Theorem
In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. For instance, Minkowski's question-mark function produces an isomorphism (a one-to-one order-preserving correspondence) between the numerical ordering of the rational numbers and the numerical ordering of the dyadic rationals. The theorem is named after Georg Cantor, who first published it in 1895, using it to characterize the (uncountable) ordering on the real numbers. It can be proved by a back-and-forth method that is also sometimes attributed to Cantor but was actually published later, by Felix Hausdorff. The same back-and-forth method also proves that countable dense unbounded orders are highly symmetric, and can be applied to other kinds of structures. However, Cantor's original proof only used the "going forth" half of this method. In terms of model theory, the isomorphism theorem can be expressed by s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Czesław Ryll-Nardzewski
Czesław Ryll-Nardzewski (; 7 October 1926 – 18 September 2015) was a Polish mathematician. Life and career Born in Wilno, Second Polish Republic (now Vilnius, Lithuania), he was a student of Hugo Steinhaus. At the age of 26 he became professor at Warsaw University. In 1959, he became a professor at the Wrocław University of Technology. He was the advisor of 18 PhD theses. His main research areas were measure theory, functional analysis, foundations of mathematics and probability theory. Several theorems bear his name: the Ryll-Nardzewski fixed point theorem, “9. Theorem of Ryll-Nardzewski” (p. 171), “(9.6) Theorem (Ryll-Nardzewski)” (p. 174) the Ryll-Nardzewski theorem See Theorem 7.3.1 Cf. (2.10) in model theory, and the Kuratowski and Ryll-Nardzewski measurable selection theorem. See Theorem 6.9.3 on p. 36 and the historical comment on p. 441 He became a member of the Polish Academy of Sciences in 1967. He died in 2015 at the age of 88 [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Model Theory
In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mathematical logic), mathematical structure), and their Structure (mathematical logic), models (those Structure (mathematical logic), structures in which the statements of the theory hold). The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be definable set, defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shel ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Morley's Categoricity Theorem
In mathematical logic, a theory is categorical if it has exactly one model ( up to isomorphism). Such a theory can be viewed as ''defining'' its model, uniquely characterizing the model's structure. In first-order logic, only theories with a finite model can be categorical. Higher-order logic contains categorical theories with an infinite model. For example, the second-order Peano axioms are categorical, having a unique model whose domain is the set of natural numbers \mathbb. In model theory, the notion of a categorical theory is refined with respect to cardinality. A theory is -categorical (or categorical in ) if it has exactly one model of cardinality up to isomorphism. Morley's categoricity theorem is a theorem of stating that if a first-order theory in a countable language is categorical in some uncountable cardinality, then it is categorical in all uncountable cardinalities. extended Morley's theorem to uncountable languages: if the language has cardinality and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fraïssé Limit
In mathematical logic, specifically in the discipline of model theory, the Fraïssé limit (also called the Fraïssé construction or Fraïssé amalgamation) is a method used to construct (infinite) mathematical structures from their (finite) substructures. It is a special example of the more general concept of a direct limit in a category. The technique was developed in the 1950s by its namesake, French logician Roland Fraïssé. The main point of Fraïssé's construction is to show how one can approximate a (countable) structure by its finitely generated substructures. Given a class \mathbf of finite relational structures, if \mathbf satisfies certain properties (described below), then there exists a unique countable structure \operatorname(\mathbf), called the Fraïssé limit of \mathbf, which contains all the elements of \mathbf as substructures. The general study of Fraïssé limits and related notions is sometimes called Fraïssé theory. This field has seen wide applic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Erwin Engeler
Erwin Engeler (born 13 February 1930) is a Swiss mathematician who did pioneering work on the interrelations between logic, computer science and scientific computation in the 20th century. He was one of Paul Bernays' students at the ETH Zürich. After completing his doctorate in 1958, Engeler spent fourteen years in the United States, teaching at the University of Minnesota and at the University of California, Berkeley. In 1959 he contributed an independent proof of several equivalent conditions to omega-categoricity, an important concept in model theory. He returned to Switzerland in 1972, where he served as a professor of logic and computer science at the ETH until his retirement in 1997. Engeler was named a Fellow of the Association for Computing Machinery in 1995. Selected publications * External links * Professor Engeler's home pageat the ETH Zurich ETH Zurich (; ) is a public university in Zurich, Switzerland. Founded in 1854 with the stated mission to educate ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lars Svenonius
Lars Svenonius (June 16, 1927, Skellefteå – September 27, 2010, Silver Spring, Maryland) was a Swedish logician and philosopher. He was a visiting professor at University of California at Berkeley in 1962–63, then held a position at the University of Chicago from 1963 to 1969, and was professor of philosophy at the University of Maryland from 1969 to 2009. He retired in 2009, but was awarded the position of emeritus professor, and continued to teach courses and advise students until his death at 83 years of age. He was the first Swedish logician to work on model theory with his dissertation ''Some problems in Model Theory'' (for which the University of Uppsala awarded him a doctorate in 1960). His early work was in formal logic, and he established a reputation for brilliance early in his career with a series of proofs, including an independent proof of Omega-categorical theory, equivalent characterizations of omega-categorical theories. A 1959 paper of his in ''Theoria (philo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Atomic Model (mathematical Logic)
In model theory, a subfield of mathematical logic, an atomic model is a model such that the complete type of every tuple is axiomatized by a single formula. Such types are called principal types, and the formulas that axiomatize them are called complete formulas. Definitions Let ''T'' be a theory. A complete type ''p''(''x''1, ..., ''x''''n'') is called principal or atomic (relative to ''T'') if it is axiomatized relative to ''T'' by a single formula ''φ''(''x''1, ..., ''x''''n'') ∈ ''p''(''x''1, ..., ''x''''n''). A formula ''φ'' is called complete in ''T'' if for every formula ''ψ''(''x''1, ..., ''x''''n''), the theory ''T'' ∪ entails exactly one of ''ψ'' and ¬''ψ''.Some authors refer to complete formulas as "atomic formulas", but this is inconsistent with the purely syntactical notion of an atom or atomic formula as a formula that does not contain a proper subformula. It follows that a complete type is principal if an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boolean Algebra (structure)
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra (with involution). Every Boolean algebra gives rise to a Boolean ring, and vice versa, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨). However, the theory of Boolean rings has an inherent asymmetry between the two operators, while the axioms and theorems of Boolean algebra express the symmetry of the theory described by the duality principle. __TOC__ History The term "Boolean algebra" honors George Boole (1815–1864), a self-educated E ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Finite Field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are the integers mod n, integers mod p when p is a prime number. The ''order'' of a finite field is its number of elements, which is either a prime number or a prime power. For every prime number p and every positive integer k there are fields of order p^k. All finite fields of a given order are isomorphism, isomorphic. Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory. Properties A finite field is a finite set that is a fiel ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prime Model
In mathematics, and in particular model theory, a prime model is a model that is as simple as possible. Specifically, a model P is prime if it admits an elementary embedding into any model M to which it is elementarily equivalent (that is, into any model M satisfying the same complete theory as P). Cardinality In contrast with the notion of saturated model, prime models are restricted to very specific cardinalities by the Löwenheim–Skolem theorem. If L is a first-order language with cardinality \kappa and T is a complete theory over L, then this theorem guarantees a model for T of cardinality \max(\kappa,\aleph_0). Therefore, no prime model of T can have larger cardinality since at the very least it must be elementarily embedded in such a model. This still leaves much ambiguity in the actual cardinality. In the case of countable languages, all prime models are at most countably infinite. Relationship with saturated models There is a duality between the definitions of pri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
