MHB Inequality of Cardinality of Sets

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
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

Back
Top