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
2answers
28 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
34 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
32 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
53 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 ...
39
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 ...
1
vote
5answers
61 views

Suppose that $A$ and $B$ are sets and that $f: A \rightarrow B$ is onto. Does being onto guarantee the sets are finite?

Suppose that $A$ and $B$ are sets and that $f: A \rightarrow B$ is onto. Determine which of the following statements are true: If $A$ is finite then $B$ is finite. If $B$ is finite, ...
0
votes
3answers
21 views

Prove that for any graph G the number of vertices multiplied by the lowest degree is $\le$ the number of edges multiplied by 2

For this proof. I know that number edges is half the sum of the degree sequence since vertices are connected only once. So if the edges are doubled that means, it will definitely be more than the ...
1
vote
1answer
31 views

Prove that if a graph has six vertices, then at least one of G or $\bar{G}$ has a subgraph isomorphic to $K_3$

I think this proof is related to proving to Theorem on friends and strangers which can be proved with the pigeonhole principle. But I am at a loss as to what are the holes and pigeons in this case. I ...
0
votes
2answers
38 views

Proving that there is a unique linear map such that $T(u_i)=v_i$.

I have a problem with understanding of a rather simple concept in linear algebra. I have seen in a book, a following question: Suppose $U,V$ are vector spaces over $K$ and $u_1,\dots,u_n$ is a ...
4
votes
2answers
26 views

Help setting out a proof about the circle $x^{2} + y^{2} + 2gx + 2fy + c = 0$

16. Given that the circle $$x^{2} + y^{2} + 2gx + 2fy + c = 0$$ touches the $y$-axis, prove that $f^{2} = c$. So, because the circle touches the $y$-axis, we know that there is a ...
0
votes
1answer
22 views

For every $A\in \mathcal {P}(U)$ there is a unique $B\in \mathcal{P}(U)$ such that for every $C\in \mathcal{P}(U)$, $C\cap A=C-B$

Pls help me out with the proof: For every $A\in \mathcal {P}(U)$ there is a unique $B\in \mathcal {P}(U)$ such that for every $C\in \mathcal {P}(U), C \cap A=C-B$. For the existence part, we have to ...
8
votes
1answer
56 views

Is there a standard name for this “continuous induction” principle?

I am working on a paper, and I want to prove that some statement $P(x)$ holds for every value of a parameter $x \in [0,\infty)$. I plan to proceed as follows: Show that $P(0)$; Show that if $P(x)$ ...
2
votes
1answer
59 views

Argue that if a sentence has a proof, then it is a tautology

This is a corollary of the soundness theorem, which states that for a set of formulas $\Phi$ (of propositional logic) and a formula $\alpha$ : $$\Phi\vdash\alpha\Longrightarrow\Phi\vDash\alpha$$ What ...
0
votes
1answer
24 views

Let T be a one-to-one linear transformation from $R^m$ to $R^n$ and B={$e_1$,$e_2$,…,$e_m$} a basis for $R^m$.

Prove that the set {T($e_1$),T($e_2$),...,T($e_m$)} is an independent set. Let T : $R^n$ → $R^m$ be a linear transformation. Then there exists a unique matrix A such that T(x) = Ax for all x in ...
2
votes
2answers
31 views

Suppose $\{v_1,v_2,v_3\}$ is a basis for some subspace $V$ of $\mathbb R^m$.

Let $b$ be a vector in that subspace. Prove that if $b$ is orthogonal to all three basis vectors, then b has to be a zero vector. Hint: What is $\|b\|$ I do not know how to start this proof. Thanks ...
7
votes
5answers
74 views

Show that if $g \circ f$ is injective, then so is $f$.

The Problem: Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions. (a) Show that if $g \circ f$ is injective, then so is $f$. (b) If $g \circ f$ is surjective, must $g$ be surjective? ...
3
votes
3answers
57 views

Exhibit a bijective function $\Bbb Z \to \Bbb Z$ with infinitely many orbits

I've the following exercise: Give an example of a bijective function $\Bbb Z\rightarrow\Bbb Z$ with infinitely many orbits. What would be its infinite orbits?
1
vote
1answer
36 views

Injections from a set of functions to R

Show there is an injection from $\Bbb R^2 \to \Bbb R $ Does there exist an injection from $X \to \Bbb R$ where $X $ is the set of all functions where f(x)=x for all but finitely many x. This is a ...
4
votes
3answers
428 views

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$.

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$. I am very new to proofs and not completely sure of how to approach this one. I tried several different ...
1
vote
3answers
66 views

