Abstract We use the model theoretic notion of coheir to give short proofs of old and new theorems in Ramsey Theory. As an illustration we start from Ramsey’s theorem itself. Then we prove Hindman’s theorem and the Hales–Jewett theorem. Finally, we prove two Ramsey theoretic principles that have among their consequences partition theorems due to Carlson and to Gowers.

Abstract We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0′. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.

We denote by KP_ the fragment of set-theory containing the axioms of extensionality, pairing, union and foundation as well as the schemas of ∆0-comprehension and ∆0-collection, that is: Kripke-Platek set-theory (KP) with the axiom of foundation in place of the ∈-induction schema. The theory KP is obtained by adding to KP_ the schema of ∈-induction Using ∈-induction it is possible to prove the existence of the transi tive closure without appealing to the axiom of infinity (see, e.g., [1]). Vice versa, when a theory proves the existence of the transitive closure, some induction is immediately ensured (by foundation and comprehension). This is not true in general: e.g., the whole of Zermelo-Fraenkel set-theory without the axiom of infinity does not prove ∈-induction (in fact, it does not prove the existence of the transitive closure; see, e.g., [3]). Open-induction is the schema of ∈-induction restricted to open formulas. We prove the following theorem. KP_ proves open-induction. We reason in a fixed but arbitrary model of KP_ whom we refer to as the model. The language is extended with a name for every set in the model. We call this constants parameters. Let φ(x) be a satisfiable open-formula possibly depending on parameters and with no free variable but x. We show that φ(x) is satisfied by an ∈-minimal set, that is, a set a such that φ(a) and (∀x ∈ a) ¬φ(x). We assume that no ordinal satisfies φ(x), otherwise the existence of a ∈-minimal set follows from foundation and comprehension.

Abstract We characterize the collapse of Buss' bounded arithmetic in terms of the provable collapse of the polynomial time hierarchy. We include also some general model-theoretical investigations on fragments of bounded arithmetic.