For questions about approaches and techniques for discovering a proof, as opposed to writing it down clearly (which involves (proof-writing)). Should not be used unless the focus is on the technique of the proof instead of the solution.

learn more… | top users | synonyms

1
vote
1answer
90 views

Intuition - Theorem - A group homomorphism preserves normal subgroups - Fraleigh p. 149. Theorem 15.16

p. 128, 129. Theorem 13.12. Let $h$ be a homomorphism of groups $G \to G'$. III. If $S \le G$, then $h[S] \le \color{red}{G'}$. IV. If $S' \le G'$, then $h^{-1}[S'] \le G$. p. 149. ...
3
votes
2answers
43 views

Intuition - Quotient Group of Direct Products - Fraleigh ch. 15

Tried http://www.proofwiki.org/wiki/Quotient_Group_of_Direct_Products Proof on p. 3 and 4 . For the case $n = 2$. Define $h: A_1 \times A_2 \rightarrow \dfrac{A_{1}} {B_{1}} \times \dfrac ...
0
votes
1answer
76 views

Easy Proofs with Functions and Big-O

I have these two questions. I tried answering them, but got them wrong and I don't know how to answer them correctly. This is not homework --- I'd appreciate a solution (at least to one), and an ...
3
votes
1answer
52 views

Compute factor group $\dfrac{\mathbb{Z}_4 \times \mathbb{Z}_6}{\langle(2,3)\rangle}$ - Fraleigh p. 147 Example 15.11

(1.) Why's there a 'great temptation' to set $2 \bmod 4$ and $3 \bmod 6$ to 0? (2.) Why are you authorized to set $2 \bmod 4$ and $3 \bmod 6$ to 0? $2 \bmod 4 \neq 0$ and $3 \bmod 6 \neq 0$, hence ...
3
votes
1answer
56 views

What is $\mathbb{Z}_2 \times \mathbb{Z}_4$ isomorphic to - Fraleigh p. 112 Exercises 11.32e

(e). p. 4 of PDF - $\mathbb{Z}_2 \oplus \mathbb{Z}_4 \not\simeq \mathbb{Z}_8$. Another solution (1.) Why is $\mathbb{Z}_2 \oplus \mathbb{Z}_4$ not cyclic? Is it because of $ \gcd(2, 4) = 2 \neq 1 ...
0
votes
1answer
37 views

Need help proving the following:

Any help at all would be great. Thank you very much. For all $m,n,p \in \mathbb{Z}$, If $p<0$ and $mp<np$ then $n<m$
2
votes
1answer
32 views

Groups Question

Let a and b be elements of a group (G,*). Show that $(a*b)^2 = a^2 * b^2$ iff $a*b = b*a$ I'm trying to prove the iff statement from left to right first. $$\begin{align} (a*b)^2 &= a^2 *b^2 \\ ...
-1
votes
1answer
48 views

If $A$ is nonsingular and $B$ is nonsingular show that $AB$ is nonsingular.

I don't understand how to prove this statement for all cases of $A$ and $B$. Can someone help?
0
votes
1answer
45 views

Group Order and Least Common Multiple

Let $G_1,G_2,...G_n$ be groups. Show that the order of an elements $(a_1,a_2,...a_n)$ $\in$ $G_1 \times G_2 \times ... \times G_n$ is lcm($o(a_1),...,o(a_n))$ I know I need to use the fact that the ...
1
vote
1answer
29 views

Multiplication cannot be obtained from zero, successor, and identity by composition without recursion

The task is to show that multiplication cannot be obtained by zero, successor, or identity functions by composition without using recursion at least twice. I'm primarily confused because it doesn't ...
0
votes
1answer
101 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...
2
votes
5answers
96 views

Prove that $A\setminus (B\setminus C) = (A\setminus B) \cup (A\setminus C^c)$ for sets $A,\ B,\ C$ in some Universal Set $U$.

I'm working on this proof for some students I am tutoring and I've gotten a little stuck. I want to show them how to do a proof in complete, extravagant detail and get them familiar with ''element ...
4
votes
1answer
192 views

Proof not a perfect square

Prove if a and b are odd that a^2+b^2 is not a perfect square. We have been learning proof by contradiction and were told to use the Euclidean Algorithm. I have tried it both as written and by ...
0
votes
1answer
182 views

Abstract algebra, prove that $(a^m)^n$ =$ a^{mn}$

Let $a$ be an element of group $G$. For any integers $m,n \in \mathbb{Z}$ ($m,n$ can be positive and negative). Prove that $(a^{m})^{n}=a^{mn}$, then show that $(a^{-1})^{-1} = a$ by using what we ...
2
votes
4answers
49 views

Proving $U_{\varepsilon}(a)\cap V_{\varepsilon}(b)=\emptyset$

I believe I have the right idea but having trouble formulating a mathematical argument for this proof. Suppose $a,b\in \mathbb{R}, a\neq b$. Show there exists $\varepsilon$-neighborhoods ...
0
votes
2answers
60 views

Consecutive positive integers proof problem

Consider any three consecutive positive integers. Prove that the cube of the largest cannot be the sum of the cubes of the other two. Work: I tried to prove via contradiction. I made three ...
1
vote
2answers
103 views

Simple proof exercise recommendation, with full answers

I apologise for asking this ridiculously simple question, but I may just become unhinged if I don't get the answer. I am quite bad at basic proof strategies, and in order to get some practice at ...
0
votes
3answers
87 views

Prove that there is no rational number solution for an equation.

Prove that there is no rational number solution to the equation $x^2-3x+1=0$. (Note, we do not assume that we know all the solutions of $x^2-3x+1=0$ are given by quadratic formula)
2
votes
1answer
322 views

Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
2
votes
2answers
36 views

Prove that for all integers $n\geq 2, n^3+1>n^2+n$

I am attempting this by induction. Base case $2^3+1 >2^2+2 \implies 8>6,$ which is true. Now the induction step $(n+1)^3+1>(n+1)^2+(n+1),$ which simplifies to $n^3+3n^2+3n+2 > n^2+3n+2.$ ...
3
votes
1answer
61 views

Collapsing a Factor to the identity element - Fraleigh p. 14 Theorem 15.8

p. 146: We should acquire an intuitive feeling for this theorem in terms of $\color{red}{collapsing}$ one of the factors to the identity element. p. 147 15.8 Theorem: $\hat{H} = \{(h, e) ...
0
votes
1answer
53 views

Prove $C(n) = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^{n + 2} - (\frac{1 - \sqrt{5}}{2})^{n + 2})$

Given: $1 + \frac{1 + \sqrt{5}}{2} = (\frac{1 + \sqrt{5}}{2})^{2}$ $1 + \frac{1 - \sqrt{5}}{2} = (\frac{1 - \sqrt{5}}{2})^{2}$ If C(n) is the number of 0/1 strings of length n that do not contain ...
1
vote
1answer
47 views

I don't understand part of a proof

I was reading a proof in my textbook today and couldn't figure out why this is true: $$ nq - mp = nq -mq +mq - mp$$ Any help would be appreciated.
1
vote
2answers
118 views

Proving ${n \choose k}={n \choose n-k}$ using a bijection

Let $S$ be an $n$-order set. Prove by bijection that the number of $k$-order subsets is equal to the number of $(n-k)$-order subsets: $${n \choose k}={n \choose n-k}.$$ Could someone help me ...
1
vote
1answer
54 views

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus?

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus? I've tried to prove it by the definition of term in first-order language. From the definition of term in ...
0
votes
1answer
113 views

If $m < n$ and $p < 0$, then $np < mp.$ [duplicate]

Let $m,n,p$ be integers. If $m < n$ and $p < 0$, then $np < mp.$ So far I have: Let $m,n,p$ be integers. Assume $m < n$ and $p < 0$, that is, $n-m \in \mathbb{N}$ and $-p \in ...
0
votes
2answers
46 views

Need help with a math proof

Any help would be greatly appreciated. Let $m,n,p,q \in \mathbb{Z}$. If $0 < m < n$ and $0 < p < q$ then $mp < nq$.
1
vote
1answer
36 views

Proving Direct Sum

Claim. Let $V$ be a vector space over $F$, and suppose that $W_1$, $W_2$, and $W_3$ are subspaces of $V$ such that $W_1 + W_3 = W_2 + W_3$. Then $W_1 = W_2$. I know that this claim is false, but ...
2
votes
3answers
71 views

Prove $3|n^3$ implies $3|n$

Trying to figure the statement $3|n$ iff $3|n^3$. While proving the forward direction was easy and stuck on the reverse direction. Any ideas?
0
votes
2answers
92 views

Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
0
votes
0answers
47 views

Is it a surjection?

Consider the sequence given by $u_1=2$ and $u_{n+1}=\{\min k: \gcd (k,u_n)>1$ and $k$ has not appread in the sequence before} Show that the this sequence is surjective on $N\setminus \{1\}$ I ...
3
votes
0answers
35 views

Intution, Figure. Negation of Continuity and Uniform Continuity (S.A. pp 117 T4.4.6)

Every time I need negation, I have to write out all the logical symbols to negate manually. I know how to determine these negations myself. But I want to compehend intuition or figure like ...
5
votes
1answer
185 views

Equivalences of continuity, sequential convergence iff limit (S.A. pp 106 t4.2.3, 110 t4.3.2)

1. This post became too long, ergo I moved this here. 2. I questioned anew here. How does $\color{red}{(I) \implies (III)}$? This contradicts $a \le b \not \implies \Leftarrow a < b$. 3. ...
0
votes
1answer
199 views

Show that two disjoint languages are not separable

What is the general method to show that two disjoint languages are not separable? As an example, suppose we have: $A = \{\langle M \rangle : M ( \langle M \rangle )$ halts and says ACCEPT$\}$ $B = ...
1
vote
0answers
43 views

Prove that for all integers, m and n, m +n is an integer

Prove that for all integers, m and n, m +n is an integer This seems deceptively easy. would this work? Let m and n be integers suppose m = 1 and n = 2 so m + n = 1 + 2 since the sum of m + n = 3 ...
1
vote
4answers
26 views

If $a$ and $b$ are odd, prove $\gcd(a,b) = \gcd(\frac {\left| {a-b} \right |} {2}, b)$

Honestly I don't have a strong idea. I don't know where to even begin, I have considered that the $\gcd(a,b)$ is somehow less than $a-b$, but I'm not even sure why that would be the case.. Any help ...
2
votes
4answers
171 views

prove by induction: $3 + 5 + 7 + … + (2n+1) = n(n+2)$

Use the principle of mathematical induction to prove that $$3 + 5 + 7 + ... + (2n+1) = n(n+2)$$ for all n in $\mathbb N$. I have a problem with induction. If anyone can give me a little insight ...
2
votes
4answers
109 views

How to Prove: Let m, n $∈ \mathbb{Z}$. If m $\le$ n $\le$ m then m = n.

Need help proving this. Any help would be greatly appreciated. Thank you! Let m, n $\in$ $\mathbb{Z}$. If m $\le$ n $\le$ m then m = n.
2
votes
3answers
51 views

modular arithmetic proof

Suppose $x$, $y$, and $z$ are integers and $x= 3y^2 -z^2$. Prove that $x\not\equiv1\mod4$. My thoughts: So I am not sure the route that can prove this. I am trying to just use the simple stuff to ...
1
vote
4answers
85 views

Showing $a \le b$ if $a \le b+\varepsilon$, for all $\varepsilon \gt 0$

So I think this is the last problem I have and I'm not thinking I'm doing it properly. Let $a,b$ be real numbers and suppose for all $\varepsilon \gt 0, a \le b+\varepsilon$. Show that $a \le b$. ...
2
votes
1answer
41 views

proving if $0 \le a \le \varepsilon$ for all $\varepsilon \gt 0$ then $a=0$

Suppose $a$ is a real number and we know that $$0 \le a \le \varepsilon$$ for every $\varepsilon \gt 0$. I need to show that $a=0$. The book I am working out of already has shown by contradiction ...
2
votes
2answers
28 views

Prove $ab + ab\overline{c} + bcd = b(a+c)(a+d)$

Do I need to use absorbtion law to prove them? $ab + ab\overline{c} + bcd = b(a+c)(a+d)$ $ab + cd = (a+c)(a+d)(b+c)(b+d)$. For 1), I simplified $ab+ ab\overline{c} + bcd$ into $b(a\overline{c} + ...
3
votes
0answers
117 views

Substitute Proof by Contradiction/Negation with Direct Proof or Proof by Contrapositive

When do proof by contradiction, or by negation, or direct proof, or proof by contrapositive all work equally well? When can any one be chosen as the proof form? I'm interested in a pragmatic answer ...
0
votes
0answers
30 views

Proof of probability distribution satisfying global independence assertions of a Markov network

For a homework problem out of the text Probabilistic Graphical Models (Koller/Friedman, 2009), I've been asked to prove the a theorem that states the following: Let $P$ be a positive distribution. ...
5
votes
1answer
133 views

Find all Pythagorean triples $a<b<c$, where $c=65$.

How can one prove that all the Pythagorean triples satisfying this condition have been found? We are working with positive integers a, b, and c.
5
votes
1answer
267 views

Tricks. If $\{x_n\}$ converges, then Cesaro Mean converges (S.A. pp 50 2.3.11)

Show if $\{x_n\}$ is a convergent sequence, then the sequences given by the averages $\{\dfrac{x_1 + x_2 + ... + x_n}{n}\}$ converges to the same limit. (Not a duplicate) Let $\epsilon>0$ be ...
2
votes
1answer
316 views

Direct proof. Square root function uniformly continuous on $[0, \infty)$ (S.A. pp 119 4.4.8)

(http://math.stanford.edu/~ksound/Math171S10/Hw8Sol_171.pdf) Prove for all $e > 0,$ there exists $d > 0$ : for all $x, y \ge 0$, $|x - y| < d \implies |\sqrt{x} - \sqrt{y}| < e$. (a) ...
0
votes
3answers
60 views

For $x+y+z=0$, if $x$ and $y$ are divisible by some integer $k$, then so is $z$.

If k|x and k|y and x+y+z = 0, then k|z. Here, "k|x" means that $k$ is a divisor of $x$ and $x,y,z,k \in \mathbb{Z}$ What strategy would you employ to prove this?
0
votes
2answers
48 views

How to prove this statement and its negation?

Assuming that you're dealing with real numbers, d ^ 2 = e ^ 2, then d = e Why would it be true? << corrected, it is not true! thanks to posters What is the negation and is it true?