Inequality of Cardinality of Sets

In summary, the problem asks if $A,B$ are sets and if $A\subseteq B$, prove that $|A| \le |B|$.The problem is actually a theorem that the textbook assigns as exercise.
  • #1
A.Magnus
138
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
  • #2
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?
 
  • #3
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
 
  • #4
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.
 
  • #5
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
 

FAQ: Inequality of Cardinality of Sets

1. What is inequality of cardinality of sets?

Inequality of cardinality of sets refers to the comparison of the number of elements in two different sets. It is a measure of the relative size of sets and is determined by counting the number of elements in each set and comparing them.

2. How is inequality of cardinality of sets represented?

Inequality of cardinality of sets is represented using the symbols <, > or = to indicate which set has more, less or an equal number of elements compared to the other set.

3. Can two sets with different cardinalities be equal in size?

No, two sets with different cardinalities cannot be equal in size. If two sets have the same number of elements, then they have the same cardinality, and if they have different cardinalities, then they have a different number of elements.

4. What is the significance of inequality of cardinality of sets in mathematics?

Inequality of cardinality of sets is significant in mathematics as it allows for the comparison of the sizes of infinite sets, which is crucial in many mathematical concepts and proofs. It also helps in understanding the concept of one-to-one correspondence between sets.

5. How is inequality of cardinality of sets related to the concept of subsets?

Inequality of cardinality of sets is closely related to the concept of subsets. If a set A has more elements than another set B, then A cannot be a subset of B. Similarly, if A has fewer elements than B, then A cannot be a superset of B. This relationship is important in understanding the hierarchy of sets and their relationships.

Similar threads

Replies
19
Views
3K
Replies
9
Views
2K
Replies
5
Views
2K
Replies
5
Views
1K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
1
Views
1K
Back
Top