0
votes
0answers
27 views

A question about an special kind of proof [on hold]

Is there some proof method in which I can prove the existence of a mathematical object? How can I prove a conjecture that it is an existence statement of a mathematical object? Which are the ...
2
votes
0answers
63 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 ...
0
votes
1answer
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 ...
1
vote
2answers
70 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 ...
1
vote
1answer
57 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]$$ ...
2
votes
2answers
112 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 ...
2
votes
2answers
98 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 ...
0
votes
1answer
39 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 ...
0
votes
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 ...
3
votes
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 ...
2
votes
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 ...
3
votes
5answers
87 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 ...
2
votes
1answer
77 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?
3
votes
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 ...
0
votes
3answers
72 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 ...
3
votes
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 ...
3
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
2
votes
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' ...
1
vote
1answer
32 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 ...
2
votes
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.
0
votes
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 ...
0
votes
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 ...
1
vote
8answers
108 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 ...
1
vote
0answers
213 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 ...
25
votes
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. ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
3
votes
0answers
96 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 ...
0
votes
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?
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
2
votes
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}}. ...
0
votes
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.
0
votes
3answers
152 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 ...
14
votes
6answers
421 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 ...
0
votes
1answer
93 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 ...
4
votes
5answers
152 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 ...
4
votes
4answers
423 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 ...
1
vote
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 ...
1
vote
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$ $\exists$x$\phi$. By ...
1
vote
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 ...
0
votes
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 ...
4
votes
0answers
152 views

Puzzle - zero knowledge proof

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 ...