No continuous injective map $f: \mathbb{S}^1 \to \mathbb{R}$ [duplicate]

A friend asked me if there could be a continuous injective map $$f: \mathbb{S}^1 \to \mathbb{R}.$$ My intuition tells me no. Endow $\mathbb{S}^1$ with a topology $\mathscr{T}$ and fix a pole $x ...
-1
votes
3answers
85 views

Prove that $\sqrt{2n}$ is irrational if $n$ is an odd natural number. [closed]

We know that $\sqrt{2}$ is irrational, but how would we go about proving this? I have already attempted to follow the same method of proving this as in the proof of $\sqrt2$ , but I cannot end up ...
1
vote
2answers
105 views

How can I find $(x,y)$ so that $x^y=y^x$, $x\neq y$? [duplicate]

I have found that there are two $(x,y)$ that fulfill the property that $x^y=y^x$, $x\neq y$: $(2,4)$ $(4,2)$ From this: How can I find more, if any? How can I prove that there are no other ...
1
vote
0answers
29 views

Show that if $\lim_{x \to a}f(x)=L$ then $f$ is bounded near $a$.

The Problem: Show that if $\lim_{x \to a}f(x)=L$ then $f$ is bounded near $a$, i.e. there are constants $C,M > 0$ such that $\left|f(x)\right|<M$ for all $x$ such that $\left|x-a\right| < ...
1
vote
2answers
45 views

Combinatorial Proof of falling factorial and binomial theorem

For $n,m,k \in \mathbb{N}$ is true: $$(n+m)^{\underline{k}}=\sum^{k}_{i=0}\binom ki \cdot n^{\underline{k-i}} \cdot m^{\underline{i}}$$ I can prove the binomial theorem for itself combinatorically ...
0
votes
0answers
21 views

Let $(X, \mathfrak T)$ be a topological space and supposed that A is a subset of X. Then $Bd(A) = Cl(A) \cap Cl(X-A)$.

Let $(X, \mathfrak T)$ be a topological space and supposed that A is a subset of X. Then $Bd(A) = Cl(A) \cap Cl(X-A)$. I know this is a true statement. I am trying to prove if because I would also ...
1
vote
2answers
57 views

Josephine problem

So the problem is Suppose there are 2n people in a circle; the first n are “good guys” and the last n are “bad guys.” Show that there is always an integer m (depending on n) such that, if we go ...
1
vote
0answers
28 views

people passing a bridge (a proof for a greedy algorithm)

the problem some people are passing a bridge . each one takes a different time to pass . assume the people are sorted by their passing time increasingly . these are the conditions of passing the ...
1
vote
1answer
53 views

Let $\mathfrak T_X = \{f^{-1} (U) : U \in \mathfrak T_Y\}$ then $\mathfrak T_X$ is a topology on X. False?

Let $f :X \rightarrow Y$ be a function and suppose that $\mathfrak T_Y$ is a topology on $Y$. Let $\mathfrak T_X = \{f^{-1} (U) : U \in \mathfrak T_Y\}$ then $\mathfrak T_X$ is a topology on X. ...
1
vote
4answers
31 views

A={n∈ℤ: 6∣n and 8∣n} and B={n∈ℤ: 48∣n}. Is A⊆B?

A={n∈ℤ: 6∣n and 8∣n} and B={n∈ℤ: 48∣n}. Is A⊆B? Is B⊆A? I'm pretty sure that they are subsets of each other, because any n that 6 and 8 would both divide would have to be divisible by 6*8, but I'm ...
1
vote
3answers
39 views

Prove there exists $m$ and $k$ such that $ n = mk^2$ where $m$ is not a multiple of the square of any prime.

For any positive integer $n$, prove that there exists integers $m$ and $k$ such that: $$n = mk^2 $$ where $m$ is not a multiple of the square of any prime. (For all primes $p$, $p^2$ does not divide ...
2
votes
4answers
31 views

How to show a set of functions is or is not an open set on the sup-metric?

This is an excerpt from my text: The set $G$ of functions $g:\mathbb{R}\rightarrow\mathbb{R}$ such that $|g(x)|\le 1$ for all $x$ is not an open set in the sup-metric space. For instance, consider ...
0
votes
1answer
23 views

Proof of inverse of composite functions

Let $A$, $B$ & $C$ sets, and left $f:A \rightarrow B$ and $g:B \rightarrow C$ be functions. Suppose that $f$ and $g$ have inverses. Prove that $g\circ f$ has an inverse, and that $(g\circ ...
2
votes
1answer
38 views

Verification of Solution for Walter Rudin Principles of Mathematical Analysis Exercise 20, Chapter 3

I have written an answer for the problem 20, chapter 3 of Walter Rudin's Principle of Mathematical Analysis. I think the proof is correct, but since I am new with this kind of proofs, I am skeptical ...
1
vote
0answers
28 views

Finite dense subset implies $X$ finite

Suppose $E \subset X$ is a finite dense subset. Prove that $X$ must also be finite. This is proven quite easily by showing that $\bar{E} = E$ since $E' = \emptyset$, so that $\bar{E} = X$. ...
0
votes
1answer
22 views

Proof of Transitivity

Let R be the following relation of x and y on Z where 3x + y is even. I can seem to get to the form of $3x + z$ when I am doing algebraic manipulations if this equation. I have $3x + y = 2k$ and $3y ...
2
votes
1answer
34 views

Proving consecutive quadratic residue modulo p [duplicate]

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]
1
vote
1answer
44 views

How to prove that $I+A^{T}A$ is invertible [duplicate]

Let $A$ be any $m\times n$ matrix and $I$ be the $n\times n$ identity. Prove that $I+A^{T}A$ is invertible.
1
vote
1answer
65 views

Convergence of a sequence by convergence of sub-subsequence

Suppose that $\{p_n\}_{n \in \mathbb{N}}$ is a sequence in a metric space $X$. Assuming that every subsequence of $\{p_n\}_{n \in \mathbb{N}}$ has itself a subsequence that converges, say, to $p$, ...
1
vote
3answers
41 views

Proving existence of a unique real number

I am working on the following question: For all $x \in \mathbb{R}$, $x \neq 6$, there exists a unique real number $y$ such that $xy+x=6y$. Now I have the existence part. That there exists a ...
0
votes
2answers
14 views

Proof of Injection and Surjection

I am having trouble proving the function f is injective and surjective. $f$ is a function from $\mathbb{Z}\times{Z} \to $\mathbb{Z}\times{Z}$ and $f(x,y) = (5x-y,x+y)$. I know it should be fairly ...
3
votes
2answers
54 views

Understanding a proof conceptually

Let's assume that $V$ and $W$ are vector spaces over a field $\mathbb{K}$, $\lambda\in\mathbb{K}$, $\lambda\neq0$. $S: V\rightarrow W$ and $T: W\rightarrow V$ are linear maps. Prove, that $\lambda$ ...
1
vote
1answer
34 views

Proving Inequality using Induction.

I am trying to prove the following statement: For every nonnegative integer $n$, $1+6n \le 7^n$. I did the base case where $n=0$ but am having trouble manipulating the inductive step. So far I ...
0
votes
2answers
19 views

Let $\text{A}$ be a nonsingular $\textit{n}\times\textit{n}$ matrix, and let $\textit{B}$ be a basis for $\mathbb{R}^n$

Show that $ B_1 = \{\textbf{Av}| \textbf{v} \in B\} $ is also a basis for $\mathbb{R}^n.$ I apologize for my informality, but I would really like some feedback as to whether I am using the correct ...
0
votes
3answers
64 views

If $ f $ is injective and $ g $ is injective, then $ f \circ g $ is surjective. [duplicate]

I can prove that if $ f $ and $ g $ are both injective, then $ f \circ g $ is injective, but I don’t know how to prove that $ f \circ g $ is surjective.
0
votes
1answer
45 views

Let $A = \{1- \frac 1n : n \in \mathbb Z ^+\}$ is closed under certain topologies on $\mathbb R$.

Let $A = \{1 - \frac 1n : n \in \mathbb Z ^+\}$ is closed under certain topologies on $\mathbb R$. I am supposed to figure out if this set is closed under certain topologies. I know that means I ...
0
votes
2answers
21 views

Suppose that $A$ and $B$ are subsets of $X$ such that $A \subseteq B$ then $Int(A) \subseteq Int(B)$.

Let $(X, \mathfrak T)$ be a topological space and suppose that $A$ and $B$ are subsets of $X$ such that $A \subseteq B$ then $Int(A) \subseteq Int(B)$. I know this a true statement so now I need to ...
2
votes
2answers
71 views

Proving $\mathbb{Q} \times \mathbb{Z_2} \ncong \mathbb{Q}$

How do I prove $\mathbb{Q} \times \mathbb{Z_2} \ncong \mathbb{Q}$? I know that they are not isomorphic because for each element in $\mathbb{Q}$, say $\frac{a}{b}$, there are two corresponding elements ...