For questions about the writing of proofs. But instead of focusing the mathematics behind the proof, these questions ask about the details and implementation of the proof.

learn more… | top users | synonyms

2
votes
1answer
50 views

What are the requirements for a statement to have a constructive proof?

In general when trying to solve an excersise, or construct a proof, I always find myself looking at what strategy should I take to complete the proof. Many times I try to solve the excercise with a ...
0
votes
1answer
23 views

Prove that a tournament is irreducible if and only if it is strongly connected

If a graph is irreducible, by definition there will be no source or sink and it will be strongly connected. Is my proof above good and how do I prove the converse?
3
votes
1answer
57 views

No truth function that is expressed by a formula that uses only implication and equivalence connectives

I proved the following statement by induction: Let $A$ be a propositional formula which uses only the connectives $→$ and $↔$. Prove (by induction on the complexity of $A$) that if every ...
1
vote
1answer
36 views

If $\vec{v}$ is an eigenvector of $A$, then also $B\vec{v}$, when $AB = BA$ [duplicate]

I have the following problem: Let $V$ be a finite dimensional vector space. Let $A$, $B$ be linear maps of $V$ into itself. Assume that $AB = BA$. Show that if $\vec{v}$ is an eigenvector of $A$, ...
2
votes
1answer
34 views

Differentiability implies continuity - A question about the proof

I have a question, to aid my understanding, about the proof that differentiabiility implies continutity. Differentiability Definition When we say a function is differentiable at $x_0$, we mean that ...
1
vote
1answer
66 views

Proving by induction on the length of a propositional formula?

I'm having a little trouble understanding the following proof question because I'm unsure what defines the 'length' of a propositional formula, I've seen multiple definitions whether it's the number ...
1
vote
2answers
55 views

How to prove the following inequality: $\frac{\sqrt{n + 1}}{\sqrt{n}} - 1 \leq \frac{1}{2n - 1}$

As a part of my practice for an upcoming mid-term, I managed to simplify the following inequality to what you see here: $$\frac{\sqrt{n + 1}}{\sqrt{n}} - 1 \leq \frac{1}{2n - 1}$$ And honestly I'm ...
0
votes
2answers
35 views

How to formally prove that an element belongs to a sequence of sets.

Take any $\delta \in [ \frac{1}{2}, 1)$, I want to show that there always exists an $n$ s.t. $\delta \in [\frac{1}{2}, 1 - \frac{1}{n}) $. Can one obtain an explicit relationship between $\delta$ and ...
4
votes
0answers
71 views

How to Prove It, Exercise 6.5.9

Suppose $R$ is a relation on $A$ and $S$ is the transitive closure of $R$. If $(a, b) \in S$, then there is some positive integer $n$ such that $(a, b) \in R^n$, and therefore by the well-ordering ...
2
votes
0answers
35 views

Clever proofs that prove one identity is equal to another, without going through the original identity?

In a previous question I attempted to formalize the argument of going from one proof of an identity to another, which turned out to be harder than I thought. The thing is, while it may be impossible ...
1
vote
2answers
25 views

Determine the rank of the linear map given by a $n \times n$ matrix , dependend on n. Proof by induction

The task: Let $$ A:= \begin{pmatrix} 1 & a & a & ... & a\\ a & 1 & a & ... &a \\ a & a & ... & a & a\\ ... & ... &... & 1 & a \\ a ...
2
votes
1answer
55 views

Induction implies by well-ordering

A problem in Spivak's Calculus, ch 2-10, asks to prove induction by the well-ordered principle. I have read a number of answers to that question on this site, but I would like to see the proof in a ...
4
votes
1answer
40 views

The set of algebraic numbers is countable: is this proof correct and well written?

Problem: prove that the set of all algebraic numbers is countable. My proof: Let $f: \bigcup^{\infty}_{n=1} \mathbb{Z}^n \rightarrow \mathcal P(\mathbb{C})$ be a function associating an ordered ...
1
vote
1answer
59 views

Did I solve exercise 4.5.4 (b) of 'How to Prove it' by velleman correctly and concisely?

