Tagged Questions
1
vote
2answers
57 views
Prove that $(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$.
Logically, the following proposition makes sense:
$(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$
Or, in english, if sets $S$ and $T$ share no elements, and the union of ...
4
votes
0answers
59 views
Infinite “String” of Implication Statements
This question is inspired by the conversations at
Does this require transfinite induction?
First of all, does an infinite string of implication statements have a conclusion? I don't think so, but I ...
2
votes
2answers
65 views
is this argument true?
i had a puzzle and used a logical argument to show a point but some says that my argument is wrong but i can't understand the reason they provide !
the puzzles says ,
Given four cards laid out on a ...
1
vote
1answer
52 views
Formal deduction in first order logic
How do you show that a deduction exist in the Hilbert Proof System, as used in Enderton's Mathematical Introduction To Logic.
L is a FOL (First Order Language).
L contains R, where R is a single ...
8
votes
1answer
104 views
Difference between a Lemma and a Theorem [duplicate]
What essentially is the difference between a lemma and a theorem in mathematics? More specifically, suppose you come across a general result while solving a mathematical problem, what are the ...
3
votes
1answer
56 views
Prove that A $\equiv B$
Suppose, I have to prove that $A\equiv B$.
I started out by proving that $¬B \implies ¬A$. This proves $A\implies B$. Next I proved that suppose B is true and A is not and this turns out to be ...
0
votes
3answers
35 views
Identifying Proof Method and Implementing It
The question I am working on is:
Prove that if $m+n$ and $n+p$ are even integers, where
$m$, $n$,and $p$ are integers, then $m+p$ is even. What kind
of proof did you use?
I was thinking--and ...
2
votes
2answers
89 views
How to prove this with induction
$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q $$
is the same as
$$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$
Do I ...
3
votes
1answer
92 views
Prove that a formal system is absolutely inconsistent
I'm using the book An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, and it does not have any solutions and barely any examples. I want to understand how to prove that all ...
3
votes
4answers
146 views
Quantifies, predicates, logical equivalence
I am asked if $(\exists x) (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \exists xQ(x)$ are logically equivalent. I dont think they are but how will I prove it. Am I supposed to use either ...
9
votes
1answer
101 views
Is there a quicker argument from the HBL derivability conditions to the equivalence of fixed points of $\neg\Box$ to $\mathsf{Con}$?
I'm just about to send off the final, final corrected PDF of the second edition of my Gödel book, and the following (neurotic?!?) question occurs to me.
In discussing matters around and about the ...
0
votes
1answer
127 views
Proof of logical equivalence of biconditional and other proposition
I am working on a problem where I need to show the logical equivalence of two propositions. One is a biconditional: p<->q. And the other is this: $(p \land q) \land (\lnot p \land \lnot q)$
I ...
34
votes
2answers
671 views
Is it possible to prove a mathematical statement by proving that a proof exists?
I'm sure there are easy ways of proving things using, well... any other method besides this!
But still, I'm curious to know whether it would be acceptable/if it has been done before?
3
votes
1answer
147 views
Primitive recursive functions and characteristic functions. Methods of proof- examples. Illumination.
I am puzzling over a sentence in an example in a textbook, showing that a function $f$, defined by cases, is primitive recursive.
Let $E$ be the set of even natural numbers. The function $f$ defined ...
24
votes
2answers
819 views
Proof by contradiction vs Prove the contrapositive
What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proofs by ...
1
vote
1answer
64 views
Show that if $\lfloor x+a \rfloor$ = $\lfloor x+b \rfloor, \forall x \in \Bbb R$ then $a=b$; is showing that $x+a=x+b$ enough?
If i show that $x+a=x+b$ only if $a=b$, does that prove that the above is also true?
$ x+a=x+b \iff x+a-x-b=0 \iff a-b=0 \implies b=a$ also is this any good?
1
vote
4answers
192 views
Prove equivalence $(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$
Prove equivalence $$(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$$
What is the step by step for the equivalence of these equations. I can first break down the ...
-2
votes
1answer
139 views
On Vacuous Truth, Vacuous Falsity
Is it "mathematically legal" to exploit vacuous truth by choosing when to focus on vacuous truth and when to neglect vacuous falsity and vice versa?
Thanks
4
votes
3answers
98 views
Want to show Quantifier elimination and completeness of this set of axioms…
Let $\Sigma_\infty$ be a set of axioms in the language $\{\sim\}$ (where $\sim$ is a binary relation
symbol) that states:
(i) $\sim$ is an equivalence relation;
(ii) every equivalence ...
4
votes
1answer
69 views
Proofs whose length depends on the input
This may be a question from proof theory, but I'm not sure, since I don't know any proof theory. What I will be asking about is what happens, if the length of a proof isn't fixed: I'm going to present ...
1
vote
1answer
62 views
Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink
So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...
2
votes
3answers
83 views
What proof strategy can we use to prove this?
$$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]$$
I tried to do a proof by case, but it doesn't work because of the quantifiers. So I was wondering what ...
3
votes
2answers
134 views
Prove or Disprove U' = Ø
It seems obvious to me that the statement is true. If you are looking at the elements that are not in the universal set, there are no elements left, thus you are left with the empty set.
However, ...
1
vote
2answers
78 views
What are the differences between these two logical statements?
$$\exists\ x \in \mathbb{N}\ \textrm{such that}\ \forall\ y \in \mathbb{N}, 2x \leq y + 1$$
$$\forall\ y \in \mathbb{N}, \exists\ x \in \mathbb{N}\ \textrm{such that}\ 2x \leq y + 1$$
I'm having ...
1
vote
2answers
121 views
Prove or Disprove: ∃x ∈ N such that ∀y ∈ N, 2x ≤y + 1
The first thing that I tried to do is: let y be an arbitrary natural number. I then tried to choose a value for x, but I cannot think of a value in which 2x ≤ y + 1..
So I then tried to prove the ...
2
votes
3answers
90 views
Prove or Disprove: $\exists y ∈ \mathbb{N}$ such that $\forall x ∈ \mathbb{N}, 2x ≤ y + 1$
Here's what I have done:
I think it's false, so I set out to prove the negation. Which is: $$\forall y \in \mathbb{N}, \exists x \in \mathbb{N}; 2x > y + 1$$
I then let $y$ be an arbitrary natural ...
3
votes
2answers
256 views
Proof of a statement involving quantifiers
I've been trying to solve the following exercise of Velleman's "How To Prove It":
Prove $\exists x(P(x)\to \forall yP(y))$.
Could anybody give a hint on this? I guessed some transformations could be ...
4
votes
2answers
256 views
Induction without integers (aka Structural Induction)
While composing the following question, I had an "ah-ha" moment. I still want to post the question along with my answer to show what I have learned. Any comments or additional answers will be greatly ...
3
votes
2answers
75 views
Is the set of self-dual connectives incomplete?
A $n$-ary connective $\$$ is called self-dual if $f_\$(x_1^*, \ldots , x_n^*) = (f_\$(x_1, \ldots , x_n))^*$ where $0^* = 1$ and $1^* = 0$.
How to show that the set of such self-dual connectives ...
0
votes
0answers
157 views
propositional logic - substitution
Prove: $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies \varphi_1[\psi/p] =\!\mathrel|\mathrel|\!= \varphi_2[\psi/p]$.
We've proven that $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies ...
0
votes
2answers
513 views
I want a clear explanation for the Principle of Strong Mathematical Induction
I understood the Principle of Mathematical Induction.
I know how to make a recursive definition.
But I am stuck with how the "Principle of Strong Mathematical Induction (- the Alternative Form)" ...
0
votes
3answers
123 views
Logical Equivalance
Determine whether the following pairs of statements are logically
equivalent or not. Give a reason.
(i) $p \to (q \to r)$ and $(p \to q) \to r$
(ii) $p \to (q \to r)$ and $q \to (p \to ...
1
vote
1answer
88 views
Proof through consistency
Take first-order Peano Arithmetic PA. We know that Gentzen proved PA consistent. Now, if one sets for example $\varphi$ to represent Fermat's theorem in FO, would proving PA+$\varphi$ consistent be ...
1
vote
0answers
80 views
Proving that a formula cannot be proven (has no formal proof) in a given deduction system
In my homework I was asked to prove that a deduction system for modal logic with $\rightarrow$, $\neg$ and $\square$, with 4 axioms and 2 inference rules (MP and a $\square$-generalization rule), is ...
13
votes
4answers
1k views
Proof by Contradiction, Circular Reasoning?
Suppose we wish to prove $P$ implies $Q$. We assume $P$. Proof by contradiction begins by assuming not $Q$, and from these two assumptions, a "contradiction" is derived. Now, sometimes that ...
4
votes
1answer
155 views
How far can a logical sentence with only two variables be simplified?
Given any sentence in sentential logic with two variables ($\mathbf{P}$ and $\mathbf{Q}$), is it possible to reduce it to an equivalent sentence where each variable is only invoked once?
As an ...
-3
votes
1answer
198 views
find formal proof for a simple tautology
Could you please help me figure out the formal proof for the following argument?
This is an example from the textbook "Language, proof and logic" (by D. Barker-Plummer et al). I am doing it in the ...
0
votes
2answers
219 views
formal proof challenge
I am desperately trying to figure out the formal proof for this argument.
$$\begin{array}{r}
A\lor B\\
A\lor C\\
\hline
A\lor (B \land C)
\end{array}$$
I am trying to apply the backwards ...
1
vote
2answers
170 views
find formal proof
Got stuck while figuring out the formal proof for the following:
$$\begin{array}{r}
A\lor B\\
\neg B\lor C\\
\hline
A\lor C
\end{array}$$
The conclusion seems obvious. But finding a formal proof ...
1
vote
3answers
370 views
inference rules application (introduction / elimination): two examples
Got stuck while trying out how to apply inference rules (introduction and elimination) for the following examples:
From $\lnot(P\land Q)$ and $P$ infer $\lnot Q$
From $P\lor Q$ and $Q$ infer $\lnot ...
4
votes
3answers
175 views
Contradiction Proof
Suppose one wants to prove $P \implies Q$ by contradiction. In general, we will probably have the following, $P_1, \dots, P_n \implies Q$. Suppose we want to prove this by contradiction. Then is it ...
1
vote
2answers
182 views
If-Then statements
I am trying to prove a statement of the form:
If A and B, then C.
Is this equivalent to the following statement?
Given A, if B, then C.
2
votes
1answer
231 views
Prove by contradiction or contrapositive
Prove: If $|x+y|<|x|+|y|$, then $x<0$ or $y<0$
This looks as though it's true from the start.
Take $x=-4, y=4$
$|-4+4|<|-4|+|4|$
$0<8$ is true.
The question is asking for a ...
1
vote
1answer
164 views
Which proof makes more logical sense?
Using two forms of provability:
Identity Elimination/Transitivity
AnaCon: Analytical Consequence
Below, "Larger(x,y)" means "x is larger than y", "Smaller(x,y)" means "x is smaller than y", and ...
4
votes
1answer
270 views
Non Higher-Order Formulation of Gödels Incompletness Theorem
I was just having a look at Gödels incompletness theorem as found in:
http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf
I noticed that Gödel used a higher order logic. At least ...
3
votes
2answers
307 views
Is it true that for all proofs of the statement, $\forall x \exists y : R(x, y)$, then we can say $y = y(x)$? (Example given)
Is it true that for all proofs $\forall x \exists y : R(x, y)$, then $y = y(x)$?
A while back I remember reading a book on functional programming that was leading into some questions about what ...
7
votes
2answers
645 views
Prove that $\beta \rightarrow \neg \neg \beta$ is a theorem using standard axioms 1,2,3 and MP
I've proven that $\neg \neg \beta \rightarrow \beta$ is a theorem, but I can't figure out a way to do the same for $\beta \rightarrow \neg \neg \beta$.
It seems the proof would use Axiom 2 and the ...
