Cardinality

• May 10th 2010, 11:04 PM
txsoutherngirl84
Cardinality
Let S,T, and W be sets.

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

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

is this like the transitive property??? I'm so confused.
• May 10th 2010, 11:39 PM
undefined
Quote:

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

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

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

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

According to Wikipedia's table of mathematical symbols, $\displaystyle \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.
• May 11th 2010, 06:24 AM
novice
Quote:

Originally Posted by undefined
According to Wikipedia's table of mathematical symbols, $\displaystyle \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.
• May 11th 2010, 06:42 AM
Plato
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 $\displaystyle S \preceq T$ means that there is a injection $\displaystyle S\to T$.
Whereas, $\displaystyle S \prec T$ means that there is a non-bijective injection $\displaystyle S\to T$.
• May 11th 2010, 06:54 AM
MoeBlee
Quote:

Originally Posted by Plato
$\displaystyle S \prec T$ means that there is a non-bijective injection $\displaystyle 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.
• May 11th 2010, 07:08 AM
MoeBlee
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.