MHB Inequality of Cardinality of Sets

AI Thread Summary
The discussion centers on proving that if set A is a subset of set B, then the cardinality of A is less than or equal to that of B. The proof correctly identifies that the identity function from A to B is an injection, supporting the conclusion that |A| ≤ |B|. Participants clarify that this theorem applies to both finite and infinite sets, countering concerns about the definitions involved. The definition of cardinality from the textbook is referenced to reinforce the proof's validity. Overall, the proof is affirmed as correct, providing confidence to the original poster.
A.Magnus
Messages
138
Reaction score
0
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
 
Physics news on Phys.org
MaryAnn said:
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?

MaryAnn said:
(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.

MaryAnn said:
(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?
 
Evgeny.Makarov said:
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.

Evgeny.Makarov said:
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.

Evgeny.Makarov said:
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
 
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.
 
Evgeny.Makarov said:
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
 

Similar threads

Back
Top