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)

In the present version of these lecture notes only a number of typos and a few glaring mistakes have been corrected. Thanks to Paul Dekker for his help in this respect. No attempt has been been made to update the original text or to incorporate new insights and approaches. For a more recent overview, see our ‘Questions’ in the Handbook of Logic and Language (edited by Johan van Benthem and Alice ter Meulen, Elsevier, 1997).

We introduce a notion of pseudo-reachability in Gaifman graphs and suggest a graph-theoretic and uniform approach to the Löwenheim-Skolem-Tarski Theorems for partition logics as well as logics with general Malitz quantifiers.

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)

Modern categorical logic as well as the Kripke and topological models of intuitionistic logic suggest that the interpretation of ordinary “propositional” logic should in general be the logic of subsets of a given universe set. Partitions on a set are dual to subsets of a set in the sense of the category-theoretic duality of epimorphisms and monomorphisms—which is reflected in the duality between quotient objects and subobjects throughout algebra. If “propositional” logic is thus seen as (...) the logic of subsets of a universe set, then the question naturally arises of a dual logic of partitions on a universe set. This paper is an introduction to that logic of partitions dual to classical subset logic. The paper goes from basic concepts up through the correctness and completeness theorems for a tableau system of partition logic. (shrink)

There are fundamentally two mathematical logics. One the Boolean logic of subsets, usually presented today in the special case of propositional logic, which has many sublogics and extensions, the most important being the intuitionistic logic usually modeled by the open subsets of a topological space. The other co-fundamental mathematical logic is the topic of this book, the logic of partitions. We are using ”logic” in a mathematical sense as being about basic mathematical objects, subsets (...) of a universe set or partitions on a universe set.1 Logic, in this mathematical sense, is not about propositions, although, as with any mathematical theory, it involves propositions about the basic objects, e.g., that an element is in a subset or that a distinction is made by a partition. Moreover, by taking the universe set to be the one element set 1, with two subsets ∅ and 1, there is a special case of subset logic, namely propositional logic, that can be interpreted as being about propositions with ∅ representing falsehood and 1 representing truth. (shrink)

The purpose of this paper is to show that the mathematics of quantum mechanics (QM) is the vector (Hilbert) space version of the mathematics of partitions at the set level. Since partitions are the math tool to describe indefiniteness and definiteness, this shows how the reality so well described by QM is a non-classical reality featuring the objective indefiniteness of superposition states. The lattice of partitions gives a skeletal model of quantum reality with the partition versions of pure states, (...) non-classical mixed states (i.e., including a superposition state), and the completely distinguished classical state that satisfies the partition logic version of the Principle of Identity of Indistinguishables. Both the key notions of quantum states and quantum observables are respectively the (density) matrix versions of partitions and vector space version of a numerical attributes. The operation of projective measurement given by the Lüders mixture operation is the vector space version of the partition join operation between the partition prefiguring the density matrix of the state being measured and the partition prefiguring the observable being measured. All this adds specific key concepts and structure to Abner Shimony’s idea of a literal understanding of QM to form what might be called the "Objective Indefiniteness Interpretation" of QM. (shrink)

It is shown that the notion of the partition of a set can be used to describe in a uniform way the meaning of the expression the same, in its basic uses in transitive and ditransitive sentences. Some formal properties of the function denoted by the same, which follow from such a description are indicated. These properties indicate similarities and differences between functions denoted by the same and generalised quantifiers.

Classical physics and quantum physics suggest two meta-physical types of reality: the classical notion of a objectively definite reality with properties "all the way down," and the quantum notion of an objectively indefinite type of reality. The problem of interpreting quantum mechanics (QM) is essentially the problem of making sense out of an objectively indefinite reality. These two types of reality can be respectively associated with the two mathematical concepts of subsets and quotient sets (or partitions) which are category-theoretically dual (...) to one another and which are developed in two mathematical logics, the usual Boolean logic of subsets and the more recent logic of partitions. Our sense-making strategy is "follow the math" by showing how the logic and mathematics of set partitions can be transported in a natural way to Hilbert spaces where it yields the mathematical machinery of QM--which shows that the mathematical framework of QM is a type of logical system over ℂ. And then we show how the machinery of QM can be transported the other way down to the set-like vector spaces over ℤ₂ showing how the classical logical finite probability calculus (in a "non-commutative" version) is a type of "quantum mechanics" over ℤ₂, i.e., over sets. In this way, we try to make sense out of objective indefiniteness and thus to interpret quantum mechanics. (shrink)

