Question

Let’s create a dictionary between logical notions and characteristic functions: Suppose that A and B are subsets of N. Express, in terms of the characteristic functions χA and χB, the following: (a) the characteristic function of N \ A i.e. the set of elements of N not in A.

(b) the characteristic function of A ∪ B.

(c) the characteristic function of A ∩ B.

(d) Suppose that A ⊂ N^2 . How do you express the characteristic function of “there exists y such that (x, y) ∈ A”?

Answer 1

a) .

To see this works, take . Then we have . So .

For , we have . So, .

So, . That is is characteristic function of the set .

b) . Here means multiplication of and .

To justify this we need to check following cases.

and , then

and then

and then

and then

So if , that means, or . So for this case,

If , that means and . So .

So .

c) , where means multiplication of and .

If and then

Also if then x oes not belong to A and B simultaneously. So .

So

d) Next . Consider the following subsets of , and . Then .

If , and . So and . So .

If , either or or both. In that case, .

So we found characteristic function for , in details.