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

-1
votes
2answers
53 views

Proving that $A\cup\emptyset=A$ and $A\cap\emptyset=\emptyset$

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
20 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
86 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
15 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
0answers
26 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 ...
2
votes
3answers
27 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
26 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. ...
3
votes
2answers
66 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
16 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
17 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?
3
votes
3answers
85 views

Prove that if $B$ is similar to $A$, then $B^T$ is similar to $A^T$ .

If two matrix ($A$ and $B$) are similar if there exists an invertible matrix $P$, such that: $$ B=P^{-1} A P $$ I'm thinking if I can prove that $A$, $B$ , $A^T$ and $B^T$ have the same characteristic ...
0
votes
2answers
24 views

Understanding Proof that $\mathbb{R} \setminus A$ is dense. Verify proof.

Here's the proof I was given but with two minor? differences Proposition.- If $A$ is countable then $\mathbb{R} \setminus A $ is dense. Proof: Suppose otherwise, then there exists real numbers $a$ ...
1
vote
0answers
20 views

Developing proof writing and logical skills

What resources can a person turn to in order to develop their proof writing and logical skills? The advanced calculus course I'm taking has made me realize how weak my logic and proof writing skills ...
5
votes
3answers
48 views

If $a\in\mathbb{Q}$, prove that the sequence $\{\sin(n!a\pi)\}_{n=1}^\infty $ has a limit.

This exercise is from Methods of Real Analysis by Richard Goldberg. If $a\in\mathbb{Q}$, prove that the sequence $\{\sin(n!a\pi)\}_{n=1}^\infty$ has a limit. I think this proof relies on the ...
1
vote
2answers
35 views

Understanding line of given proof

I have to understand a set of proofs and I don't understand the reasoning behind this line "This is an injection, if $g(b_1) = g(b_2)$ then $F_{b_1}$ And $F_{b_2}$ intersect, which we shown never ...
0
votes
1answer
26 views

Proof that the sup of a set is the least upper bound.

I have to prove: Assume $s \in \mathbb{R}$ is an upper bound for a set $A \subseteq \mathbb{R}$. Then, $s = \text{sup}A$ if and only if, for every choice of $\varepsilon > 0$, there exists an ...
2
votes
1answer
36 views

Proving $R(3,4)\le 9$

I am trying to prove $R(3,4)\le 9$. This is my approach: For any $K_9$ we have (WLOG) at least 4 red edges by the pigeonhole principle. Consider all of the edges between these 4 red edges, if ...
-1
votes
2answers
18 views

On Closure of Product subset of $\Bbb R×\Bbb R$

Suppose that $\Bbb R×\Bbb R$ has the standard topology. If $S=\left\{(t,\sin{\frac{1}{t}})\mid t\in R\text{ and }t\gt 0\right\}$. Show that $(0,0)$ $\in \overline{S} $
0
votes
2answers
58 views

$\mathbb{R}$ is uncountable with Cantors Diagonal argument (how to improve binary expansion specificity?)

I know it's spelled out more than usual, but this is an introduction to higher math class. If there's any way I can improve this, please let me know. Thank you in advance. Let ...
0
votes
1answer
29 views

Prove that $f^{-1}\left(U_1\times\cdots\times U_\kappa\right)=\bigcap_{i=1}^\kappa \left(f_i\right)^{-1}\left(U_i\right)$

Im working through Bloch's Proofs and Fundamentals and exercise 4.3.11 is Let $B$ be a set, let $A_i,\cdots,A_\kappa$ be sets for some $k\in\mathbb{N}$ be a subset for all ...
0
votes
0answers
69 views

Herbrands Algorithms and greek philospher

So the problem states "outline the steps in Herbrands algorithm leading to the proof that the following statement is right. ...
1
vote
3answers
17 views

Proving continuity with two different metrics

