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
votes
0answers
40 views

Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5] [closed]

Define $I_n = \{1, 2, ..., n \} $. Let $A$ be a nonempty set. TFAE : (i) $A$ is finite (ie: a bijection $h:A\rightarrow I_{N}$ exists) or A is countably infinite (ie: a bijection $h:A\rightarrow ...
3
votes
1answer
31 views

Generalized Pythagorean triples construction.

All primitive Pythagorean triples $(a, b, c) : \{ a^2 + b^2 = c^2 \} \wedge \{ a \equiv 0 \pmod{2} \}$ can be expressed in the form:$$\{ a = 2pq, b = p^2 - q^2, c = p^2 + q^2 \}$$ for positive ...
0
votes
1answer
19 views

Proving elementary inequalities with equations

Assume $b > 0,\ d > 0$. Assume: $$ \frac{a}{b} < \frac{c}{d} $$. Prove that: $$ \frac{a}{b} < \frac{a + c}{b + d} < \frac{c}{d} $$. I would like to find an intuitive way to solve ...
0
votes
2answers
45 views

Sum of the eigenvalues

if $V$ is a finite-dimensional vector space and $t \in \mathcal L (V,V) $is such that $t^2 = id_V$ prove that the sum of eigenvalues of t is an integer. I started the prove as such: Let $\lambda_1 ...
1
vote
1answer
48 views

Enquiry to network flow

Could anyone advise me on how to find a feasible flow to the following graph so that the edges $(2,5), (4,5), (6,5),(6,7)$ are saturated? This means, I have to formulate the network flow as a linear ...
1
vote
2answers
44 views

Proof strategy for $(=>)$: If $g \circ f = id_A$, then f onto $\iff$ g 1-1. [Chartrand 3Ed P239 9.72]

For nonempty sets A and B and functions f : A → B and g : B → A, suppose that $g \circ f =$ the identity function on A. $(♦)$ (d) $(=>)$ Assume that $f$ is onto. This means there exist ...
0
votes
1answer
22 views

Proof of simple interest formula

Can someone please prove to me that $I = PRT$, where $P$ is the principal, $R$ is the interest rate, and $T$ is the number of years/time. I have seen $I = P(1+TR) = P+PTR$ which does not equal $PRT$, ...
0
votes
4answers
47 views

Help with a certain proof

For all $x,y \in \mathbb{R} - \{0\}$, $(xy)^{-1}=x^{-1}y^{-1}$. I was wondering how I could solve this.
0
votes
1answer
22 views

Unsure how to solve this proof involving the real numbers

Let $x,y \in \mathbb{R}$ such that $x<y$. Then there exists $z \in \mathbb{R}$ such that $x<z<y$. Any help would be greatly appreciated.
0
votes
3answers
35 views

Let $x,y \in \mathbb{R}_{>0}$. If $x<y$ then $0<1/y<1/x$.

I came across a proof in my textbook and was wondering how to solve it: Let $x,y \in \mathbb{R}_{>0}$. If $x<y$ then $0<1/y<1/x$.
1
vote
1answer
16 views

Help with composite identity functions in discrete mathematics

I am having trouble with the following problem: For nonempty sets $A$ and $B$ and functions $f : A \rightarrow B$ and $g: B \rightarrow A$ suppose that $g \circ f = i_A$, the identity function on ...
1
vote
1answer
57 views

Help with proof that the union of two undirected cycle graphs is a cycle graph (with two edge deletions)

I am seeking advice on how to prove something. Apologies if my terminology is incorrect: I am not a mathematician. Let $G_1$ and $G_2$ be undirected cycle graphs with edges $E_{G1}$ and $E_{G2}$ ...
1
vote
2answers
31 views

Not all ideals are finitely generated

Let $R=\{a_0+a_1X+...+a_nX^n \ | \ a_1,...,a_n \in \mathbb{Q}, a_o \in \mathbb{Z}, n\in \mathbb{Z}_{\geq 0} \}$ and $I=\{a_1X+...+a_nX^n \ | \ a_1,...,a_n \in \mathbb{Q}, n\in \mathbb{Z}^{+} \}.$ ...
0
votes
3answers
29 views

Proof by Contradiction that n is even

Can someone help with this proof? $$P(n): \forall n \in Z, n^2 + 5 $$ is odd implies that n is even. I honestly don't even know where to start. I do know that $n=2k$ is even, and $n=2k + 1$ is odd, ...
0
votes
0answers
25 views

Equal fields and dimension

Let $K \subseteq L$ be fields. Show that K=L if and only if $dim_k L=1$ I know that I will have to show both directions of the implication. I'm very new to the topic of fields so I'm still ...
0
votes
0answers
20 views

Discrete Math identity function proof

Hi I am having trouble with this question: For nonempty sets $A$ and $B$ and functions $f:A\rightarrow B$ and $g:B\rightarrow A$ suppose that $g\circ f=i_A$, the identity function on $A$. How do ...
1
vote
1answer
28 views

Help with identity functions in discrete mathematics

I have trouble with trying to solve the following problem: For nonempty sets $A$ and $B$ and functions $f:A\rightarrow B$ and $g:B\rightarrow A$ suppose that $g\circ f=i_A$, the identity function on ...
-1
votes
3answers
41 views

Proving functions are injective and surjective

I am having trouble with the following problem: For nonempty sets $A$ and $B$ and functions $f:A \rightarrow B$ and $g:B \rightarrow A$ suppose that $g\circ f=i_A$, the identity function of $A$. ...
1
vote
3answers
36 views

Prove that $\sec^2{\theta}=(4xy)/(x+y)^2$ only when $x=y$

Show that the equation below is only possible when $x=y$ $$ \sec^2{\theta}=\frac{4xy}{(x+y)^2}$$ The only way I can think of doing this is by rewriting it as $$ ...
1
vote
4answers
40 views

Proving that a function is bijective

I have trouble figuring out this problem: Prove that the function $f: [0,\infty)\rightarrow[0,\infty)$ defined by $f(x)=\frac{x^2}{2x+1}$ is a bijection. Work: First, I tried to show that $f$ is ...
0
votes
1answer
14 views

Proving Integer Modulo is Well-Defined

I have trouble figuring out this problem: $h: Z_4 \rightarrow Z_6$ by $h([a])=[3a]$ for each $a\in Z$. Prove that h is well-defined thus it is a function and that h is neither injective nor ...
0
votes
3answers
39 views

Proof that $X^C \cap Y^C= \;(X \cup Y)^c$

Proof that if $X \subset S,\; Y\subset S,\;$ then $\;X^C \cap Y^C= \;(X \cup Y)^c:$ It must be shown that the two sets have the same elements, that each element of the set on the left is an element ...
1
vote
2answers
26 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
2
votes
2answers
59 views

Could this linear algebra proof be done without computation?

From page 95 of Hoffman & Kunze's Linear algebra: Let $T$ be the linear operator on $\mathbb{R}^2$ defined by $T(x_1,x_2)=(-x_2,x_1)$ Prove that if $B$ is any ordered basis ...
0
votes
2answers
44 views

assuming the conclusion

A natural deduction proof goes from premmisses to conclusion, and under normal circumstances you will not assume the conclusion. Sometimes you may assume the negation of the conclusion and do some ...
4
votes
1answer
91 views

A tough one: show that this is not differentiable at any point in R

Here's the question: Define $\phi: \ \mathbb{R} \rightarrow \mathbb{R}$ by $$ \phi(x) = \begin{cases}x & 0\leq x\leq\frac{1}{2}\\ 1-x & \frac{1}{2}\leq x\leq 1\end{cases}. $$ And then ...
0
votes
1answer
39 views

show that $f(x,y) =2x^2 + 3y$ is differentiable at $(0,0)$ by finding a linear function T

Here's the question: Prove that $f: \mathbb{R}^2 \rightarrow \mathbb{R}$ defined $f(x,y) = 2x^2 + 3y$ is differentiable at $\begin{bmatrix} 0\\0 \end{bmatrix}$ by producing a linear function T and ...
0
votes
3answers
35 views

What is this problem stating? And how to prove this?

$$\exists! x : A(x) \Rightarrow \exists x : A(x)$$ Assuming that $A(x)$ is an open sentence. I'm new to abstract mathematics and proofs, so I came here to ask for some simplification. Thanks
0
votes
0answers
63 views

Show that the likelihood ratio test can be distributed Chi-Squared

Show that the asymptotic likelihood ratio test statistic, Chi-Square LRT = -2log(Λ), to test H0: μ = μ0 vs. HA: μ ≠ μ0 is truly Chi-Squared (df=1)-distributed for Y1,…,Yn~ N(μ,σ^2) when σ^2 is known ...
0
votes
0answers
14 views

Field Extensions Identities

I'm working on proving some identities but I need some help clarifying the notation and what exactly each statement is saying. Prove the following identities. (a) $K(A) = QF (K[A])$ (b) $R[A_1 ...
1
vote
4answers
68 views

Prove that the set of triples $\{(a,b,c)|a,b,c \in \mathbb{N}\}$ is countable

I have the following question in my textbook: Prove that the set of triples $\{(a,b,c)|a,b,c \in \mathbb{N}\}$ is countable Now I know that $\mathbb{N}$ is countable already, and I have completed a ...
1
vote
1answer
32 views

Divisors of prime factorizations

Let $f,g,h \in F[x]$, with $f(x)$ and $g(x)$ relatively prime. If $f(x)$ divides $h(x)$ and $g(x)$ divides $h(x)$ prove that $f(x)g(x)$ divides $h(x)$. My thoughts: there are certain properties that ...
0
votes
1answer
25 views

Greatest common divisor of ring elements

Consider the ring $\mathbb Q[x]$. (a) Suppose that $a(x) = (x+1)^3(x-1)^4(x+2)$ and $b(x) = (x+1)^2(x+2)^3(x-3)^4$. What is the $\gcd (a(x),b(x))$? (b) Suppose that $c(x) = (x^2-1)^4(x^2+3x+2)$. ...
1
vote
0answers
41 views

If $P=NP$, prove that $L' \in NP$

I think I'm overthinking this problem and need some hints in the right direction. The goal of this question is to show that if $P=NP$ then for every language $L \in NP$ via a polynomial time verifier ...
1
vote
0answers
12 views

Splitting Fields Proof

Let $K\subseteq L$ be fields and $ f \in K[X] \setminus K$. Prove that the following are equivalent. (a) $L$ is a splitting field for $f$ over $K$ (b) $f$ splits over $L$ and $L=K(a_1,\ldots,a_n)$ ...
0
votes
1answer
31 views

Normal Subgroups and Isomorphisms Help

Prove or give a counterexample: If $H, K$ are normal subgroups to $G$ and $G/H$ is isomorphic to $G/K$, then $H$ is isomorphic to $K$. proof: Let $G$ be the Klein-4 Group ($V$), $H = \langle ...
0
votes
2answers
69 views

The concept of $\epsilon - N$ proofs

I just don't understand how to complete $\epsilon - N$ proofs. I don't know what my goal is or why they prove what they do. I have asked two questions on here in the past, but I simply don't 'get it'. ...
1
vote
2answers
22 views

Normal Subgroups Proof Help Abstract

Prove or disprove the following assertion. The set of all nonzero scalars matrices is a normal subgroup of $GL_2(\mathbb{R})$. Proof: Let $I$ be the identity matrix. Consider the scalar matrix $sI$ ...
0
votes
2answers
35 views

Solving Problem by different Method ( non-induction)

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method). I want to find number of solution for $$0 \le ...
1
vote
1answer
31 views

