0

I need assistance with the following proofs. I am not sure how to prove that one set is contained in another set. Here are the things required to be proven:

Let $S$, $S_1$ and $S_2$ be non–empty sets in $R_n$. $ S^*$ = {$p|p^Tx \leq 0, \forall x \in S$}. Then

(a) $S \subseteq S^{**}$, where $S^{**}=(S^*)^*$

(b) $S_1 \subseteq S_2$ implies $S_2^* \subseteq S_1^*$

(c) $(K(S))^* = S^* $, $K(S)$ = { $ \sum x_i\lambda_i | x_i \in S, \lambda_i \geq 0, i=1,..., m ; m \in N $}

Natalie
  • 309
  • Where are you stuck? (a) and (b) seem to just follow from the definition! – Prahlad Vaidyanathan Oct 07 '13 at 10:50
  • 1
    The usual way to prove that one set is contained in another set is to take an arbitrary element of the first set and show that it satisfies the conditions for being in the second set. For example, in (b) consider an element $p \in S_2^$, which means that $p^Tx \le 0$ for all $x \in S_2$. For $p$ to be in $S_1^$ as well, what condition does it need to satisfy? –  Oct 07 '13 at 10:52

1 Answers1

1

Hints: For (a) we have to prove, that any $x \in S$ is an element of $(S^*)^*$. To be an elment of $(S^*)^*$, for all $ p\in S^*$ it must hold that $x^t p \le 0$. But as $x^t p = p^t x$ and $x \in S$, $p\in S^*$, we have from the definition of $S^*$ that ...

(b) Let $p \in S_2^*$, we must show that $p \in S_1^*$, that is $p^t x \le 0$ for all $x \in S_1$, but as $p \in S_2^*$, we have $p^t x \le 0$ for all $x \in S_2$. Now use $S_1 \subseteq S_2$.

(c) For (c) note that $S \subseteq K(S)$, so (b) gives you one inclusion, for the other, let $p \in S^*$. We want to show that $p \in K(S)^*$, so let $x \in K(S)$, then $x = \sum_i \lambda_i x_i$, with $x_i \in S$ and $\lambda_i \ge 0$. Then $$ p^t x = \sum_i \lambda_i p^t x_i \le \cdots $$

martini
  • 84,101