We consider finite partitions of the closure F¯ of an ωα-uniform barrier F. For each partition, we get a homogeneous set having both the same combinatorial and topological structure as F¯, seen as a subspace of the Cantor space 2N.

The theory of granular partitions is designed to capture in a formal framework important aspects of the selective character of common-sense views of reality. It comprehends not merely the ways in which we can view reality by conceiving its objects as gathered together not merely into sets, but also into wholes of various kinds, partitioned into parts at various levels of granularity. We here represent granular partitions as triples consisting of a rooted tree structure as first component, a domain satisfying (...) the axioms of Extensional Mereology as second component, and a mapping (called ’projection’) of the first into the second as a third component. We define ordering relations among granular partitions the resulting structures are called partition frames. We then introduce an axiomatic theory which sentences are interpreted in partition frames. (shrink)

The paper examines Schopenhauer’s complex diagrams from the Berlin Lectures of the 1820 s, which show certain partitions of classes. Drawing upon ideas and techniques from logical geometry, we show that Schopenhauer’s partition diagrams systematically give rise to a special type of Aristotelian diagrams, viz. (strong) α -structures.

Classical physics and quantum physics suggest two meta-physical types of reality: the classical notion of a objectively definite reality with properties "all the way down," and the quantum notion of an objectively indefinite type of reality. The problem of interpreting quantum mechanics is essentially the problem of making sense out of an objectively indefinite reality. These two types of reality can be respectively associated with the two mathematical concepts of subsets and quotient sets which are category-theoretically dual to one another (...) and which are developed in two dual mathematical logics, the usual Boolean logic of subsets and the more recent logic of partitions. Our sense-making strategy is "follow the math" by showing how the mathematics of set partitions can be transported in a natural way to complex vector spaces where it yields the mathematical machinery of QM. And then we show how the machinery of QM can be transported the other way down to set-like vector spaces over ℤ₂ yielding a rather fulsome "toy" or pedagogical model of "quantum mechanics over sets." In this way, we try to make sense out of objective indefiniteness and thus to interpret quantum mechanics. (shrink)

The paper examines Schopenhauer’s complex diagrams from the Berlin Lectures of the 1820 s, which show certain partitions of classes. Drawing upon ideas and techniques from logical geometry, we show that Schopenhauer’s partition diagrams systematically give rise to a special type of Aristotelian diagrams, viz. (strong) α -structures.

We show that Miller partition forcing preserves selective independent families and P-points, which implies the consistency of $\mbox {cof}(\mathcal {N})=\mathfrak {a}=\mathfrak {u}=\mathfrak {i}<\mathfrak {a}_T=\omega _2$. In addition, we show that Shelah’s poset for destroying the maximality of a given maximal ideal preserves tight mad families and so we establish the consistency of $\mbox {cof}(\mathcal {N})=\mathfrak {a}=\mathfrak {i}=\omega _1<\mathfrak {u}=\mathfrak {a}_T=\omega _2$.

There exist two main notions of typicality in computability theory, namely, Cohen genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity, which is at the intersection of these two notions of typicality, and show that many basis theorems apply to partition genericity. More precisely, we prove that every co-hyperimmune set and every Kurtz random is partition generic, and that every partition generic set admits weak infinite subsets, for various notions (...) of weakness. In particular, we answer a question of Kjos-Hanssen and Liu by showing that every Kurtz random admits an infinite subset which does not compute any set of positive effective Hausdorff dimension. Partition genericity is a partition regular notion, so these results imply many existing pigeonhole basis theorems. (shrink)

We show that a version of Ramsey’s theorem for trees for arbitrary exponents is equivalent to the subsystem ${{\sf ACA}^\prime_{0}}$ of reverse mathematics.

The purpose of this paper is to show that the mathematics of quantum mechanics is the mathematics of set partitions linearized to vector spaces, particularly in Hilbert spaces. That is, the math of QM is the Hilbert space version of the math to describe objective indefiniteness that at the set level is the math of partitions. The key analytical concepts are definiteness versus indefiniteness, distinctions versus indistinctions, and distinguishability versus indistinguishability. The key machinery to go from indefinite to more definite (...) states is the partition join operation at the set level that prefigures at the quantum level projective measurement as well as the formation of maximally-definite state descriptions by Dirac’s Complete Sets of Commuting Operators. This development is measured quantitatively by logical entropy at the set level and by quantum logical entropy at the quantum level. This follow-the-math approach supports the Literal Interpretation of QM—as advocated by Abner Shimony among others which sees a reality of objective indefiniteness that is quite different from the common sense and classical view of reality as being “definite all the way down”. (shrink)

The last section made it clear that an analysis which at first seems to fail is viable after all. It is viable if we let it depend on a partition function to be provided by the context of conversation. This analysis leaves certain traits of the partition function open. I have tried to show that this should be so. Specifying these traits as Pollock does leads to wrong predictions. And leaving them open endows counterfactuals with just the right (...) amount of variability and vagueness. (shrink)

The advocate of modal logic or relevant logic has traditionally argued that her preferred system offers the best regimentation of the theory of entailment. Essential to the projects of modal and relevant logic is the importation of non-truth-functional expressive resources into the object language on which the logic is defined. The most elegant technique for giving the semantics of such languages is that of frame semantics, a variation on which features the device of partitioned frames that (...) divide 'points of evaluation' into two types: normal points and abnormal points. This essay attempts to provide satisfying philosophical interpretations of the partitioned frame semantics for some weak modal logics and relevant logics. According to the current best interpretation, partitioned frame semantics are a kind of possible worlds semantics that appeal to 'logically impossible worlds' where the laws of logic may fail to hold. This is undermined by the fact that all of the target logics fail to satisfy criteria of expressibility needed to support the thesis that laws of logic fail to hold at abnormal points. This suggests that we should not look for a monistic interpretive paradigm for partitioned frame semantics. (shrink)

For which infinite cardinals $\kappa $ is there a partition of the real line ${\mathbb R}$ into precisely $\kappa $ Borel sets? Work of Lusin, Souslin, and Hausdorff shows that ${\mathbb R}$ can be partitioned into $\aleph _1$ Borel sets. But other than this, we show that the spectrum of possible sizes of partitions of ${\mathbb R}$ into Borel sets can be fairly arbitrary. For example, given any $A \subseteq \omega $ with $0,1 \in A$, there is a forcing (...) extension in which ${A = \{ n :\, \text {there is a partition of } {{\mathbb R}} \text { into }\aleph _n\text { Borel sets}\}}$. We also look at the corresponding question for partitions of ${\mathbb R}$ into closed sets. We show that, like with partitions into Borel sets, the set of all uncountable $\kappa $ such that there is a partition of ${\mathbb R}$ into precisely $\kappa $ closed sets can be fairly arbitrary. (shrink)

For an infinite cardinal K a stronger version of K-distributivity for Boolean algebras, called k-partition completeness, is defined and investigated . It is shown that every k-partition complete Boolean algebra is K-weakly representable, and for strongly inaccessible K these concepts coincide. For regular K ≥ u, it is proved that an atomless K-partition complete Boolean algebra is an updirected union of basic K-tree algebras. Using K-partition completeness, the concept of γ-almost compactness is introduced for γ ≥ (...) K. For strongly inaccessible K we show that K is K-almost compact iff K is weakly compact, and if K is 2K-almost compact, then K is measurable. Further K is strongly compact iff it is γ-almost compact for all γ ≥ K. (shrink)

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n (...) ∈ ω with its set of predecessors, so n = {0, 1, 2, …, n − 1}. (shrink)

