nyuuzyou/wikis huggingface dataset:
Infinite Sequence Property of Strictly Well-Founded Relation/Reverse Implication

== Theorem ==
Let $\struct {S, \RR}$ be a relational structure.
Let $\RR$ be such that there exists no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: a_{n + 1} \mathrel \RR a_n$
Then $\RR$ is a strictly well-founded relation.
== Proof 1 ==
== Proof 2 ==
Category:Infinite Sequence Property of Strictly Well-Founded Relation
Infinite Sequence Property of Strictly Well-Founded Relation/Reverse Implication/Proof 1

== Theorem ==
== Proof ==
Suppose $\RR$ is not a strictly well-founded relation.
So by definition there exists a non-empty subset $T$ of $S$ which has no strictly minimal element.
Let $a \in T$.
Since $a$ is not strictly minimal in $T$, we can find $b \in T: b \mathrel \RR a$.
This holds for all $a \in T$.
Hence the restriction $\RR \restriction_{T \times T}$ of $\RR$ to $T \times T$ is a right-total endorelation on $T$.
So, by the Axiom of Dependent Choice, it follows that there is an infinite sequence $\sequence {a_n}$ in $T$ such that:
:$\forall n \in \N: a_{n + 1} \mathrel \RR a_n$
It follows by the Rule of Transposition that if there is no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: a_{n + 1} \mathrel \RR a_n$
then $\RR$ is a strictly well-founded relation.
Category:Infinite Sequence Property of Strictly Well-Founded Relation
Infinite Sequence Property of Strictly Well-Founded Relation/Reverse Implication/Proof 2

== Theorem ==
== Proof ==
Suppose $\RR$ is not a strictly well-founded relation.
Hence there exists $T \subseteq S$ such that $T$ has no strictly minimal element under $\RR$.
Let $a_0 \in T$.
We have that $a_0$ is not strictly minimal in $T$.
So:
:$\exists a_1 \in T: a_1 \mathrel \RR a_0$
Similarly, $a_1$ is not strictly minimal in $T$.
So:
:$\exists a_2 \in T: a_2 \mathrel \RR a_1$
Let $a_{k + 1}$ be an arbitrary element for which $a_{k + 1} \mathrel \RR a_k$.
In order to allow this to be possible in the infinite case, it is necessary to invoke the Axiom of Dependent Choice as follows:
Let $a_k \in T$.
Then as $a_k$ is not strictly minimal in $T$:
:$\exists a_{k + 1} \in T: a_{k + 1} \mathrel \RR a_k$
Hence by definition $\RR$ is a right-total relation.
So, by the Axiom of Dependent Choice, it follows that:
:$\forall n \in \N: \exists a_n \in T: a_{n + 1} \mathrel \RR a_n$
Thus we have been able to construct an infinite sequence $\sequence {a_n}$ in $T$ such that:
:$\forall n \in \N: a_{n + 1} \mathrel \RR a_n$.
It follows by the Rule of Transposition that if there is no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: a_{n + 1} \mathrel \RR a_n$
then $\RR$ is a strictly well-founded relation.
Category:Infinite Sequence Property of Strictly Well-Founded Relation
Infinite Sequence Property of Well-Founded Relation

== Theorem ==
Let $\struct {S, \RR}$ be a relational structure.
Then $\RR$ is a well-founded relation there exists no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } \paren {a_{n + 1} \ne a_n}$
== Proof ==
=== Reverse Implication ===
=== Forward Implication ===
== Sources ==
* : $\S 1$: Naive Set Theory: $\S 1.5$: Relations: Lemma $1.5.1$
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $9$
* : $\S 1.2.1$: Mathematical Induction: Exercise $15 \ \text{(f)}$
Category:Well-Founded Relations
Category:Infinite Sequence Property of Well-Founded Relation
Infinite Sequence Property of Well-Founded Relation/Forward Implication

