nyuuzyou/wikis huggingface dataset:
Index in Subgroup

== Theorem ==
Let $G$ be a group.
Let $H, K$ be subgroups of finite index of $G$.
Then:
:$\index H {H \cap K} \le \index G K$
where $\index G K$ denotes the index of $K$ in $G$.
Equality happens $G = H K$.
== Proof ==
We list out all the left cosets of $H \cap K$ in $H$:
:$H / \paren {H \cap K} = \set {h_n \paren {H \cap K}: h_n \in H, n \in I}$
where $I$ is some finite indexing set.
For each pair $h_i, h_j \in H \subseteq G$, where $i \ne j$:
:$h_i^{-1} h_j \notin H \cap K \quad$ Cosets are Equal iff Product with Inverse in Subgroup
Since $H$ is a subgroup, $h_i^{-1} h_j \in H$.
Thus:
:$h_i^{-1} h_j \notin K$
By Cosets are Equal iff Product with Inverse in Subgroup, $h_i K$ and $h_j K$ are different left cosets.
Hence there must be at least $\index H {H \cap K}$ left cosets of $K$ in $G$, namely $h_n K$ for each $n \in I$.
It follows that $\index H {H \cap K} \le \index G K$.
=== Equality ===
Suppose equality holds.
Then the construction above gives all left cosets of $K$ in $G$.
For any $x \in G$, $x \in h_i K$ for some $h_i \in H$.
Hence $G \subseteq H K$.
The inclusion $H K \subseteq G$ is seen from .
Hence $G = H K$ by definition of set equality.
Now suppose $G = H K$.
To show equality we must show that the construction above gives all left cosets of $K$ in $G$.
Let $g K$ be a left coset of $K$ in $G$, where $x \in G$.
Since $G = H K$:
:$\exists h \in H, k \in K: g = h k$
Then by Left Coset Equals Subgroup iff Element in Subgroup:
:$g K = h \paren {k K} = h K$
Since $h \in H$:
:$\exists i \in I: h \in h_i \paren {H \cap K}$
By Element in Left Coset iff Product with Inverse in Subgroup:
:$h^{-1} h_i \in H \cap K \subseteq K$
Thus by Left Cosets are Equal iff Product with Inverse in Subgroup:
:$h_i K = h K = g K$
Hence all left cosets of $K$ in $G$ are obtained in the construction.
This gives equality.
== Sources ==
* : $\S 3.3$: Group actions and coset decompositions: Exercise $9$
Category:Subgroups
Category:Index of Subgroups
Index is One iff Subgroup equals Group

== Theorem ==
Let $G$ be a group whose identity element is $e$.
Let $H$ be a subgroup of $G$.
Then:
:$\index G H = 1 \iff G = H$
where $\index G H$ denotes the index of $H$ in $G$.
== Proof ==
For finite groups, we can apply Lagrange's Theorem:
:$\index G H = \dfrac {\order G} {\order H}$
But then:
:$\dfrac {\order G} {\order H} = 1 \iff \order G = \order H$
Hence the result.
For the general case (including infinite groups) we need to consider the (left) coset space $G / H$.
Note that we must have $e H = H \in G / H$.
Hence:
:$\index G H = 1 \iff G / H = \set H \iff G = H$
== Sources ==
* : $0$: Some Conventions and some Basic Facts
Category:Order of Groups
Category:Index of Subgroups
Index of Intersection of Subgroups

== Theorem ==
Let $G$ be a group.
Let $H, K$ be subgroups of finite index of $G$.
Then:
:$\index G {H \cap K} \le \index G H \index G K$
where $\index G H$ denotes the index of $H$ in $G$.
Note that here the symbol $\le$ is being used with its meaning less than or equal to.
Equality holds $H K = \set {h k: h \in H, k \in K} = G$.
=== Corollary ===
== Proof ==
Note that $H \cap K$ is a subgroup of $H$.
From Tower Law for Subgroups, we have:
:$\index G {H \cap K} = \index G H \index H {H \cap K}$
From Index in Subgroup, also:
:$\index H {H \cap K} \le \index G K$
Combining these results yields the desired inequality.
Again from Index in Subgroup, it follows that:
:$\index H {H \cap K} = \index G K$
 $H K = G$.
