Tagged Questions

62 views

Can we always give a direct proof? [duplicate]

This is something I was wondering about for quite a while. Is it possible to construct a statement that can only be proven by using 'proof by contradicition' or contraposition? Or to put it ...
35 views

proving{$\neg(\forall x)\alpha \rightarrow \alpha$}$\models$$(\forall x)\alpha prove {\neg(\forall x)\alpha \rightarrow \alpha}\vdash\space(\forall x)\alpha Im not sure what is the convention, so to be clear I am talking about proving the formula from the seven axiom ... 2answers 69 views How to deal with equivalences in proofs? There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: (p \equiv q) \equiv (q \equiv p) . Given p and q ... 1answer 55 views My proof is wrong, can anyone tell me why?$$\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, [x(x+1) = y(y+1)] \Leftrightarrow [x = y]\forall x \in \mathbb{Z} , \forall y \in \mathbb{Z}, [x(x+1)=y(y+1)]\Leftrightarrow [x=y]$$... 2answers 111 views Proof of Sylow's theorem. I read this proof of Sylow's theorem in Rotman's "An introduction to the Theory of Groups" and I don't understand what is the argument in the second paragraph (the one in the green box) for. Isn't ... 2answers 97 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 ... 1answer 35 views Disjunctive Normal Form (DNF) of a boolean combination Upon revisiting chapter 1 of Robert S. Wolf's "A tour though mathematical logic" I sumbled upon the following Proposition on page 13 : Suppose that P is a Boolean combination of ... 2answers 101 views How can one pass from “almost surely” to “surely”? Several results (e.g in probability theory or using prob. theory) are stated in an almost surely phrasing (meaning the set of outcomes where this is not so has measure zero) How can one pass from ... 1answer 36 views HA^{\omega} is a conservative extension of HA. But why? This is definitely a silly question, but I've no one to ask... HA^{\omega} is an extension of HA in all finite types. One can formalize a model of HA^{\omega} in HA using indicies of partial ... 1answer 70 views Do we sometimes have to go “each way” separately for iff proofs? So, I often enjoy trying to prove "if and only if" statements by only using if and only if arguments. i.e. RTP: A \Leftrightarrow D. Proof: A \Leftrightarrow B \Leftrightarrow C \Leftrightarrow ... 5answers 86 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 ... 1answer 76 views A proof in naive set theory. I am trying to use naive set theory to figure out a proof of the following statement:$$(x = u \land y = v) \to 〈x, y〉 = 〈u, v〉$$. What propositions should i use to prove this? 2answers 89 views Law of excluded middle. Do we need it in proofs? Quite often when I am making a natural deduction proof, and I have no fixed idea on how to continue. I find myself thinking: "lets start with some form of the law of the excluded middle (LEM) and ... 3answers 69 views How can I prove this statement by proving its contra-positive? Prove the following statement by proving its contra-positive: If r is irrational, then r^{1/5} is irrational. I am totally confused! (1) How does proving the contra-positive prove ... 2answers 88 views Proofs for Relational Predicate Logic --Difficult Question! I have been working on this problem for four and a half hours and I think I have simply missed something. I need the help of my peers here. The rules I am allowed to use are the Basic Inference rules ... 0answers 68 views Finding a finite model Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this: Suppose L is a language which includes an infinite list ... 1answer 42 views LK-\Phi proof of \exists y Pby I am having difficulty with the concept of LK-\Phi proofs, here is a question I have been working on: Let \Phi = \{Pafa\}, where P is a binary predicate symbol and f is a unary function ... 1answer 59 views What exactly does \vdash_T G_T \leftrightarrow \lnot \exists y Prf(\ulcorner G_T \urcorner, y) mean? To me this translates to: G_T is provable in T if and only if there doesn't exist a y such that y is a witness to the provability of \ulcorner G_T \urcorner. But I'm not entirely sure what ... 1answer 33 views Why [\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha] is a tautology? Let c be a new constant symbol in the language. Then [\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha] is a tautology. This ... 1answer 45 views A question to the proof of a lemma in Enderton's Mathematical Introduction to logic I'm referring to the proof to Lemma 25\text{B} \ ,pg\ 133 of Enderton's Mathematical Introduction to Logic(2^\text{nd} edition): \overline s(u^{x}_{t})=\overline {s(x|\overline s(t))}(u). The ... 5answers 69 views If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof) Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ... 1answer 109 views Some burning questions on First-order logic from an amateur I'm currently taking an introductory course in Mathematical logic(prerequisites is only advanced calculus) and my lecture notes are based on Enderton's book 'Mathematical Introduction to Logic' ... 1answer 31 views big o statement prove or disprove (impossible) This question is harder than it looks folks for all a in the reals and for all b in the reals, [(a <= b) => (n^a is O(n^b))] n^a is O(n^b) if n^a <= cn^b for some n>= n, (n less than or equal ... 3answers 58 views Proving \neg A\vee(A\wedge \neg B)= \neg A \vee \neg B. How do I prove using boolean algebra that \neg A\vee(A\wedge \neg B)= \neg A \vee \neg B? I can see it in the logic table and it is logical, but I can't prove it mathematically. 1answer 61 views A finite set of wffs has an independent equivalent subset This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ... 2answers 23 views negation of powersets If given two power sets P(A) and P(B), and told that the Union of these two sets was a subset of another powerset P(C), what would be the negation of this statement? Would the Union go to an ... 8answers 107 views Prove if n^3 is odd, then n^2 +1 is even I'm studying for finals and reviewing this question on my midterm. My question is stated above and I can't quite figure out the proof. On my midterm I used proof by contraposition by stating: If n^2 ... 0answers 212 views Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ... 12answers 4k views Prove that a counterexample exists without knowing one I strive to find a statement S(n) with n \in N that can be proven to be not generally true despite the fact that noone knows a counterexample, i.e. it holds true for all n ever tested so far. ... 3answers 65 views Show that “\Gamma \models S \Rightarrow \Gamma \vdash S” entails “if \Gamma \nvdash P \And \sim P then \Gamma is satisfiable” Show that "\Gamma \models S \Rightarrow \Gamma \vdash S" entails "if \Gamma \nvdash P \And \sim P then \Gamma is satisfiable" I'm primarily confused with the notation being used here. In ... 2answers 63 views Replacement of sentence symbols by 0-place connectives Suppose we add 0-place connectives \top, \bot to our language. For each well-formed formula wff , \phi and sentence symbol, A, let \phi^{A}_{\top} be the wff obtained from \phi by ... 1answer 54 views How do I prove that the function symbol \circ is not a term by induction in the calculus? How do I prove that the function symbol \circ is not a term by induction in the calculus? I've tried to prove it by the definition of term in first-order language. From the definition of term in ... 0answers 95 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 ... 3answers 58 views For x+y+z=0, if x and y are divisible by some integer k, then so is z. If k|x and k|y and x+y+z = 0, then k|z. Here, "k|x" means that k is a divisor of x and x,y,z,k \in \mathbb{Z} What strategy would you employ to prove this? 1answer 49 views Prove A \ B = A \cap B^c I see the use of A \ B = A \cap B^c being used in bigger problems but how do you prove this? Is the proof as simple as: A \ B \iff x \in (A \setminus B) \iff x\in A \cap ... 1answer 95 views Is proving both sides of iff necessary? I have always been taught to prove both ways of an "if and only if" statement in a formal proof, but if the opposite way is very similar to the proof of the first way. Can you just leave a note and ... 0answers 52 views Replacement of sentence symbols in a well-formed formula Suppose \theta is a tautology and A,B are sentence symbols occurring in \theta and \psi is a well formed formula obtained by replacing B with A. Is \psi is a tautology? My proof: We ... 2answers 76 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}}. ... 4answers 71 views (A_1\rightarrow\wedge A_2) is not a well-formed formula Let A_1,A_2 be sentence symbols. Could anyone advise me how to prove (A_1\rightarrow\wedge A_2) is not a well-formed formula? Thank you. 3answers 151 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 ... 6answers 418 views When to use the contrapositive to prove a statment My question tries to address the intuition or situations when using the contrapositive to prove a mathematical statement is an adequate attempt. Whenever we have a mathematical statement of the form ... 1answer 92 views Proof by contradiction: May I assume P (true) in \neg Q \land P \Rightarrow P \land \neg P to prove Q by contradiction Suppose I wish to do a proof by contradiction the statement Q. In proving Q may I assume \neg Q \land P (where P is a statement known to be true) and show the implication \neg Q \land P ... 5answers 151 views Are p \to (q \to r) and p \to (q \wedge r) logically equivalent? Is p \to (q \to r) logically equivalent to p \to (q \wedge r)? I simplified each one, I got \neg\, p \vee(q \vee r) and \neg\, p ∨(\neg\, q \wedge r) respectively. Not sure if my ... 4answers 420 views If we accept a false statement, can we prove anything? [duplicate] I think that the question is contained in the title. Suppose we begin from something that is false for example 1=0. Is it possible using only \Rightarrow (and of course \lnot ,\wedge,\lor) to ... 3answers 116 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 ... 2answers 92 views Formal proof involving existential quantifier It is common sense that to derive a formula with existential quantifier is only necessary to prove that a formula is valid for any term , ie: \Gamma , \phi [t/x] \vdash \existsx\phi. By ... 0answers 66 views Cut-off Subtraction in Coq I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ... 1answer 48 views Propositional logic derivation Data given : Y value is either 0 or 1 Premises : 1) (X=Y)$$\iff$ (R $\lor$ S) 2) S $\iff$ $(X=0)$ 2) R $\implies$ $(X=1)$ Result : $(X=1)$ $\implies$ R Can i infer result from premises and ...
I am solving the following problem : I have edge-matching puzzles, where all pieces are squares and the grid has $n$*$n$ format. There is no global image to guide a puzzle solver. Despite the puzzles ...