nyuuzyou/wikis huggingface dataset:
Subset is Compatible with Ordinal Successor/Proof 3

== Theorem ==
== Proof ==
First note that by Successor Set of Ordinal is Ordinal, $x^+$ and $y^+$ are ordinals.
By Ordinal Membership is Trichotomy, one of the following must be true:
We will show that the first two are both false, so that the third must hold.
Two preliminary facts:
By $(1)$ and Equality of Successors:
:$x^+ \ne y^+$
Thus the first of the three possibilities is false.
 $y^+ \in x^+$.
Then:
But we already know that $y \notin x$ by $(2)$ and $y \ne x$ by $(1)$.
So this is a contradiction, and we conclude that $y^+ \notin x^+$.
Thus we have shown that the second possibility is false.
Thus the third and final one must hold: $x^+ \in y^+$.
Category:Subset is Compatible with Ordinal Successor
Subset is Element of Power Set

== Theorem ==
Let $x$ be a set.
Let $\powerset x$ denote the power set of $x$.
Then:
:$y \in \powerset x \iff y \subseteq x$
== Proof ==
By definition of power set, $\powerset x$ is the set of subsets of $x$.
Hence the result, by definition of subset and power set.
== Sources ==
* : Chapter $2$: Some Basics of Class-Set Theory: $\S 6$ The power axiom: Remarks $(2)$
Category:Power Set
Category:Subsets
Subset is Right Compatible with Ordinal Addition

== Theorem ==
Let $x, y, z$ be ordinals.
Then:
:$x \le y \implies \paren {x + z} \le \paren {y + z}$
== Proof ==
The proof proceeds by transfinite induction on $z$.
=== Base Case ===
=== Inductive Case ===
=== Limit Case ===
The result follows by transfinite induction.
== Sources ==
* : $\S 8.7$
Category:Ordinal Arithmetic
Subset is Right Compatible with Ordinal Exponentiation

== Theorem ==
Let $x, y, z$ be ordinals.
Then:
:$x \le y \implies x^z \le y^z$
== Proof ==
The proof shall proceed by Transfinite Induction on $z$.
=== Basis for the Induction ===
If $z = \O$, then $x^z = 1$
This proves the basis for the induction.
=== Induction Step ===
The inductive hypothesis states that $x^z \le y^z$ for $y$.
Then:
This proves the induction step.
=== Limit Case ===
The inductive hypothesis for the limit case states that:
:$\forall w \in z: x^w \le y^w$ where $z$ is a limit ordinal.
This proves the limit case.
== Sources ==
* : $\S 8.35$
Category:Ordinal Arithmetic
Subset is Right Compatible with Ordinal Multiplication

== Theorem ==
Let $x, y, z$ be ordinals.
Then:
:$x \le y \implies \paren {x \cdot z} \le \paren {y \cdot z}$
== Proof ==
The proof shall proceed by Transfinite Induction on $z$.
=== Basis for the Induction ===
By definition of ordinal multiplication:
:$x \cdot 0 = 0$
so the statement simply reduces to:
:$0 \le 0$
This proves the basis for the induction.
=== Induction Step ===
This proves the induction step.
=== Limit Case ===
This proves the limit case.
== Also see ==
* Subset is Right Compatible with Ordinal Addition
== Sources ==
* : $\S 8.21$
Category:Ordinal Arithmetic
Subset not necessarily Submagma

== Theorem ==
Let $\struct {S, \circ}$ be a magma.
Let $T \subseteq S$.
Then it is not necessarily the case that:
: $\struct {T, \circ} \subseteq \struct {S, \circ}$
That is, it does not always follow that $\struct {T, \circ}$ is a submagma of $\struct {S, \circ}$.
== Proof ==
Let $\struct {\Z, -}$ be the magma which is the set of integers under the operation of subtraction.
We have that the natural numbers $\N$ are a subset of the integers.
Consider $\struct {\N, -}$, the natural numbers under subtraction.
We have that Natural Number Subtraction is not Closed.
For example:
: $1 - 2 = -1 \notin \N$
Thus $\struct {\N, -}$ is not closed.
So $\struct {\N, -}$ is not a submagma of $\struct {\Z, -}$
Hence it is not true to write $\struct {\N, -} \subseteq \struct {\Z, -}$, despite the fact that $\N \subseteq \Z$.
Thus $\struct {\N, -}$ is not a submagma of $\struct {\Z, -}$.
== Sources ==
* : $\S 0.5$: Example $17$
Category:Magmas
Category:Submagmas
Category:Subsets
Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup

== Theorem ==
Let $\struct {G, \circ}$ be an abelian group.
Let $S \subset G$ be a non-empty subset of $G$ such that $\struct {S, \circ}$ is closed.
Let $H$ be the set defined as:
:$H := \set {x \circ y^{-1}: x, y \in S}$
Then $\struct {H, \circ}$ is a subgroup of $\struct {G, \circ}$.
== Proof ==
Let $x \in S$.
Then:
:$x \circ x^{-1} \in H$
and so $H \ne \O$.
Now let $a, b \in H$.
Then:
:$a = x_a \circ y_a^{-1}$
and:
:$b = x_b \circ y_b^{-1}$
for some $x_a, y_a, x_b, y_b \in S$.
Thus:
As $\struct {S, \circ}$ is closed, both $x_a \circ y_b \in S$ and $x_b \circ y_a \in S$.
Thus $a \circ b$ is in the form $x \circ y^{-1}$ for $x, y \in S$.
Thus $a \circ b \in H$
Hence by the One-Step Subgroup Test, $H$ is a subgroup of $G$.
== Examples ==
== Also see ==
* Definition:Inverse Completion
== Sources ==
* : Chapter $5$: Subgroups: Exercise $3$
Category:Abelian Groups
Category:Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup
Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup/Examples

== Examples of Use of Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup ==
=== $\struct {\Z_{\ne 0}, \times}$ in $\struct {\R_{\ne 0}, \times}$ ===
Category:Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup
Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup/Examples/Non-Zero Integers in Non-Zero Reals under Multiplication

== Examples of Use of Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup ==
Let $\struct {\Z_{\ne 0}, \times}$ denote the algebraic structure formed by the set of non-zero integers under multiplication.
Let $\struct {\R_{\ne 0}, \times}$ denote the algebraic structure formed by the set of non-zero real numbers under multiplication.
Let $H$ denote the set:
:$H := \set {x \times y^{-1}: x, y \in \Z_{\ne 0} }$
Then $H$ is the subgroup of $\struct {\R_{\ne 0}, \times}$ which is the set of non-zero rational numbers under multiplication:
:$H = \struct {\Q_{\ne 0}, \times}$
== Proof ==
From Non-Zero Integers Closed under Multiplication:
:$\forall a, b \in \Z_{\ne 0}: a \times b \in \Z_{\ne 0}$
From Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup:
:$H$ is a subgroup of $\struct {\R_{\ne 0}, \times}$
The elements of $H$ are all the numbers of the form:
:$x = \dfrac p q$
where $p, q \in \Z_{\ne 0}$
and thus by definition rational numbers.
Hence the result.
We also note that Non-Zero Rational Numbers under Multiplication form Infinite Abelian Group for further confirmation.
== Sources ==
* : Chapter $5$: Subgroups: Exercise $4$
Category:Subset of Abelian Group Generated by Product of Element with Inverse Element is Subgroup
Subset of Bounded Above Set is Bounded Above

== Theorem ==
Let $A$ and $B$ be sets of real numbers such that $A \subseteq B$.
Let $B$ be bounded above.
Then $A$ is also bounded above.
== Proof ==
Let $B$ be bounded above.
Then by definition $B$ has an upper bound $U$.
Hence:
:$\forall x \in B: x \le U$
But by definition of subset:
:$\forall x \in A: x \in B$
That is:
:$\forall x \in A: x \le U$
Hence, by definition, $A$ is bounded above by $U$.
== Sources ==
* : $1$: Review of some real analysis: Exercise $1.5: 1$
Category:Bounded Above Sets of Real Numbers
Subset of Bounded Below Set is Bounded Below