== Sources ==
* : $1$: Subgroups: $1.\text{T}.2$
* : Chapter $2$: Subgroups and Cosets: $\S 39 \beta$
* : $\S 3.3$: Group actions and coset decompositions: Exercise $9$
Category:Subgroups
Category:Index of Subgroups
Category:Set Intersection
Category:Index of Intersection of Subgroups
Index of Intersection of Subgroups/Corollary

== Theorem ==
Let $G$ be a group.
Let $H$ be a subgroup of $G$.
Let $K$ be a subgroup of finite index of $G$.
Then:
:$\index H {H \cap K} \le \index G K$
where $\index G K$ denotes the index of $K$ in $G$.
Note that here the symbol $\le$ is being used with its meaning less than or equal to.
Equality holds $H K = \set {h k: h \in H, k \in K} = G$.
== Proof ==
Note that $H \cap K$ is a subgroup of $H$.
From Index of Intersection of Subgroups, we have:
:$\index G {H \cap K} \le \index G H \index G K$
Setting $G = H$, we have:
:$\index H {H \cap K} \le \index H H \index H K$
== Sources ==
* : $1$: Subgroups: $1.\text{T}.2$
Category:Index of Intersection of Subgroups
Index of Proper Subgroup of Symmetric Group

== Theorem ==
Let $n \in \N$ be a natural number such that $n > 4$.
Let $S_n$ denote the symmetric group on $n$ letters.
Let $A_n$ denote the alternating group on $n$ letters.
$A_n$ is the only proper subgroup of $S_n$ whose index is less than $n$.
== Proof ==
From Normal Subgroup of Symmetric Group on More than 4 Letters is Alternating Group:
:$A_n$ is the only proper non-trivial normal subgroup of $S_n$.
Suppose $H$ is a subgroup of $S_n$ whose index $\index {S_n} H$ is less than $n$.
If $\index {S_n} H = 2$ then from Subgroup of Index 2 is Normal $H$ is normal.
Hence $H = A_n$.
Suppose $\index {S_n} H > 2$.
Then $A_n \nsubseteq H$.
Thus the hypotheses of Isomorphism of Finite Group with Permutations of Quotient with Subgroup are fulfilled.
Thus $S_n$ is isomorphic to a subgroup of the group of permutations $\map \Gamma {S_n / H}$ of $S_n / H$.
However:
which is a contradiction.
== Sources ==
* : Chapter $2$: The Symmetric Groups: $\S 85$
Category:Symmetric Groups
Category:Examples of Subgroups
Index of Refraction of Atmosphere for Radio Waves

== Theorem ==
The index of refraction of the atmosphere of Earth for radio waves of frequency less than $3 \times 10^{10} \, \mathrm {Hz}$ is given by:
:$\paren {n - 1} 10^6 = \dfrac {77 \cdotp 6} t \paren {p + \dfrac {4810 e} t}$
where:
:$n$ denotes the index of refraction of the atmosphere
:$t$ denotes the temperature in kelvin
:$p$ denotes the total atmospheric pressure in millibars
:$e$ denotes the water vapor partial pressure in millibars.
== Sources ==
* : $2$. Physical Constants and Conversion Factors: Table $2.4$ Miscellaneous Conversion Factors
Category:Radio Waves
Index of Square Triangular Number from Preceding

== Theorem ==
Let $T_n$ be the $n$th triangular number.
Let $T_n$ be square.
Then $T_{4 n \paren {n + 1} }$ is also square.
== Proof ==
The product of two squares is also square.
Let $T_n$ be square.
Therefore $T_{4 n \paren {n + 1} }$ is also square.
== Sources ==
* : $15$
* : $15$
Category:Triangular Numbers
Category:Square Numbers
Index of Subgroup equals Index of Conjugate