4.5.4 Suppose R is a strict partial order on A. Let S be the reflexive closure of R. (b) Show that if R is a strict total order, then S is a total order. Suppose R is a strict total order. ...
0
votes
7answers
112 views

Prove $ \{(p \lor q) \land (p \implies r) \land (q \implies r) \} \implies r$ is a tautology using logical properties

I spent quite a bit of time on this and have little to no ideas on how to proceed. Using the conditional laws and De Morgan's law, I got to $$( \sim p \land \sim q) \lor (p \land \sim r) \lor(q ...
2
votes
1answer
37 views

what is wrong with this proof? (proving the transitive property of Big O)

So the problem is if $f(n) \in O(g(n))$,and $g(n) \in O(h(n))$ then $f(n) \in O(h(n))$ Assume $f(n) \geq 0, g(n) \geq 0, h(n) \geq 0$ Proof: From assumptions, ...
0
votes
1answer
58 views

Show that A is an open subset of M

If $m\in\mathbb{N}$, $M=\{0,1\}^{\mathbb{N}}$ and $A \subseteq M$ is an open set of sequence where the number 1 appears at least $m$ times. Show that $A$ is an open subset of $M$. I wanted to show ...
2
votes
1answer
45 views

Complex analysis, residues of function

If $f(z)$ has residue $b_1$ at $z=z_0$, show by example that $[f(z)]^2$ need not to have residue $b_1^2$ at $z=z_0$ What I tried Suppose that $f$ is analytics in the neighborhood of $z_0$ and ...
1
vote
1answer
76 views

$\mathbb{A}^2\setminus (0,0)$ is not affine

I want to prove that $X = \mathbb{A}^2\setminus (0,0)$ is not affine. My attempt: If $\Bbbk[X] = \Bbbk[x,y]$ then $X$ is not affine since $(x,y) \subset \Bbbk[x,y]$ is a proper ideal, but $V(x,y) ...
1
vote
1answer
33 views

On existence of square root of positive elements of a unital $C^*$-algebra

Given a unital $\mathcal{C}^*$-algebra $A$ and a positive element $a \in A$, I am trying to prove the existence of a square root $a^{\frac{1}{2}}$ i.e. a positive element $b \in A$ such that $b^2 = ...
0
votes
1answer
50 views

Prove that length of a curve is finite / infinite

I have problems proving the following: Let $\alpha > 0 $. Consider the curve $\gamma : [0,1] \to \mathbb{R}^2$ given by $\gamma (0)=(0,0) , \gamma(t) = (t^\alpha \cos ( \frac {1}{t}), t^\alpha ...
1
vote
1answer
29 views

Converging subsequences and subsets having infinite elements

We have a metric space (V,d). Proof that the following two properties are equivalent. a) Every sequence $a_n \in V$ has a subsequence which converges to a element $x \in V$ b) For every ...
0
votes
1answer
36 views

Proving that a solution exists

Proof that there exists a $x>0$ with $x \in \mathbb{R}$ s.t. $\sin(x) = \frac{x}{2}$ I tried to use the intermediate value theorem, but I don't know how to apply it correctly. Obviously ...
0
votes
4answers
48 views

How can I prove that this matrices statement is false?

How can I prove that this is not true: If for matrices A, B and C, AB=AC and A is not the zeroth matrix, then B=C.
3
votes
1answer
27 views

Characterization of subsets of $\mathbb{R}^n$ of the form $X+Y$

The following comes from the mathematical tripos exam at Cambridge: Let $X,Y \subset \mathbb{R}^n$, and define $X+Y = \{x+y : x \in X, y \in Y\}$ Prove or disprove each of the following: (i) If ...
2
votes
2answers
40 views

Prove using Hilbert calculus $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$, formal proof.

Prove: $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$ Using Hilbert Calculus Format of solution: Step (my understanding) Solution: (1) $\forall x(Px\rightarrow x\equiv a)\vdash ...
3
votes
2answers
71 views

Proving that $\sum_{i=2}^n(5i-4)=\frac{n(5n-3)-2}{2}$ for all $n\geq 1$ by mathematical induction