== Theorem ==
Let $A$ and $B$ be sets of real numbers such that $A \subseteq B$.
Let $B$ be bounded below.
Then $A$ is also bounded below.
== Proof ==
Let $B$ be bounded below.
Then by definition $B$ has a lower bound $L$.
Hence:
:$\forall x \in B: x \ge L$
But by definition of subset:
:$\forall x \in A: x \in B$
That is:
:$\forall x \in A: x \ge L$
Hence, by definition, $A$ is bounded below by $L$.
== Sources ==
* : $1$: Review of some real analysis: Exercise $1.5: 3$
Category:Bounded Below Sets of Real Numbers
Subset of Bounded Subset of Metric Space is Bounded

== Theorem ==
Let $M = \struct {A, d}$ be a metric space.
Let $B$ be a bounded subset of $M$.
Let $\map \diam B$ denote the diameter of $B$.
Let $C \subseteq B$ be a subset of $B$.
Then $C$ is a bounded subset of $M$ such that:
:$\map \diam C \le \map \diam B$
== Proof ==
== Sources ==
* : $2$: Continuity generalized: metric spaces: Exercise $2.6: 4$
Category:Bounded Metric Spaces
Subset of Cartesian Product

== Theorem ==
Let $S$ be a set of ordered pairs.
Then $S$ is the subset of the cartesian product of two sets.
== Proof ==
Let $S$ be a set of ordered pairs.
Let $x \in S$ such that $x = \set {\set a, \set {a, b} }$ as defined in Kuratowski Formalization of Ordered Pair.
Since the elements of $S$ are sets, we can form the union $\mathbb S = \bigcup S$ of the sets in $S$.
Since $x \in S$ it follows that the elements of $x$ are elements of $\mathbb S$.
Since $\set {a, b} \in x$ it follows that $\set {a, b} \in \mathbb S$.
Now we can form the union $\mathbb S' = \bigcup \mathbb S$ of the sets in $\mathbb S$.
Since $\set {a, b} \in \mathbb S$ it follows that both $a$ and $b$ are elements of $\mathbb S' = \bigcup \bigcup S$.
Thus from the Kuratowski Formalization of Ordered Pair we have that $S$ is a subset of some $A \times B$.
We can at this stage take both $A$ and $B$ as being equal to $\bigcup \bigcup S$.
Finally, the axiom of specification is applied to construct the sets:
:$A = \set {a: \exists b: \tuple {a, b} \in S}$
and
:$B = \set {b: \exists a: \tuple {a, b} \in S}$
$A$ and $B$ are seen to be the first and second projections respectively of $S$.
== Sources ==
* : $\S 6$: Ordered Pairs
Category:Cartesian Product
Category:Axiomatic Set Theory
Subset of Cartesian Product not necessarily Cartesian Product of Subsets

== Theorem ==
Let $A$ and $B$ be sets.
Let $A$ and $B$ both have at least two distinct elements.
Then there exists $W \subseteq A \times B$ such that $W$ is not the cartesian product of a subset of $A$ and a subset of $B$.
== Proof ==
Let $a \in A, b \in A, c \in B, d \in B$ be arbitrary elements of $A$ and $B$.
Let:
:$W = \set {\tuple {a, c}, \tuple {a, d}, \tuple {b, d} }$
Then $W \subseteq A \times B$.
Suppose $W = X \times Y$ such that $X \subseteq A, Y \subseteq B$.
Then $a, b \in X$ and $c, d \in Y$.
But $X \times Y$ also contains $\tuple {b, c}$ which is not in $W$.
Hence the result.
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 5$: Products of Sets: Exercise $3$
Category:Cartesian Product
Subset of Codomain is Superset of Image of Preimage

== Theorem ==
Let $f: S \to T$ be a mapping.
Then:
:$B \subseteq T \implies \paren {f \circ f^{-1} } \sqbrk B \subseteq B$
where:
:$f \sqbrk B$ denotes the image of $B$ under $f$
:$f^{-1}$ denotes the inverse of $f$
:$f \circ f^{-1}$ denotes composition of $f$ and $f^{-1}$.
This can be expressed in the language and notation of direct image mappings and inverse image mappings as:
:$\forall B \in \powerset T: \map {\paren {f^\to \circ f^\gets} } B \subseteq B$
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Sources ==
* : Chapter $1$: Mappings: $\S 12 \alpha$
* : Chapter $1$: Theory of Sets: $\S 6$: Functions: Exercise $1 \ \text{(b})$
* : $1$: Set Theory and Logic: $\S 2$: Functions
Category:Composite Mappings
Category:Preimages under Mappings
Category:Subset of Codomain is Superset of Image of Preimage
Subset of Codomain is Superset of Image of Preimage/Proof 1

== Theorem ==
== Proof ==
From Image of Preimage under Mapping:
: $B \subseteq T \implies \left({f \circ f^{-1} }\right) \left[{B}\right] = B \cap f \left[{S}\right]$
The result follows from Intersection is Subset.
Category:Subset of Codomain is Superset of Image of Preimage
Subset of Codomain is Superset of Image of Preimage/Proof 2

== Theorem ==
== Proof ==
Let $y \in B$.
Then:
:$\exists x \in S: y = f \left({x}\right)$
Therefore by definition of preimage of subset:
:$\exists x \in f^{-1} \left[{B}\right]$
It follows by definition of image of subset that:
:$y \in f \left[{f^{-1} \left[{B}\right]}\right]$
Thus by definition of composition $f$ with $f^{-1}$:
:$y \in \left({f \circ f^{-1}}\right) \left[{B}\right]$
The result follows by definition of subset.
== Sources ==
* : $\S 10$: Inverses and Composites
Category:Subset of Codomain is Superset of Image of Preimage
Subset of Codomain is Superset of Image of Preimage/Proof 3

== Theorem ==
== Proof ==
Let $B \subseteq T$.
Then:
So by definition of subset:
:$B \subseteq T \implies \paren {f \circ f^{-1} } \sqbrk B \subseteq B$
== Sources ==
* : $\S 5$. Induced mappings; composition; injections; surjections; bijections: Theorem $5.8$
Category:Subset of Codomain is Superset of Image of Preimage
Subset of Convex Set can be Uniquely Expressed as Partition of Maximal Convex Sets

== Theorem ==
Let $\struct {S, \preccurlyeq}$ be an ordered set.
Then $S$ can be uniquely expressed as the partition whose components are maximally convex sets.
== Proof ==
== Sources ==
* : Part $\text {II}$: Counterexamples: $39$. Order Topology: $2$
Category:Convex Sets (Order Theory)
Subset of Countable Set is Countable

== Theorem ==
A subset of a countable set is countable.
== Proof ==
Let $S$ be a countable set.
Let $T \subseteq S$.
By definition, there exists an injection $f: S \to \N$.
Let $i: T \to S$ be the inclusion mapping.
We have that $i$ is an injection.
Because the composite of injections is an injection, it follows that $f \circ i: T \to \N$ is an injection.
Hence, $T$ is countable.
== Also see ==
* Subset of Countably Infinite Set is Countable, a special case of this theorem
== Sources ==
* : Exercise $17.12$
* : $1$: Set Theory and Logic: $\S 7$: Countable and Uncountable Sets: Corollary $7.3$
Category:Countable Sets
Category:Subsets
Subset of Countably Infinite Set is Countable

== Theorem ==
Every subset of a countably infinite set is countable.
== Proof ==
Let $S = \set {a_0, a_1, a_2, \ldots}$ be countably infinite.
Let $T \subseteq S = \set {a_{n_0}, a_{n_1}, a_{n_2}, \ldots}$, where $a_{n_0}, a_{n_1}, a_{n_2}, \ldots$ are the elements of $S$ also in $T$.
If the set of numbers $\set {n_0, n_1, n_2, \ldots}$ has a largest number, then $T$ is finite.
Otherwise, consider the bijection $i \leftrightarrow n_i$.
This leads to the bijection $i \leftrightarrow a_{n_i}$
This latter bijection is the required one-to-one correspondence between the elements of $T$ and those of $\N$, showing that $T$ is indeed countable.
== Also see ==
* Subset of Countable Set is Countable
* Superset of Co-Countable Set
== Sources ==
* : Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability
* : $\S 2.2$: Countable sets: Theorem $1$
* : Chapter $1$: Mappings: $\S 15 \eta$
* : Chapter $1$: Preliminaries: Exercises: $1.10$
Category:Countable Sets
Category:Subsets
Subset of Cover is Cover of Subset

== Theorem ==
Let $S$ be a set.
Let $\CC$ be a cover of $S$.
Let $T \subseteq S$.
Let:
:$\CC_T = \set {C \in \CC : C \cap T \ne \O}$
Then $\CC_T$ is a cover of $T$:
:$T \subseteq \bigcup \CC_T$
== Proof ==
Let $x \in T$.
By definition of a cover:
:$\exists C \in \CC : x \in C$
By definition of set intersection:
:$x \in C \cap T$
Hence:
:$C \in \CC_T$
Since $x$ was arbitrary, it follows that $\CC_T$ is a cover of $T$ by definition and:
:$T \subseteq \bigcup \CC_T$
Category:Covers
Category:Subsets
Subset of Discrete Set of Subsets is Discrete

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Let $\FF \subseteq \powerset S$ be a set of subsets of $S$.
Let $\GG \subseteq \FF$.
If $\FF$ is discrete then $\GG$ is discrete.
== Proof ==
We prove the contrapositive statement:
:If $\GG$ is not discrete then $\FF$ is not discrete.
Let $\GG$ not be discrete.
By definition of discrete:
:$\exists x \in S : \forall N \subseteq S : N$ is a neighborhood of $x : \exists X_1, X_2 \in \GG : X_1 \ne X_2: X_1 \cap N \ne \O, X_2 \cap N \ne \O$
By definition of subset:
:$\forall X \in \GG : X \in \FF$
Hence:
:$\exists x \in S : \forall N \subseteq S : N$ is a neighborhood of $x : \exists X_1, X_2 \in \FF : X_1 \ne X_2: X_1 \cap N \ne \O, X_2 \cap N \ne \O$
By definition, $\FF$ is not discrete.
The result follows from Rule of Transposition.
Category:Discrete Sets of Subsets
Subset of Domain is Subset of Preimage of Image

== Theorem ==
Let $f: S \to T$ be a mapping.
Then:
:$A \subseteq S \implies A \subseteq \paren {f^{-1} \circ f} \sqbrk A$
where:
:$f \sqbrk A$ denotes the image of $A$ under $f$
:$f^{-1} \sqbrk A$ denotes the preimage of $A$ under $f$
:$f^{-1} \circ f$ denotes composition of $f^{-1}$ and $f$.
This can be expressed in the language and notation of direct image mappings and inverse image mappings as:
:$\forall A \in \powerset S: A \subseteq \map {\paren {f^\gets \circ f^\to} } A$
=== Equality does Not Necessarily Hold ===
== Proof ==
As a mapping is by definition a left-total relation.
Therefore Preimage of Image under Left-Total Relation is Superset applies:
:$A \subseteq S \implies A \subseteq \paren {\RR^{-1} \circ \RR} \sqbrk A$
where $\RR$ is a relation.
Hence:
:$A \subseteq S \implies A \subseteq \paren {f^{-1} \circ f} \sqbrk A$
== Sources ==
* : $\S 10$: Inverses and Composites
* : Chapter $\text {II}$: New Structures from Old: $\S 12$: Homomorphisms: Exercise $12.13 \ \text{(c)}$
* : Chapter $1$: Mappings: $\S 12 \alpha$
* : $\S 1.12$: Set Inclusions for Image and Inverse Image Sets: Theorem $12.7 \ \text{(b)}$
* : $\S 5$. Induced mappings; composition; injections; surjections; bijections: Theorem $5.8$
* : Chapter $1$: Theory of Sets: $\S 6$: Functions: Exercise $1 \ \text{(a})$
* : $1$: Set Theory and Logic: $\S 2$: Functions
Category:Preimages under Mappings
Category:Composite Mappings
Category:Subset of Domain is Subset of Preimage of Image
Subset of Domain is Subset of Preimage of Image/Equality does Not Necessarily Hold

