∑_{0}^{1}- Definitions of Infinity

Ali Enayat

Given a model M in a language L, a logic L (such as first order logic L_{ω,ω} or monadic second order logic L_{ω,ω}^{Mon}) and an infinite cardinal κ, let us say that L defines κ in M if there is an L-formula φ(X) in the language L∪{X}, where X is a new unary predicate, such that for all subsets A of M, (M, A) ⊧ φ(A) iff | A |≥ κ. For example, L_{ω,ω} does not define ℵ_{0} in the linear order (ℚ <) of the rationals but L_{ω,ω}^{Mon} defines ℵ_{0} in any linear order. However, L_{ω,ω} defines ℵ_{0} in (ℝ, <), and L_{ω,ω}^{Mon} can define ℵ_{1} in (ℝ, <), at least in the presence of CH (by an old result of Gurevic). In this talk we survey known results dealing with such definability/undefinability results, and prove some new theorems, such as:

Theorem A: Let P A_{n} = P A with induction restricted to ∑_{n}formulas. For each natural number n there is a nonstandard model M of P A_{n} such that L_{ω,ω} defines ℵ_{0} in M (in contrast to the fact that the only model of P A in which L_{ω,ω} can define ℵ_{0} is the standard model of P A).

Theorem B: Suppose F is a real closed field. L_{ω,ω} defines ℵ_{0} in F iff F ≅ ℝ (in contrast with the fact that L_{ω,ω} defines ℵ_{0} in any finite extension of ℚ).

Address: : Dept. of Math/Stat, American University, Washington, D.C. 20016-8050

E-mail: enayat@american.edu