To show this proposition holds, I need to assume $\phi$ is a theorem, i.e. there is a derivation where the set of hypothesis is empty and its conclusion is $\phi$. I need to prove $\psi \to \phi$ is a theorem, i.e. there is a derivation where the set of hypothesis is empty and its conclusion is $\psi \to \phi$. Is my understanding correct ? How can I start filling the details of this proof ? P.D.: The book I am using is &quot;Logic and Structure&quot; by Dirk Van Dalen.
7995
Apparently, according to the Conditional Introduction rule, this is valid:     Prove $C \to A$   Source:  Page 5  So before this, the way I viewed the CI rule, was that it allowed us to prove that if we assume the antecedent is true, we can prove the consequent can derived from the antecedent, by referring to the premises which lead to the consequent. If later we find that the antecedent is true, then we can conclude what we already done so before when we just assumed. So basically, sub derivations are inactive at first, but activated if the assumption of said sub derivation is confirmed.  In this example, it's basically stating that the mere assumption of some proposition is enough to state that it applies to some other already proven proposition. It's like you might as well skipped over the sub derivation and said, 'Given $A, C \to A$ because I want it to'.   Personally, I think this is a mistake, though if not, I can't see how you could justify that $C \to A$ given $A$ and assuming $C$ is true alone.
90218
I have no idea about the underlying theory from which the mathematical induction was derived.  How to prove the mathematical induction is true?
22175
Suppose that $X$ is infinite and that $A$ is a finite subset of $X$. Then $X$ and $X \setminus A$ are equinumerous.     My attempt:  Let $|A|=n$. We will prove by induction on n. It's clear that the the theorem is trivially true for $n=0$. Assume the theorem is true for all $n=k$. For $n=k+1$, then $|A \setminus \{a\}|=k$ for some $a \in A$. Thus $X \setminus (A \setminus \{a\}) \sim X$ by inductive hypothesis, or $(X \cap \{a\}) \cup (X \setminus A) \sim X$, or $\{a\} \cup (X \setminus A) \sim X$. We have $\{a\} \cup (X \setminus A) \sim X \setminus A$ since the theorem is true for $n=1$. Hence $X \setminus A \sim \{a\} \cup (X \setminus A) \sim X$. Thus $X \setminus A \sim X$. This completes the proof.       Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!     Update: Here I prove that the theorem is true for $n=1$.  Assume that $A = \{a\}$ and consequently $X \setminus A= X \setminus\{a\}$. It's clear that $|X \setminus A| \le |X|$. Next we prove that $|X| \le |X \setminus A|$. Since $X$ is infinite, there exists $B \subsetneq X$ such that $B \sim X$ (Here we assume Axiom of Countable Choice). Thus $|X|=|B|$. There are only two possible cases.   $a \in X \setminus B$   Then $B \subseteq X \setminus \{a\}=X \setminus A$ and consequently $|X|=|B| \le |X \setminus A|$. Thus $|X| \le |X \setminus A|$ and $|X \setminus A| \le |X|$. By Schröder–Bernstein theorem, we have $|X \setminus A| = |X|$. It follows that $X \setminus A \sim X$.   $a \in B$.   Let $b \in X \setminus B$. We define a bijection $f:X \setminus \{a\} \to X \setminus \{b\}$ by $f(x)= x$ for all $x \in X \setminus \{a,b\}$ and $f(b)=a$. Thus $X \setminus \{a\} \sim X \setminus \{b\}$. Since $b \in X \setminus B$, it follows from Case 1 that $X \setminus \{b\} \sim X$. Hence $X \setminus \{a\} \sim X \setminus \{b\} \sim X$. Thus $X \setminus \{a\} = X \setminus A \sim X$.  To sum up, $X \setminus A \sim X$ for all $|A|=1$.
2650
Theorem. Let $X$ and $Y$ be sets with $X$ nonempty. Then (P) there exists an injection $f:X\rightarrow Y$ if and only if (Q) there exists a surjection $g:Y\rightarrow X$.  For the P $\implies$ Q part, I know you can get a surjection $Y\to X$ by mapping $y$ to $x$ if $y=f(x)$ for some $x\in X$ and mapping $y$ to some arbitrary $\alpha\in X$ if $y\in Y\setminus f(X)$. But I don't know about the Q $\implies$ P part.  Could someone give an elementary proof of the theorem?
76911
So I believe I've finished the proof, but it all amounts to case-work and I really think (and hope) there's a better approach than this. Here's what I've done: Attempt: Within $\text{Aut}_\mathsf{Grp}(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z})$ identities must be mapped to identities thus what defines each isomorphism is the bijective function between its last three elements: \begin{matrix} (0,0) &amp; \mapsto &amp; (0,0) \\ (0,1) &amp; &amp; (0,1) \\(1,0) &amp; &amp; (1,0) \\(1,1) &amp; &amp; (1,1) \\ \end{matrix} If every bijective function between these last three elements constitutes a homomorphism (including the first unchanged mapping of identities), then $\text{Aut}_\mathsf{Grp}(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}) \cong S_3$ in that isomorphisms in $\text{Aut}_\mathsf{Grp}(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z})$ can be identified with permutations of three elements, which is exactly what $S_3$ is. I then, essentially go case-by-case showing every one of the six different bijections is a homomorphism. For two of those bijections (which are just compositions of other bijections I've already checked) I apply the following lemma:  If $\phi :G \to H$ and $\psi : H \to K$ are bijective homomorphisms, then $(\psi \circ \phi)$ is a homomorphism. As proof, assume the premise. We then have $\forall a,b \in G:$ $$\psi (\phi (ab))= \psi(\phi(a) \phi(b))=\psi (\phi(a))\psi (\phi(b))$$ $\implies (\psi \circ \phi)$ is a homomorphism.  So my questions are:  Is the proof that I have sufficient? Is there a better proof for this problem? (A hint towards it rather than complete give-away would be much more appreciated)  EDIT: I have indeed looked at , but the approach carried out there uses vector spaces which I have not been introduced to or am supposed to use to solve this problem.
81416
I know that there is a similar post, but I 'm trying a different proof. I will write $P$  for the set of all positive prime numbers. Question: If $\phi$ is Euler's Phi Function, we want to find all $n \in \mathbb{Z^+}$ such that $\phi(n)=4$. Answer: Let $n=p_1^{n_1}\dotsb p_k^{n_k}\in \mathbb{Z}^+$ be the factorisation of $n$ in to primes. Then $$\phi(n)=p_1^{n_1-1} \dotsb p_k^{n_k-1}(p_1-1) \dotsb (p_k-1)=4.$$ So, for any $i \in \{1,2,\cdots,k\}$ we have $p_i-1|4$. Hence, $$p_i-1\in\{1,2,4\} \iff p_i\in \{2,3,5\} \subset P.$$ Now, we can see the primes that $n$ contains: $n=2^{n_1}3^{n_2}5^{n_3}$, where  $n_1,n_2,n_3 \in \mathbb{Z}^+$. So, \begin{align*} \phi(2^{n_1}3^{n_2}5^{n_3})=4 \iff \phi(2^{n_1})\phi(3^{n_2})\phi(5^{n_3})=4  \tag{*} \end{align*} The possible cases for $n_i$ are:  $n_1=1,2,3\implies \phi(2)=1,\phi(2^2)=2, \phi(2^3)=4$ respectively $n_2=1 \implies \phi(3)=2$ $n_3=1 \implies \phi(5)=4$  All the posible combinations for the relation (*) are $\phi(5)$, $\phi(5)\phi(2)$, $\phi(3)\phi(2^2)$, $\phi(2^3)$. So, $$n \in \{5,10,12,8\}.$$ Is this completely right? Thank you.
99260
So I see that the process for proof by induction is the following (using the following statement for sake of example:  $P(n)$ is the formula for the sum of natural numbers $\leq n$:  $0 + 1 + \cdots +n = (n(n+1))/2$ )   Show that the base case is trivially true: $P(0)$: let $n = 0$. Then $0 = (0(0+1))/2$, which is true. Show that if $P(k)$ holds then $P(k+1)$ also holds. Assume $P(k)$ holds for some unspecified value of $k$. It must be then shown that $P(k+1)$ holds.   This is the part I don't get: 'Assume $P(k)$ holds'  We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesnt seem to hold up to me. Oviously proof by induction works so am I viewing the process incorrectly?
2477
Here is the statement :  Let $E$ a finite $\mathbb{K}$-vectorial space and $\phi_1, \ldots, \phi_p, \psi$ a collection of linear forms on $E$ such that : $\bigcap \limits_{i=1}^p\ker(\phi_i)\subset \ker(\psi)$. Then $\psi \in \operatorname{span}\{\phi_1,\ldots, \phi_p\}$.  The suggestion is to make an induction on $p\ge 1$ (I already know that this method is not the fastest way) : For $p=1$ then $\ker(\phi_1)\subset \ker(\psi)$. If $\phi_1 \equiv 0$ then $\ker(\phi_1)=E$ so $\psi \equiv 0$ and the statement is true. If not, we have the fact that $\phi_1$ and $\psi$ are linearly dependent so $\psi \in \operatorname{span} \{\phi_1\}$ and the statement is also true. Now we want to check the statement for $p+1$. We suppose $\bigcap \limits_{i=1}^{p+1}\ker(\phi_i)\subset \ker(\psi)$ and we want to prove that  $\psi \in \operatorname{span}\{\phi_1,\ldots, \phi_{p+1}\}$. If all the linear forms are null then $\psi \equiv 0$ and the statement is true. If not, we have $\bigcap \limits_{i=1}^{p+1}\ker(\phi_i)\subset \bigcap \limits_{i=1}^p \ker(\phi_i) \subset \ker(\psi)$ so by the induction's hypothesis, $\psi \in \operatorname{span}\{\phi_1,\ldots, \phi_p\}$. Moreover (not sure) $\ker(\phi_{p+1})\subset \ker(\psi)$ so $\psi \in \operatorname{span} \{\phi_{p+1}\}$. Then I'm stuck... Thanks in advance
108605
Let $G$ and $G'$ be groups. Let $\phi: G \to G'$ be a homomorphism. Let $H$ be a group of $G$ and let $H'=\{\phi(h): h\in H\}$.  Want to show that $H'$ is a subgroup.  Proof:  (i)  $H'$ has identity since $\phi(e_G)\in H'$.  This is because $\phi(e_G)=e_{G'}$.  (ii)  $H'$ is closed because of the following: Let $h_{1}^{'}, h_{2}^{'} \in H'$.  Then there exists an $h_1,h_2$ in $H$ such that $h_1^{'}=\phi(h_1)$ and $h_2=\phi(h_{2}^{'})$.  Then $h_1^{'}h_2^{'}=\phi(h_1)\phi(h_2)=\phi(h_1h_2)$.  (iii) For each $h^{'} \in H'$ there exists an $h \in H$ such that $\phi(h)=h'$.  But, $h'^{-1}=\phi(h)^{-1}=\phi(h^{-1})$.  Hence it has inverses.  Did I prove this correctly?
61562
My final for my introductory analysis course is tomorrow and my teacher gave us a list of possible theorems to prove. If anyone could please show me a proof for The Intermediate Value Theorem that is short and easy to follow, so even if I still cannot understand it I can at least memorize it. Also, I have looked through numerous texts and the internet, but they all seem to confuse me. I know that itis an insult to all you math experts to memorize proofs, but I am desperate at this point. Thank you
59190
How to show that when the linear transformation $\Phi =\psi \circ \phi : E \rightarrow G$  (where $\phi : E \rightarrow F$ and $\psi : F \rightarrow G$) is (1) injective, then $\phi$ is injective and when (2) $\Phi$ is surjective, then $\psi$ is also surjective ?  I've tried to prove it by the definition of injection and surjection, but I'm not convinced myself by it.  For example, in the first case :  If $\Phi$ is injective, $\forall g \in G$, we have $0$ or $1$ $e \in E$ such as $\Phi(e)=g$.  $\Rightarrow \Phi(e) = \psi(\phi(e)) = \psi(f) =g$.   So $\forall f \in F$, we also have $0$ or $1$ $e \in E$ such as $\phi(e)=f \in F$.   $\Rightarrow \phi$ is injective.  Is this right or did I prove nothing at all ? I think it is easier to convince myself/ to understand with surjectivity but still..
42816
As the question states, we are to show that $C = \{ f : f \text{ is a function} \}$ is a proper class.  Assume for the sake of contradiction that $C$ is a set. Then consider the class function $\Phi$ which takes as input a function $f$ and spits out the set of inputs to $f$. So if $f : A \to B$ then $\Phi(f) = A$. By replacement schema, $\Phi[C]$ is a set. However, since $\{ S : S \text { is a set} \}$ is not a set, we have a contradiction.  Does this proof make sense?
42854
Please let me know if you find my proof satisfactory.  Let $A\subset B\subset \mathbb{R}^n$, where $\bar{A}$ is the closure of $A$.  If $\vec{x}\in \bar{A}$ then $\vec{x}\in A^\circ$ or $\vec{x}\in ∂A$ (in the boundary of $A$). If $\vec{x}\in A^\circ$ then $\vec{x}\in A \implies \vec{x}\in B\subset \bar{B}$. If $\vec{x} \in ∂A$ then $B_\varepsilon(\vec{x})\cap A\ne \emptyset \ne B_\varepsilon(\vec{x})\cap B$ (for any $\varepsilon &gt; 0$). Thus, since $A\subset B$, $\vec{x}\in B \implies \bar{A}\subset \bar{B}$.
92889
So i have to prove that: $$\{\neg A\to B,A\to C,B\to D\}\vdash \neg C\to D$$ I can use logical axioms, modus ponens and 'metatheorems'.  Logical axioms:   φ→(ψ→φ) (φ→(ψ→χ))→((φ→ψ)→(φ→χ)) (¬φ→¬ψ)→(ψ→φ)   Also i can use modus ponens(the only rule i can use) and metatheorems   Some thoughts:So i started experimenting with all $3$ tools i have, started asking myself is any of the hypotheses can give as something new using the logic axioms but then  i stalled, and modus ponens can't do much on it's own knowing these hypotheses atleast.My next thought was that i have to use those 2 metatheorems in order to actualy prove one part of $\neg C\to D$ (based on metatheorem 2) meaning i use as a hypothesis $\neg C$ to prove $D$ but i am stuck and i don't undestand even how to start.
121041
Given the set of standard axioms (I'm not asking for proof of those), do we know for sure that a proof exists for all unproven theorems? For example, I believe the Goldbach Conjecture is not proven even though we "consider" it true.  Phrased another way, have we proven that if a mathematical statement is true, a proof of it exists? That, therefore, anything that is true can be proven, and anything that cannot be proven is not true? Or, is there a counterexample to that statement?  If it hasn't been proven either way, do we have a strong idea one way or the other? Is it generally thought that some theorems can have no proof, or not?
63331
So I know that if $(a,n)=1$, then $a^{\phi(n)}≡1\pmod{n}$ by Euler's Theorem. I also know that $d \mid a^k$ and obviously $d \mid n$. I know I probably need to use this in the proof, but I just don't know how to get started.
8673
From A Classical Introduction to Modern Number Theory by Ireland and Rosen, page 33:     Corollary 1 (Euler's Theorem). If $(a,m) = 1$, then $a^{\phi(m)} \equiv 1\,(m)$.      Proof. The units in $\mathbb{Z}/m\mathbb{Z}$ form a group of order $\phi(m)$. If $(a,m) = 1$, $\bar{a}$ is a unit. Thus $\bar{a}^{\phi(m)} = \bar{1}$ or $a^{\phi(m)} \equiv 1\,(m)$.   If I'm interpreting this correctly, this proof implicitly uses the fact(?) that if $G$ is a group and $x\in G$, then $x^{|G|}=1$, where $1$ is the identity element of $G$.  If this is indeed true, can someone explain why? (I have had no prior exposure to group theory.)