There is no known syntactic characterization of the class of finite definitions in terms of a set of basic definitions and a set of basic operators under which the class is closed. Furthermore, it is known that the basic propositional operators do not preserve finiteness. In this paper I survey these problems and explore operators that do preserve finiteness. I also show that every definition that uses only unary predicate symbols and equality is bound to be (...) finite. (shrink)

The paper discusses the notion of finite model truth definitions (or FM-truth definitions), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition. We compare FM-truth definitions with Vardi's concept of the combined complexity of logics, noting an important difference: the difficulty of defining FM-truth for a logic ᵍ does not depend on the syntax of L, as long as it is decidable. It follows that for a natural ᵍ there exist (...) FM-truth definitions whose evaluation is much easier than the combined complexiy of ᵍ would suggest. We apply the general theory to give a complexity-theoretical characterization of the logics for which the $\Sigma_{m}^{d}$ classes (prenex classes of higher order logics) define FM-truth. For any $d \geq 2.m \geq 1$ we construct a family $\{[\Sigma_{m}^{d}]^{\leg\kappa}\}\kappa\in\omega$ of syntactically defined fragments of $\Sigma_{m}^{d}$ which satisfy this characterization. We also use the $[\Sigma_{m}^{d}]\leg\kappa$ classes to give a refinement of known results on the complexity classes captured by $\Sigma_{m}^{d}$ . We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary $\sigma$ , of a fixed number $\kappa$ such that model checking for all first order sentences over $\sigma$ can be done in deterministic time $n^{\kappa}$. (shrink)

Quasi-set theory is a ZFU-like axiomatic set theory, which deals with two kinds of ur-elements: M-atoms, objects like the atoms of ZFU, and m-atoms, items for which the usual identity relation is not defined. One of the motivations to advance such a theory is to deal properly with collections of items like particles in non-relativistic quantum mechanics when these are understood as being non-individuals in the sense that they may be indistinguishable although identity does not apply to them. According to (...) some authors, this is the best way to understand quantum objects. The fact that identity is not defined for m-atoms raises a technical difficulty: it seems impossible to follow the usual procedures to define the cardinal of collections involving these items. In this paper we propose a definition of finite cardinals in quasi-set theory which works for collections involving m-atoms. (shrink)

We provide the syntactic equivalent for the theorem stating that all epimorphisms of finite projective planes are isomorphisms. The definition of the inequality relation that we provide adds little to our understanding of the theorem, since its very validity can be discerned only from the validity of the model-theoretic theorem regarding epimorphisms.

In many classes of structures, each computable structure has computable dimension 1 or $\omega$. Nevertheless, Goncharov showed that for each $n < \omega$, there exists a computable structure with computable dimension $n$. In this paper we show that, under one natural definition of relativized computable dimension, no computable structure has finite relativized computable dimension greater than 1.

0.0. Theistic Ethics as a Challenge and a Diagnostic Tool. Naturalistic conceptions in metaethics come in many varieties. Many philosophers who have sought to situate moral reasoning in a naturalistic metaphysical conception have thought it necessary to adopt non-cognitivist, prescriptivist, projectivist, relativist, or otherwise deflationary conceptions. Recently there has been a revival of interest in non-deflationary moral realist approaches to ethical naturalism. Many non-deflationary approaches have exploited the resources of non-empiricist “causal” or “naturalistic” conceptions of reference and of kind (...) class='Hi'>definitions in service of the “naturalistic” metaphilosophical conception that substantive moral questions, and questions about the metaphysics of morals, are broadly a posteriori questions, somewhat analogous to scientific questions, and are not amenable to a priori resolution by “conceptual analysis.”. (shrink)

We show how to interpret Heyting's arithmetic in an intuitionistic version of TT, Russell's Simple Theory of Types. We also exhibit properties of finite sets in this theory and compare them with the corresponding properties in classical TT. Finally, we prove that arithmetic can be interpreted in intuitionistic TT, the subsystem of intuitionistic TT involving only three types. The definitions of intuitionistic TT and its finite sets and natural numbers are obtained in a straightforward way from the classical (...) class='Hi'>definitions. This is very natural and seems to make intuitionistic TT an interesting intuitionistic set theory to study, beside intuitionistic ZF. (shrink)

This contribution sheds light on the role of infinite idealization in structural analysis, by exploring how infinite elements and finite element methods are combined in civil engineering models. This combination, I claim, should be read in terms of a ‘complementarity function’ through which the representational ideal of completeness is reached in engineering model-building. Taking a cue from Weisberg’s definition of multiple-model idealization, I highlight how infinite idealizations are primarily meant to contribute to the prediction of structural behavior in Multiphysics approaches.