== Theorem ==
Let $f: S \to T$ be a mapping.
From Subset of Domain is Subset of Preimage of Image:
:$A \subseteq S \implies A \subseteq \paren {f^{-1} \circ f} \sqbrk A$
where:
:$f \sqbrk A$ denotes the image of $A$ under $f$
:$f^{-1} \sqbrk A$ denotes the preimage of $A$ under $f$
:$f^{-1} \circ f$ denotes composition of $f^{-1}$ and $f$.
It is not necessarily the case that:
:$A \subseteq S \implies A = \paren {f^{-1} \circ f} \sqbrk A$
== Proof ==
Proof by Counterexample:
Let:
:$S = \set {0, 1}$
:$T = \set 2$
Let $f: S \to T$ be defined as:
:$\map f 0 = 2$
:$\map f 1 = 2$
Let $A \subseteq S$ be defined as:
:$A = \set 0$
Then we have:
:$f \sqbrk A = \set 2$
but:
:$f^{-1} \circ f \sqbrk A = f^{-1} \sqbrk 2 = \set {0, 1}$
That is:
:$A \subseteq \paren {f^{-1} \circ f} \sqbrk A$
but it is not the case that:
:$A \paren {f^{-1} \circ f} \sqbrk A$
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 12$: Homomorphisms: Exercise $12.13 \ \text{(c)}$
Category:Subset of Domain is Subset of Preimage of Image
Subset of Empty Set iff Empty

== Theorem ==
Let $S$ be a set.
Let $\O$ denote the empty set.
Then $S \subseteq \O$ $S = \O$.
== Proof ==
Suppose $x \in S$.
Then since $S \subseteq \O$, it follows that $x \in \O$.
Hence $x \notin S$.
That is, $S = \O$.
Category:Empty Set
Subset of Euclidean Plane whose Product of Coordinates are Greater Than or Equal to 1 is Closed

== Theorem ==
Let $\struct {\R^2, \tau_d}$ be the real number plane with the usual (Euclidean) topology.
Let $A \subseteq R^2$ be the set of all points defined as:
:$A := \set {\tuple {x, y} \in \R^2: x y \ge 1}$
Then $A$ is a closed set in $\struct {\R^2, d}$.
== Proof ==
By definition, $\tau_d$ is the topology induced by the Euclidean metric $d$.
Consider the complement of $A$ in $\R^2$:
:$A' := \R^2 \setminus A$
Thus:
:$A := \set {\tuple {x, y} \in \R^2: x y < 1}$
Let $a = \tuple {x_a, y_a} \in A^2$.
Let $\epsilon = \size {1 - x_a y_a}$.
Then the open $\epsilon$-ball of $a$ in $\R^2$ lies entirely in $A'$.
As $a$ is arbitrary, it follows that any such $a$ has an open $\epsilon$-ball of $a$ in $\R^2$ which lies entirely in $A'$.
Thus, by definition, $A'$ is open in $\R^2$.
So, also by definition, $A$ is closed in $\R^2$.
== Sources ==
* : Part $\text {II}$: Counterexamples: $33$. Special Subsets of the Plane: $1$
Category:Closed Sets
Category:Real Number Plane with Euclidean Topology
Subset of Excluded Point Space is not Dense-in-itself

