Please do the following three parts.

$($a$)$ Give an outline of an algorithm which takes a formula $$ and a

positive integer $k$ and determines whether $$ has a model with

exactly $k$ elements in its universe.

$($b$)$ A formula is monadic if all of its predicate symbols are monadic

$($i$.$e$.,$ unary$)$ and it has no function symbols. Show that if $$ is a

satisfiable monadic formula with $n$ predicate symbols, then $$ is

satisfiable in a universe with at most $2^n$ elements. $($Hint: Start

with a model for $$ with universe $U,$ and define a certain equiva$-$

lence relation on $U.$ Now show that the set of equivalence classes

can be made into a model.$)$

$($c$)$ It follows from the two previous parts that there is an algorithm

which determines whether a given monadic formula $$ is satisfiable.

Give a rough upper bound on the run$-$time of the algorithm in

terms of the length $l$ of $$ and the number $n$ of distinct monadic

predicate symbols in $.$ Justify your answer.