== Theorem ==
Let $\struct {S, \RR}$ be a relational structure.
Let $\RR$ be a well-founded relation.
Then there exists no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } \paren {a_{n + 1} \ne a_n}$
== Proof ==
Let $\RR$ be a well-founded relation.
 there exists an infinite sequence $\sequence {a_n}$ in $S$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } \paren {a_{n + 1} \ne a_n}$
Let $T = \set {a_0, a_1, a_2, \ldots}$.
Let $a_k \in T$ be a minimal element of $T$.
That is:
:$\forall y \in T \setminus \set {a_k}: \neg \paren {y \mathrel \RR a_k}$
But we have that:
:$a_{k + 1} \mathrel \RR a_k$ and $a_{k + 1} \ne a_k$.
So $a_k$ is not a minimal element.
It follows by Proof by Contradiction that such an infinite sequence cannot exist.
== Sources ==
* : $\S 1$: Naive Set Theory: $\S 1.5$: Relations: Lemma $1.5.1$
Category:Infinite Sequence Property of Well-Founded Relation
Infinite Sequence Property of Well-Founded Relation/Reverse Implication

== Theorem ==
Let $\struct {S, \RR}$ be a relational structure.
Let $\RR$ be such that there exists no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } \paren {a_{n + 1} \ne a_n}$
Then $\RR$ is a well-founded relation.
== Proof 1 ==
== Proof 2 ==
Category:Infinite Sequence Property of Well-Founded Relation
Infinite Sequence Property of Well-Founded Relation/Reverse Implication/Proof 1

== Theorem ==
== Proof ==
Suppose $\RR$ is not a well-founded relation.
So by definition there exists a non-empty subset $T$ of $S$ which has no minimal element.
Let $a \in T$.
Since $a$ is not minimal in $T$, we can find $b \in T: \paren {b \mathrel \RR a} \text { and } \paren {b \ne a}$.
This holds for all $a \in T$.
Hence the restriction $\RR \restriction_{T \times T}$ of $\RR$ to $T \times T$ is a right-total endorelation on $T$.
So, by the Axiom of Dependent Choice, it follows that there is an infinite sequence $\sequence {a_n}$ in $T$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } \paren {a_{n + 1} \ne a_n}$
It follows by the Rule of Transposition that if there is no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } \paren {a_{n + 1} \ne a_n}$
then $\RR$ is a well-founded relation.
Category:Infinite Sequence Property of Well-Founded Relation
Infinite Sequence Property of Well-Founded Relation/Reverse Implication/Proof 2

== Theorem ==
== Proof ==
Suppose $\RR$ is not a well-founded relation.
Hence there exists $T \subseteq S$ such that $T$ has no minimal element under $\RR$.
Let $a_0 \in T$.
We have that $a_0$ is not minimal in $T$.
So:
:$\exists a_1 \in T: \paren {a_1 \mathrel \RR a_0} \text { and } a_1 \ne a_0$
Similarly, $a_1$ is not minimal in $T$.
So:
:$\exists a_2 \in T: \paren {a_2 \mathrel \RR a_1} \text { and } a_2 \ne a_1$
Let $a_{k + 1}$ be an arbitrary element for which $a_{k + 1} \mathrel \RR a_k$ and $a_{k + 1} \ne a_k$.
In order to allow this to be possible in the infinite case, it is necessary to invoke the Axiom of Dependent Choice as follows:
Let $a_k \in T$.
Then as $a_k$ is not minimal in $T$:
:$\exists a_{k + 1} \in T: \paren {a_{k + 1} \mathrel \RR a_k} \text { and } \paren {a_{k + 1} \ne a_k}$
Hence by definition $\RR$ is a right-total relation.
So, by the Axiom of Dependent Choice, it follows that:
:$\forall n \in \N: \exists a_n \in T: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } a_{n + 1} \ne a_n$
Thus we have been able to construct an infinite sequence $\sequence {a_n}$ in $T$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } a_{n + 1} \ne a_n$
It follows by the Rule of Transposition that if there is no infinite sequence $\sequence {a_n}$ of elements of $S$ such that:
:$\forall n \in \N: \paren {a_{n + 1} \mathrel \RR a_n} \text { and } a_{n + 1} \ne a_n$
then $\RR$ is a well-founded relation.
== Sources ==
* : $\S 1$: Naive Set Theory: $\S 1.5$: Relations: Lemma $1.5.1$
Category:Infinite Sequence Property of Well-Founded Relation
Infinite Sequence in Countably Compact Space has Accumulation Point

== Corollary to Countably Infinite Set in Countably Compact Space has Omega-Accumulation Point ==
Let $T = \struct {S, \tau}$ be a countably compact topological space.
Let $\sequence {x_n}_{n \mathop \in \N}$ be an infinite sequence in $S$.
Then $\sequence {x_n}$ has an accumulation point in $T$.
== Proof ==
Let $A \subseteq S$ be the range of $\sequence {x_n}$:
:$A = \set {x_n: n \in \N}$
If $A$ is finite, then consider the equality:
:$\ds \N = \bigcup_{y \mathop \in A} \set {n \in \N: x_n = y}$
Therefore, there exists a $y \in A$ such that $\set {n \in \N: x_n = y}$ is an infinite set.
Hence, $y$ is an accumulation point of $\sequence {x_n}$.
Otherwise, $A$ is countably infinite.
Then $A$ has an $\omega$-accumulation point in $T$.
It follows that $\sequence {x_n}$ has an accumulation point in $T$.
== Sources ==
* : Part $\text I$: Basic Definitions: Section $3$: Compactness: Global Compactness Properties
Category:Countably Compact Spaces
Category:Sequences
Category:Accumulation Points
Infinite Series of Functions is Uniformly Convergent iff Sequence of Partial Sums is Uniformly Cauchy

== Theorem ==
Let $S \subseteq \R$.
Let $\sequence {f_n}$ be a sequence of real functions $S \to \R$.
Then the infinite series: 
:$\ds \sum_{n \mathop = 1}^\infty f_n$
converges uniformly on $S$ for all $\varepsilon \in \R_{> 0}$ there exists $N \in \N$ such that:
:$\ds \size {\sum_{k \mathop = m + 1}^n \map {f_k} x} < \varepsilon$
for all $x \in S$ and $n > m > N$.
== Proof ==
Let $\sequence {s_n}$ be a sequence of real functions $S \to \R$ with: 
:$\ds \map {s_n} x = \sum_{k \mathop = 1}^n \map {f_k} x$
for each $n \in \N$ and $x \in S$.
By definition of uniform convergence of an infinite series:
:$\ds \sum_{n \mathop = 1}^\infty f_n$ is uniformly convergent $\sequence {s_n}$ is uniformly convergent.
By Sequence of Functions is Uniformly Cauchy iff Uniformly Convergent:
:$\sequence {s_n}$ is uniformly convergent it is uniformly Cauchy.
That is:
:for all $\varepsilon \in \R_{> 0}$ there exists $N \in \N$ such that for all $m, n > N$ we have:
::$\size {\map {s_n} x - \map {s_m} x} < \varepsilon$ for all $x \in S$.
Note that if $n = m$: 
:$\size {\map {s_n} x - \map {s_m} x} = 0 < \varepsilon$
, we can therefore take $n > m$.
If $n > m$, then:
So $\sequence {s_n}$ is uniformly Cauchy for all $\varepsilon \in \R_{> 0}$ there exists $N \in \N$ such that:
:$\ds \size {\sum_{k \mathop = m + 1}^n \map {f_k} x} < \varepsilon$
for all $n > m > N$ and $x \in S$.
== Sources ==
* : $\S 9.6$: Uniform Convergence of Infinite Series of Functions: Theorem $9.5$
Category:Uniform Convergence
Infinite Series of Measurable Functions is Measurable

