Totally non-immune sets

Let L be a countable first-order language and M = (M, . . .) be an L-structure. "Definable set" means a subset of M which is L-definable inMwith parameters. A set X subset of M is said to be immune if it is infinite and does not contain any infinite definable subset. X is said to be partially immune if for some definable A, A boolean AND X is immune. X is said to be totally non-immune if for every definable A, A boolean AND X and A boolean AND (M\X) are not immune. Clearly every definable set is totally non-immune. Here we ask whether the converse is true and prove that it is false for every countable structure M whose class of definable sets satisfies a mild condition. We investigate further the possibility of an alternative construction of totally non-immune non-definable sets with the help of a subclass of immune sets, the class of cohesive sets, as well as with the help of a generalization of definable sets, the semi-definable ones (the latter being naturally defined in models of arithmetic). Finally connections are found between totally non-immune sets and generic classes in nonstandard models of arithmetic. (C) 2015 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim