We consider natural strengthenings of H. Friedman's Borel diagonalization propositions and characterize their consistency strengths in terms of the n -subtle cardinals. After providing a systematic survey of regressive partition relations and their use in recent independence results, we characterize n -subtlety in terms of such relations requiring only a finite homogeneous set, and then apply this characterization to extend previous arguments to handle the new Borel diagonalization propositions.

We consider several kinds of partition relations on the set ${\mathbb{R}}$ of real numbers and its powers, as well as their parameterizations with the set ${[\mathbb{N}]^{\mathbb{N}}}$ of all infinite sets of natural numbers, and show that they hold in some models of set theory. The proofs use generic absoluteness, that is, absoluteness under the required forcing extensions. We show that Solovay models are absolute under those forcing extensions, which yields, for instance, that in these models for every well (...) ordered partition of ${\mathbb{R}^\mathbb{N}}$ there is a sequence of perfect sets whose product lies in one piece of the partition. Moreover, for every finite partition of ${[\mathbb{N}]^{\mathbb{N}} \times \mathbb{R}^{\mathbb{N}}}$ there is ${X \in [\mathbb{N}]^{\mathbb{N}}}$ and a sequence ${\{P_{k} : k \in \mathbb{N}\}}$ of perfect sets such that the product ${[X]^{\mathbb{N}} \times \prod_{k}^{\infty}P_{k}}$ lies in one piece of the partition, where ${[X]^{\mathbb{N}}}$ is the set of all infinite subsets of X. The proofs yield the same results for Borel partitions in ZFC, and for more complex partitions in any model satisfying a certain degree of generic absoluteness. (shrink)

We consider colorings of the pairs of a family \ of topological type \, for \; and we find a homogeneous family \ for each coloring. As a consequence, we complete our study of the partition relation \^2_{l,m}}\) identifying \ as the smallest ordinal space \^2_{l,4}}\).

Several canonical partition theorems are obtained, including a simultaneous generalization of Neumer's lemma and the Erdos-Rado theorem. The canonical partition relation for infinite cardinals is completely determined, answering a question of Erdos and Rado. Counterexamples are given showing that in several ways these results cannot be improved.

We study the subtlety of a cardinal κ and of. We show that, under a certain large cardinal assumption, it is consistent that is subtle for some but κ is not subtle, and the consistency of such a situation is much stronger than the existence of a subtle cardinal. We show that the subtlety of can be characterized by a certain partition relation on. We also study the property of faintness of κ, and the subtlety of with the strong (...) inclusion. (shrink)

It is a theorem of Rowbottom [12] that ifκis measurable andIis a normal prime ideal onκ, then for eachλ<κ,In this paper a natural structural property of ideals, distributivity, is considered and shown to be related to this and other ideal theoretic partition relations.The set theoretical terminology is standard and background results on the theory of ideals may be found in [5] and [8]. Throughoutκwill denote an uncountable regular cardinal, andIa proper, nonprincipal,κ-complete ideal onκ.NSκis the ideal of nonstationary subsets (...) ofκ, andIκ= {X⊆κ∣∣X∣<κ}. IfA∈I+ −I), then anI-partitionofAis a maximal collectionW⊆,P ∩I+so thatX∩ Y ∈IwheneverX, Y∈W, X≠Y. TheI-partitionWis said to be disjoint if distinct members ofWare disjoint, and in this case, fordenotes the unique member ofWcontainingξ. A sequence 〈Wα∣α<η} ofI-partitions ofAis said to be decreasing if wheneverα<β<ηandX∈Wβthere is aY∈Wαsuch thatX⊆Y.. (shrink)

The goal of this short note is to interest set theorists in the order type ω*ω1, and to encourage them to work on the question of whether or not the Continuum Hypothesis decides the partition relation τ→2, for τ=ω*ω1 and for τ=ω1ω+2.

Using previous work of Baumgartner, Shelah and others, we describe, for each infinite cardinal θκ, the smallest κ-normal ideal J on Pκ such that.

