# Partial subsets of a given set: reference request

Given a set or space X, a characteristic function on X is a function whose domain is X and whose value is either 0 or 1. The subsets of X may be taken as defined by characteristic functions on X.

It is usually assumed that characteristic functions are total, that is, defined for each member x of X. But there are also partial functions with domain of X and range of {0,1}. These may be regarded as defining subsets of X, which might be called "partial subsets."

There are hints of this sort of thing in, for example, Chapter 7 of Shoenfield's text Mathematical Logic. I'm not aware of any in-depth explorations of partial subsets, though, and would appreciate hearing about any you know of.

• Why? The subset of a subset is a subset anyways. For characteristic functions, you can treat the wlog as being deined on the larger set. You could also treat a partial characteristic function as a pair of subsets of X in which, say, the first coordinate is a subset of the second coordinate. Just take the domain of the partial function to be the second coordinate and the set of points mapped to 1 to be the first coordinate. Are such pairs interesting? If not, partial characteristic functions aren't either. – Michael Greinecker Nov 13 '11 at 5:39

• A set $A\subset\mathbb{N}$ is computably decidable if the characteristic function of $A$ is a computable function.
• The set $A$ is merely computably enumerable, however, if the partial function $1\upharpoonright A$, having constant value $1$ on domain $A$, is computable. Equivalently, $A$ is enumerable if there is some computable partial subset function, in your terminology, which includes $A$ in its domain and is correct for $A$ on its domain.
In set theory, one often considers the partial subset concept that you mention in connection with forcing. For example, the partial order of all finite partial subsets of $\mathbb{N}$, ordered by extension, is exactly the forcing to add a Cohen real. The idea is that partial information about the generic subset can be specified by a finite piece of it, and continued in diverse ways. Other forcing notions also use partial functions in this way, to allow a forcing condition to specify partial information about the generic object, often in combination with other complicated requirements on the domain or support of the conditions.