The lattice operations of join and meet were defined for set partitions in the nineteenth century, but no new logical operations on partitions were defined and studied during the twentieth century. Yet there is a simple and natural graph-theoretic method presented here to define any n-ary Boolean operation on partitions. An equivalent closure-theoretic method is also defined. In closing, the question is addressed of why it took so long for all Boolean operations to be defined for partitions.

Louveau, A., S. Shelah and B. Velikovi, Borel partitions of infinite subtrees of a perfect tree, Annals of Pure and Applied Logic 63 271–281. We define a notion of type of a perfect tree and show that, for any given type τ, if the set of all subtrees of a given perfect tree T which have type τ is partitioned into two Borel classes then there is a perfect subtree S of T such that all subtrees of S of (...) type τ belong to the same class. This result simultaneously generalizes the partition theorems of Galvin-Prikry and Galvin-Blass. The key ingredient of the proof is the theorem of Halpern-Laüchli on partitions of products of perfect trees. (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 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 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.

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 set algebras with an operator (SAO) that satisfy the axioms of S5 knowledge. A necessary and sufficient condition is given for such SAOs that the knowledge operator is defined by a partition of the state space. SAOs are constructed for which the condition fails to hold. We conclude that no logic singles out the partitional SAOs among all SAOs.

The Knowability Paradox is a logical argument that, starting from the plainly innocent assumption that every true proposition is knowable, reaches the strong conclusion that every true proposition is known; i.e. if there are unknown truths, there are unknowable truths. The paradox has been considered a problem for every theory assuming the Knowability Principle, according to which all truths are knowable and, in particular, for semantic anti-realist theories. A well known criticism to the Knowability Paradox is the so called restriction (...) strategy. It bounds the scope of the universal quantification in (KP) to a set of formulas whose logical form avoids the paradoxical conclusion. Specifically, Tennant suggests to restrict the quantifier in (KP) to propositions whose knowledge is provably inconsistent. He calls them Anti-Cartesian propositions and distinguished them in three kinds. In this paper we will not be concerned with the soundness of the restriction proposal and the criticisms it has received. Rather, we are interested in analyzing the proposed distinction. We argue that Tennant’s distinction is problematic because it is not completely clear, it is not grounded on an adequate logical analysis, and it is incomplete. We suggest an alternative distinction, and we give some reasons for accepting it: it results logically grounded and more complete than Tennant’s one, inclusive of it and independent from non-epistemic notions. (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}}\).

