# Math Help - Cardinality

1. ## Cardinality

Let S,T, and W be sets.

a. Prove: If $S \preceq T$ and $T \prec W$, then $S \prec W$.

b. Prove: If $S \prec T$ and $T \preceq W$, then $S \prec W$.

is this like the transitive property??? I'm so confused.

2. Originally Posted by txsoutherngirl84
Let S,T, and W be sets.

a. Prove: If $S \preceq T$ and $T \prec W$, then $S \prec W$.

b. Prove: If $S \prec T$ and $T \preceq W$, then $S \prec W$.

is this like the transitive property??? I'm so confused.
According to Wikipedia's table of mathematical symbols, $\prec$ 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.

3. Originally Posted by undefined
According to Wikipedia's table of mathematical symbols, $\prec$ 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.
I saw in an old book, the notation being used for cardinality related topics.

4. 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 $S \preceq T$ means that there is a injection $S\to T$.
Whereas, $S \prec T$ means that there is a non-bijective injection $S\to T$.

5. Originally Posted by Plato
$S \prec T$ means that there is a non-bijective injection $S\to T$.
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.

6. 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.