Model Theory

George Lakoff (in his book Women, Fire, and Dangerous Things(1987) and the paper "Cognitive semantics" (1988)) champions some radical foundational views. Strikingly, Lakoff opposes realism as a metaphysical position, favoring instead some supposedly mild form of idealism such as that recently espoused by Hilary Putnam, going under the name "internal realism." For what he takes to be connected reasons, Lakoff also rejects truth conditional model-theoretic semantics for natural language. This paper examines an argument, given by Lakoff, against realism and MTS. (...) We claim that Lakoff's argument has very little, if any, impact for linguistic semantics. (shrink)

It is proved that $\Pi^1_1$ -indescribability in $P_{\kappa}\lambda$ can be characterized by combinatorial properties without taking care of cofinality of $\lambda$ . We extend Carr's theorem proving that the hypothesis $\kappa$ is $2^{\lambda^{<\kappa}}$ -Shelah is rather stronger than $\kappa$ is $\lambda$ -supercompact.

We study the distributivity of the bounded ideal on Pkλ and answer negatively to a question of Johnson in [13]. The size of non-normal ideals with the partition property is also studied.

We investigate the partition property of ${\mathcal{P}_{\kappa}\lambda}$ . Main results of this paper are as follows: (1) If λ is the least cardinal greater than κ such that ${\mathcal{P}_{\kappa}\lambda}$ carries a (λ κ , 2)-distributive normal ideal without the partition property, then λ is ${\Pi^1_n}$ -indescribable for all n < ω but not ${\Pi^2_1}$ -indescribable. (2) If cf(λ) ≥ κ, then every ineffable subset of ${\mathcal{P}_{\kappa}\lambda}$ has the partition property. (3) If cf(λ) ≥ κ, then the completely ineffable ideal over (...) ${\mathcal{P}_{\kappa}\lambda}$ has the partition property. (shrink)

Assuming the existence of a supercompact cardinal and a weakly compact cardinal above it, we provide a generic extension where there are no Aronszajn trees of height ω 2 or ω 3 . On the other hand we show that some large cardinal assumptions are necessary for such a consistency result.

We present some techniques in c.c.c. forcing, and apply them to prove consistency results concerning the isomorphism and embeddability relations on the family of ℵ 1 -dense sets of real numbers. In this direction we continue the work of Baumgartner [2] who proved the axiom BA stating that every two ℵ 1 -dense subsets of R are isomorphic, is consistent. We e.g. prove Con). Let K H , be the set of order types of ℵ 1 -dense homogeneous subsets of (...) R with the relation of embeddability. We prove that for every finite model L , : Con iff L is a distributive lattice. We prove that it is consistent that the Magidor-Malitz language is not countably compact. We deal with the consistency of certain topological partition theorems. E.g. We prove that MA is consistent with the axiom OCA which says: “If X is a second countable space of power ℵ 1 , and { U 0 ,\h.;, U n−1 } is a cover of D ▪ X x X -} x,x> ¦ x ϵ X } consisting of symmetric open sets, then X can be partitioned into { X i \brvbar; i ϵ ω } such that for every i ϵ ω there is l such that D ⊇ U l ”. We also prove that MA+OCA [xrArr] 2 ℵ 0 = ℵ 2. (shrink)

A forcing poset of size 221 which adds no new reals is described and shown to provide a Δ22 definable well-order of the reals . The encoding of this well-order is obtained by playing with products of Aronszajn trees: some products are special while other are Suslin trees. The paper also deals with the Magidor–Malitz logic: it is consistent that this logic is highly noncompact.

We pursue a model-oriented rather than axiomatic approach to the foundations of Quantum Mechanics, with the idea that new models can often suggest new axioms. This approach has often been fruitful in Logic and Theoretical Computer Science. Rather than seeking to construct a simplified toy model, we aim for a 'big toy model', in which both quantum and classical systems can be faithfully represented—as well as, possibly, more exotic kinds of systems. To this end, we show how Chu spaces can (...) be used to represent physical systems of various kinds. In particular, we show how quantum systems can be represented as Chu spaces over the unit interval in such a way that the Chu morphisms correspond exactly to the physically meaningful symmetries of the systems—the unitaries and antiunitaries. In this way we obtain a full and faithful functor from the groupoid of Hubert spaces and their symmetries to Chu spaces. We also consider whether it is possible to use a finite value set rather than the unit interval; we show that three values suffice, while the two standard possibilistic reductions to two values both fail to preserve fullness. (shrink)

Genericity is the idea that the same program can work at many different data types. Longo, Milstead and Soloviev proposed to capture the inability of generic programs to probe the structure of their instances by the following equational principle: if two generic programs, viewed as terms of type , are equal at any given instance A[T], then they are equal at all instances. They proved that this rule is admissible in a certain extension of System F, but finding a semantically (...) motivated model satisfying this principle remained an open problem.In the present paper, we construct a categorical model of polymorphism, based on game semantics, which contains a large collection of generic types. This model builds on two novel constructions:•A direct interpretation of variable types as games, with a natural notion of substitution of games. This allows moves in games A[T] to be decomposed into the generic part from A, and the part pertaining to the instance T. This leads to a simple and natural notion of generic strategy.•A “relative polymorphic product” which expresses quantification over the type variable Xi in the variable type A with respect to a “universe” which is explicitly given as an additional parameter B. We then solve a recursive equation involving this relative product to obtain a universe in a suitably “absolute” sense.Full Completeness for ML types is proved for this model. (shrink)

Let α be any countable admissible ordinal greater than ω. There is a transitive set A such that A is admissible, locally countable, On A = α, and A satisfies Σ 1 -separation. In fact, if B is any nonstandard model of $KP + \forall x \subseteq \omega$ (the hyperjump of x exists), the ordinal standard part of B is greater than ω, and every standard ordinal in B is countable in B, then HC B ∩ (standard part of B) (...) satisfies Σ 1 -separation. (shrink)

Let A be a standard transitive admissible set. Σ 1 -separation is the principle that whenever X and Y are disjoint Σ A 1 subsets of A then there is a Δ A 1 subset S of A such that $X \subseteq S$ and $Y \cap S = \varnothing$ . Theorem. If A satisfies Σ 1 -separation, then (1) If $\langle T_n\mid n is a sequence of trees on ω each of which has at most finitely many infinite paths in (...) A then the function $n\mapsto$ (set of infinite paths in A through T n ) is in A. (2) If A is not closed under hyperjump and α = On A then A has in it a nonstandard model of V = L whose ordinal standard part is α. Theorem. Let α be any countable admissible ordinal greater than ω. Then there is a model of Σ 1 -separation whose height is α. (shrink)