== Theorem ==
Let $G$ be a group.
Let $H$ be a subgroup of $G$.
Then:
:$\index G H = \index G {a H a^{-1} }$
where $\index G H$ denotes the index of $H$ in $G$.
== Proof ==
== Sources ==
* : Chapter $6$: Cosets: Exercise $9$
Category:Subgroups
Category:Conjugacy
Index of Subsequence not Less than its Index

== Theorem ==
Let $\sequence {x_n}_{n \mathop \ge 1}$ be a sequence in a set $S$.
Let $\sequence {x_{n_r} }$ be a subsequence of $\sequence {x_n}$.
Then:
:$\forall n \in \N_{>0}: n_r \ge r$
== Proof ==
The proof proceeds by induction.
For all $r \in \Z_{\ge 1}$, let $\map P r$ be the proposition:
:$n_r \ge r$
=== Basis for the Induction ===
The first term of $\sequence {x_{n_r} }$ by definition cannot be less than $1$.
That is:
:$n_1 \ge 1$
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$n_k \ge k$
from which it is to be shown that:
:$n_{k + 1} \ge {k + 1}$
=== Induction Step ===
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall r \in \Z_{\ge 1}: n_r \ge r$
== Sources ==
* : $\S 5$: Subsequences: $\S 5.1$: Subsequences
Category:Subsequences
Index of Trivial Subgroup is Cardinality of Group

== Theorem ==
Let $G$ be a group whose identity element is $e$.
Let $\set e$ be the trivial subgroup of $G$.
Then:
:$\index G {\set e} = \order G$
where:
:$\index G {\set e}$ denotes the index of $\set e$ in $G$
:$\order G$ denotes the cardinality of $G$.
== Proof ==
By definition of cardinality and the trivial subgroup:
:$\order {\set e} = 1$
From Lagrange's Theorem:
:$\index G {\set e} = \dfrac {\order G} {\order {\set e} } = \dfrac {\order G} 1 = \order G$
== Sources ==
* : $\S 1.9$
Category:Order of Groups
Category:Index of Subgroups
Indexed Cartesian Space/Examples/Singleton Index

== Example of Indexed Cartesian Space ==
Let $X$ be a set.
Then the indexed Cartesian space $X^{\set 1}$ is defined as:
:$X^{\set 1} = \set 1 \times X$
== Proof ==
== Sources ==
* : $\S 1$: Naive Set Theory: $\S 1.6$: Functions: Exercise $1.6.5$
Category:Examples of Indexed Families
Indexed Cartesian Space is Set of all Mappings

== Theorem ==
Let $I$ be an indexing set.
Let $\ds \prod_{i \mathop \in I} S$ denote the cartesian space of $S$ indexed by $I$.
Then $\ds \prod_{i \mathop \in I} S$ is the set of all mappings from $I$ to $S$, and hence the notation:
:$S^I := \ds \prod_{i \mathop \in I} S$
== Proof ==
Let $\family {S_i}_{i \mathop \in I}$ be an indexed family of sets.
By definition of the Cartesian product of $\family {S_i}_{i \mathop \in I}$:
 
:$(1): \quad \ds \prod_{i \mathop \in I} S_i := \set {f: \paren {f: I \to \bigcup_{i \mathop \in I} S_i} \land \paren {\forall i \in I: \paren {\map f i \in S_i} } }$
where $f$ denotes a mapping.
We have that that:
:$\forall i \in I: S_i = S$
From Set Union is Idempotent:
:$\ds \bigcup_{i \mathop \in I} S = S$
Hence when $S_i = S$ for all $i \in I$, $(1)$ can be written:
:$\ds \prod_{i \mathop \in I} S = \set {f: \paren {f: I \to S} \land \paren {\forall i \in I: \paren {\map f i \in S_i} } }$
which is exactly the definition of $S^I$ towards which we are aiming.
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 10$: Arbitrary Products: Exercise $1$
Category:Cartesian Product
Category:Indexed Families
Indexed Family/Examples/Arbitrary Sets of Students