Problem statement: Let $X$ be the set of all continuous functions $f:[a,b]\rightarrow \Bbb R$, and define the metric $d^*(f,g)$ on $X$ by $$d^*(f,g) = \int_{a}^{b} |f(t) - g(t)|dt$$ Now, for each ...
0
votes
3answers
27 views

Let $A$ be a subset of a topological space. Prove that $Cl(A) = Int(A) \cup Bd(A)$

Let $A$ be a subset of a topological space. Prove that $Cl(A) = Int(A) \cup Bd(A)$ Here are my defintions: Closure: Let $(X,\mathfrak T)$ be a topological space and let $ A \subseteq X$ . The ...
25
votes
4answers
1k views

What really is mathematical rigor? How can I be more rigorous?

I'm an undergraduate mathematics student who has received some constructive feedback from two instructors at the end of my exams. Namely, that I am a bit hand-wavey and not always very rigorous. While ...
0
votes
1answer
43 views

Show that if $n$ is fixed, then $\phi(x) = n$ has only a finite number of solutions [on hold]

Where $\phi(x)$ is the number of integers, $1\leq i \leq x$, such that $GCD(i, x) = 1$.
1
vote
1answer
53 views

Question 7F from general topology by Stephen willard?

Can someone help me with 7F from Willard? In part two : $\mathbf{7}$F. Functions to and from the plane. The facts presented here for the plane will be proved in more generality for ...
2
votes
1answer
43 views

Do I write $f\in C^{-n}$ for an integrable function?

I have seen in a variety of texts that an $n$-differentiable function $f$ is written \begin{align} f\in C^{n}\Longleftrightarrow f^{\left(n\right)}\in C,\tag{1} \end{align} such as in Widder's ...
0
votes
0answers
25 views

A manifold with boundary in $\mathbb{R}^{n}$.

I want to show that the cylinder $C = \{ (x,y,z)\in\mathbb{R}^3: x^2 + y^2 = 1, 0 \le z \le 1 \}$ is a differentiable manifold with boundary, of dimension 2, this is: A subset $M \subset ...
0
votes
2answers
21 views

Define $f : X \rightarrow Y$ by $f(x) = y_0$ for every $x \in X$. Then $f$ is $\mathfrak T_1 - \mathfrak T_2$ continuous.

Suppose that $(X, \mathfrak T_1)$ and $(Y, \mathfrak T_2)$ are topological spaces and suppose $y_0 \in Y$. Define $f : X \rightarrow Y$ by $f(x) = y_0$ for every $x \in X$. Then $f$ is $\mathfrak ...
1
vote
1answer
42 views

Show that this is indeed a differentiable manifold with boundary.

I want to show that the cylinder: $$C = \{ (x,y,z)\in\mathbb{R}^3: x^2 + y^2 = 1, 0 \le z \le 1 \}$$ is indeed a a differentiable manifold with boundary, this means the following: A subset $M ...
3
votes
2answers
45 views

Proving UNIT INTERSECTION NP-complete [duplicate]

I am working on some review problems right now and am extremely stuck on how to solve problem - any help would be so appreciated. We are told to consider the following combinatorial problem: Unit ...
3
votes
0answers
67 views
+50

Looking for help to clearly define a function that counts the number of twin primes in a range

My goal is to define a function that counts the number of twin primes between $q$ and $q^2$ where $q$ is any prime greater than $7$. I would like to do this using: The Sieve of Eratosthenes The ...
2
votes
2answers
83 views

Prove ten objects can be divided into two groups that balances each other when placed on the two pans of balance. [on hold]

There are 10 objects with total weight 20, each of the weight being a positive integer. Given that none of the weights exceed 10, prove ten objects can be divided into two groups that balances each ...
0
votes
0answers
26 views

Simple Turing machine problems [duplicate]

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem ...
1
vote
1answer
42 views

Distributing identical objects into distinct boxes

The problem I'm trying to solve is: find the number of ways of distributing $r$ identical objects into $n$ distinct boxes such that no box is empty, where $r \geq n$. I've found conflicting answers ...
1
vote
1answer
37 views

