Featured post

# Number Of Reflexive & Symmetric Relations On Set S with n Elements

Suppose S is a set with n elements.

(a) How many relations are there on S?

There are $2^{n^2}$ relations on S.

(b) How many reﬂexive relations are there on S?

There are $2^{n*(n-1)}$ reflexive relations on S.

(c) How many symmetric relations are there on S?

There are $2^{n*(n+1)/2}$ reflexive relations on S.

(d) How many relations are there on S that are both reﬂexive and symmetric?

There are $2^{n*(n-1)/2}$ reflexive & symmetric relations on S.

Write formal descriptions of the following sets

(a) The set containing the numbers 1, 10, 100:

{1, 10, 100}

(b) The set containing all integers greater than 5:

{n ε  Z | n > 5}

(c) The set containing all natural numbers that are less than 5:

{n ε  N | n < 5}

(d) The set containing the string aba:

{aba}

(e) The set containing the empty string:

{ε}

(f) The set containing nothing:

Ø