I have this question: Show, using mathematical induction, that for all natural numbers $n$, $$6 + 11 + 16 + 21 + \cdots + (5n-4) = \frac{n(5n-3)-2}{2}$$ I am confused in that that question states ...
2
votes
4answers
40 views

Does an arbitrary matrix $X \in M_{n \times p}$ have a SVD?

I have proven, as below, that if $X \in M_{n \times n}$ is symmetric, then it has a SVD. $D(\lambda_i) = \text{Diag}(\lambda_i)$ is a diagonal matrix with entries $\lambda_1, \lambda_2, \dots$. ...
2
votes
1answer
40 views

Using lipschitz estimate to show $|f_n(x) - f_p(x) - (f_n(c)-f_p(c))| \leq |b-a|\sup_{y \in (a,b)}|f'_n(y)-f_p'(y)|$

Assume $(f_n)$ is a sequence of functions that are continuous on $[a,b]$ and differentiable on $(a,b)$. Then using Lipschitz estimate to prove that $$|f_n(x) - f_p(x) - (f_n(c)-f_p(c))| \leq ...
5
votes
1answer
33 views

Proof check, showing pointwise convergence

My problem is this: For $x \in [0,\frac{\pi}{2}]$, $f_n(x) = \frac{nx}{1 + n\sin(x)}$ Find the pointwise limit of $(f_n)$ for all $x \in [0, \frac{\pi}{2}]$ I am not sure if the way I constructed ...
0
votes
0answers
15 views

Prove that unitary normal vector to a manifold is $\nabla g / |\nabla g|$ [duplicate]

I want to solve the following exercise: Let $A\subset\mathbb{R}^n$ open $g:A\to\mathbb{R}$ of class $C^{1}$ and $g'(x)\not=0$ in each $x\in A$ then I want to compute $dV$ in the differentiable ...
1
vote
2answers
39 views

Let $V$ be a $K$ - Vector Space, $f: V \rightarrow V$ a linear map. Under some condition, show that $v, f(v),…,f^n(v)$ is linear independent.

Let $V$ be a $K$ - Vector Space, $f: V \rightarrow V$ a linear map. Let $v \in V$. May a number $n ≥ 0$ exist, so that: $f^n(v) \not= 0$ and $ f^{n+1}(v) = 0$. Show that $v, f(v),...,f^n(v)$ is ...
2
votes
1answer
25 views

Prove that if $f$ is an invertible function and $g$ is an inverse, then the codomain of $g$ is equal to the domain of $f$ and vice versa

I am trying to show, without using the bijection properties, what is above. Assume $f$ is an invertible function and $g$ is an inverse of $f$. For $f \circ g $ to be well defined then the image of ...
0
votes
1answer
20 views

Placement of quantifiers in a symbolic statement

I have the statement: Let $A_n$ be an indexed set of numbers defined by $A_n = n\mathbb{Z}_{\geq m}$ for $n,m \in \mathbb{Z}$. Consider the claim C: For all $n$, if $x,y$ is in $A_n$, then ...
1
vote
2answers
44 views

Proving the well ordering principle

THe well ordering principle has that every subset of $\mathbb{Z}^+_0$ has a least element. or if $S$ is a non-empty subset of $\mathbb{Z}^+_0$ and $S = \{a_1, a_2, a_3 ... a_n\}$, then there is a ...
1
vote
2answers
46 views

Proof variance of Geometric Distribution

I have a Geometric Distribution, where the stochastic variable $X$ represents the number of failures before the first success. The distribution function is $P(X=x) = q^x p$ for $x=0,1,2,\ldots$ and ...
1
vote
1answer
55 views

Contradiction proofs

I'm a first year Physics student and I have some trouble approaching Proofs by Contradiction in some of my Math classes. Once I get the first 2 or 3 statements I can finish the proof but a lot of the ...
2
votes
0answers
100 views

Geometric proof for Sophomore's dream