== Example of Indexed Family ==
Let $S$ be the set of students at a given university.
Let:
:$A_1$ denote the set of first year students
:$A_2$ denote the set of second year students
:$A_3$ denote the set of third year students
:$A_4$ denote the set of fourth year students.
We have:
:$I = \set {1, 2, 3, 4}$ is an indexing set.
Hence $\alpha: I \to S$ is an indexing function on $S$.
Hence:
:$\ds \bigcup_{\alpha \mathop \in I} A_\alpha = $ the set of all undergraduates at the university
and:
:$\ds \bigcap_{\alpha \mathop \in I} A_\alpha = \O$
where $\ds \bigcup_{\alpha \mathop \in I} A_\alpha$ and $\ds \bigcap_{\alpha \mathop \in I} A_\alpha$ denote the union of $\family {A_\alpha}$ and intersection of $\family {A_\alpha}$ respectively.
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 4$: Indexed Families of Sets
Category:Examples of Indexed Families
Indexed Iterated Operation does not Change under Permutation

== Theorem ==
Let $G$ be a commutative semigroup.
Let $a, b \in\Z$ be integers.
Let $\closedint a b$ be the integer interval between $a$ and $b$.
Let $f: \closedint a b \to G$ be a mapping.
Let $\sigma: \closedint a b \to \closedint a b$ be a permutation.
=== Nondegenerate case ===
Let $a \le b$.
Then we have an equality of indexed iterated operations:
:$\ds \prod_{i \mathop = a}^b \map f i = \prod_{i \mathop = a}^b \map f {\map \sigma i}$
=== General case ===
Let $G$ be a commutative monoid.
Then we have an equality of indexed iterated operations:
:$\ds \prod_{i \mathop = a}^b \map f i = \prod_{i \mathop = a}^b \map f {\map \sigma i}$
== Also see ==
=== Special cases ===
* Indexed Summation does not Change under Permutation
Category:Operations
Indexed Summation of Multiple of Mapping

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a, b$ be integers.
Let $\closedint a b$ denote the integer interval between $a$ and $b$.
Let $f: \closedint a b \to \mathbb A$ be a mapping.
Let $\lambda \in \mathbb A$.
Let $g = \lambda \cdot f$ be the product of $f$ with $\lambda$.
Then we have the equality of indexed summations:
:$\ds \sum_{i \mathop = a}^b \map g i = \lambda \cdot \sum_{i \mathop = a}^b \map f i$
== Proof ==
The proof goes by induction on $b$.
=== Basis for the Induction ===
Let $b < a$.
Then all indexed summations are zero.
Because $0 = \lambda \cdot 0$, the result follows.
This is our basis for the induction.
=== Induction Step ===
Let $b \geq a$.
We have:
By the Principle of Mathematical Induction, the proof is complete.
== Also see ==
* Linear Combination of Indexed Summations
* Summation of Multiple of Mapping on Finite Set
* General Distributivity Theorem
Category:Summations
Indexed Summation of Sum of Mappings

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a, b$ be integers.
Let $\closedint a b$ denote the integer interval between $a$ and $b$.
Let $f, g: \closedint a b \to \mathbb A$ be mappings.
Let $h = f + g$ be their pointwise sum.
Then we have the equality of indexed summations:
:$\ds \sum_{i \mathop = a}^b \map h i = \sum_{i \mathop = a}^b \map f i + \sum_{i \mathop = a}^b \map g i$
== Proof ==
The proof proceeds by induction on $b$.
For all $b \in \Z_{\ge 0}$, let $\map P b$ be the proposition:
:$\ds \sum_{i \mathop = a}^b \map h i = \sum_{i \mathop = a}^b \map f i + \sum_{i \mathop = a}^b \map g i$
=== Basis for the Induction ===
Let $b < a$.
Then all indexed summations are zero.
Because $0 = 0 + 0$, the result follows.
=== Basis for the Induction ===
Let $b = a$.
Thus $\map P a$ is seen to hold.
This is our basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P k$ is true, where $k \ge a$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$\ds \sum_{i \mathop = a}^k \map h i = \sum_{i \mathop = a}^k \map f i + \sum_{i \mathop = a}^k \map g i$
from which it is to be shown that:
:$\ds \sum_{i \mathop = a}^{k + 1} \map h i = \sum_{i \mathop = a}^{k + 1} \map f i + \sum_{i \mathop = a}^{k + 1} \map g i$
=== Induction Step ===
We have:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
== Also see ==
* Indexed Summation of Multiple of Mapping
* Summation of Sum of Mappings on Finite Set
Category:Summations
Indexed Summation over Adjacent Intervals

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a, b, c$ be integers.
Let $\closedint a c$ denote the integer interval between $a$ and $c$.
Let $b \in \closedint {a - 1} c$.
Let $f : \closedint a c \to \mathbb A$ be a mapping.
Then we have an equality of indexed summations:
:$\ds \sum_{i \mathop = a}^c \map f i = \sum_{i \mathop = a}^b \map f i + \sum_{i \mathop = b + 1}^c \map f i$
== Proof ==
The proof goes by induction on $b$.
=== Basis for the Induction ===
Let $b = a-1$.
We have:
This is our basis for the induction.
=== Induction Step ===
Let $a \le b \le c$.
We have:
By the Principle of Mathematical Induction, the proof is complete.
== Also see ==
* Sum over Disjoint Union of Finite Sets
Category:Summations
Indexed Summation over Interval of Length One

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a \in \Z$ be an integer.
Let $f: \set a \to \mathbb A$ be a mapping on the singleton $\set a$.
Then the indexed summation:
:$\ds \sum_{i \mathop = a}^a \map f i = \map f a$
== Proof ==
We have:
== Also see ==
* Indexed Summation over Interval of Length Two
* Summation over Singleton Set
Category:Summations
Indexed Summation over Interval of Length Two

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a \in \Z$ be an integer.
Let $f: \set {a, a + 1} \to \mathbb A$ be a real-valued function.
Then the indexed summation:
:$\ds \sum_{i \mathop = a}^{a + 1} \map f i = \map f a + \map f {a + 1}$
== Proof ==
We have:
Category:Summations
Indexed Summation over Translated Interval

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a$ and $b$ be integers.
Let $\closedint a b$ be the integer interval between $a$ and $b$.
Let $f: \closedint a b \to \mathbb A$ be a mapping.
Let $c\in\Z$ be an integer.
Then we have an equality of indexed summations:
:$\ds \sum_{i \mathop = a}^b f(i) = \sum_{i \mathop = a + c}^{b + c} \map f {i - c}$
== Proof ==
The proof goes by induction on $b$.
=== Basis for the Induction ===
Let $b < a$.
Then:
:$b + c < a + c$
Thus both indexed summations are zero.
This is our basis for the induction.
=== Induction Step ===
Let $b \ge a$.
We have:
By the Principle of Mathematical Induction, the proof is complete.
== Also see ==
* Change of Variables in Indexed Summation
Category:Summations
Indexed Summation without First Term

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a$ and $b$ be integers with $a \le b$.
Let $\closedint a b$ be the integer interval between $a$ and $b$.
Let $f: \closedint a b \to \mathbb A$ be a mapping.
Then we have an equality of indexed summations:
:$\ds \sum_{i \mathop = a}^b \map f i = \map f a + \sum_{i \mathop = a + 1}^b \map f {\map \sigma i}$
== Proof ==
The proof goes by induction on $b$.
=== Basis for the Induction ===
Let $b = a$.
We have:
This is our basis for the induction.
=== Induction Step ===
Let $b \ge a + 1$.
We have:
By the Principle of Mathematical Induction, the proof is complete.
== Also see ==
* Indexed Summation over Adjacent Intervals
Category:Summations
Indexed Union Equality

== Theorem ==
Let $A$, $B_x$, and $C_x$ be classes.
Then:
:$\ds \forall x \in A: B_x = C_x \implies \bigcup_{x \mathop \in A} B_x = \bigcup_{x \mathop \in A} C_x$
== Proof ==
Proof follows from Indexed Union Subset and definition of set equality.
Category:Set Union
Indexed Union Subset

== Theorem ==
Let $A$, $B_x$ and $C_x$ be classes.
Then:
:$\ds \forall x \in A: B_x \subseteq C_x \implies \bigcup_{x \mathop \in A} B_x \subseteq \bigcup_{x \mathop \in A} C_x$
== Proof ==
Category:Set Union
Indicator is Well-Defined

== Theorem ==
Let $G$ be a finite group, and $a \in G$.
Let $H$ be a subgroup of $G$.
Then the indicator of $a$ in $H$ is well defined.
== Proof ==
If $a \in H$, then for $n = 1$, $a^n \in H$.
Suppose that $a \notin H$. By Identity of Subgroup, we have that the identity $e$ of $G$ is in $H$.
Moreover, by Element of Finite Group is of Finite Order, there is $n \in \N$ such that $a^n = e \in H$.
Therefore, for any $g \in G$, there is some $n \in \N$ such that $a^n \in H$.
That is, the set of positive integers $n$ such that $a^n \in H$ is non-empty.
So by the Well-Ordering Principle, this set has a least element, and the indicator is well defined.
Category:Subgroups
Indices of Complete Bipartite Graph Commute

