Let S,T, and W be sets.
a. Prove: If and , then .
b. Prove: If and , then .
is this like the transitive property??? I'm so confused.
table of mathematical symbols, refers to Karp reduction, which is part of computational complexity theory. Is this what we're talking about?
Edit: Oh, I guess since S, T, and W are sets we must be talking about something else.
The is almost standard notation is many areas of mathematics.
This is lesson that a posting should contain explanations of terminology.
It is also a warning not to rely heavily upon Wikipedia. There are mistakes there.
Here is a guess as to the uses of those symbols.
On a collection of subsets means that there is a injection .
Whereas, means that there is a non-bijective injection .
In other words, to prove that T strictly dominates S, it is not enough to show that there exists an injection from S into T that is not a bijection (since it might be the case that there is an injection from S into T that is not a bijection while still there does exist a bijection from S to T), but rather it does suffice to show that there is an injection from S into T while also there does not exist a bijection from S to T.
To address the original question, hints:
a. For existence of injection from S into W, consider composition of functions. For non-existence of a bijection from S into W, argue by contradiction, and apply a famous theorem you probably just covered in your course.
b. Same as for a., mutatis mutandis.