== Theorem ==
Let $\struct {X, \Sigma}$ be a measurable space. 
Let $\sequence {f_n}_{n \mathop \in \N}$ be a sequence of $\Sigma$-measurable functions $f_n : X \to \overline \R$ such that: 
:for each $N \in \N$ and $x \in X$, the summation $\ds \sum_{n \mathop = 1}^N \map {f_n} x$ is well-defined.
Then: 
:the series $\ds \sum_{n \mathop = 1}^\infty f_n$ is $\Sigma$-measurable.
== Proof ==
From Pointwise Sum of Measurable Functions is Measurable: General Result, we have: 
:$\ds \sum_{n \mathop = 1}^N f_n$ is $\Sigma$-measurable for each $N \in \N$. 
Then, from Pointwise Limit of Measurable Functions is Measurable, we have: 
:$\ds \lim_{N \mathop \to \infty} \sum_{n \mathop = 1}^N f_n$ is $\Sigma$-measurable.
From the definition of infinite series, we have: 
:$\ds \lim_{N \mathop \to \infty} \sum_{n \mathop = 1}^N f_n = \sum_{n \mathop = 1}^\infty f_n$
so that: 
:$\ds \sum_{n \mathop = 1}^\infty f_n$ is $\Sigma$-measurable.
Category:Measurable Functions
Infinite Series preserves Strict Inequality

== Theorem ==
Let $\sequence {x_n}_{n \mathop \in \N}$ and $\sequence {y_n}_{n \mathop \in \N}$ be real sequences such that: 
:$x_n \le y_n$ for all $n \in \N$
and:
:$x_m < y_m$ for at least one $m \in \N$.
Suppose that: 
:$\ds \sum_{n \mathop = 1}^\infty x_n$ and $\ds \sum_{n \mathop = 1}^\infty y_n$ both converge.
Then:
:$\ds \sum_{n \mathop = 1}^\infty x_n < \sum_{n \mathop = 1}^\infty y_n$ 
== Proof ==
We have: 
:$\ds \sum_{n \mathop = 1}^N x_n \le \sum_{n \mathop = 1}^N y_n$ for each $N \in \N$.
Then: 
:$\ds \sum_{n \mathop = 1}^N \paren {y_n - x_n} \ge 0$ for each $N \in \N$. 
From the Well-Ordering Principle, there exists a least $m \in \N$ such that $x_m < y_m$. 
Then for this $m$ we have $y_m - x_m > 0$.
So for $N \ge m$ we have: 
:$\ds \sum_{n \mathop = 1}^N \paren {y_n - x_n} \ge y_m - x_m > 0$
From Linear Combination of Convergent Series:
:$\ds \sum_{n \mathop = 1}^\infty \paren {y_n - x_n}$ converges and: 
::$\ds \sum_{n \mathop = 1}^\infty \paren {y_n - x_n} = \sum_{n \mathop = 1}^\infty y_n - \sum_{n \mathop = 1}^\infty x_n$
From Limits Preserve Inequalities, we have: 
:$\ds \sum_{n \mathop = 1}^\infty \paren {y_n - x_n} \ge y_m - x_m > 0$
That is: 
:$\ds \sum_{n \mathop = 1}^\infty y_n > \sum_{n \mathop = 1}^\infty x_n$
Category:Series
Infinite Set has Countably Infinite Subset

== Theorem ==
Every infinite set has a countably infinite subset.
== Intuitive Proof ==
== Proof 1 ==
== Proof 2 ==
This proof follows the same steps as the intuitive one, but with more formality.
== Proof 3 ==
== Proof 4 ==
== Comment ==
What this in effect shows is that countably infinite sets are the smallest possible infinite sets.
== Sources ==
* : $\S 2.2$: Theorem $3$
* : $\S 1.3$
* 
Category:Countable Sets
Category:Infinite Sets
Category:Subsets
Category:Infinite Set has Countably Infinite Subset
Infinite Set has Countably Infinite Subset/Intuitive Proof

