For questions about the formulation of a proof, not about the mathematics behind it.

learn more… | top users | synonyms

1
vote
1answer
155 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
63 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
40 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
103 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
44 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
31 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
79 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
57 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
70 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. ...
1
vote
7answers
301 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
55 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
59 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
52 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
77 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
81 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
57 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
36 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
46 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
56 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
31 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
49 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
80 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
47 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
46 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
16 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
53 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
33 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
29 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
75 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
3answers
114 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
71 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
126 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
48 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
73 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
40 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
43 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 ...
8
votes
2answers
184 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
83 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.
13
votes
7answers
253 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
69 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
293 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
108 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
57 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
80 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 ...
1
vote
3answers
39 views

Base of the $\mathbb{R}$ vector space that contains all real functions: $f(x) \not= 0$ for finitely many x $\in\mathbb{R}$

I did already prove that this is a vector space. It is easily shown that addition and scalar multiplication with functions that hold the above property again yields a function with $f(x) \not= 0$ for ...
1
vote
1answer
39 views

An equation to prove with terms of Fibonacci sequence

I would like to prove an equation but I have stuck. The equation that is to prove is the below: $f(n)^2 + (-1)^{n+1} = f(n+1)f(n-1) , n \ge 2$. I'm trying to do an inductive proof of this equation. ...
4
votes
2answers
104 views

Theorem 7.2 in General Topology by S. Willard

Theorem 7.2 If $X$ and $Y$ are topological spaces and $f:X \to Y$ , then the following are all equivalent :- I) $f$ is continuous. II) for each E $\subset X$ , $f(\bar E) \subset ...
1
vote
1answer
18 views

Proving that in a complete graph $\lambda(K_{n}) = \delta(K_{n})$

Since $K_{n}$ is n-1 regular. Then $\lambda(G)$ must be n-1. Since $\lambda(K_{n}) \leq \delta(K_{n})$ then by definition they must be equivalent. Can I use the definition or should I say since ...
1
vote
1answer
21 views

Proving that in a complete graph $\kappa(K_{n}) = \delta(K_{n})$

Since $K_{n}$ is n-1 regular. Then $\delta(G)$ must be n-1. Since $\kappa(K_{n}) \leq \delta(K_{n})$ then by definition they must be equivalent. Am I approaching this proof the right way?