Splitting parties into committees

I feel like this should be an extremely simple problem, but I can't quite figure it out. How many ways are there to split $2n + 1$ places in a committee among $3$ nonempty parties, such that a ...
0
votes
1answer
83 views

Density of Subgraphs

I am stuck trying to make sense of this review problem: Given a graph G(V, E), we say that the induced subgraph G(S) on a subset of vertices S ⊆ V is a subgraph of G whose vertex set is S and edge ...
0
votes
3answers
151 views

Proving prime number combinatorics

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, ...
0
votes
1answer
104 views

Turing Machine recognizability

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem ...
1
vote
1answer
104 views

Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
0
votes
0answers
19 views

Proof of an congruence modulo n [duplicate]

I've the following theorem: For $n\in\Bbb Z$, prove that $n^3\equiv n \pmod{6}$ Please check whether I produced a good proof: 1) Let $k,n\in\Bbb Z$ s.t. $6=kn$ since $n^{3}$ is congruent to $n ...
0
votes
1answer
25 views

Show that the tangent space of a manifold is a certain set.

Let $A\subset \mathbb{R}^n$ an open set, and $g:A\to \mathbb{R}$ continously differentiable such that $g'(x)\not=0 $ for $x\in A$. If $M = g^{-1}(\{0\})\not=\emptyset$, then I want to show that the ...
2
votes
2answers
27 views

If $A$ is a finite set in $(\mathbb R, \mathfrak T_U)$ then $A' = \emptyset$.

If $A$ is a finite set in $(\mathbb R, \mathfrak T_U)$ then $A' = \emptyset$. My knowledge: $\mathfrak T_U$ is the usual topology $A'$ is the set of all limit points and my definition for this is: ...
1
vote
1answer
33 views

Every complete axiomatizable theory is decidable

Enderton (in A Mathematical Introduction to Logic) gives the following theorems: Theorem $17$F : A set of expressions is decidable iff both it and its complement (relative to the set of all ...
1
vote
2answers
31 views

Properties of the deductive closure

Let $\Phi_0$ be the set of $\cal L$-sentences. For $\Gamma\subseteq\Phi_0$, the deductive closure of $\Gamma$ is given by $$\mathsf{Cn}(\Gamma)=\left\{\phi\in\Phi_0\mid\Gamma\vdash\phi\right\}$$ ...
-1
votes
0answers
30 views

How to prove $T(n) = 2*T(\lfloor n/2 \rfloor) + n \quad \text{is}\quad \Omega(n \log n)$?

In CLRS edition 3, this is the question in chapter 4. They have proved that the inequality is $O(n \log n)$ and wants learners to prove that it is also $\Omega(n \log n)$ and thus establish that it is ...
5
votes
3answers
52 views

Show $x^n \geq x_1^n+x_2^n+\ldots+x_k^n \Bigg\vert x_1+x_2+\ldots+x_k = x, x \geq 0, n \geq 1, k\in\mathbb{Z}$

Hello StackExchange Community, This is my first post on the forum. Please forgive me for any errors with formatting and my expressions. I am working on the following proof: Show $$x^n \geq ...
37
votes
9answers
7k views

Is an irrational number odd or even?

My sister just asked this question to me: "Is an irrational number odd or even?" I told her that decimals are not odd or even and that does imply that not recurring and non repeating decimals will ...
1
vote
2answers
17 views

Help with induction step of proving a recursive definition / sequence

I'm a bit of a maths noob so please bear with me with what is probably a really dumb question, but I could really do with some help - I'm self-learning at home. I'm stuck on the question below from ...
0
votes
1answer
23 views

Proof that there is at most one perfect matching in a tree

I'm trying to understand this proof to prove that there is at most one perfect matching in a tree. Let M, M' be perfect matchings in the tree T = (V, E) and consider the graph on V with edge set ...