Discusses Frege's formal definitions and characterizations of infinite and finite sets. Speculates that Frege might have discovered the "oddity" in Dedekind's famous proof that all infinite sets are Dedekind infinite and, in doing so, stumbled across an axiom of countable choice.

We describe how finite colimits can be described using the internal lanuage, also known as the Mitchell-Benabou language, of a topos, provided the topos admits countably infinite colimits. This description is based on the set theoretic definitions of colimits and coequalisers, however the translation is not direct due to the differences between set theory and the internal language, these differences are described as internal versus external. Solutions to the hurdles which thus arise are given.

We present a theory that copes with the dynamics of inconsistent information. A method is set forth to represent possibly inconsistent information by a finite state. Next, finite operations for expansion and contraction of finite states are given. No extra-logical element — a choice function or an ordering over (sets of) sentences — is presupposed in the definition of contraction. Moreover, expansion and contraction are each other's duals. AGM-style characterizations of these operations follow.

two elements, one can eliminate definitions with a polynomial bound on the increase in proof length. In any classical first-order theory strong enough to code finite functions, including sequential theories, one can also eliminate Skolem functions with a polynomial bound on the increase in proof length.

From proofs in any classical first-order theory that proves the existence of at least two elements, one can eliminate definitions in polynomial time. From proofs in any classical first-order theory strong enough to code finite functions, including sequential theories, one can also eliminate Skolem functions in polynomial time.

Discusses Frege's formal definitions and characterizations of infinite and finite sets. Speculates that Frege might have discovered the "oddity" in Dedekind's famous proof that all infinite sets are Dedekind infinite and, in doing so, stumbled across an axiom of countable choice.

We refine the constructions of Ferrante-Rackoff and Solovay on iterated definitions in first-order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier-free case and in the case of purely existential or universal quantifiers, we show that (...) Ω quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao-Håstad switching lemma. (shrink)

We give a definition, in the ring language, of Zp inside Qp and of Fp[[t]] inside Fp), which works uniformly for all p and all finite field extensions of these fields, and in many other Henselian valued fields as well. The formula can be taken existential-universal in the ring language, and in fact existential in a modification of the language of Macintyre. Furthermore, we show the negative result that in the language of rings there does not exist a uniform definition (...) by an existential formula and neither by a universal formula for the valuation rings of all the finite extensions of a given Henselian valued field. We also show that there is no existential formula of the ring language defining Zp inside Qp uniformly for all p. For any fixed finite extension of Qp, we give an existential formula and a universal formula in the ring language which define the valuation ring. (shrink)

This contribution sheds light on the role of infinite idealization in structural analysis, by exploring how infinite elements and finite element methods are combined in civil engineering models. This combination, I claim, should be read in terms of a ‘complementarity function’ through which the representational ideal of completeness is reached in engineering model-building. Taking a cue from Weisberg’s definition of multiple-model idealization, I highlight how infinite idealizations are primarily meant to contribute to the prediction of structural behavior in Multiphysics approaches.

This paper obtains the weak completeness and decidability results for standard systems of modal logic using models built from formulas themselves. This line of work began with Fine (Notre Dame J. Form. Log. 16:229-237, 1975). There are two ways in which our work advances on that paper: First, the definition of our models is mainly based on the relation Kozen and Parikh used in their proof of the completeness of PDL, see (Theor. Comp. Sci. 113-118, 1981). The point is to (...) develop a general model-construction method based on this definition. We do this and thereby obtain the completeness of most of the standard modal systems, and in addition apply the method to some other systems of interest. None of the results use filtration, but in our final section we explore the connection. (shrink)

In this note we shall assume acquaintance with [T4] and the parts of [T1] which deal with intuitionistic arithmetic in all finite types. The bibliography just continues the bibliography of [T4].The principal purpose of this note is the discussion of two models for intuitionistic finite type arithmetic with fan functional. The first model is needed to correct an oversight in the proof of Theorem 6 [T4, §5]: the model ECF+as defined there cannot be shown to have the required properties inEL+ (...) QF-AC, the reason being that a change in the definition ofW12alone does not suffice—if one wishes to establish closure under the operations of HAωthe definitions ofW1σfor other σ have to be adopted as well. It is difficult to see how to do this directly in a uniform way — but we succeed via a detour, which is described in §2.For a proper understanding, we should perhaps note already here thaton the assumption of the fan theorem, ECF+as defined in [T4] and the new model of this note coincide ; but inELit is impossible to prove this. (shrink)

