Welcome to our community

Be a part of something great, join today!

Inequality of Cardinality of Sets

MaryAnn

Member
Oct 28, 2016
53
I am working on a proof problem and I would love to know if my proof goes through:

If $A, B$ are sets and if $A \subseteq B$, prove that $|A| \le |B|$.​

Proof:
(a) By definition of subset or equal, if $x \in A$ then $x \in B$. However the converse statement if $x \in B$ then $x \in A$ is not always well defined.
(b) Therefore the identity function $f: A \rightarrow B$ defined by $f(x) = x$ is only an injection. Hence by theorem on the textbook, $|A| \le |B|$.

Thank you for your time and gracious helps. ~MA
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,488
If $A, B$ are sets and if $A \subseteq B$, prove that $|A| \le |B|$.​
On infinite sets this is the definition of $|A|\le|B|$ because you can't express the number of elements in $A$ and $B$ as numbers in order to compare them. Does this theorem presuppose that $A$ and $B$ are finite?

(a) By definition of subset or equal, if $x \in A$ then $x \in B$. However the converse statement if $x \in B$ then $x \in A$ is not always well defined.
It is well defined, but does not necessarily hold. However, in a proof one does not usually write things that are not necessarily true.

(b) Therefore the identity function $f: A \rightarrow B$ defined by $f(x) = x$ is only an injection. Hence by theorem on the textbook, $|A| \le |B|$.
If $f$ were a surjection as well, would it prevent applying this theorem? Again, you don't have to write things that may be true but probably aren't.

And what is this theorem from the textbook?
 

MaryAnn

Member
Oct 28, 2016
53
On infinite sets this is the definition of $|A|\le|B|$ because you can't express the number of elements in $A$ and $B$ as numbers in order to compare them. Does this theorem presuppose that $A$ and $B$ are finite?
The problem is actually a theorem that the textbook assigns as exercise. It is under the chapter section titled "The Ordering of Cardinality." I believe you are right, the paragraphs above this theorem make lots of reference that both $A, B$ are finite sets.

It is well defined, but does not necessarily hold. However, in a proof one does not usually write things that are not necessarily true.

If $f$ were a surjection as well, would it prevent applying this theorem? Again, you don't have to write things that may be true but probably aren't.
Thank you. Just to recap what you said: The term "well-defined" and "holds" do not necessarily mean the same thing.

And what is this theorem from the textbook?
Here is a paragraph quoted from the textbook under Definition: (Not Theorem as I had thought - sorry. The textbook is Stephen R. Lay's Analysis with An Introduction to Proof, 5th ed, 2014, Pearson Education Inc.)

We denote the cardinal number of a set $S$ by $|S|$, so that we have $|S| = |T|$ iff $S$ and $T$ are equinumerous. That is, $|S| = |T|$ iff there exists a bijection $f: S \rightarrow T$. In light of our discussion above, we define $|S| \leq |T$| to mean that there exists an injection $f: S \rightarrow T$.
Thank you again for your time and gracious helps. ~MA
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,488
With this definition your proof in post #1 is basically correct: if $A\subseteq B$, then $f:A\to B$ defined by $f(x)=x$ is an injection, which means $|A|\le|B|$ by definition. This applies to both finite and infinite sets.
 

MaryAnn

Member
Oct 28, 2016
53
With this definition your proof in post #1 is basically correct: if $A\subseteq B$, then $f:A\to B$ defined by $f(x)=x$ is an injection, which means $|A|\le|B|$ by definition. This applies to both finite and infinite sets.
Thank you! Phew! Finally I got one proof right. ~ MA