# Tagged Questions

29 views

### How to go about a “not divisible by..” proof

I need to show the following proof: For any integer x, x^2 + 4 is not divisible by 3. I was trying proof by contraposition, but I do not believe that is the most efficient way to go about this. ...
55 views

64 views

### Proof by contradiction that $B \cap C$ is an empty set

Let $B$ and $C$ be sets such that $$B = \{b \in\mathbb{Z} \mid b = 8n+2 \text{ for some } n\in\mathbb{Z}\}$$ $$C = \{c \in\mathbb{Z} \mid c = 4m \text{ for some } m\in\mathbb{Z}\}$$ Prove by ...
63 views

### How do I use proof by contradiction to prove that for all prime numbers $x$, $y$, and $z$, $x^2 + y^2 \neq z^2$?

Original implication: For all prime numbers $x$, $y$, and $z$, $x^2 + y^2 \neq z^2$. I'm not certain if I'm understanding the process of proof by contradiction correctly. What I am understanding so ...
47 views

### How to define new constants in Tableaux Method of predicate logic

As you all know, in predicate logic when using Tableaux Method the quantifiers must be removed and their variables must be replaced with constants inside the relations and functions. The problem is I ...
66 views

18 views

### Find X so that $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is contradiction

I have to find X so that this $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is a contradiction. Then I also have to find out whether or not I can find an X is a tautology. What's the most ...
70 views

### Proving that rational numbers are dense

I am trying to show that for any real number a, there exist infinitely many rational numbers m/n with $|a - m/n| < 1 /n^{2}$. I've tried to attempt the question by assuming there are finite ...
144 views

### Prove $x^5 + x^4 + x^3 + x^2 + 1 = 0$ has no rational solution

Prove $x^5 + x^4 + x^3 + x^2 + 1 = 0$ has no rational solution I want to prove it by Proof by Contradiction, but I am not sure how to proceed with the proof.
21 views

### Twisted colouring problem

I had doubts in the following similar looking questions I came across:- $Q1.$ The Cartesian plane is coloured with 2 colours. Prove that there exists 3 points of the same colour, which are the ...
84 views

### Proof by contradiction in Discrete Mathematics

Ok, so my college book is the worst book ever and I can only survive from this site and youtube. Could someone please explain the answer below? I really do not understand the answer and to me there is ...
62 views

### Does Gödel's incompleteness theorem contradict itself?

I have problems understanding Gödel's incompleteness theorem. I presume I have a misunderstanding of some phrase or I have to look closer at the meaning of some detail. Gödel's second incompleteness ...
89 views

### Proof by contradiction that if a set $A$ contains $n_0$ and contains $k+1$ whenever it contains $k$, then it contains all numbers $\ge n_0$

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$. I have attempted a proof by contradiction ...
474 views

### Proof by induction or contradiction that $(4k + 3) ^2 - (4k + 3)$ is not divisible by $4$?

I have to prove that $(4k + 3) ^2 - (4k + 3)$ is not divisible by $4$. What would be the best approach for this, proof by induction or contradiction? I've tried both and haven't got very far. Any ...
43 views

### Rectifying Proof

At the moment I read "How to Prove It" by Velleman. I reached & solved the same exercise as in this question: Finding flaw in proof. The exercise was formulated like this and the other asker had ...
152 views

### Real analysis …show if its a rational number

Show $(3+(2\sqrt{2})^\frac{2}{3}$ is not a rational number... My result $x^3-6x^\frac{3}{2}+7=0$ $\{-1,1,-7,7\}$ will not equal to zero .. Is my polynomial acceptable? I used contradiction for ...
79 views

### Is this a valid proof for $1+1=2$? [duplicate]

I am extremely new to proofs, and quite bad at them. In studying and practicing the different types of proofs, I developed this very rough proof that $1+1=2$, one of the simplest mathematical truths I ...
162 views

### Proof by Contradiction on prime numbers [duplicate]

Prove using contradiction that any prime number greater than $3$ is of the form $6n \pm 1$. Thanks for any help
63 views

### Other method show that $A(x)=x^2+x+1=0$ has a zeros in $\mathbb{R}$ but why this contradiction?

Let $A(x)=x^2+x+1$ be a quadratic polynomial equation and $x \in\mathbb{R}$. It is well known that $A(x)=x^2+x+1=0$ hasn't a roots in $\mathbb {R}$ , we choose another way to solve this equation ...
95 views

### Finding flaw in proof

This is one of the problem I have been working on Velleman's How to prove book: Incorrect Theorem. Suppose F and G are families of sets. If ∪F and ∪G are ...
37 views

### Can you use proof by contradiction inside simple induction?

During a proof using simple induction, I assumed P(k) is true. Now in order to show P(k+1) is true using P(k), can I do a proof by contradiction on P(k+1) and say P(k) would be wrong if P(k+1) is ...
29 views

### For every integer m, 2 divides m, and 4 doesn't divide m, there are no integers, x and y that satisfy x^2 + 3y^2 = m.

For every integer m, 2 divides m, and 4 doesn't divide m, there are no integers, x and y that satisfy x^2 + 3y^2 = m. Use a contradiction (assume the negation is true) Is my negation of the ...
674 views

### How to prove that there are infinitely many primes without using contradiction

How can I prove that there are infinitely many primes without using contradiction? I know the proof that is (not) by Euclid saying there are infinitely many primes. It assumes that there is a ...
51 views

### Prove $\forall a,b \in \mathbb{Z}$, $a^2 -4b - 3 \ne 0$ using proof by contradiction

Prove $\forall a,b \in \mathbb{Z}$, $a^2 -4b - 3 \ne 0$ I want to do a proof by Contradiction. I know that this can be figured out using Rational root theorem by subbing in (1, -1, 3, -3), but I am ...
45 views

### Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$

Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$ Is there a way to do this using proof by contradiction without using mod?
42 views

### What means $A \subsetneq X$ with A ~ X? [closed]

How it is possible to have a subset A, which is $\neq$ to X and at the same time they have an equivalence relation ~? When $A \subset X$ therefore a $\in$ A is also a $\in$ X. With A ~ X ...
23 views

$1$. Claim: $\varnothing$ is an antichain. $Proof$: Suppose $\varnothing$ is not an antichain. Then $\exists$ a pair $x, y \in \varnothing$ such that $x$ and $y$ are comparable. Contradiction: ...
49 views

### How do I prove this using proof by contradiction

There is a set a set $S$ of numbers. i.e. $(s_1, s_2, s_3, s_4, s_5, ..., s_n)$. The average of the numbers in the set is $N$. How do I prove that at least one of the numbers in the set is greater ...
184 views

### Understanding the proof of “$\sqrt{2}$ is irrational” by contradiction.

I have some difficulties in understanding the proof of "$\sqrt{2}$is irrational" by contradiction. I am reading it in 10th class(in India) Mathematics book( available online, here ) This is the ...
94 views

### For every $x \in [\frac{\pi}{2},\pi]$, $\sin(x)+\cos(x)\geq 1$. Prove rigorously by contradiction.

For every $x \in [o,\frac{\pi}{2}]$, $\sin(x)+\cos(x)\geq 1$. How do you prove this rigorously by contradiction? I understand you start by assuming that $\sin(x)+ \cos(x)<1$ and prove this is a ...
19 views

### Proof by contradiction how to show is properly

For every $x \in \left[\pi/2,\pi\right]\,,\ \sin\left(x\right) − \cos\left(x\right) \geq 1$. I have drawn the graph and can clearly see that A is true however how do I prove it correctly.
75 views

### prove pigeonhole problem using contradiction

I'm trying to prove this pigeonhole problem: Given that fact that $\lceil x \rceil < x + 1$, give a proof by contradiction that if $n$ items are placed in $m$ boxes then at least one box must ...
### prove by contradicition that there does not exist a constant $c$, such that for all integers $n \geq1$, $(n+1)^2 - n^2 < c$
First thing I did was simplify the above to $2n-1 < c$, from there I changed the simplified expression to $2n-1 \geq c$ and tried to make that contradict with $n \geq 1$. the problem being that I ...