Is there a "visual proof" for sophomore's dream? $$\int_0^1 x^{-x}\,dx = \sum_{n=1}^\infty n^{-n}.$$ In the wikipedia article there are two algebraic proofs, but the integral and the summation has ...
2
votes
1answer
40 views

Why this set is the pole set of $z$?

Suppose $V\subset \mathbb P$ a projective variety, $z$ a rational function on $V$ and let's define $J_z=\{F\in k[X_1,\ldots, K_{n+1}\mid \overline Fz\in \Gamma_h(V)\}$ and $S_z$ the polo set of $z$, ...
2
votes
5answers
49 views

Prove that $X \subset Y \implies f^{-1}(X) \subset f^{-1}(Y)$

Let E and F be two sets and $f: E \to F $ be a function, and $X, Y \subset F$. Prove that $X \subset Y \implies f^{-1}(X) \subset f^{-1}(Y)$ My answer: Let $y \in X$, then $f^{-1}(y) \in ...
2
votes
1answer
32 views

Injection proof

Prove that if f is injective, then $f(A \cap B) = f(A)\cap f(B)$ My answer: i) $f(A \cap B) \subset f(A) \cap f( B )$ Take an $x \in A \cap B$. $x \in A \cap B \implies x \in A \land x \in B$ $x ...
1
vote
1answer
26 views

Prove $\vdash\forall x(\alpha\to\beta)\to(\exists x\alpha\to\exists x\beta)$

I want to show that: $\vdash\forall x(\alpha\to\beta)\to(\exists x\alpha\to\exists x\beta)$ I started my deduction as follows: $\vdash\forall x(\alpha\to\beta)\to(\forall ...
9
votes
2answers
157 views

Proving $\sqrt{2}(a+b+c) \geq \sqrt{1+a^2} + \sqrt{1+b^2} + \sqrt{1+c^2}$

I've been going through some of my notes when I found the following inequality for $a,b,c>0$ and $abc=1$: $$ \begin{equation*} \sqrt{2}(a+b+c) \geq \sqrt{1+a^2} + \sqrt{1+b^2} + \sqrt{1+c^2} ...
-3
votes
3answers
53 views

Prove that for any sets $A$ and $B$ there is a unique set $C$ such that $A ∆ C=B$

Using Venn diagram, I see that letting $C = A ∆ B$ works. But I have trouble proving this using notations. Show me how to do the existence and uniqueness part of this proof.
14
votes
7answers
204 views

What are statements about the natural numbers where induction is impossible or unnecessary to prove?

I'm looking for statements like "for all natural numbers, ____" where induction would be impossible or unnecessarily complicated. This is for pedagogical reasons. When students first learn induction, ...
-2
votes
2answers
65 views

Proving that $A\cup\emptyset=A$ and $A\cap\emptyset=\emptyset$ [closed]

I need to prove that $A\cup\emptyset=A$, and $A\cap\emptyset=\emptyset$. It's seem like it's obvious, yet how can I prove it mathematically?
0
votes
1answer
69 views

The Change-making problem algorithm proof (at the dynamic programming method)

I saw here the algorithm for the "Change-making problem" (at the dynamic programming method). I saw it here: http://www.columbia.edu/~cs2035/courses/csor4231.F07/dynamic.pdf I'm trying to find a ...
1
vote
3answers
105 views

Prove $\frac{1}{n} =\frac{1}{n+1}+\frac{1}{n(n+1)}$ for all integers $n\in\Bbb Z$

I'm pretty sure that we need induction, since it's the format I had to use for previous problems similar to this (it isn't specified that it HAS to be an inductive proof, either, if there is another ...
0
votes
1answer
19 views

If $G$ is a connected graph with $n$ vertices and$ n - 1$ edges then $G$ is a tree, using Induction.

I am still new to proof methods and not sure if this is the correct use of induction. Base case: $n = 1$ has $0$ edges and is a tree. Assume every connected graph with $k$ vertices and $k-1$ edges ...
0
votes
1answer
59 views

Some proofs regarding Stirling numbers

I would like you to help me to prove two proofs correlated with Stirling numbers (the first one includes Stirling numbers of the second kind and the second one I guess Stirling numbers of the second ...