Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

In computability theory, the pervasive distinction between a computably decidable set and a computably enumerable set is exactly related to the concept you mention, namely,

  • 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.

The point is that not every computable partial function can be extended to a computable total function.

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.

share|improve this answer
    
Thanks for your answer. That was my impression: partial subsets come up now and again in various connections, but no one seems to have studied them in depth. For example, if we include both partial and total subsets of X in the powerset of X, then the algebra of those sets is not boolean, since the union of a set and its complement need not be X. That might be interesting. (It depends on what one finds interesting.) –  MikeC Nov 13 '11 at 16:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.