We show that if κ is a weakly compact cardinal, then $\left( \matrix \kappa ^{+} \\ \kappa\endmatrix \right)\rightarrow \left(\left( \matrix \alpha \\ \kappa \endmatrix \right)_{m}\left( \matrix \kappa ^{n} \\ \kappa \endmatrix \right)_{\mu}\right)^{1,1}$ for any ordinals α < κ⁺ and µ < κ, and any finite ordinals m and n. This polarized partition relation represents the statement that for any partition $\kappa \times \kappa ^{+}=\underset i<m\to{\bigcup }K_{i}\cup \underset j<\mu \to{\bigcup }L_{j}$ of κ × κ⁺ into m + µ pieces (...) either there are A ∈ [κ]κ, B ∈ [κ⁺]α, and i < m with A × B ⊆ Ki or there are C ∈ [κ]κ, D ∈ [κ⁺]α, and j < μ with C × D ⊆ Lj. Related results for measurable and almost measurable κ are also investigated. Our proofs of these relations involve the use of elementary substructures of set models of large fragments of ZFC. (shrink)

We investigate the effect of adding $\omega _2$ Cohen reals on graphs on $\omega _2$, in particular we show that $\omega _2 \to (\omega _2, \omega : \omega )^2$ holds after forcing with $\mathsf {Add}(\omega, \omega _2)$ in a model of $\mathsf {CH}$. We also prove that this result is in a certain sense optimal as $\mathsf {Add}(\omega, \omega _2)$ forces that $\omega _2 \not \to (\omega _2, \omega : \omega _1)^2$.