Proving a lower bound for the traveling salesman problem

This link provides a guide for bounding solutions to the traveling salesman problem (TSP). In it, the author gives a lower bound on the optimal cost of any tour. For each vertex $v$ in the problem: ...
0
votes
2answers
42 views

Help with a proof I came across

I came across this in my textbook and was wondering how it could be proven. If $a\mid m$ and $b\mid m$ and $gcd(a,m) = 1$, then $ab\mid m$. It's near some Euclid and Extended Euclid proofs so I ...
0
votes
0answers
27 views

Prove that THEOREMS is NP-complete

I have an essay where I shall explain polynomial time reductions, NP definitions and give an "non-strict" proof that THEOREMS is NP-complete. THEOREMS is the problem of providing mathematical proofs ...
0
votes
1answer
26 views

Proof - Fundamental Theorem of Arithmetic using Euclid's Lemma

Let $n \in Z > 1$. Then the expression for $n$ as the product of $\ge 1$ primes is unique, up to the order in which they appear. From Proofwiki. Suppose $n$ has two prime factorizations: ...
1
vote
2answers
22 views

Proof of Conjugate Subgroup Isomorphism

Let $G$ be a group, and let $H$ be a subgroup of $G$. Prove that if $a$ is an element of $G$, then the subset $aHa^{-1} = \{g ∈ G | g = aha^-1 \text{ for some } h \in H\}$ is a subgroup of $G$ that is ...
0
votes
1answer
27 views

