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

learn more… | top users | synonyms

21
votes
7answers
2k views

Can you use both sides of an equation to prove equality?

For example: $\color{red}{\text{Show that}}$$$\color{red}{\frac{4\cos(2x)}{1+\cos(2x)}=4-2\sec^2(x)}$$ In high school my maths teacher told me To prove ...
3
votes
1answer
20 views

Prove $O(f(n)+g(n)) = O(f(n))$ when $g(n)=O(f(n))$

Given $g(n) = O(f (n))$, how can I prove that the following expression is true: $O(f (n) + g(n)) = O(f (n)) \tag1$ So I just write down what it says: $g(n) = O(f (n)) <=> f(n) \le c_1 ...
2
votes
1answer
34 views

Show that for propositional logic $\vdash_i \neg \varphi \Leftrightarrow \vdash_c \neg \varphi$.

As the title says, where $\vdash_i$ is derivations in Intuitionistic logic and $\vdash_c$ is derivations in Classical logic. I am allowed to use a corollary that states that $\vdash_i \varphi ...
0
votes
0answers
14 views

$\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ iif it exists $j\in\{1,…,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$

Show a vector $\vec c$ exists such that $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ if and only if it exists $j\in\{1,...,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$ I'm only asking for a ...
1
vote
1answer
69 views

Correct process for proof in graph theory.

I'm working on what I'm sure is a fairly basic proof in graph theory. I must prove that $Every$ $graph$ $G$ $contains$ $a$ $path$ $with$ $\delta(G)$ $edges$. $\delta(G)$ is the minimum degree of the ...
2
votes
2answers
29 views

Can$A \cap (B' \cap C')$ be $(A \cap B') \cap (A \cap C')$?

If I use the above statement, provided that it is right, in a question, would I have to prove it as well?
1
vote
2answers
24 views

How to show that countable union of $F_\sigma$ is $F_\sigma$

On https://www.physicsforums.com/threads/countable-intersection-of-f-sigma-sets.666055/ Is it claimed that it is obvious that countable union of $F_\sigma$ is $F_\sigma$ Can someone elaborate why ...
0
votes
1answer
25 views

Proof formalization help: Given a vector $u$ in $\mathbb{R}^3$ and a compact 2 dimensional manifold $m$, $u$ is normal to the $m$ at 2 points.

Proof formalization help: Given a vector $u$ of Euclidean length $1$ in $\mathbb{R}^3$ and a compact 2 dimensional manifold $m$, $u$ is normal to the $m$ at at least 2 points. I've thought about the ...
1
vote
3answers
27 views

Proving a basis in linear algebra

So at the moment I'm trying to go through proofs and I came across this one: Suppose $ P_n $ is the vector space of all polynomials with degree less than or equal to n. Prove that $ \{1, x − 1, ...
0
votes
1answer
60 views

What kind of proof is this?

Let's say that we want to prove that object A is blue. Is the following reasoning true? First assume that $A$ is indeed blue. Then, use other axioms to show that depending on a control parameter ...
0
votes
0answers
26 views

Proving a basis and dimension

Hi I'm currently looking at proofs in linear algebra and came across this one and I'm compketely baffled Suppose $ C_{ij} $ is the $2\times3$ matrix with $1$ in the $ i,j^{th} $ entry and zero ...
0
votes
1answer
25 views

How to use monotone convergence theorem to show that $\int \sum |f_n| = \sum \int |f_n|$

In https://math.la.asu.edu/~quigg/teach/courses/473/2009/lectures/11integral.pdf, pg 4 The monotone convergence theorem was used to state $$\int \sum |f_n| = \sum \int |f_n|$$ without proof. Can ...
2
votes
1answer
24 views

How to show that all sequentially compact spaces are bounded?

I want to show given a sequentially compact subset $A \subseteq M \implies A$ is bounded. I read this Every sequentially compact set is closed and bounded. but the proof is poorly written and jumpy ...
0
votes
1answer
24 views

Clean proof for showing $f^{-1}([a,\infty))$ measurable implies $f^{-1}([a,b))$ measurable

I wish to show that for $f:\mathbb{R} \to \mathbb{R}$, $f^{-1}([a,\infty))$ measurable implies $f^{-1}([a,b))$ measurable Looks fairly easy if $f^{-1}([a,b))$ is one piece. Suppose ...
-5
votes
2answers
142 views
+400

How many ways are there to prove Cayley-Hamilton Theorem?

I see many proofs for Cayley-Hamilton Theorem in textbooks and net, so I want to know how many proofs are there for this important and applicable theorem.
0
votes
2answers
37 views

How to prove that the square matrix $A_{n}$ matrix is nilpotent such that $A^{(n-1)}=0$

The matrix A looks like this: $$A=\begin{bmatrix} 0 & 1 & 0 & 0 & .&.&. &0\\ 0 & 0 & 2 & 0 & .&.&. &0\\ 0 & 0 & 0 & 3 ...
18
votes
1answer
776 views

Is there such a thing as a mathematical thesaurus?

I want this for two reasons: When writing proofs, I am constantly in need of synonyms of basic words like thus, there exists, for all, such as, contains, etc. A lot of mathematical concepts have ...
0
votes
1answer
28 views

Verifying multiplicative inverses of modulo n are the elements that are relatively prime to n

A proposition in my book states: $(\mathbb{Z}/n\mathbb{Z})^{\times} = \{a \in \mathbb{Z}/n\mathbb{Z}~|(a,n) = 1\}$ which I want to prove. I start by defining $a$ in terms of prime factors $$a = ...
0
votes
2answers
489 views

Prove that the order of $U(n)$ is even when $n>2$.

I'm trying to provide a solution to the following claim: "The order of $U(n)$ is even when $n>2$." Note: here, $U(n)$ is the set of all positive elements that are less than and relatively prime ...
5
votes
2answers
72 views

Proof using induction: $n! > n^2$, for $n\geq4$

Proof using induction: $n! > n^2$, for $n\geq4$ Basis: For n = 4, we have: $4! > 4^2$ $24 > 16$ (TRUE) Inductive step: By the induction hypothesis: $k! > k^2$ $(k+1)k! > (k+1)k^2$ ...
2
votes
3answers
43 views

Proof help: Prove that $x^2+y^2+z^2 \geq xy+xz+yz$ [duplicate]

$x^2+y^2+z^2 \geq xy+xz+yz $ for all real numbers, x, y, and z. I'm not very good with working inequality proofs. Can someone help me prove this? The technique doesn't really matter.
0
votes
0answers
18 views

Existence of convergent sequence in a closed set?

Is it true that if $C$ is a closed set, and $x \in {C}$ then there exist a sequence $\{x_i\}$ which tends to $x$? I'm not sure about the correctness of this statement, and whether it is true for ...
1
vote
0answers
52 views

I did not understand one thing in the proof of substitution lemma?

The substitution lemma in lambda-calculus is proved by the following way, but I just did not understand the application of induction hypothesis in it. The lemma as shown below, where x and y are ...
0
votes
3answers
44 views

Prove that graph with odd number of odd degree vertices does not exist

I need to prove that it is impossible to have a graph in which there are an odd number of odd degree vertices. What is the easiest way to formally prove this? I feel that I can prove it just by ...
0
votes
1answer
31 views

Prove that if A and B are sets such that $A \cup B \neq \emptyset$, then $A \neq \emptyset$ or $B \neq \emptyset$

Prove that if A and B are sets such that $A \cup B \neq \emptyset$, then $A \neq \emptyset$ or $B \neq \emptyset$. It was suggested to me that the easiest way to approach this was with a proof by ...
-5
votes
3answers
96 views

Prove that $3^x$ divides $(3x)!\,\,\,\, \forall x \ge 1$ [closed]

Prove that $3^x$ divides $(3x)!\,\,\,\, \forall x \ge 1$ For example, $3$ divides $6 = 3!$
-5
votes
0answers
24 views

Proof by induction of for the cardinality of finite sets A and B [closed]

Can someone please help me with this proof? Proof by induction that for finite sets, A and B, an injection $f: A \rightarrow B$ exists if and only if A is finite and $|A| \le |B|$.
2
votes
2answers
25 views

Proof outer measure satisfies monotonicity: $A \subseteq B \implies m^*(A) \leq m^*(B)$

Theorem: $$A \subseteq B \implies m^*(A) \leq m^*(B)$$ Proof Attempt: By definition, $m^*(B) = \inf\{\sum\limits_{k=1}^\infty |J_k||\{J_k\} \text{ is a cover of B }\}$, $m^*(A) = ...
0
votes
2answers
30 views

Moments of a continuous random variable (Exercise 4.3.3 from Grimmett and Stirzaker)

Let $X$ be a non-negative random variable with density function $f$. Show that $$ E(X^r) = \int_0^\infty r x^{r-1} P(X > r)\,dx. $$ I tried using integration by parts to obtain \begin{align} ...
0
votes
0answers
17 views

Suppose G and G' are isomorphic and G has m vertices of degree k. Prove that G' has m vertices of degree k

Suppose G and G' are isomorphic and G has m vertices of degree k. Prove that G' has m vertices of degree k. I don't know how to start this one
5
votes
1answer
88 views

Is my proof correct? If $f$ has a finite number of discontinuities on $[a, b]$, then it is integrable on $[a, b]$

Question: Suppose a function $f(x)$ over the interval $[a, b]$ is bounded and has only a finite number of discontinuous points on $[a, b]$. I intend to prove that it must be integrable on $[a, b]$. ...
1
vote
1answer
25 views

Need help understanding algebra steps taken in proof of why an even minus an odd is odd

I don't understand the algebra used in the below example proof from my textbook. Where does the + 1 come from? Is it okay to just add 1 anywhere you want? Or is there some rule here or reason you ...
15
votes
3answers
611 views

Papers with unorthodox writing style

I'm not sure if this is the right forum for this question, in any case probably CW is appropriate? I've been looking around the mathblogosphere for the past few weeks and ran into mathgen. It's ...
0
votes
1answer
26 views

Proof of Interceting Lines

I have this practice problem from a final exam study guide. Let $f,g$ be continuous on $[a,b]$ and $f(a)>g(a)$ but $g(b)>f(b)$. Prove that $\exists c \in [a,b]$ such that $f(c)=g(c)$. My ...
2
votes
2answers
2k views

Is my proof correct? 'let a,b​​∈ Z. We write A | B if A divides B. Is the relation |, symmetric, transitive and/or reflexive?'

The relationship is not symmetrical. When a relationship is symmetrical: if xRy implies yRx for all x, y ∈ A (where A is a non-empty set, and R is a relation in A) If a, b ​​∈ Z, and as a | b means ...
1
vote
1answer
29 views

How to verify this relationship between area under the graph and the preimage?

Define $h : \mathbb{R} \to [0, \infty)$, Let $H = \{(x,y)| 0 \leq y \leq h(x)\}$ be the area under the graph (including the boundary) I wish to show the following is true: $$H = ...
2
votes
0answers
35 views

Simple Vacuous Proof, Correct Approach?

I am doing some practice exercises as I am starting out on proofs but I noticed that though I am getting the correct approach between vacuous and trivial proofs, I am not doing it in the same format ...
1
vote
1answer
16 views

How does one consider what a graph looks like in a mathematical proof

Mostly I am wondering for example what it would be like to prove that a linear graph (negative slope) shifted right would look the same as one shifted up. Can you consider how a graph looks when ...
2
votes
1answer
164 views

Show that boundary of a closed set is nowhere dense

Let $H$ be a closed set then, $Cl(H) =H$ and hence the $\partial H \subset H$. Now to show that the boundary is nowhere dense, it would suffice to show that $Int(Cl(\partial H)) =\emptyset$, i.e., ...
0
votes
1answer
768 views

Disjunctive normal form (BOTH dnf and cnf) example help

T or ( not x and y ) or ( x and y ) In class we went over examples of how many things can be both DNF and CNF... eg. (not z) or y can be thought of as both (not z) or y .... dnf ((not z) or ...
2
votes
0answers
39 views

When is it appropriate to write “Then it follows”

I am reading a proof, and before the proof fully finishes, the author writes "Then it follows [the statement we are trying to prove] is true" I have been spending the last three hours justifying the ...
0
votes
2answers
667 views

Proving the Division Algorithm using induction

Let $n \in \mathbb{N}$. For every $m \in \mathbb{Z}$, there exist unique $q, r \in \mathbb{Z}$ such that $ m = qn+r$ and $0 \le r \le n-1$. We call $q$ the quotient and $r$ the remainder when dividing ...
1
vote
0answers
32 views

Why is this proof that a circular cone is not a surface not rigorous?

In example $4.1.5$, page $73$ of Pressley's Elementary Differential Geometry, a "heuristic" argument is given to prove that the circular cone with vertex the origin and angle $\pi/4$, is not a ...
0
votes
1answer
164 views

Barendregt's Substitution Lemma (lambda calculus)

I am struggling to put words on an idea used in Barendregt's Substitution Lemma's proof. (available here) The lemma states that: If x≠y and x not free in L and M, L are $\lambda$-terms: then ...
0
votes
0answers
25 views

Real Analysis Theorems - Help with this proof

I am having problems trying to prove the following. Given a set A = {(n,1) / n Natural and n < 6} and given F: R*R -> R, a function that belongs to C1 class and F(P) = 0 for any P inside A. I need ...
20
votes
5answers
989 views

How many faces of a solid can one “see”?

What is the maximum number of faces of totally convex solid that one can "see" from a point? ...and, more importantly, how can I ask this question better? (I'm a college student with little ...
36
votes
11answers
6k views

How can you prove that the square root of two is irrational?

I have read a few proofs that $\sqrt{2}$ is irrational. I have never, however, been able to really grasp what they were talking about. Is there a simplified proof that $\sqrt{2}$ is irrational?
0
votes
1answer
13 views

Prove that multiplication by an integer $a$ that is relatively prime to $n$ defines a bijection from $\mathbb{Z}_n-\{0\}$ to itself

If gcd$(a,n)=1$, then multiplication by $a$ defines a bijection from $\mathbb{Z}_n-\{0\}$ to itself. My working: If $n=p$ a prime, then we can use the Fermat's Little Theorem. If $n$ is not prime in ...
0
votes
1answer
11 views

Show that monotonicity implies positive definiteness of the Jacobian

Given $f: \mathbb{R}^n \to \mathbb{R}^n$, $f$ differentiable, $x,y, p \in \mathbb{R}^n$, show that $(x-y)^T(f(x) - f(y)) \geq 0 \Leftrightarrow p^TDf(x)p \geq 0, \forall p \in \mathbb{R}^n$ This ...
1
vote
0answers
31 views

Should this be rephrased into saying no common factors but 1?

This is from Discrete Mathematics and its Applications Example Prove that $\sqrt{2}$ is irrational by giving a proof by contradiction. Solution Let $p$ be the proposition "$\sqrt{2}$ is ...