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.

Printable View

- May 10th 2010, 11:04 PMtxsoutherngirl84Cardinality
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. - May 10th 2010, 11:39 PMundefined
According to Wikipedia's 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. - May 11th 2010, 06:24 AMnovice
- May 11th 2010, 06:42 AMPlato
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 . - May 11th 2010, 06:54 AMMoeBlee
Ordinarily, it means "there is an injection from S into T but no bijection between S and T" or "S is strictly dominated by T". That is different from "there exists an injection from S into T that is not a bijection" or, as you've put it, "There is a non-bijective injection from S to T". For example, there is an injection from the set of natural numbers into itself that is not a bijection (there is a non-bijective injection from the set of natural numbers into itself) but the set of natural numbers does not strictly dominate the set of natural numbers.

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. - May 11th 2010, 07:08 AMMoeBlee
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.