Cardinality

Mar 2010
11
0
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.
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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.
 
Sep 2009
502
39
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.
 

Plato

MHF Helper
Aug 2006
22,455
8,631
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\).
 
Feb 2010
470
154
\(\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.
 
  • Like
Reactions: undefined
Feb 2010
470
154
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.