MHB Proving Cardinality of Sets: $\{a_n: n \in \omega\}$

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Cardinality Set
AI Thread Summary
The discussion focuses on proving that a countable set \( X \) is bijective to the union of itself and an additional element \( b \) not in \( X \). A function \( f \) is defined to map elements from \( \{ a_n: n \in \omega \} \cup \{ b \} \) to \( \{ a_n: n \in \omega \} \), demonstrating its one-to-one and onto properties. A second function \( g \) is constructed to show that \( X \cup \{ b \} \) is also bijective to \( X \). The proof hinges on the existence of a countable subset within \( X \). The conclusion establishes that \( X \sim X \cup \{ b \} \) holds true.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

Suppose that $X$ contains a countable set. Let $b \notin X$. Show that $X \sim X \cup \{b\}$.
Prove that in general if $B$ is at most countable with $B \cap X=\varnothing$ then $X \sim X \cup B$.

Proof:We will show that $X \sim X \cup \{b\}$.
There is a $\{ a_n: n \in \omega \} \subset X$.
We define the function:
$$f: \{ a_n: n \in \omega \} \cup \{ b \} \overset{\text{bijective}}{\to} \{ a_n: n \in \omega \}$$
as follows:

$$f(b)=a_0\\f(a_n)=a_{n+1} \text{ for each } n \in \omega$$
We easily see that $f$ is 1-1 and surjective.

We define $g: X \cup \{b\} \to X$ as follows:

$$g(x)=x \text{ if } x \in X-(\{ a_n: n \in \omega \} \cup \{ b \})\\g(x)=f(x) \text{ if } x \in (\{ a_n: n \in \omega \} \cup \{b\})$$

Then $g$ is 1-1 and surjective.
From which point do we deduce that there is a $\{ a_n: n \in \omega \} \subset X$ ? (Thinking)
 
Physics news on Phys.org
evinda said:
From which point do we deduce that there is a $\{ a_n: n \in \omega \} \subset X$ ? (Thinking)
From the fact that $X$ contains a countable set.
 
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top