Let κ be a cardinal which is measurable after generically adding ${\beth_{\kappa+\omega}}$ many Cohen subsets to κ and let ${\mathcal G= ( \kappa,E )}$ be the κ-Rado graph. We prove, for 2 ≤ m < ω, that there is a finite value ${r_m^+}$ such that the set [κ] m can be partitioned into classes ${\langle{C_i:i (...) G}$ in ${\mathcal G}$ such that ${[\mathcal{G} ^\ast ] ^m\cap C_i}$ is monochromatic. It follows that ${\mathcal{G}\rightarrow (\mathcal{G} ) ^m_{<\kappa/r_m^+}}$ , that is, for any coloring of ${[ \mathcal {G} ] ^m}$ with fewer than κ colors there is a copy ${\mathcal{G} ^{\prime}}$ of ${\mathcal{G}}$ such that ${[\mathcal{G} ^{\prime} ] ^{m}}$ has at most ${r_m^+}$ colors. On the other hand, we show that there are colorings of ${\mathcal{G}}$ such that if ${\mathcal{G} ^{\prime}}$ is any copy of ${\mathcal{G}}$ then ${C_i\cap [\mathcal{G} ^{\prime} ] ^m\not=\emptyset}$ for all ${i 2 we have ${r_m^+ > r_m}$ where r m is the corresponding number of types for the countable Rado graph. (shrink)

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)

The literature on conditionals is rife with alternate formulations of the abstract semantics of conditional logic. Each formulation has its own advantages in terms of applications and generalizations; nevertheless, they are for the most part equivalent, in the sense that they underwrite the same range of logical systems. The purpose of the present note is to bring under this umbrella the partition semantics introduced by Brian Skyrms in (Skyrms, 1984).

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.

This paper discusses two combinatorial problems in stability theory. First we prove a partition result for subsets of stable models: for any A and B, we can partition A into |B |<κ(T ) pieces, Ai | i < |B |<κ(T ) , such that for each Ai there is a Bi ⊆ B where |Bi| < κ(T ) and Ai..

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 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.

It is known that in an infinite very weakly cancellative semigroup with size $\kappa $, any central set can be partitioned into $\kappa $ central sets. Furthermore, if $\kappa $ contains $\lambda $ almost disjoint sets, then any central set contains $\lambda $ almost disjoint central sets. Similar results hold for thick sets, very thick sets and piecewise syndetic sets. In this article, we investigate three other notions of largeness: quasi-central sets, C-sets, and J-sets. We obtain that the statement applies (...) for quasi-central sets. If the semigroup is commutative, then the statement holds for C-sets. Moreover, if $\kappa ^\omega = \kappa $, then the statement holds for J-sets. (shrink)

We prove that all algebras P/IR, where the IR-'s are ideals generated by partitions of W into finite and arbitrary large elements, are isomorphic and homogeneous. Moreover, we show that the smallest size of a tower of such partitions with respect to the eventually-refining preordering is equal to the smallest size of a tower on ω.

In the Zermelo–Fraenkel set theory (ZF), |$|\textrm {fin}(A)|<2^{|A|}\leq |\textrm {Part}(A)|$| for any infinite set |$A$|⁠, where |$\textrm {fin}(A)$| is the set of finite subsets of |$A$|⁠, |$2^{|A|}$| is the cardinality of the power set of |$A$| and |$\textrm {Part}(A)$| is the set of partitions of |$A$|⁠. In this paper, we show in ZF that |$|\textrm {fin}(A)|<|\textrm {Part}_{\textrm {fin}}(A)|$| for any set |$A$| with |$|A|\geq 5$|⁠, where |$\textrm {Part}_{\textrm {fin}}(A)$| is the set of partitions of |$A$| whose members are finite. We (...) also show that, without the Axiom of Choice, any relationship between |$|\textrm {Part}_{\textrm {fin}}(A)|$| and |$2^{|A|}$| for an arbitrary infinite set |$A$| cannot be concluded. (shrink)

Generalizing model companions from model theory we define companions of pieces of canonical partitions of Polish G-spaces. This unifies several constructions from logic. The central problem of the paper is the existence of companions which form a G-orbit which is a Gδ-set. We describe companions of some typical G-spaces.

We investigate the following weak Ramsey property of a cardinal κ: If χ is coloring of nodes of the tree κ <ω by countably many colors, call a tree ${T \subseteq \kappa^{ < \omega}}$ χ-homogeneous if the number of colors on each level of T is finite. Write ${\kappa \rightsquigarrow (\lambda)^{ < \omega}_{\omega}}$ to denote that for any such coloring there is a χ-homogeneous λ-branching tree of height ω. We prove, e.g., that if ${\kappa < \mathfrak{p}}$ or ${\kappa > \mathfrak{d}}$ (...) is regular, then ${{\kappa \rightsquigarrow (\kappa)^{ < \omega}_{\omega}}}$ and that ${\mathfrak{b}}$ ${(\mathfrak{b})^{ < \omega}_{\omega}}$ and ${\mathfrak{d}}$ ${(\mathfrak{d})^{ < \omega}_{\omega}}$ . The arrow is applied to prove a generalization of a theorem of Hurewicz: A Čech-analytic space is σ-locally compact iff it does not contain a closed homeomorphic copy of irrationals. (shrink)

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of (...) questions for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively. (shrink)

In the setting of ZF, i.e., Zermelo–Fraenkel set theory without the Axiom of Choice , we study partitions of Russell-sets into sets each with exactly n elements , for some integer n. We show that if n is odd, then a Russell-set X has an n -ary partition if and only if |X | is divisible by n. Furthermore, we establish that it is relative consistent with ZF that there exists a Russell-set X such that |X | is not (...) divisible by any finite cardinal n > 1. (shrink)