There is a natural relationship between sets and bit strings which is called the characteristic vector for a set. We'll look only at subsets of the...

There is a natural relationship between sets and bit strings which is called the characteristic vector for a set. We'll look only at subsets of the universe U = {0, . . . , n − 1} for some n, but the concept can be generalised to arbitrary sets. For a set S ⊆ U, the characteristic vector is denoted by χS and is an n-bit string where bit j is 1 if and only if j ∈ S. For example, with n = 4 and S = {1, 3} we have χS = 1010.