== Theorem ==
== Intuitive Proof ==
Let $S$ be an infinite set, and let $a_0 \in S$.
$S$ is infinite, so $\exists a_1 \in S, a_1 \ne a_0$, and $\exists a_2 \in S, a_2 \ne a_0, a_2 \ne a_1$, and so on.
That is, we can continue to pick elements out of $S$, and assign them the labels $a_0, a_1, a_2, \ldots$ and this procedure will never terminate as $S$ is infinite.
Each one of the elements is in one-to-one correspondence with the elements of $\N$, and therefore the set $\left\{{a_0, a_1, a_2, \ldots}\right\} \subseteq S$ is countably infinite.
=== Warning ===
The intuitive nature of this proof obscures the fact that it is not a trivial truth that one may choose elements of $S$ in this manner when $S$ is infinite.
In Zermelo-Fraenkel set theory, a rigorous application of the principle of mathematical induction would show that one can repeat the procedure any finite number of times to construct a finite set $\set {a_0, a_1, \ldots, a_n}$.
However, in general, one needs the axiom of dependent choice to justify repeating such a procedure indefinitely.
It should be noted that the weaker axiom of countable choice is sufficient to prove the stated theorem.
== Sources ==
* : $\S 15$: The Axiom of Choice
* : $\S 2.2$: Countable sets: Theorem $3$
Category:Infinite Set has Countably Infinite Subset
Infinite Set has Countably Infinite Subset/Proof 1

== Theorem ==
== Proof ==
Let $S$ be an infinite set.
We use Between Two Sets Exists Injection or Surjection.
Suppose that there exists an injection $\psi: \N \to S$.
Let $T$ be the image of $\psi$.
From Injection to Image is Bijection, it follows that $\psi^{-1}: T \to \N$ is a bijection.
Hence, $T$ is a countably infinite subset of $S$.
Now, suppose that that there exists a surjection $\phi: \N \to S$.
From Surjection from Natural Numbers iff Countable, it follows that $S$ is countably infinite.
So, from Set is Subset of Itself, we have that $S$ is a countably infinite subset of $S$.
Category:Infinite Set has Countably Infinite Subset
Infinite Set has Countably Infinite Subset/Proof 2

== Theorem ==
== Proof ==
Let $S$ be an infinite set.
First an injection $f: \N \to S$ is constructed.
Let $g$ be a choice function on $\powerset S \setminus \set \O$.
Then define $f: \N \to S$ as follows:
:$\forall n \in \N: \map f n = \begin {cases} \map g S & : n = 0 \\ \map g {S \setminus \set {\map f 0, \ldots, \map f {n - 1} } } & : n > 0 \end {cases}$
Since $S$ is infinite, $S \setminus \set {\map f 0, \ldots, \map f {n - 1} }$ is non-empty for each $n \in \N$.
Therefore $f \sqbrk \N$ is infinite.
To show that $f$ is injective, let $m, n \in \N$, say $m < n$.
Then:
:$\map f m \in \set {\map f 0, \ldots, \map f {n - 1} }$
but:
:$\map f n \in S \setminus \set {\map f 0, \ldots, \map f {n - 1} }$
Hence $\map f m \ne \map f n$.
Since $f$ is injective, it follows from Injection to Image is Bijection that $f$ is a bijection from $\N$ to $f \sqbrk \N$.
Thus $f \sqbrk \N$ is a countable subset of $S$.
Category:Infinite Set has Countably Infinite Subset
Infinite Set has Countably Infinite Subset/Proof 3

