nLab
disjoint subsets

Disjoint subsets

Idea

Two concrete sets are disjoint if they have no common elements.

Definitions

Given an abstract set VV, two subsets AA and BB of VV meet if their intersection is inhabited; AA and BB are disjoint if they do not meet, in other words if their intersection is empty.

Foundational issues

In material set theory, we may speak of take AA and BB to be simply sets, rather than subsets of some ambient set? VV. Equivalently, one may take VV to be the class of all sets by default. (In this context, it’s important that whether AA and BB meet or are disjoint is independent of the ambient set or class.)

In constructive mathematics, the default meaning of ‘disjoint’ is as above, but sometimes one wants a definition relative to some inequality relation \ne on VV. Then AA and BB are \ne-disjoint if, whenever xAx \in A and yBy \in B, xyx \ne y. (Ordinary disjointness is relative to the denial inequality.)

Relation to disjoint unions

The concrete sets AA and BB are disjoint iff they have an internal disjoint union, in other words if their inclusions? into their union ABA \cup B form a coproduct diagram in the category of sets. (Etymologically, of course, this is backwards.)

Many authors are unfamiliar with disjoint unions. When the disjoint union oid two abstract sets AA and BB is needed, they will typically lapse into material set theory (even when the work is otherwise perfectly structural), and make some comment such as ‘without loss of generality, assume that AA and BB are disjoint’ or (especially when A=BA = B) ‘take two isomorphic copies of AA and BB’, then call the disjoint union simply a ‘union’. (This works by the previous paragraph.)

Internalization

In any category with an object VV, two subobjects AA and BB are disjoint if their pullback is initial in CC. Then disjoint subsets are precisely disjoint subobjects in Set.

To internalize the characterization in terms of internal disjoint unions is harder. If AA and BB have a join in the poset of subobjects Sub(V)Sub(V), then we may ask whether this forms a coproduct diagram in CC. This should be equivalent if CC has disjoint coproducts.

Revised on August 24, 2013 20:01:15 by Toby Bartels (141.0.8.162)