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

learn more… | top users | synonyms

45
votes
9answers
9k 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
58 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
63 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
85 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
72 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 ...
2
votes
1answer
84 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
45 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
43 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
33 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 ...
9
votes
1answer
131 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
85 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
32 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
41 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
179 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
62 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
46 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
475 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
151 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
vote
2answers
167 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
1answer
34 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
137 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
50 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
281 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
77 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
70 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
57 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
38 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
371 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
273 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
52 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
24 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
143 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
55 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
110 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
76 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
23 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
58 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
46 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
21 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
131 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.
1
vote
1answer
67 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
145 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
75 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 ...
0
votes
2answers
55 views

proving a system with $A\vec{x} = \vec{0}=A^k\vec{x} $

The question: "Let $A\vec{x} = \vec{0}$ be a homogeneous system of $n$ linear equations in $n$ unknowns that has only the trivial solution. Show that if $k$ is any positive integer, then the ...
0
votes
1answer
30 views

Let $(X,\mathfrak T)$ be a topological space and suppose that A and B are subsets of X such that $A \subseteq B$ then $Cl(A) \subseteq Cl(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 $Cl(A) \subseteq Cl(B)$. My definition of closure is "Let $(X, \mathfrak T)$ be ...
0
votes
1answer
68 views

Let $(X, \mathfrak T)$ be a topological space and suppose that $A$ is a subset of $X$. If $Bd(A) = \emptyset$ then A =∅ or $A = X$ .

Let $(X, \mathfrak T)$ be a topological space and suppose that $A$ is a subset of $X$. If $Bd(A) = \emptyset$ then $A = \emptyset$ or $A = X$. I am studying introduction to proofs and we have learned ...
2
votes
1answer
32 views

Prove that $A\subseteq B$ if and only if $A^{C}\cup B=\mathscr{U}$

Prove that $A\subseteq B$ if and only if $A^{C}\cup B=\mathscr{U}$. I know we have to show that: if $A\subseteq B$ then $A^{C}\cup B=\mathscr{U}$ if $A^{C}\cup B=\mathscr{U}$ then $A\subseteq ...
2
votes
2answers
240 views

Help with factorial inequality induction proof: $3^n + n! \le (n+3)!$

So I'm asked to prove $3^n + n! \le (n+3)!$, $\forall \ n \in \mathbb N$ by induction. However I'm getting stuck in the induction step. What I have is: (n=1) $3^{(1)} + (1)! = 4$ and $((1) + 3)! = ...
2
votes
2answers
70 views

Is it ok to do this change of variable in integration: let $x = x - 1$

In integrals like $\int \sqrt{x-1}\,dx$, is it ok to make this change of variable in integration: "let $x = x - 1$"? It looks sketchy — like saying, let 5 = 4.