== Theorem ==
Let $G = \struct {A \mid B, E} =: K_{m, n}$ be the complete bipartite graph with $m$ vertices in $A$ and $n$ vertices in $B$.
Then:
:$K_{m, n}$ is isomorphic to $K_{n, m}$
for all $m, n \in \N$.
== Proof ==
Let $K_{m, n}$ be represented by the graph $G = \struct {A \mid B, E}$, where $\card A = m$ and $\card B = n$.
Let $K_{n, m}$ be represented by the graph $G' = \struct {A' \mid B', E'}$, where $\card {A'} = n$ and $\card {B'} = m$
Let:
First we note that:
:$\card {\set {A \mid B} } = \card {\set {A' \mid B'} }$
Let us define the isomorphism $\phi: \set {A \mid B} \to \set {A' \mid B'}$ as follows:
:$\forall v \in G: \map \phi v = \begin {cases} b_k' & : v = a_k \\ a_k' & : v = b_k \end {cases}$
It remains to be confirmed that $\phi$ is indeed an isomorphism.
Let $e = \set {u, v} \in E$.
Then:
:$\set {\map \phi u, \map \phi v} = \begin {cases} \set {b_i', a_j'} & : \set {u, v} = \set {a_i, b_j} \\ \set {a_i', b_j'} & : \set {u, v} = \set {b_i, a_j} \end {cases}$
We have that:
demonstrating that $\phi$ is a surjection.
It follows from Cardinality of Codomain of Surjection that $\phi$ is a bijection.
Finally we note that:
:$\forall v' \in G': \map {\phi^{-1} } {v'} = \begin {cases} b_k & : v' = a_k' \\ a_k & : v' = b_k' \end {cases}$
Hence the result, by definition of isomorphism.
Category:Complete Bipartite Graphs
Indirect Proof

== Theorem ==
Let $P$ be a proposition whose truth value is to be proved (either true or false).
An indirect proof has one of the following two argument forms:
=== Reductio ad Absurdum ===
A Reductio ad Absurdum argument for the truth of $P$ is a valid argument which takes as a premise the negation of $P$, and from it deduces a contradiction:
=== Proof by Contradiction ===
A Proof by Contradiction argument for the falsehood of $P$ is a valid argument which takes $P$ as a premise, and from it directly deduces a contradiction:
== Proof ==
For proofs, see:
* Reductio ad Absurdum/Sequent Form
* Proof by Contradiction/Sequent Form
== Also defined as ==
== Sources ==
* : $\text{I}$: 'NOT' and 'IF': $\S 3$
* : $3$: The Method of Deduction: $3.6$: The Rule of Indirect Proof
* : Appendix $\text{A}.5$: Theorems and Proofs
* : $\S 5$: Proof by contradiction
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic
* 
* 
* 
* 
Category:Proof Techniques
Indirect Proof/Also defined as

== Indirect Proof: Also defined as == 
In their handing of Indirect Proof, some sources do not spend much time on explaining the differences between what is defined here on as:
:Proof by Contradiction: Assume the truth of the proposition, derive a contradiction, and hence deduce that the proposition must be false.
:Reductio ad Absurdum: Assume the negation of the proposition, derive a contradiction, and hence deduce that the proposition must have been true after all.
The former is accepted as a valid argument in general universally.
The latter requires the assumption of the Law of Excluded Middle.
== Also see ==
* Definition:Intuitionist School who reject that Law of Excluded Middle: that just because something is not false does not necessarily make it true.
Category:Indirect Proof
Indiscrete Non-Singleton Space is not T0

== Theorem ==
Let $T = \struct {S, \set {\O, S} }$ be an indiscrete topological space which has more than one element.
Then $T$ is not a $T_0$ (Kolmogorov) space.
== Proof ==
Let $a, b \in S$.
By definition of indiscrete space, $S$ is the only open set in $T$ which is non-empty.
So (trivially) there is no open set in $T$ containing $a$ and not $b$, or $b$ and not $a$.
Hence the result, by definition of $T_0$ (Kolmogorov) space.
== Sources ==
* : Part $\text {II}$: Counterexamples: $4$. Indiscrete Topology: $10$
Category:T0 Spaces
Category:Indiscrete Topology
Indiscrete Space is Arc-Connected iff Uncountable

== Theorem ==
Let $T = \struct {S, \set {\O, S} }$ be an indiscrete topological space.
Then $T$ is arc-connected $S$ is an uncountable set.
== Proof ==
Let $T = \struct {S, \set {\O, S} }$ be an indiscrete topological space such that $S$ is uncountable.
Let $a, b \in S$.
Consider an injection $f: \closedint 0 1 \to S$ such that $\map f 0 = a$ and $\map f 1 = b$.
This can always be found because $S$ is itself uncountable.
From Mapping to Indiscrete Space is Continuous, we have that $f$ is ‎continuous.
Thus $T$ is arc-connected.
Now suppose $S$ is an indiscrete topological space which is arc-connected.
Then there exists an injection $f: \closedint 0 1 \to S$ such that $\map f 0 = a$ and $\map f 1 = b$.
This can only exist if $S$ is uncountable.
== Sources ==
* : Part $\text {II}$: Counterexamples: $4$. Indiscrete Topology: $9$
Category:Arc-Connected Spaces
Category:Indiscrete Topology
Category:Uncountable Sets
Indiscrete Space is Connected

== Theorem ==
Let $T = \struct {S, \set {\O, S} }$ be an indiscrete topological space.
Then $T$ is connected.
== Proof ==
We have that an Indiscrete Space is Path-Connected.
Then we have that a Path-Connected Space is Connected.
== Sources ==
* : Part $\text {II}$: Counterexamples: $4$. Indiscrete Topology: $9$
Category:Connected Spaces
Category:Indiscrete Topology