Prove language is in $NP$ without using a reduction

I've been stuck on this question for hours, can't seem to figure this out. $L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and ...
0
votes
2answers
35 views

Planar complete tripartite graphs

For which values of $r$, $s$, and $t$ is the complete tripartite graph $K_{r,s,t}$ planar? Obviously I want to look for either a $K_5$ or a $K_{3,3}$ in order to show that a specific graph is ...
0
votes
0answers
10 views

Preservation of a map

There is a map from Z(mod12) to Z(mod4) defined by f(x)=3x. The thought I had was this. Say you have [a],[b] that are in Z(mod12). Would f([a][b])=f([a])f([b])? So you basically view this as a ...
0
votes
2answers
34 views

Proof over subsets

So I'm currently taking a course for proofs, could you please check my work? Prove if $B \subseteq C$ then $A \cup C^c$ is a subset of $A \cup B^c$. For all $x \in B$, $x$ will be an element of $C$. ...
0
votes
1answer
47 views

Combinatorial proofs - how?

I'm suppose to proof the following with combinatorial proofs. 1)$$\sum_{i=0}^{n} {a+i \choose i} = {a+n+1 \choose n}$$ 2)$$\sum_{i=0}^{n} i{n \choose i} = n2^{n-1}$$ 3)$$\sum_{i=0}^{n} {n \choose ...
1
vote
2answers
23 views

A question on Noetherian $R$ -module. [duplicate]

Let $M$ be Noetherian $R$-module(where $R$ contains $1$) and $\phi:M \to M$ be $R$ -module homomorphism . Suppose $\phi$ is surjective, how do I show that $\phi$ is injective ? Hints will suffice, ...