The prospects and limitations of defining truth in a finite model in the same language whose truth one is considering are thoroughly examined. It is shown that in contradistinction to Tarski's undefinability theorem for arithmetic, it is in a definite sense possible in this case to define truth in the very language whose truth is in question.

This paper presents an in-depth analysis of the anatomy of both thermodynamics and statistical mechanics, together with the relationships between their constituent parts. Based on this analysis, using the renormalization group and finite-size scaling, we give a definition of a large but finite system and argue that phase transitions are represented correctly, as incipient singularities in such systems. We describe the role of the thermodynamic limit. And we explore the implications of this picture of critical phenomena for the questions of (...) reduction and emergence. (shrink)

We use finite model theory to prove:Let m ≥ 2. Then: If there exists k such that NP ⊆ σmTIME ∩ ΠmTIME, then for every r there exists kr such that PNP[nr] ⊆ σmTIME ∩ ΠmTIME; If there exists a superpolynomial time-constructible function f such that NTIME ⊆ Σpm ∪ Πpm, then additionally PNP[nr] ⊈ Σpm ∪ Πpm.This strengthens a result by Mocas [M96] that for any r, PNP[nr] ⊈ NEXP.In addition, we use FM-truth definitions to give a simple (...) sufficient condition for the σ11 arity hierarchy to be strict over finite models. (shrink)

We consider the problem of constructing first-order definitions in the language of rings of holomorphy rings of one-variable function fields of characteristic 0 in their integral closures in finite extensions of their fraction fields and in bigger holomorphy subrings of their fraction fields. This line of questions is motivated by similar existential definability results over global fields and related questions of Diophantine decidability.

We discuss Herzberg’s :319–337, 2015) treatment of linear aggregation for profiles of infinitely many finitely additive probabilities and suggest a natural alternative to his definition of linear continuous aggregation functions. We then prove generalizations of well-known characterization results due to :410–414, 1981). We also characterize linear aggregation of probabilities in terms of a Pareto condition, de Finetti’s notion of coherence, and convexity.

We carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and lower (...) bounds established here cannot be made substantially tighter, unless outstanding conjectures in complexity theory are resolved at the same time. (shrink)

We investigate the issues of Diophantine definability over the non-finitely generated version of non-degenerate modules contained in the infinite algebraic extensions of the rational numbers. In particular, we show the following. Let k be a number field and let K inf be a normal algebraic, possibly infinite, extension of k such that k has a normal extension L linearly disjoint from K inf over k. Assume L is totally real and K inf is totally complex. Let M inf be a (...) non-degenerate O k -module, possibly non-finitely generated and contained in O Kinf . Then M inf contains a submodule M¯ inf such that M inf /M¯ inf is torsion and O k has a Diophantine definition over M¯ inf. (shrink)

Until Tarski’s semantic truth definition, the concept of truth was used informally in metalogic (metamathematics) or even proposed to be eliminated in favour of syntactic concepts, as in Rudolf Carnap’s early programme of philosophy via logical syntax. Tarski demonstrated that the concept of truth can be defined using precise mathematical devices. If L is a language for which the truth definition is given, it must be done in the metalanguage ML. According to this construction, semantics for L must be performed (...) in ML. The most important example concerns the arithmetic of natural numbers. According to Tarski’s theorem of undefinability, the set of truths of this theory cannot be defined in it – such a definition can be formulated in the metatheory. This fact illuminates the relation between syntax and semantics. If Th is a rich theory and presented as a syntactic theory (a calculus), its semantics is not reducible to its syntax. According to Tarski’s view, related to his work in the simple theory of types, semantics for L can be always constructed in the morphology of ML, provided that L is of the finite order. Two problems arise: what does the word “morphology” mean and how to formulate these ideas, when the framework is based on the distinction between first‑order logic and higher‑order logic. As far as the issue concerns morphology, it is possible to consider it as an extended syntax, i.e. vocabulary which does not refer to semantic concepts or defines such notions by not‑semantic, e.g. set‑theoretical, categories. If the hierarchy of logical types is replaced by the distinction of logics of various orders, in particular between first‑order and higher‑order (it is sufficient to use second‑order), it is possible to show that semantics of first‑order rich theories cannot be defined inside them. (shrink)

