We show in (the usual set theory without Choice) that for any set X, the collection of sets Y such that each element of the transitive closure of is strictly smaller in size than X (the collection of sets hereditarily smaller than X) is a set. This result has been shown by Jech in the case (where the collection under consideration is the set of hereditarily countable sets).

We define a class of higher inductive types that can be constructed in the category of sets under the assumptions of Zermelo‐Fraenkel set theory without the axiom of choice or the existence of uncountable regular cardinals. This class includes the example of unordered trees of any arity.

We will prove in Zermelo-Fraenkel set theory without axiom of choice that the transitive hull R* of a relation R is not much “bigger” than R itself. As a measure for the size of a relation we introduce the notion of κ+-narrowness using surjective Hartogs numbers rather than the usul injective Hartogs values. The main theorem of this paper states that the transitive hull of a κ+-narrow relation is κ+-narrow. As an immediate corollary we obtain that, for every infinite cardinal (...) κ, the class HCκ of all κ-hereditary sets is a set with von Neumann rank ϱ(HCκ) ≤ κ+. Moreover, ϱ(HCκ) = κ+ if and only if κ is singular, otherwise ϱ(HCκ) = κ. The statements of the corollary are well known in the presence of the axiom of choice (AC). To prove them without AC - as carried through here - is, however, much harder. A special case of the corollary (κ = ω1, i.e., the class HCω1 of all hereditarily countable sets) has been treated independently by T. JECH. (shrink)

We investigate whether classical combinatorial theorems are provable in ZF. Some statements are not provable in ZF, but they are equivalent within ZF. For example, the following statements (i)–(iii) are equivalent: $$cf({\omega }_1)={\omega }_1$$ c f ( ω 1 ) = ω 1, $${\omega }_1\rightarrow ({\omega }_1,{\omega }+1)^2$$ ω 1 → ( ω 1, ω + 1 ) 2, any family $$\mathcal {A}\subset [{On}]^{<{\omega }}$$ A ⊂ [ On ] < ω of size $${\omega }_1$$ ω 1 contains a $$\Delta (...) $$ Δ -system of size $${\omega }_1$$ ω 1. Some classical results cannot be proven in ZF alone; however, we can establish weaker versions of these statements within the framework of ZF, such as $${{\omega }_2}\rightarrow ({\omega }_1,{\omega }+1)$$ ω 2 → ( ω 1, ω + 1 ), any family $$\mathcal {A}\subset [{On}]^{<{\omega }}$$ A ⊂ [ On ] < ω of size $${\omega }_2$$ ω 2 contains a $$\Delta $$ Δ -system of size $${\omega }_1$$ ω 1. Some statements can be proven in ZF using purely combinatorial arguments, such as: given a set mapping $$F:{\omega }_1\rightarrow {[{\omega }_1]}^{<{\omega }}$$ F : ω 1 → [ ω 1 ] < ω, the set $${\omega }_1$$ ω 1 has a partition into $${\omega }$$ ω -many F-free sets. Other statements can be proven in ZF by employing certain methods of absoluteness, for example: given a set mapping $$F:{\omega }_1\rightarrow {[{\omega }_1]}^{<{\omega }}$$ F : ω 1 → [ ω 1 ] < ω, there is an F-free set of size $${\omega }_1$$ ω 1, for each $$n\in {\omega }$$ n ∈ ω, every family $$\mathcal {A}\subset {[{\omega }_1]}^{{\omega }}$$ A ⊂ [ ω 1 ] ω with $$|A\cap B|\le n$$ | A ∩ B | ≤ n for $$\{A,B\}\in {[\mathcal {A}]}^{2}$$ { A, B } ∈ [ A ] 2 has property B. In contrast to statement (5), we show that the following ZFC theorem of Komjáth is not provable from ZF + $$cf({\omega }_1)={\omega }_1$$ c f ( ω 1 ) = ω 1 : (6$$ ^*$$ ∗ ) every family $$\mathcal {A}\subset {[{\omega }_1]}^{{\omega }}$$ A ⊂ [ ω 1 ] ω with $$|A\cap B|\le 1$$ | A ∩ B | ≤ 1 for $$\{A,B\}\in {[\mathcal {A}]}^{2}$$ { A, B } ∈ [ A ] 2 is essentially disjoint. A function f is a uniform denumeration on$${\omega }_1$$ ω 1 iff $${\text {dom}}(f)={\omega }_1$$ dom ( f ) = ω 1, and for every $$1\le {\alpha }<{\omega }_1$$ 1 ≤ α < ω 1, $$f({\alpha })$$ f ( α ) is a function from $${\omega }$$ ω onto $${\alpha }$$ α. It is easy to see that the existence of a uniform denumeration of $${\omega }_1$$ ω 1 implies $$cf({\omega }_1)={\omega }_1$$ c f ( ω 1 ) = ω 1. We prove that the failure of the reverse implication is equiconsistent with the existence of an inaccessible cardinal. (shrink)