In this paper we aim to compare Kurepa trees and Aronszajn trees. Moreover, we analyze the effect of large cardinal assumptions on this comparison. Using the the method of walks on ordinals, we will show it is consistent with ZFC that there is a Kurepa tree and every Kurepa tree contains an Aronszajn subtree, if there is an inaccessible cardinal. This is stronger than Komjath's theorem in [5], where he proves the same consistency from two inaccessible cardinals. Moreover, we prove it is consistent with ZFC that there is a Kurepa tree T such that if U⊂T is a Kurepa tree with the inherited order from T, then U has an Aronszajn subtree. This theorem uses no large cardinal assumption. Our last theorem immediately implies the following: If MAω2 holds and ω2 is not a Mahlo cardinal in then there is a Kurepa tree with the property that every Kurepa subset has an Aronszajn subtree. Our work entails proving a new lemma about Todorcevic's ρ function which might be useful in other contexts.

Abstract We considerωn-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of lengthωnfor some integern≥ 1. We show that all these structures areω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation forω2-automatic (resp.ωn-automatic forn> 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem forωn-automatic boolean algebras,n≥ 2, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a -set nor a -set. We obtain that there exist infinitely manyωn-automatic, hence alsoω-tree-automatic, atomless boolean algebras , which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [14].

Definition 1 (Kurepa [3, p. 99]). Let E be a partially ordered set. Then σE denotes the set of all bounded well-ordered subsets of E. We consider σE as a partially ordered set with ordering defined as follows: s t if and only if s is an initial segment of t. Then σE is a tree, i.e., {s ∈ σ E∣ s t} is well-ordered for every t ∈ σE. The trees of the form αE were extensively studied by Kurepa in [3]–[10]. For example, in [4], he used σQ and σR to construct various sorts of Aronszajn trees. (Here Q and R denote the rationals and reals, respectively.) While considering monotone mapping between some kind of ordered sets, he came to the following two questions several times: P.1. Does there exist a strictly increasing rational function on σQ? (See [4, Problème 2], [5, p. 1033], [6, p. 841], [7, Problem 23.3.3].) P.2. Let T be a tree in which every chain is countable and every level has cardinality <2ℵ0. Does there exist a strictly increasing real function on T? (See [6, p. 246] and [7].) It is known today that Problem 2 is independent of the usual axioms of set theory (see [1]). Concerning Problem 1 we have the following.