== Theorem ==
== Proof ==
Let $S$ be an infinite set.
First an injection $f: \N \to S$ is constructed.
Let $f$ be a choice function on $\powerset S \setminus \set \O$.
That is:
:$\forall A \in \powerset S \setminus \set \O: \map f A \in A$
This is justified only if the Axiom of Choice is accepted.
Let $\CC$ be the set of all finite subsets of $S$.
Let $A \in \CC$.
Since $S$ is infinite it follows that $S \setminus A \ne \O$.
So $S \setminus A \in \Dom f$.
Let $g: \CC \to \CC$ be the mapping defined as:
:$\map g A = A \cup \set {\map f {S \setminus A} }$
That is, $\map g A$ is constructed by joining $A$ with the element that $f$ chooses from $S \setminus A$.
Consider the Recursion Theorem applied to $g$, starting with the set $\O$.
We obtain a mapping $U: \N \to \CC$ such that:
:$\map U x = \begin{cases}
\O & : x = 0 \\ \map U n \cup \set {\map f {S \setminus \map U n} } & : x = n^+
\end{cases}$
where here $\N$ is considered as the set of elements of the von Neumann construction of natural numbers.
Consider the mapping $v: \N \to S$, defined as:
:$\forall n \in \N: \map v n = \map f {S \setminus \map U n}$
We have that, by definition of $v$:
:$(1): \quad \forall n \in \N: \map v n \notin \map U n$
:$(2): \quad \forall n \in \N: \map v n \in \map U {n^+}$
:$(3): \quad \forall m, n \in \N: n \le m \implies \map U n \subseteq \map U m$
Then because $\map v n \in \map U m$ but $\map v m \notin \map U m$:
:$(4): \quad \forall m, n \in \N: n < m \implies \map v n \ne \map v m$
So $(4)$ implies that $v$ maps distinct elements of $\N$ onto distinct elements of $S$.
Thus $v: \N \to S$ is an injection.
It follows from Injection to Image is Bijection that $v$ is a bijection from $\N$ to $\map v \N$.
Thus $\map v \N$ is the countable subset of $S$ that was required.
== Sources ==
* : $\S 15$: The Axiom of Choice
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 1$ Introduction to well ordering: Exercise $1.8$
Category:Infinite Set has Countably Infinite Subset
Infinite Set has Countably Infinite Subset/Proof 4

== Theorem ==
If the axiom of countable choice is accepted, then it can be proven that every infinite set has a countably infinite subset.
== Proof ==
Let $S$ be an infinite set.
For all $n \in \N$, let:
:$\FF_n = \set {T \subseteq S: \size T = n}$
where $\size T$ denotes the cardinality of $T$.
From Set is Infinite iff exist Subsets of all Finite Cardinalities:
:$\FF_n$ is non-empty.
Using the axiom of countable choice, we can obtain a sequence $\sequence {S_n}_{n \mathop \in \N}$ such that $S_n \in \FF_n$ for all $n \in \N$.
Define:
:$\ds T = \bigcup_{n \mathop \in \N} S_n \subseteq S$
For all $n \in \N$, $S_n$ is a subset of $T$ whose cardinality is $n$.
From Set is Infinite iff exist Subsets of all Finite Cardinalities:
:$T$ is infinite.
From Countable Union of Countable Sets is Countable, $T$ is countable.
Category:Infinite Set has Countably Infinite Subset
Infinite Set in Compact Space has Omega-Accumulation Point

== Theorem ==
Let $\struct {X, \tau}$ be a compact topological space.
Let $A \subseteq X$ be infinite.
Then $A$ has an $\omega$-accumulation point in $X$.
== Proof ==
 $A$ has no $\omega$-accumulation points in $X$.
Then for any $x \in X$, there exists some open set $U_x$ such that $U_x$ only contains a finite number of points in $A$.
The collection of all such open sets $\CC = \set {U_x: x \in X}$ is an open cover for $X$.
Since $X$ is compact, $\CC$ has a finite subcover $\CC'$.
$\CC'$ contains a finite number of sets in $\CC$, and each of those sets contain a finite number of points in $A$.
Therefore $\bigcup \CC'$ contains a finite number of points in $A$.
However by definition of a subcover, $A \subseteq X \subseteq \bigcup \CC'$.
Thus $\bigcup \CC'$ contains all points in $A$, of which there are infinite.
This is a contradiction.
Therefore $A$ must have an $\omega$-accumulation point in $X$.
Category:Compact Spaces
Category:Omega-Accumulation Points
Infinite Set is Equivalent to Proper Subset