Working in ZFC, we show that for any infinite cardinal κ and ordinal $\gamma the polarized partition relation $\[\begin{pmatrix} (2^{ → $\[\begin{pmatrix}(2^{ holds. Our proof of this relation involves the use of elementary substructures of set models of large fragments of ZFC.

Building upon earlier work of Donna Carr, Don Pelletier, Chris Johnson, Shu-Guo Zhang and others, we show that a normal ideal J on Pκ is strongly normal if and only if J+→< 2 for every μ < κ, and we describe the least normal ideal J on Pκ such that J+ →< 2.

It is shown that for any cardinal $\kappa, \dbinom{(2^{ , and if κ is weakly compact $\dbinom{\kappa^+}{\kappa} \rightarrow \dbinom{\kappa}{\kappa}_{.

We prove the independence of a strong partition relation on ℵ ω , answering a question of Erdos and Hajnal. We then give an almost complete answer to the free subset problem.

A fairly quotable special, but still representative, case of our main result is that for 2 ≤ n ≤ ω, there is a natural number m (n) such that, the following holds. Assume GCH: If $\lambda are regular, there is a cofinality preserving forcing extension in which 2 λ = μ and, for all $\sigma such that η +m(n)-1) ≤ μ, ((η +m(n)-1) ) σ ) → ((κ) σ ) η (1)n . This generalizes results of [3], Section 1, and (...) the forcing is a "many cardinals" version of the forcing there. (shrink)

The paper deals with a generalization of the notion of partition for wider classes of binary relations than equivalences: for quasiorders and tolerance relations. The counterpart of partition for the quasiorders is based on a generalization of the notion of equivalence class while it is shown that such a generalization does not work in case of tolerances. Some results from [5] are proved in a much more simple way. The third kind of “partition” corresponding to (...) tolerances, not occurring in [5], is introduced. (shrink)

Given a regular infinite cardinal κ and a cardinal λ > κ, we study fine ideals H on Pκ that satisfy the square brackets partition relation equation image, where μ is a cardinal ≥2.

We generalize a well-knownSmullyan's result, by showing that any two sets of the kindC a = {x/ xa} andC b = {x/ xb} are effectively inseparable (if I b). Then we investigate logical and recursive consequences of this fact (see Introduction).

Several types of polarized partition relations are considered. In particular we deal with partitions defined on cartesian products of more than two factors. MSC: 03E05.

We continue [21] and study partition numbers of partial orderings which are related to /fin. In particular, we investigate Pf, be the suborder of /fin)ω containing only filtered elements, the Mathias partial order M, and , ω the lattice of partitions of ω, respectively. We show that Solomon's inequality holds for M and that it consistently fails for Pf. We show that the partition number of is C. We also show that consistently the distributivity number of ω is (...) smaller than the distributivity number of /fin. We also investigate partitions of a Polish space into closed sets. We show that such a partition either is countable or has size at least D, where D is the dominating number. We also show that the existence of a dominating family of size 1 does not imply that a Polish space can be partitioned into 1 many closed sets. (shrink)

The Halpern–Läuchli theorem, a combinatorial result about trees, admits an elegant proof due to Harrington using ideas from forcing. In an attempt to distill the combinatorial essence of this proof, we isolate various partition principles about products of perfect Polish spaces. These principles yield straightforward proofs of the Halpern–Läuchli theorem, and the same forcing from Harrington’s proof can force their consistency. We also show that these principles are not ZFC theorems by showing that they put lower bounds on the (...) size of the continuum. (shrink)

An important part of the Unified Medical Language System (UMLS) is its Semantic Network, consisting of 134 Semantic Types connected to each other by edges formed by one or more of 54 distinct Relation Types. This Network is however for many purposes overcomplex, and various groups have thus made attempts at simplification. Here we take this work further by simplifying the relations which involve the three Semantic Types – Diagnostic Procedure, Laboratory Procedure and Therapeutic or Preventive Procedure. We define (...) operators which can be used to generate terms instantiating types from this selected set when applied to terms designating certain other Semantic Types, including almost all the terms specifying clinical tasks. Usage of such operators thus provides a useful and economical way of specifying clinical tasks. The operators allow us to define a mapping between those types within the UMLS which do not represent clinical tasks and those which do. This mapping then provides a basis for an ontology of clinical tasks that can be used in the formulation of computer-interpretable clinical guideline models. (shrink)

There are some who defend a view of vagueness according to which there are intrinsically vague objects or attributes in reality. Here, in contrast, we defend a view of vagueness as a semantic property of names and predicates. All entities are crisp, on this view, but there are, for each vague name, multiple portions of reality that are equally good candidates for being its referent, and, for each vague predicate, multiple classes of objects that are equally good candidates for being (...) its extension. We provide a new formulation of these ideas in terms of a theory of granular partitions. We show that this theory provides a general framework within which we can understand the relation between vague terms and concepts on the one hand and correlated portions of reality on the other. We also sketch how it might be possible to formulate within this framework a theory of vagueness which dispenses with the notion of truth-value gaps and other artifacts of more familiar approaches. (shrink)

The Axiom of Choice implies the Partition Principle and the existence, uniqueness, and monotonicity of (possibly infinite) sums of cardinal numbers. We establish several deductive relations among those principles and their variants: the monotonicity follows from the existence plus uniqueness; the uniqueness implies the Partition Principle; the Weak Partition Principle is strictly stronger than the Well-Ordered Choice.

We have a variety of different ways of dividing up, classifying, mapping, sorting and listing the objects in reality. The theory of granular partitions presented here seeks to provide a general and unified basis for understanding such phenomena in formal terms that is more realistic than existing alternatives. Our theory has two orthogonal parts: the first is a theory of classification; it provides an account of partitions as cells and subcells; the second is a theory of reference or intentionality; it (...) provides an account of how cells and subcells relate to objects in reality. We define a notion of well-formedness for partitions, and we give an account of what it means for a partition to project onto objects in reality. We continue by classifying partitions along three axes: (a) in terms of the degree of correspondence between partition cells and objects in reality; (b) in terms of the degree to which a partition represents the mereological structure of the domain it is projected onto; and (c) in terms of the degree of completeness with which a partition represents this domain. (shrink)

There are well-known isomorphisms between the complete lattice of all partitions of a given set A and the lattice of all equivalence relations on A. In the paper the notion of partition is generalized in order to work correctly for wider classes of binary relations than equivalence ones such as quasiorders or tolerance relations. Some others classes of binary relations and corresponding counterparts of partitions are considered.

Classical logic is usually interpreted as the logic of propositions. But from Boole's original development up to modern categorical logic, there has always been the alternative interpretation of classical logic as the logic of subsets of any given (nonempty) universe set. Partitions on a universe set are dual to subsets of a universe set in the sense of the reverse-the-arrows category-theoretic duality--which is reflected in the duality between quotient objects and subobjects throughout algebra. Hence the idea arises of a dual (...) logic of partitions. That dual logic is described here. Partition logic is at the same mathematical level as subset logic since models for both are constructed from (partitions on or subsets of) arbitrary unstructured sets with no ordering relations, compatibility or accessibility relations, or topologies on the sets. Just as Boole developed logical finite probability theory as a quantitative treatment of subset logic, applying the analogous mathematical steps to partition logic yields a logical notion of entropy so that information theory can be refounded on partition logic. But the biggest application is that when partition logic and the accompanying logical information theory are "lifted" to complex vector spaces, then the mathematical framework of quantum mechanics is obtained. Partition logic models indefiniteness (i.e., numerical attributes on a set become more definite as the inverse-image partition becomes more refined) while subset logic models the definiteness of classical physics (an entity either definitely has a property or definitely does not). Hence partition logic provides the backstory so the old idea of "objective indefiniteness" in QM can be fleshed out to a full interpretation of quantum mechanics. (shrink)

Our object is to study the interaction between mereology and David Lewis’ theory of subject-matters, elaborating his observation that not every subject matter is of the form: how things stand with such-and-such a part of the world. After an informal introduction to this point in Section 1, we turn to a formal treatment of the partial orderings arising in the two areas – the part-whole relation, on the one hand, and the relation of refinement amongst partitions of the set of (...) worlds, on the other. We emphasize a certain duality, formulated in and in Section 2, between the corresponding lattice operations – mereological joins with partition-lattice meets, mereological meets with partition-lattice joins. Section 3 presents some issues that are raised by consideration of the informally familiar idea of logical subtraction. These include, in particular, a problem about the need for a notion of independence different from the usual logical notion going by that name. The apparatus of Section 2 promises to throw some light on this problem, as we indicate in Section 4. Section 5 ties up some loose ends and suggests an area in which further work would be desirable. (shrink)

Current theories make a distinction between two types of case, STRUCTURAL case and INHERENT (or LEXICAL) case (Chomsky 1981), similar to the older distinction between GRAMMATICAL and SEMANTIC case (Kuryłowicz 1964).1 Structural case is assumed to be assigned at S-structure in a purely configurational way, whereas inherent case is assigned at D-structure in possible dependence on the governing predicates’s lexical properties. It is well known that not all cases fall cleanly into this typology. In particular, there is a class of (...) cases that pattern syntactically with the structural cases, but are semantically conditioned. These cases however depend on different semantic conditions than inherent cases do: instead of being sensitive to the thematic relation that the NP bears to the verbal predicate, they are sensitive to the NP’s definiteness, animacy, or quantificational properties, or to the aspectual character of the VP, or to some combination of these factors. The Finnish partitive is a particularly clear instance of this apparently hybrid category of semantically conditioned structural case. (shrink)

Several stepping up lemmas are proved which are then used to investigate the connection between definable partition relations and admissible ordinals.

The partitions of a given set stand in a well known one-to-onecorrespondence with the equivalence relations on that set. We askwhether anything analogous to partitions can be found which correspondin a like manner to the similarity relations (reflexive, symmetricrelations) on a set, and show that (what we call) decompositions – of acertain kind – play this role. A key ingredient in the discussion is akind of closure relation (analogous to the consequence relationsconsidered in formal logic) having nothing especially (...) to do with thesimilarity issue, and we devote a final section to highlighting some ofits properties. (shrink)

We study the partition relation $X@>{\rm w}>>[Y]_{p}^{2}$ that is a weakening of the usual partition relation $X\rightarrow [Y]_{p}^{2}$ . Our main result asserts that if κ is an uncountable strongly compact cardinal and $\germ{d}_{\kappa}\leq \lambda ^{<\kappa}$ , then $I_{\kappa,\lambda}^{+}@>{\rm w}>>[I_{\kappa,\lambda}^{+}]_{\lambda <\kappa}^{2}$ does not hold.

We study tree-like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the partition width of models is bounded, or the theory admits definable pairing functions. Our proof rests on structure results concerning indiscernible sequences and finitely satisfiable types for theories without definable pairing functions. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

A new logic of partitions has been developed that is dual to ordinary logic when the latter is interpreted as the logic of subsets of a fixed universe rather than the logic of propositions. For a finite universe, the logic of subsets gave rise to finite probability theory by assigning to each subset its relative size as a probability. The analogous construction for the dual logic of partitions gives rise to a notion of logical entropy that is precisely related to (...) Claude Shannon's entropy. In this manner, the new logic of partitions provides a logico-conceptual foundation for information-theoretic entropy or information content. (shrink)

T. K. Menas [4, pp. 225-234] introduced a combinatorial property χ (μ) of a measure μ on a supercompact cardinal κ and proved that measures with this property also have the partition property. We prove here that Menas' property is not equivalent to the partition property. We also show that if α is the least cardinal greater than κ such that P κ α bears a measure without the partition property, then α is inaccessible and Π 2 (...) 1 -indescribable. (shrink)