== Theorem ==
Let $T = \struct {S, \tau_{\bar p} }$ be a excluded point space such that $S$ is not a singleton.
Let $H \subseteq S$.
Then $H$ is not dense-in-itself.
== Proof ==
From Limit Points in Excluded Point Space, the only limit point of $H$ is $p$.
So by definition, all points of $H$ are isolated in $H$ except $p$.
So if $H \ne \set p$, $H$ contains at least one point which is isolated in $H$.
As for $p$ itself, from Singleton Point is Isolated we have that $p$ is itself isolated in $\set p$.
So if $H = \set p$, $H$ also contains one point which is isolated in $H$.
Hence the result, by definition of dense-in-itself.
== Sources ==
* : Part $\text {II}$: Counterexamples: $13 \text { - } 15$. Excluded Point Topology: $5$
Category:Denseness
Category:Excluded Point Topology
Subset of Finite Dimensional Normed Vector Space is Compact iff Closed and Bounded/Sufficient Condition

== Theorem ==
Let $\struct {X, \norm {\,\cdot\,}}$ be a finite-dimensional normed vector space.
Let $K \subset X$ be a compact subset.
Then $K$ is closed and bounded.
== Proof ==
=== Closedness ===
Let $\sequence {x_n}_{n \mathop \in \N}$ be a sequence in $K$.
Suppose, $\sequence {x_n}_{n \mathop \in \N}$ converges to $L \in K$. 
Then there is a subsequence $\sequence {x_{n_k}}_{k \mathop \in \N}$ convergent to $L' \in K$. 
But $\sequence {x_{n_k}}_{k \mathop \in \N}$ is a subsequence $\sequence {x_n}_{n \mathop \in \N}$.
Hence, $\sequence {x_{n_k}}_{k \mathop \in \N}$ converges to $L$.
By uniqueness of limits, $L = L'$.
By definition, $K$ is closed.
=== Boundedness ===
Suppose, $K$ is not bounded.
Then:
:$\forall n \in \N : \exists x_n \in K: \norm {x_n} > n$
Therefore, no subsequence of $\sequence {x_n}_{n \mathop \in \N}$ is convergent.
Hence, $K$ is not compact.
This is in contradiction with the assumption.
Thus, $K$ is bounded.
Category:Subset of Finite Dimensional Normed Vector Space is Compact iff Closed and Bounded
Subset of Finite Set is Finite

== Theorem ==
Let $X$ be a finite set.
If $Y$ is a subset of $X$, then $Y$ is also finite.
== Proof ==
From the definition, $X$ is finite $\exists n \in \N$ such that there exists a bijection:
:$f: X \leftrightarrow \N_n$
where $\N_n$ is the set of all elements of $\N$ less than $n$, that is:
:$\N_n = \set {0, 1, 2, \ldots, n - 1}$
The case in which $X$ is empty is trivial.
We begin proving the following particular case:
:If $X$ is finite and $a \in X$, then $X \setminus \set a$ is also finite.
From Bijection between Specific Elements there exists a bijection $f: \N_n \to X$, which satisfies $\map f n = a$.
Next we prove the general case by induction.
=== Basis for the Induction ===
If $n = 1$ then $X \setminus \set a = \O$ is finite.
If $n > 1$, the restriction of $f$ to $\set {k \in \N: k \le n - 1}$ yields a bijection into $X \setminus \set a$.
Hence $X \setminus \set a$ is finite and has $n - 1$ elements.
So, we have that if $n = 1$, then its subsets ($\O$ and $X$) are finite.
This is the basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if our Theorem is valid for sets with $n$ elements, it is also true for sets with $n + 1$ elements.
This is our induction hypothesis.
=== Induction Step ===
This is our induction step:
Let $X$ have $n + 1$ elements, and let $Y \subseteq X$.
If $Y = X$, there is nothing to prove.
Otherwise, $\exists a \in X \setminus Y$.
This means that $Y$ is actually a subset of $X \setminus \set a$.
Since $X \setminus \set a$ has $n$ elements, it follows that $Y$ is finite.
== Also see ==
* Cardinality of Subset of Finite Set
== Sources ==
* : $\S 10.24$
* : $\S 1.2$
* : $1$: Set Theory and Logic: $\S 6$: Finite Sets: Corollary $6.6$
* : Chapter $3$: The Natural Numbers: $\S 6$ Finite Sets: Exercise $6.1 \ (2)$
Category:Subsets
Category:Finite Sets