== Theorem ==
A set is infinite it is equivalent to one of its proper subsets.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Examples ==
== Also see ==
* Dedekind-Infinite: used this result as the definition of an infinite set.
* Galileo's Paradox
== Sources ==
* : Chapter $\text {I}$: Sets of Points: $1 \cdot 2$. Infinite sets
* : Exercise $1.3: \ 14$
* : $\S 3.7$. Similar sets: Example $56$
* : Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets
* 
* 
Category:Infinite Set is Equivalent to Proper Subset
Category:Set Equivalence
Category:Infinite Sets
Category:Proper Subsets
Infinite Set is Equivalent to Proper Subset/Examples/Even Integers

== Examples of Use of Infinite Set is Equivalent to Proper Subset ==
Let $\Z$ be the set of integers.
By Integers are Countably Infinite, $\Z$ is infinite.
Let $E$ be the set of all even integers.
We have that, for example, $3 \in \Z$ but $3 \notin E$
Hence $E$ is a proper subset of $\Z$
Let $f: \Z \to E$ be the mapping defined as:
:$\forall x \in \Z: \map f x = 2 x$
Then $f$ is a bijection.
Hence $\Z$ and $E$ are equivalent.
== Sources ==
* : Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets
* 
* 
Category:Examples of Use of Infinite Set is Equivalent to Proper Subset
Infinite Set is Equivalent to Proper Subset/Proof 1

== Theorem ==
== Proof ==
Let $T$ be an infinite set.
By Infinite Set has Countably Infinite Subset, it is possible to construct a countably infinite subset of $T$.
Let $S = \set {a_1, a_2, a_3, \ldots}$ be such a countably infinite subset of $T$.
Create a Partition of $S$ into:
:$S_1 = \set {a_1, a_3, a_5, \ldots}, S_2 = \set {a_2, a_4, a_6, \ldots}$
Let a bijection be established between $S$ and $S_1$, by letting $a_n \leftrightarrow a_{2 n - 1}$.
This is extended to a bijection between $S \cup \paren {T \setminus S} = T$ and $S_1 \cup \paren {T \setminus S} = T \setminus S_2$ by assigning each element in $T \setminus S$ to itself.
So a bijection has been demonstrated between $T$ and one of its proper subsets $T \setminus S_2$.
That is, if $T$ is infinite, it is equivalent to one of its proper subsets.
Now, let $T_0 \subsetneq T$ be a proper subset of $T$, and $f: T \to T_0$ be a bijection.
It follows from No Bijection between Finite Set and Proper Subset that $T$ must be infinite.
== Sources ==
* : $\S 2.3$: Equivalence of sets: Theorem $4$
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 1$ Introduction to well ordering: Exercise $1.7$
Category:Infinite Set is Equivalent to Proper Subset
Infinite Set is Equivalent to Proper Subset/Proof 2

== Theorem ==
== Proof ==
Let $S$ be a set.
Suppose $S$ is finite.
From No Bijection between Finite Set and Proper Subset we have that $S$ can not be equivalent to one of its proper subsets.
Suppose $S$ is infinite.
From Infinite Set has Countably Infinite Subset, we can construct $v: \N \to S$ such that $v$ is an injection.
We now construct the mapping $h: S \to S$ as follows.
:$\map h x = \begin {cases}
\map v {n + 1} & : \exists n \in \N: x = \map v n \\
x & : x \notin \Img v
\end {cases}$
It is clear that $h$ is an injection.
But we have that $\map v 0 \notin \Img h$ and so $\Img h \subsetneq S$.
The result follows from Injection to Image is Bijection.
== Sources ==
* : $\S 15$: The Axiom of Choice
Category:Infinite Set is Equivalent to Proper Subset