First of all I'd like to say that I have looked for the answers to my specific question and have not found it in the existing topics.  The question is fairly simple. Say, we need to  prove statement P by the method of contradiction. Assuming that $\lnot P$ holds, using the list of statements proven earlier to hold or derived by us during the proof, we arrive to P being $true$.  $$\lnot P  \to A_1 \to\ ... \ \to A_n \to P$$ $$\lnot P  \to  P \iff \lnot(\lnot P) \lor P \iff P $$  We can therefore add P to the list of our proven statements, because it was derived. Most of the proofs contain something in the lines of "the obtained contradiction proves that our initial assumption ($\lnot P$) was wrong and so $P$ holds".  What I don't understand is, if the initial assumption ($\lnot P$) is thus proven to be false, then why can we be sure that anything derived from it holds (in particular, that P holds)? On the other hand, if it cannot be derived then the assumption ($\lnot P$) can in fact be true.   Can someone explain why this type of argument cannot be used?
20540
Let's say that I prove statement $A$ by showing that the negation of $A$ leads to a contradiction.   My question is this: How does one go from "so there's a contradiction if we don't have $A$" to concluding that "we have $A$"?  That, to me, seems the exact opposite of logical. It sounds like we say "so, I'll have a really big problem if this thing isn't true, so out of convenience, I am just going to act like it's true".
100786
Show that the logic $ \ \forall x \exists y \ P(x,y) \ $ is not logically equivalent to $ \ \exists x \forall y \ P(x,y) \ $  in the domain $ \ \{-1,0,1 \} \ $ by giving a counter example .  Answer:  Let   $ x=\{0,1 \} \\ y=\{-1,0 ,1 \} \ $  Let $ P(x,y) \ $ be the property such that $ \ x \geq y \ $   Then , $ \forall x \exists y \ P(x,y) \ $ is true.   But, $ \ \exists x \forall y \ P(x,y) \ $ is False. Because for $ x=0 \ $ , we have $ \ 0 \ngeqslant y=1 \ $.  I need confirmation of my work.
34329
The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove $(\lnot C\implies\lnot B)\implies(B\implies C)$ by using the three axioms $(A1,A2,A3)$ without using the Deduction theorem (and without any hypothesis).  The axioms are:  $A1: B\implies(C\implies B)$  $A2: (B\implies(C\implies D))\implies((B\implies C)\implies(B\implies D))$ $A3: (\lnot C\implies\lnot B)\implies((\lnot C\implies B)\implies C)$  The only inference rule is MP.  I have a proof but it is long. My proof is based on the proof of Lemma 1.11 (d) which proves $(\lnot C\implies\lnot B)\implies(B\implies C)$ but uses the Deduction Theorem (Proposition 1.9). Then, like Mendelson suggests in exercise 1.49, I apply the process used to prove the Deduction Theorem to the steps. To be precise, I assume $(\lnot C\implies\lnot B)$ as a Hypothesis $H$. If $C_1,C_2,\dots,C_n$ is a proof of $(B\implies C)$ that uses $H$ then stepwise I prove $H\implies C_i$ for $i=1,\dots,n$. The last step is $H\implies C_n$ which is what we want to prove.  This way requires around 4 uses of Axiom1, 4 of Axiom2, 1 Axiom3, and 9 uses of Modus Ponens.  Do I miss a shorter proof?
88968
Firstly, how do I read it? Is below right? With braces   $$p \vdash (q \Rightarrow p)$$  The given proof is:    ${p}$, premise ${q}$, assumption  $p$ by (1) // what???  ${q} \Rightarrow p$ by implication introduction with 2 and 2.1 QED...    I can't really get the link between $p$ and $q$ in 2.1 ...
87027
When we talk about formal logic, we generally agree that $P$ and $Q$ are deductively valid propositions. Below fact is supported by  Rutger Uni. page no.2 (PDF doc) And further when we talk about implication or material/concrete conditional $P\to Q$ we assume: &quot;if $P$ is true, then $Q$ is also true&quot; or more generally in formal logic we assume: if premises are true then conclusions are also true because we are dealing with deductively valid propositions. But when we draw truth-table of $P\to Q$ we come across one paradox. That is,  When $P$ is false, and $Q$ is true, $P\to Q$ is still true!  Why so? How can premise (deductively valid proposition or antecedent) be false  with a conclusion (deductively valid proposition or consequent) be true, and their implication be still TRUE! Reading through the explanations given on the question:  It is bit clear with the given examples that: When $P$ is false, and $Q$ is true, $P\to Q$ is true in some situations. Out of given examples I am selecting example given by Jai [3rd top answer on that page] which in fact comes from this :  &quot;If you get an A, then I'll give you a dollar.&quot; What if it's false that you get an A? Whether or not I give you a dollar, I haven't broken my promise.  Does this mean that if I get A+ or B- or I was ill for the exam, I will still get a dollar as promised? Because, I thought propositions are rigid and their use in conditional should be consider as-is without changing the meaning of them, then what is intended by the author of the given example. Here, it is very clear that author of the example suggest that; it is a necessary condition for &quot;Get an A&quot; is &quot;I'll give you a dollar&quot; and a sufficient condition for &quot;I'll give you a dollar&quot; is &quot;Get an A&quot;. Is there any further explanation: The premise (antecedent) requires further support or can be overlooked or ignored in order for conclusion (consequent) to be true when antecedent is false and consequent is true?
124305
On  in XI Free Models and Logic Programming of Ebbinghaus' Mathematical Logic:  In general, the following statement is false: (*)  If $\Phi \models \exists x \phi$  then there is a term $t$  with $\Phi \models \phi \frac{t}{x}$ We  get  a  counterexample for  $S  = \{R\}$  with unary $R$,  $\Phi = \{\exists x Rx\}$,  and  $\phi  =  Rx$.  In the counterexample, why if $\{\exists x Rx\} \models \exists x R x $, then there is no term $t$   with $\{\exists x Rx\} \models R t $? Thanks.
122666
I'm taking a course from Stanford in Logic. I'm stuck with an exercise where I'm doing some proof. The Fitch system I'm given only allows   $ \land $ introduction and elimination $ \lor $ introduction and elimination $ \to $ introduction and elimination $ \equiv $ introduction and elimination $ \lnot$ introduction and  $ \lnot \lnot $ elimination   but not    $ \bot $ introduction and elimination   I've been struggling to prove the law of excluded middle (``p ∨ ¬p`) within this system. All of the proofs I've seen online make use of $\bot$ elimination to prove it by contradiction:  | ~(p | ~p)  (assumption) | | p        (assumption) | | p | ~p   (or introduction) | | $\bot$ | | | ~p       (assumption) | | p | ~p   (or introduction) | | $\bot$ | | (p | ~p)   (proof by contradiction)   Since I can't use $\bot$ elimination, I was trying to do this with $ \lnot$ introduction:  | ~(p | ~p)  (assumption) | | ??? | ~(p | ~p) =&gt; x | | | ??? | ~(p | ~p) =&gt; ~x | p | ~p     (not introduction)   but I just can't get it. I can't figure out how to get x and ~x.  Is this provable without $\bot$ elimination? If so, what are the steps?    Background:  What I'm ultimately trying to prove is : Given p ⇒ q, use the Fitch System to prove ¬p ∨ q. I'm able to prove that p ⇒ ¬p ∨ q and that ¬p ⇒ ¬p ∨ q, but I need to be able to plug p ∨ ¬p into the proof to be able to do 'or elimination'.
18901
I am trying to get an intuition (ohh, the irony) about the logical truth tables. In particular, I am looking at the basic conditional P-&gt;Q with the following truth table:  P  Q  | P -&gt; Q  T  T      T  F  T      T  T  F      F  F  F      T  How does one obtain this truth table? If it is an axiom, what is the motivation behind this particular form?
78501
In Chiswell's Mathematical Logic, there is the following problem is posed using the language of propositions (LP):     In some systems of logic (mostly constructive systems where 'true' is taken to mean 'provable') there is a rule      if $(\Gamma\vdash(\phi\,\lor\psi))$ is a correct sequent then at least   one of $(\Gamma\vdash\phi)$ and $(\Gamma\vdash\psi)$ is also correct.      By giving a counterexample to a particular instance, show that this is   unacceptable as a rule for LP. [Start by giving counterexamples for   both the sequents $(\vdash p_0)$ and $(\vdash(\neg p_0))$.]   In my , it was answered that one can let $\Gamma = \{p_0\,\lor\,(\neg p_0)\}$.  From there, one can deduce neither $(\Gamma\vdash p_0)$ nor $(\Gamma\vdash (\neg p_0))$.  But this does not proceed by the counterexample route that the author suggests.  Namely, he seems to imply that we should (1) take an interpretation of propositional variables $p_0,\,p_1,\,\ldots$ (setting each one equal to T or F), and (2) write $\phi$ and $\psi$ as functions of these propositional variables, and (3) pick sentences for $\Gamma$ which are all T, all with the conditions that (A) $(\phi\,\lor\psi)$ is evaluated as T, yet (B) both $\phi$ and $\psi$ are evaluated as F.  This, of course, seems impossible.  What, then, am I missing?  It seems that taking a concrete interpretation of the propositional symbols makes the constructivist's rule irrefutable.  (Note: this is supposed to be a very simple problem set, and I am an elementary logician).
24726
In my textbook I am introduced to two ways to prove that a set of connectives is functionally incomplete. The first one is to prove that it has a property that not all truth functions do.  I am stuck at finding one such property for $\{\lnot\}$ (and I can't believe I am so dumb to be stuck...). I have two ideas: first one is to prove that $\lnot$ always returns a $F$ for any true argument (thus rendering a truth function that returns $T$ from a true arugment impossible).      Prove that if $\phi$ is built up using the variable $P$ with $\lnot$, and $v$ is the truth assignment s.t. $v(p)=T$, then $v(\phi)=F$.      Induction on the number $n$ of connectives in $\phi$.      Base case $n=0$: $\phi=P$ - there isn't any $\lnot$ to talk about, so it is vacuously true.      Assume that it holds true for $\le n$, prove that it holds true for $n+1$.      $\phi=\lnot \psi$: Number of connectives within $\psi=n$, thus it holds true for $\psi$. Therefore $v(p)=T\to v(\psi)=F$.   As you can see, if $v(\psi)=F$, then $v(\phi)=v(\lnot \psi)=T$, which is not what we want. This seems to be an instance of double negation; it can flip whatever truth value to the opposite, so it seems futile to try and show that there is a truth function $\{\lnot\}$ cannot show, because with double negation you can always show a $T/F$.  The second idea to show that a negation can only show a truth function with one argument, but not one with more than one. But this seems only to be a syntactical problem: yes, you can't show a formula of $&gt;1$ variables with only negation, but you can still draw a truth table for it nonetheless.  So my first question is,      1) what went wrong with my proof, and how to prove $\{\lnot\}$ is functionally incomplete by showing a property that only this set has?     The second way is to show how many truth functions of $n$ arguments can be represented; if this number is $&lt;2^{2^n}$, then it is not complete; vice versa.  The book showed how to use this approach to prove that $\{\land\}$ is incomplete. The number for this set is $2^n -1$. My question is,      2) how do we know the number for $\{\lnot,\land,\lor\}=2^{2^n}$?    It must be so since it is complete, but I just don't know how to prove it.   (The book equivalated formulas $\phi$ built up using variables in the set $\{p_1, p_2, . . . , p_n\}$ to a normal form where no parenthesis remains and only variables are left, and explained that the number of non-empty subsets of this set of variables used to build the normal form $=2^n -1$. e.g. $\phi=(p_3\land p_1)\land (p_2\land(p_1\land p_4))$, normal form=$p_1\land p_2 \land p_3 \land p_4$)  Really appreciate any help offered!
34301
My understanding of logic is really basic, and I ask this question out of curiosity.  Is there an explicit example of a statement whose proof uses the continuum hypothesis and is unprovable in $ZFC + \lnot CH$.   ADDED: Preferably I'm looking for an example outside set theory.
71608
I am not able to understand implication well. I can see If in $P \implies Q$, if Pis true and Q is false then implication is false. But i cannot understand other cases where it is taken as true. Is this just a convention ? or some underlying reasoning behind it  Thanks
96596
I know that we can prove a contradiction in naive set theory.  Let D be a set of all sets that don't contain itself. Say D does not contain D. Then D contains D. That means D contains itself. A contradiction. Hence, D contains D. But that means D doesn't contain itself. That means D doesn't contain D again. But we presume D contains D. So another contradiction. Because either D contains itself and D does not contain itself is false, we're pretty much stuck.  So, set theory is pretty much upgraded to kingdom come to prevent this so called contradiction. I am still unsure how after so much upgrade the contradiction is gone.  How do we know that there will be no contradiction for group or other theory? How do I know if that from some axioms like commutative, associative, have identity, etc. suddenly I found out that A is a group and not a group or something like that.  Note: The problem with one contradiction is if you can proof one you can proof anything. Say I want to proof 1=0. Say 1 is not 0. Now, let Z be a set of all sets that doesn't contain it self. Yada yada yada... Contradiction. Hence, 1=0. The sun also rises in the west (at least for the last 300 years)
68799
Recently I finished my first pure mathematics course but with some intrigue about some proofs of definitions by contradiction and contrapositive but not direct proofs (the existence of infinite primes for example), I think most of them because the direct proof extends away from a first mathematics course or the proofs by contradiction/contrapositive are more didactic. The one that most bothers me in particular is the demonstration that the empty set is a subset of every set, and it is unique. I understand the uniqueness and understand the proof by contradiction:  "Suppose $\emptyset \subsetneq A$ where $A$ is a set. So it exists an element $x \in \emptyset$ such that $x \notin A$ wich is absurd because $\emptyset$ does not have any elements by definition."  but I would like to know if there exists a direct proof of this and if indeed extends from a first course. Thanks beforehand.
92080
Given two statements, $P$ and $Q$, and the logical connective, $\implies$, the truth table for $P \implies Q$ is:  $$\begin{array}{ c | c || c | }   P &amp; Q &amp; P\Rightarrow Q \\ \hline   \text T &amp; \text T &amp; \text T \\   \text T &amp; \text F &amp; \text F \\   \text F &amp; \text T &amp; \text T \\   \text F &amp; \text F &amp; \text T  \end{array}$$  Lines one and two are quite clear. What is ambiguous is lines three and four.  One explanation as to why $P \implies Q$ is true when $P$ is false, provided by Velleman goes:     Let $P(x)$ be the statement $x&gt;2$ and $Q(x)$, $x^2 &gt; 4$. When $x=3$, $P$ is true, and $Q(x) = 9$ thus $Q$ is true. If $P(x) = 1$ then $Q(x) = 1$ and they are both false. If $P(x) = -3$ then $Q(x) = 9$ and so the statement is true.   This explanation was quite unsatisfactory to me. Looking at Enderton, we have:     For example, we might translate the English sentence, ”If you're telling the truth then I'm a monkey's uncle,” by the formula ($V \implies M$). We assign this formula the value $T$ whenever you are fibbing. In assigning the value $T$, we are certainly not assigning any causal connection between your veracity and any simian features of my nephews or nieces. The sentence in question is a conditional statement. It makes an assertion about my relatives provided a certain condition — that you are telling the truth — is met. Whenever that condition fails, the statement is vacuously true.      Very roughly, we can think of a conditional formula ($p\implies q$) as expressing a promise that if a certain condition is met (viz., that $p$ is true), then q is true. If the condition $p$ turns out not to be met, then the promise stands unbroken, regardless of $q$.   Though a significant improvement over the Velleman explanation, I still feel uncomfortable with it.  Really, it seems we can conjure up as many silly counter-examples as we like, such as:     If pigs can fly, then I can walk on water.   Though following the above truth table, the implication is that my ability to walk on water is true.  After considering it, it seems to me that $\implies$ is only meaningful when $P$ is true, then we can look at it in relation to $Q$. However, if $P$ is false, then we actually know nothing about the relationship between $P$ and $Q$. This would give a truth table of:  $$\begin{array}{ c | c || c | }   P &amp; Q &amp; P\Rightarrow Q \\ \hline   \text T &amp; \text T &amp; \text T \\   \text T &amp; \text F &amp; \text F \\   \text F &amp; \text T &amp; \text ? \\   \text F &amp; \text F &amp; \text ?  \end{array}$$  where the $?$ denotes that given $P$ we actually don't know anything about $ \implies $.  Thus. one way to clear this up would be to assume that $? = T$. Thus the vacuous truth is a "definition of convenience" in a sense.  The above is my take on the matter.  Could someone provide some clarification on the conditional logical connective?
46677
From: Philip Johnson-Laird , Stuart Professor of Psychology Emeritus at Princeton.    (Author isn't  a logician.)    . p. 44.       For premises that have several models, a single model consistent with   them—an example—establishes a conclusion about what is possible; but   all the models must be examples to establish a conclusion about what is   necessary. The opposite is the case for refutations: a single counterexample   refutes a conclusion about what is necessary, whereas all models must be   counterexamples to refute a conclusion about what is possible. And so we   should draw a conclusion about what’s possible faster than a conclusion about   what’s necessary, but we should draw a conclusion about what’s not necessary   faster than a conclusion about what’s not possible. This prediction is crucial for   a theory that takes possibilities as fundamental, and several experiments have   p. 45     corroborated it. One caveat, learned the hard way, is that it’s no use asking   adults whether something is possible if it's [Author's bungle. This ought be "its".] necessity is obvious. They baulk   at saying, “yes”, in these circumstances; and so inferences have to be hard   enough that when an event is possible its necessity isn’t obvious too. Here is   a typical trial from an experiment. The premises are about a game of one-on-one basketball in which two players take part:           [1.] If Allan is in [the game] then Betsy is in.     [2.] If Carla is in then David is out.            The participants were more accurate and faster to infer that Betsy could be in   the game than to infer that she must be in the game. If you list the possible   games compatible with the premises, you’ll discover that there are three games   and that Betsy is in all of them: Allan versus Betsy, Betsy versus Carla, Betsy   versus David.      I refer to the players by only their initials.    Why are A vs. C and A vs. D impossible?  How can you efficiently deduce the emboldened sentence, without applying 1 and 2 to each person separately in order (1st: Alan v. B, C, D. 2nd: B v. C, D. 3rd: C v. D)?
59562
So, I don't like proofs.  To me building a proof feels like constructing a steel trap out of arguments to make true what you're trying to assert.  Oftentimes the proof in the book is something that I get if I study, but hard to come up with on my own.  In other words I can't make steel traps, but I feel fine buying them from others.  How does one acquire the ability to create steel traps with fluency and ease?  Are there any particular reference books that you found helped you really get how to construct a proof fluently?  Or is it just practice?