# Cartesian product question

#### entrepreneurforum.co.uk

Okay, I have this problem from a maths textbook and its along the same lines as

If S and T are sets

the Cartesian product S x T of S and T is defined

[(s,t) : s ∈ S, t ∈ T}

Prove if S and T are convex sets in ℝ^n and ℝ^m

then ℝ^(n+m) is convex also

---------

I have the answer but I'm completely confused on how it was derived

#### Krahl

Suppose S and T are convex sets in $$\displaystyle \Re ^n$$ and $$\displaystyle \Re ^m$$ respectively
$$\displaystyle \Longleftrightarrow$$ $$\displaystyle \forall x_1,y_1 \in S$$, $$\displaystyle \forall t \in [0,1]$$
$$\displaystyle (1-t)x_1 + ty_1 \in \Re ^n$$
and
$$\displaystyle \forall x_2,y_2 \in T$$, $$\displaystyle \forall t \in [0,1]$$
$$\displaystyle (1-t)x_2 + ty_2 \in \Re ^m$$

with $$\displaystyle a(x,y)$$ defined as $$\displaystyle (ax,ay)$$ for $$\displaystyle a \in \Re$$ and $$\displaystyle (x,y)\in S \times T$$ and $$\displaystyle (x_1,y_1) + (x_2,y_2) = (x_1+x_2,y_1+y_2)$$...

Last edited:

#### entrepreneurforum.co.uk

λs1 + (1-λ)s2 $$\displaystyle forall$$ S $$\displaystyle forall R^n$$

λt1 + (1-λ)t2 $$\displaystyle forall$$ T $$\displaystyle forall R^m$$

and now I can't understand why R^n , R^m makes SxT convex

thanks

Last edited:

#### Krahl

Ok so this is what you've written;
λs1 + (1-λ)s2 $$\displaystyle \forall$$ S $$\displaystyle \forall R^n$$

λt1 + (1-λ)t2 $$\displaystyle \forall$$ T $$\displaystyle \forall R^m$$

s1 and s2 are elements of set S and t1 and t2 are elements of set T. I wouldn't write the "forall Rn" part since the statements are only true for the convex sets S and T in Rn,Rm. So basically S and T are convex sets in $$\displaystyle \Re^n$$ and $$\displaystyle \Re^m$$. This means that the following by definition is true;
λs1 + (1-λ)s2 $$\displaystyle \in \Re^n$$ $$\displaystyle \forall s1,s2 \in$$ S

λt1 + (1-λ)t2 $$\displaystyle \in \Re^m$$$$\displaystyle \forall t1,t2 \in$$ T

(If S is a convex set in $$\displaystyle \Re^n$$ then λs1 + (1-λ)s2 is in $$\displaystyle \Re^n$$).

We've just applied the definition of a convex set so far. Now we want to show the set S $$\displaystyle \times$$ T (which is of the form x1=(s1,t1)) is also a convex set. So we want to show that;

λx1 + (1-λ)x2 $$\displaystyle \in \Re^{n \times m}$$$$\displaystyle \forall x1,x2 \in$$ S $$\displaystyle \times$$ T

We begin with the equation

λx1 + (1-λ)x2$$\displaystyle \forall x1,x2 \in$$ S $$\displaystyle \times$$ T

which becomes (x1 = (s1,t1), x2 = (s2,t2) are elements of $$\displaystyle S \times T$$)

λ(s1,t1) + (1-λ)(s2,t2) $$\displaystyle \forall s1,s2 \in$$ S and $$\displaystyle \forall t1,t2 \in$$ T

which means (λ(s1,t1) = (λs1,λt1))

(λs1,λt1) + ((1-λ)s2,(1-λ)t2)$$\displaystyle \forall s1,s2 \in$$ S and $$\displaystyle \forall t1,t2 \in$$ T

which then becomes ((s1,t1)+(s2,t2) = (s1+s2,t1+t2))

((λs1 + (1-λ)s2),(λt1 + (1-λ)t2))$$\displaystyle \forall s1,s2 \in$$ S and $$\displaystyle \forall t1,t2 \in$$ T

what can we say about the equations (λs1 + (1-λ)s2) and (λt1 + (1-λ)t2) ?

Last edited:

#### entrepreneurforum.co.uk

what can we say about the equations (λs1 + (1-λ)s2) and (λt1 + (1-λ)t2) ?
Well am I correct in saying that ((s1,t1)+(s2,t2) = (s1+s2,t1+t2)) therefore S and T are convex IF they both lie in S x T (on a graph)
(I'm slightly confused)

I really have no idea

Edit: If S and T are two convex sets in R^n and R^m then their intersection S∩T is also convex, - I understand that but I don't know how its proved that its convex in R^n+m

Last edited:

#### Krahl

what can we say about the equations (λs1 + (1-λ)s2) and (λt1 + (1-λ)t2) ?
By definition (written above) (λs1 + (1-λ)s2) is in $$\displaystyle \Re^n$$ and (λt1 + (1-λ)t2) is in $$\displaystyle \Re^m$$ so that the element ((λs1 + (1-λ)s2),(λt1 + (1-λ)t2)) is in $$\displaystyle S \times T$$. This means by definition that $$\displaystyle S \times T$$ is a convex set in $$\displaystyle \Re^{n\times m}$$

What we've done is taken any two elements x1 and x2 of $$\displaystyle S \times T$$ and showed that λx1 + (1-λ)x2 also lies in $$\displaystyle S \times T$$.

Well am I correct in saying that ((s1,t1)+(s2,t2) = (s1+s2,t1+t2)) therefore S and T are convex IF they both lie in S x T (on a graph)
No the operation (s1,t1)+(s2,t2) = (s1+s2,t1+t2) is just how the elements are added. What we need to show is that for any two elements of S x T the equation λx1 + (1-λ)x2 lies in it as well.

Last edited: