# Tagged Questions

1k views

### There exist no integers for which $x^2-4y=2$

I am working on a new exercise in my textbook: $$\text{Prove that: (P): }\;\nexists \;x,y \in \mathbb{Z}, x^2-4\cdot y = 2$$ I am stuck and I would really like to see a correct proof so I can move ...
52 views

### How to prove that for all $x$ there exists some $y$ where $(x^2 + y^2 \geq 0)$?

How can I prove that $\forall \,\,x\,\,\exists y\,\,,(x^2 + y^2 \geq 0)$?
69 views

### $a > b+1 \Rightarrow a>x>b$?

If I have $a,b \in \mathbb R$ such that $$a > b+1$$ It is assured that $\exists\space x \in \mathbb Z: a>x>b$ Does this property have some special name? How can this be proved? This idea ...
29 views

### Show that | and $\downarrow$ are the only binary connectives \$such that {$} is functionally complete.

I've been reading and coping with van Dalen's Logic and Structure for a a few days. However, I've getting problems to solve his Exercise 6 from Ch 1 Sec 1.3 (p.28). In this exercise, van Daken asks ...
35 views

### Using logical Properties to prove a tautology

So I have to prove this as a tautology. I've been stuck on this forever and am not sure where to go. I experimented and got this far, and looking for some pointers on where to take it next. (p → q) ...
35 views

### Questions on logic behind “proof by contradiction”

I'm trying to understand the logic behind "proof by contradiction" and hoping that I can clear up a few things in this post. First of all, suppose I have a proposition $P$ and from this I can imply ...
45 views

72 views

### Checking understanding on proving uniqueness of identity and inverse elements of a group.

Sorry for such a trivial question, but just wanted to check my understanding. When proving a statement, for example, that the inverse of a group element is unique (in elementary group theory) one ...
41 views

### How to write $a|b \wedge ((a=0 \wedge b=0) \vee (a\ne0 \wedge b\ne0))$

How can I write the expression $$a|b \wedge ((a=0 \wedge b=0) \vee (a\ne0 \wedge b\ne0))$$ concisely and clearly in English? A direct translation yields $a$ divides $b$ and either {$a$ and $b$ ...
79 views

### The “converse” of $P\rightarrow(Q\rightarrow R)$

As everyone know, even when reading mathematics books, a paragraph written in natural language contains much more information than just its purely logical translation. For my next tutor session, I am ...
25 views

### Can the proof for the following 4 cases be simplified to 2 cases?

Let $X$ and $Y$ be finite and disjoint sets. Suppose we are required to prove the following: $|X|\ge 0 \text{ and } |Y|\ge 0 \Rightarrow Q$ where $Q$ is some statement. Therefore, I know I need to ...
40 views

### Correctly understanding truth table problem?

I'm typing up a solution set for an "intro to proof" course. One of the problems asks the student to "construct a truth table for $(P \implies Q) \implies (\neg P)$." I interpreted this as requesting ...
53 views

### Why are the different ways to write a universal statements equivalent?

Consider the following universal statements: $\forall a \in \mathbb{R}-\{0\}, a^2 > 0$ $\{a \in \mathbb{R} - \{0\}| a^2 > 0 \} = \mathbb{R}-\{0\}$ $a\in \mathbb{R}-\{0\} \Rightarrow a^2>0$ ...
44 views

127 views

### How to prove that the law of the excluded middle is necessary?

This is a follow up question to this answer by Carl Mummert to the question whether every proof with contradiction can also be proved without contradiction. As Carl Mummert pointed out, there are ...
48 views

### Free and bound variables in “if” statements

The assertion $x>2$ is true when we replace $x$ by a number greater than $2$($3$ for example) and false if we replace it by $1$. But the assertion $\forall x(x>2)$ is false. In the first case ...
62 views

### Prove $\neg\exists x \neg P(x)$ is a logical consequence of $\forall x P(x)$

How would you prove that 2. is a logical consequence of 1. using a Fitch style proof? $\forall x P(x)$ $\neg\exists x \neg P(x)$
96 views

### Difference between bound and free variable

What is the difference between $\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$ I know in the first one the variable x is bound but in the second one the variable is free. What are the ...
65 views

Below is a proof that any group of order $p^2$ is abelian $(p$ prime of course). Let $Z \left({G}\right)$ be the center of $G$. We know $|Z(G)|>1$. $\color{blue}{\text{Suppose}} \left\vert{Z ... 2answers 44 views ### What is the proper way to prove this? First of all, here is the question I am trying to answer for context. I can see that the statement$\forall x \in \mathbb{Z} , \exists y \in \mathbb{Z}((x\leq y ) \wedge (x+y=0)) $negates to ... 2answers 61 views ### Logic Proof with Natural Deduction: if I assume the antecedent, do I still have to prove the consequent? I have the unpleasent feeling that my "proof" is dead wrong. The core of my concerns is: when I have something like A -> (B -> C) and I assumed ... 1answer 51 views ### Question about Logic Proof Assuming$P$is a unary predicate and$Q$is a propositional variable, I'm trying to prove the following implication: $$(\forall x (P(x)\rightarrow Q)\rightarrow ((\forall x P(x) )\rightarrow Q)$$ ... 3answers 119 views ### Are truth tables a valid method to prove an iff statement? I recently had a homework assignment returned to me (for a Differential Geometry course, undergrad level) in which my instructor wrote "You cannot use truth tables to prove an if and only if ... 1answer 67 views ### Proof negation in Gentzen system I am provided with the L¬ and R¬ Gentzen rules for negation (besides “Cut” rule and some rules for ⋀ and →): $${\Gamma\vdash\Delta,\varphi\over \Gamma,\lnot\varphi\vdash \Delta}\ L\lnot \\[4ex] ... 2answers 117 views ### Show there are a pair of sentences where the first says the second is provable and the second says the first is unprovable Given B_1(y) and B_2(y) in the language of arithmetic, show there are sentences G_1 and G_2 such that:$$\vdash_Q G_1 \leftrightarrow B_2(\ulcorner G_2 \urcorner)\vdash_Q G_2 ... 3answers 80 views ### Giving Proof by counterexample I just started learning college mathematics and one of the things I don't like is giving proofs by counterexamples. My question is how is disproving by giving counterexample is seen by advanced ... 2answers 109 views ###$2 \uparrow^n 2 = 4$and the magnificence of$2$I was reading up on tetration when I realized: $$2 \uparrow\uparrow 2 = 2\uparrow 2 = 2 \times 2 = 2+2 =4$$ Infact, when generally speaking: $$2 \uparrow^n 2 =4$$ Now, I realize that this is because ... 0answers 126 views ### Substitute Proof by Contradiction/Negation with Direct Proof or Proof by Contrapositive When do proof by contradiction, or by negation, or direct proof, or proof by contrapositive all work equally well? When can any one be chosen as the proof form? I'm interested in a pragmatic answer ... 1answer 62 views ### What is the proper way to format a hypothetical syllogism proof? Problem: Show that these three statements are equivalent, where$a, b \in R:$(i)$a < b$, (ii) the average of$a, b,$is greater than$a,$and (iii) the average of$a$and$b$is less than$b$. ... 0answers 27 views ### Selecting a unique pair satisfying a condition$\varphi$with an ordering Given a finite structure$\mathfrak{A}$with Universe$|A| < \infty$and signature$\tau$. We say a pair$(a,a') \in A$satisfies a$\tau$-formular$\varphi$iff $$\mathfrak{A} \models ... 2answers 183 views ### For all x there exists a y such that x+y=0 I know this statement is true but I am having trouble actually proving it. I know that if x=5 then y=-5. How can you prove that properly. 2answers 80 views ### Restate a logical claim using logical symbols Proposition: Strictly between any two distinct rational numbers lies another rational number. How may I present this statement using logical symbols? My answer: \forall x, y \in {\mathbb{Q}}. ... 6answers 761 views ### (P\implies Q) \implies [(R ∨ P)\implies (R ∨ Q)] is a tautology I'm currently trying to work on the proof for this tautology. But every time I derive the right side, I end up with a lone R that will never cancel out. Like I always end up with$$(P\implies Q) ... 1answer 39 views ### On provability within minimal logic In its most naive form my question boils down to this: when is a proposition that is provable "by contradiction" also provable "directly"? IOW, is it possible to know, a priori, that a ... 3answers 167 views ### Using rules of inference (Leibniz) to prove theorems. Leibniz: If$A \equiv B$is a theorem, then so is$C[p:= A] \equiv C[p:= B]$. Note: p is "fresh" means p doesn't occur in$A, B, C$. I am trying to understand how to use Leibniz rule of inference for ... 1answer 43 views ### Negate Implication Written as a Sentence without “If …, Then …” [Chartrand P246] P246 Theorem 10.4: Every infinite subset of a denumerable set is denumerable. P252 Theorem 10.10: Let$A \subseteq B$be sets. If$A$is uncountable, then$B$is uncountable. I'm aware how ... 1answer 60 views ### Prove by Hilbert deduction: ⊢∃x(AvB)→(∃xAv∃xB); ⊢(∃xAv∃xB)→∃x(AvB) I'd really like your help proving: 1)⊢∃x(AvB)→(∃xAv∃xB) 2)⊢(∃xAv∃xB)→∃x(AvB) Our proof system contains next Hilbert's axioms: 1.A→(B→A) 2.(A→B)→((A→(B→X))→(A→X)) 3.(A&B)→A 4.(A&B)→B ... 3answers 264 views ### Premise vs. Assumption I have just asked about the difference between A,B and A∧B in A,B ⊢ M However, I have ... 1answer 31 views ### Defining substitution by structural recursion For a term u, let$u{x\atop t}$be the expression obtained from$u$by replacing the variable$x$by the term$t$. Define$u{x\atop t}$by recursion on$u$. Not really sure how to start this one. ... 3answers 132 views ### How do I derive$(\forall x)(\forall y)(\exists z)(x = y \circ z)\$ from these three group axioms and some previously established theorems?

I am currently self-studying Patrick Suppes' Introduction to Logic and I am stuck on exercise 5.2.4. I've successfully worked out proofs for Theorems 1 to 7, but I am having trouble coming up with a ...