In the paper we formulate a sufficient criterion in order for the first order theory with finite set of axioms to be represented by definitions in predicate calculus. We prove the corresponding theorem. According to this criterion such theories as the theory of equivalence relation, the theory of partial order and many theories based on the equality relation with finite set of functional and predicate symbols are represented by definitions in the first-order predicate calculus without equality.

Definition in the genre of travel writing has a special status: the discovery of otherness leads to a new relationship between language and the world. In this genre, written by lexicologists who are often amateurs, the definition of an absent reality evolves between analogy, approximation and invention.

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite (...) satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic. (shrink)

A characterization of a property of binary relations is of finite type if it is stated in terms of ordered T-tuples of alternatives for some positive integer T. The concept was introduced informally by Knoblauch (2005). We give a clear, complete definition below. We prove that a characterization of finite type can be used to determine in polynomial time whether a binary relation over a finite set has the property characterized. We also prove a simple but useful nonexistence theorem and (...) apply it to three examples. (shrink)

In \(\textbf{ZF}\), the well-known Fichtenholz–Kantorovich–Hausdorff theorem concerning the existence of independent families of _X_ of size \(|{\mathcal {P}} (X)|\) is equivalent to the following portion of the equally well-known Hewitt–Marczewski–Pondiczery theorem concerning the density of product spaces: “The product \({\textbf{2}}^{{\mathcal {P}}(X)}\) has a dense subset of size |_X_|”. However, the latter statement turns out to be strictly weaker than \(\textbf{AC}\) while the full Hewitt–Marczewski–Pondiczery theorem is equivalent to \(\textbf{AC}\). We study the relative strengths in \(\textbf{ZF}\) between the statement “_X_ has (...) no independent family of size \(|{\mathcal {P}}(X)|\) ” and some of the definitions of “_X_ is finite” studied in Levy’s classic paper, observing that the former statement implies one such definition, is implied by another, and incomparable with some others. (shrink)

The goal of this paper is to define and study the notion of infinity in the framework of finitely supported structures, presenting new properties of infinite cardinalities. Some of these properties are extended from the non-atomic Zermelo–Fraenkel set theory to the world of atomic objects with finite support, while other properties are specific to finitely supported structures. We compare alternative definitions for infinity in the world of finitely supported sets, and provide relevant examples of atomic sets which satisfy some (...) forms of infinity, while do not satisfy others. Finally, we provide a characterization of finitely supported countable sets. (shrink)

Quasi-set theory Q is an alternative set-theory designed to deal mathematically with collections of indistinguishable objects. The intended interpretation for those objects is the indistinguishable particles of non-relativistic quantum mechanics, under one specific interpretation of that theory. The notion of cardinal of a collection in Q is treated by the concept of quasi-cardinal, which in the usual formulations of the theory is introduced as a primitive symbol, since the usual means of cardinal definition fail for collections of indistinguishable objects. In (...) a recent work, Domenech and Holik have proposed a definition of quasi-cardinality in Q. They claimed their definition of quasi-cardinal not only avoids the introduction of that notion as a primitive one, but also that it may be seen as a first step in the search for a version of Q that allows for a greater representative power. According to them, some physical systems can not be represented in the usual formulations of the theory, when the quasi-cardinal is considered as primitive. In this paper, we discuss their proposal and aims, and also, it is presented a modification from their definition we believe is simpler and more general. (shrink)

In [3] a certain family of topological spaces was introduced on ultraproducts. These spaces have been called ultratopologies and their definition was motivated by model theory of higher order logics. Ultratopologies provide a natural extra topological structure for ultraproducts. Using this extra structure in [3] some preservation and characterization theorems were obtained for higher order logics. The purely topological properties of ultratopologies seem interesting on their own right. We started to study these properties in [2], where some questions remained open. (...) Here we present the solutions of two such problems. More concretely we show 1. that there are sequences of finite sets of pairwise different cardinalities such that in their certain ultraproducts there are homeomorphic ultratopologies and 2. if A is an infinite ultraproduct of finite sets, then every ultratopology on A contains a dense subset D such that |D| < |A|. (shrink)