For T any completion of Peano Arithmetic and for n any positive integer, there is a model of T of size $\beth_n$ with no (n + 1)-length sequence of indiscernibles. Hence the Hanf number for omitting types over T, H(T), is at least $\beth_\omega$ . (Now, using an upper bound previously obtained by Julia Knight H (true arithmetic) is exactly $\beth_\omega$ ). If T ≠ true arithmetic, then $H(T) = \beth_{\omega1}$ . If $\delta \not\rightarrow (\rho)^{ , then any completion of (...) Peano Arithmetic has a model of size δ with no set of indiscernibles of size ρ. There are similar results for theories strongly resembling Peano Arithmetic, e.g., ZF + V = L. (shrink)

Suppose that $\sigma\in{\mathcal{L}}_{\omega _{1},\omega }$ is such that all equations occurring in $\sigma$ are positive, have the same set of variables on each side of the equality symbol, and have at least one function symbol on each side of the equality symbol. We show that $\sigma$ satisfies Vaught’s conjecture. In particular, this proves Vaught’s conjecture for sentences of $ {\mathcal{L}}_{\omega _{1},\omega }$ without equality.

Working in a fixed Grothendieck topos Sh(C, J C ) we generalize \({\mathcal{L}_{{\infty},\omega}}\) to allow our languages and formulas to make explicit reference to Sh(C, J C ). We likewise generalize the notion of model. We then show how to encode these generalized structures by models of a related sentence of \({\mathcal{L}_{{\infty},\omega}}\) in the category of sets and functions. Using this encoding we prove analogs of several results concerning \({\mathcal{L}_{{\infty},\omega}}\) , such as the downward Löwenheim–Skolem theorem, the completeness theorem and (...) Barwise compactness. (shrink)

The axiom of choice ensures precisely that, in ZFC, every set is projective: that is, a projective object in the category of sets. In constructive ZF (CZF) the existence of enough projective sets has been discussed as an additional axiom taken from the interpretation of CZF in Martin-Löf’s intuitionistic type theory. On the other hand, every non-empty set is injective in classical ZF, which argument fails to work in CZF. The aim of this paper is to shed some light on (...) the problem whether there are (enough) injective sets in CZF. We show that no two element set is injective unless the law of excluded middle is admitted for negated formulas, and that the axiom of power set is required for proving that “there are strongly enough injective sets”. The latter notion is abstracted from the singleton embedding into the power set, which ensures enough injectives both in every topos and in IZF. We further show that it is consistent with CZF to assume that the only injective sets are the singletons. In particular, assuming the consistency of CZF one cannot prove in CZF that there are enough injective sets. As a complement we revisit the duality between injective and projective sets from the point of view of intuitionistic type theory. (shrink)

Finitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by σ-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.

Finitary quasivarieties are characterized categorically by the existence of colimits and of an abstractly finite, regularly projective regular generator G. Analogously, infinitary quasivarieties are characterized: one drops the assumption that G be abstractly finite. For (finitary) varieties the characterization is similar: the regular generator is assumed to be exactly projective, i.e., hom(G, –) is an exact functor. These results sharpen the classical characterization theorems of Lawvere, Isbell and other authors.

We formulate a Π1 sentence τ which is a version of the Tableau consistency of GlΔ0. The sentence τ is true and is provable in GlΔ0 + exp. We construct a model M of GlΔ0+Ω1+τ+BGs1 which has no proper end-extension to a model of GlΔ0+Ω1+τ. Also we prove that GlΔ0+Ω1+τ is not Π1 conservative over GlΔ0+τ.

We prove that any 1-closed (see def 1.1) model of the Π 2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Godel incompleteness theorem without the use of the Godel diagonal lemma. We prove a few other theorems by the same method.

The Birkhoff-Maltsev problem asks for a characterization of those lattices each of which is isomorphic to the lattice L(K) of all subquasivarieties for some quasivariety K of algebraic systems. The current status of this problem, which is still open, is discussed. Various unsolved questions that are related to the Birkhoff-Maltsev problem are also considered, including ones that stem from the theory of propositional logics.

LetL(K) denote the lattice (ordered by inclusion) of quasivarieties contained in a quasivarietyK and letD 2 denote the variety of distributive (0, 1)-lattices with 2 additional nullary operations. In the present paperL(D 2) is described. As a consequence, ifM+N stands for the lattice join of the quasivarietiesM andN, then minimal quasivarietiesV 0,V 1, andV 2 are given each of which is generated by a 2-element algebra and such that the latticeL(V 0+V1), though infinite, still admits an easy and nice description (...) (see Figure 2) while the latticeL(V 0+V1+V2), because of its intricate inner structure, does not. In particular, it is shown thatL(V 0+V1+V2) contains as a sublattice the ideal lattice of a free lattice with free generators. Each of the quasivarietiesV 0,V 1, andV 2 is generated by a 2-element algebra inD 2. (shrink)