Defeasible conditionals are statements of the form ‘if A then normally B’. One plausible interpretation introduced in nonmonotonic reasoning dictates that ) is true iff B is true in ‘most’ A-worlds. In this paper, we investigate defeasible conditionals constructed upon a notion of ‘overwhelming majority’, defined as ‘truth in a cofinite subset of \’, the first infinite ordinal. One approach employs the modal logic of the frame \\), used in the temporal logic of discrete linear time. We introduce and investigate (...) conditionals, defined modally over \\); several modal definitions of the conditional connective are examined, with an emphasis on the nonmonotonic ones. An alternative interpretation of ‘majority’ as sets cofinal ) rather than cofinite ) is examined. For these modal approaches over \\), a decision procedure readily emerges, as the modal logic \ of this frame is well-known and a translation of the conditional sentences can be mechanically checked for validity; this allows also for a quick proof of \-completeness of the satisfiability problem for these logics. A second approach employs the conditional version of Scott-Montague semantics, in the form of \-many possible worlds, endowed with neighborhoods populated by collections of cofinite subsets of \. This approach gives rise to weak conditional logics, as expected. The relative strength of the conditionals introduced is compared to KLM logics and other conditional logics in the literature. (shrink)

We examine a definition of the mutual information of two reals proposed by Levin in [5]. The mutual information iswhereK is the prefix-free Kolmogorov complexity. A realAis said to have finite self-information ifI is finite. We give a construction for a perfect Π10class of reals with this property, which settles some open questions posed by Hirschfeldt and Weber. The construction produces a perfect set of reals withK≤+KA+f for any given Δ20fwith a particularly nice approximation and for a specific choice of (...) f it can also be used to produce a perfect Π10set of reals that are low for effective Hausdorff dimension and effective packing dimension. The construction can be further adapted to produce a single perfect set of reals that satisfyK≤+KA+f for allfin a ‘nice’ class of Δ20functions which includes all Δ20orders. (shrink)

We don't yet have adequate theories of what the human mind is representing when it represents a social group. Worse still, many people think we do. This mistaken belief is a consequence of the state of play: Until now, researchers have relied on their own intuitions to link up the conceptsocial groupon the one hand and the results of particular studies or models on the other. While necessary, this reliance on intuition has been purchased at a considerable cost. When looked (...) at soberly, existing theories of social groups are either (i) literal, but not remotely adequate (such as models built atop economic games), or (ii) simply metaphorical (typically a subsumption or containment metaphor). Intuition is filling in the gaps of an explicit theory. This paper presents a computational theory of what, literally, a group representation is in the context of conflict: It is the assignment of agents to specific roles within a small number of triadic interaction types. This “mental definition” of a group paves the way for acomputational theory of social groups– in that it provides a theory of what exactly the information-processing problem of representing and reasoning about a group is. For psychologists, this paper offers a different way to conceptualize and study groups, and suggests that a non-tautological definition of a social group is possible. For cognitive scientists, this paper provides a computational benchmark against which natural and artificial intelligences can be held. (shrink)

Hegel's Science of Logic makes the just not low claim to be an absolute, ultimate-grounded knowledge. This project, which could not be more ambitious, has no good press in our post-metaphysical age. However: That absolute knowledge absolutely cannot exist, cannot be claimed without self-contradiction. On the other hand, there can be no doubt about the fundamental finiteness of knowledge. But can absolute knowledge be finite knowledge? This leads to the problem of a self-explication of logic (in the sense of (...) Hegel) and further, as will be shown, to a new definition of the dialectical procedure. The stringency of which results from the fact that always exactly that implicit content is explicated that was generated by the preceding explication step itself and is thus concretely comprehensible. At the same time, a new implicit content is generated by this act of explication, which requires a new explication step, and so forth. In the dialectical procedure reinterpreted in this way, dialectical arguments are not beheld, guessed at or even surreptitiously obtained, but are methodically accountable. Thereby dialectics is understood as a self-explication of logic by logical means and thus as a proof of the possibility of ultimate-grounding in the form of absolute and nevertheless finite – and thus also fallible – knowledge. (shrink)

Following Henkin's discovery of partially-ordered (branching) quantification (POQ) with standard quantifiers in 1959, philosophers of language have attempted to extend his definition to POQ with generalized quantifiers. In this paper I propose a general definition of POQ with 1-place generalized quantifiers of the simplest kind: namely, predicative, or "cardinality" quantifiers, e.g., "most", "few", "finitely many", "exactly α", where α is any cardinal, etc. The definition is obtained in a series of generalizations, extending the original, Henkin definition first to a general (...) definition of monotone-increasing (M↑) POQ and then to a general definition of generalized POQ, regardless of monotonicity. The extension is based on (i) Barwise's 1979 analysis of the basic case of M↑ POQ and (ii) my 1990 analysis of the basic case of generalized POQ. POQ is a non-compositional Ist-order structure, hence the problem of extending the definition of the basic case to a general definition is not trivial. The paper concludes with a sample of applications to natural and mathematical languages. (shrink)