I am a linguist and not a mathematician. If I was an expert mathematician, I wouldn't need your help.  In response to a query in a comment about when if P, Q is true, I recently was told by @amWhy:   "If P then Q" (P→Q) is true whenever P is false, or Q is true (or both).   This was in response to a comment on this question here:      (You will only be able to see this post if you have a very large reputation score)  Now this interpretation is one of many mathematical (not all very simple) interpretations of when If P, Q is true. What I would like to know is whether the following sentence is true, if it is said about a particular number which as been written down on a specific piece of paper:   If the number written on the paper is divisible by 9, it is divisible by 3.   In particular, suppose the number which is written on the paper is 4, is the sentence true?
123933
I am not a mathematician, I'm a linguistics PhD student. As part of my research I need to put various convoluted sentences through various syntactic transformations and see then check whether people think they are true or not. Mathematical statements (well, some of them) suit my purposes very well, because they are less context dependent and can be straightforwardly assigned a truth value (i.e. be deemed true or false). The problem is that I'm not a mathematician. When these sentences get a bit convoluted, I have a bit of a problem knowing whether they are true or false myself (before they undergo various syntactic transformations).   I have a particular sentence which states that if a given number is:   an integer divisible by 7 (meaning it will yield an integer if divided by 7) a square number   then it is divisible by 49. I intuitively believe this to be correct (although I can't explain why). Is this actually true? I don't want to waste everybody's time by starting with an untrue untransformed sentence.
47928
Determine if this is true or not:  For any natural numbers $a$, $b$, $c$, and $d$, if $a | c$ and $b | d$ then $ab|cd$.  My answer was True, I went:  $a = 2$, $b = 4$, $c = 6$, and $d = 8$. If $2|6$ and $4|8$, then $(2 * 4) | (6 * 8)$.  Is there another way to do it using, for example, a contradiction proof?
79184
Excerpt from a mathematical proof that serves to prove by contradiction, using the Well Ordered Principle, that predicate P(n) is true for all nonzero integers n.     If n belongs to set C i.e. n >= c, then P(n) is false.      This implies the contrapositive,      If P(n) is true, n has to not be a part of set C i.e n &lt; c.   I know that the above implication is valid but why so? How should I know that n cannot take on 2 values simultaneously -- n being both >= c and &lt; c, thus P(n) being both true and false simultaneously? (Yes I am thinking Dialetheism, maybe even quantum logic but I know nothing other than that quantum logic defies certain aspects of propositional logic.) What is the basis behind a predicate (or any proposition) being either true or false? Or would the simultaneity be possible just that I wouldn't be dealing with a proposition to begin with?  Also, if you don't mind, please do let me know if you feel my understanding of concepts and terminologies (i.e. discrete, predicate, contrapositive, assume) are erroneous. I am extremely new to discrete mathematics and could really use the extra guidance.  Thank you.
119953
I am having trouble proving the two following questions:    If $p|N$, $q|N$ and gcd(p,q)=1, then prove that $pq|N$ If $x$ is non zero positive integer number, then prove that $3|x$ if and only if 3 divides the sum of all digits of $x$.   For both questions I tried to use theorems of discrete mathematics, but I could not find the way to solve them.
62177
How is the statement $\bot \to \top$ true? If, for example, I take the statement  $P = 2$ is an odd number $Q = 5$ is an odd number Then $P$ is false and $Q$ is true.  Clearly, false implies true translates to  if $2$ is an odd number then 5 is an odd number  which means that  if $2$ is not an odd number (i.e. even) then $5$ is not an odd number  which is clearly false as $2$ is indeed an even number. Please help me to find what I’m missing out in this. Thanks for your help!
4112
I am currently reading the paper "PRIMES is in p" and have come across some notation that I don't quite understand in this following sentence     Consider a prime $q$ that is a factor of $n$ and let $q^k || n$. Then...   What does the notation $q^k || n$ mean here?  The full paper can be found  and the notation described above is used in the proof on page 2
24677
Let $a\in \mathbb{Z}$ be such that $a=b^2+c^2$ where, $b,c \in \mathbb{Z}-\{0\}$. Then $a$ cannot be written as    $pd^2$ where $d \in \mathbb{Z}$ and $p$ is prime with $p \equiv 1~(mod~4)$ $pd^2$ where $d \in \mathbb{Z}$ and $p$ is prime with $p \equiv 3~(mod~4)$ $pqd^2$ where $d \in \mathbb{Z}$ and $p,q$ are primes with $p \equiv 1~(mod~4)$ and $q \equiv 3~(mod~4)$ $pqd^2$ where $d \in \mathbb{Z}$ and $p,q$ are primes with $p,q \equiv 3~(mod~4)$   The similar question with some part missing is asked , but I want to discuss additional options too.  Here, I got 1) is false Since $13=3^2+2^2$ For other options What should I do
85088
Every lecture that I watched on mathematical logic and my textbook say that $P \Rightarrow Q$ has the same meaning  as $\text{"If $P$ then $Q$"}$ which has the same meaning as $\text{$Q$ only if $P$}$.   How does " $\text{if $P$ then $Q$}$ " have the same meaning as " $\text{$Q$ only if $P$}$  ?   i think that is not true. For instance, let $P = \text{a human $x$ killed human $y$}$  and $Q = \text{the human $x$ will be arrested}$.   Then $P \Rightarrow Q$ means $(\text{a human $x$ killed human $y$})  \Rightarrow (\text{the human $x$ will be arrested})$ which means  $$\text{if a human $x$ killed human $y$, then the human $x$ will be arrested} \quad (1)$$  but if we say ,   $$\text{a human $x$ will be arrested, only if the human $x$ killed human $y$} \quad (2)$$  then the meaning of (1) differs from (2). Statement (2) says that the human $x$ will be arrested in only one case which is killing $y$.
118996
I would like to know if someone can explain in a somehow down to earth (almost logic free) way why is it true that in an axiom system where there is some statement $P$ such that $P$ and its negation $\lnot P$ are true, then every statement in the system is true?  I'm not sure if this can be done, but basically since I don't know any formal logic at all, I'm interested in seeing if at least the argument can be conveyed in an intuitive way, or if the idea can be explained without talking about first or second order logic and using symbols like $\top$, $\bot$, and $\vdash$.  This  is like the formal version (which I don't understand) so maybe my question can be thought of as a version for dummies of that question.   Thanks a lot in advance.
14267
Often, when I try to describe mathematics to the layman, I find myself struggling to convince them of the importance and consequence of "proof". I receive responses like: "surely if Collatz is true up to $20×2^{58}$, then it must always be true?"; and "the sequence of number of edges on a complete graph starts $0,1,3,6,10$, so the next term must be 15 etc."  Granted, this second statement is less logically unsound than the first since it's not difficult to see the reason why the sequence must continue as such; nevertheless, the statement was made on a premise that boils down to "interesting patterns must always continue".  I try to counter this logic by creating a ridiculous argument like "the numbers $1,2,3,4,5$ are less than $100$, so surely all numbers are", but this usually fails to be convincing.  So, are there any examples of non-trivial patterns that appear to be true for a large number of small cases, but then fail for some larger case? A good answer to this question should:   be one which could be explained to the layman without having to subject them to a 24 lecture course of background material, and have as a minimal counterexample a case which cannot (feasibly) be checked without the use of a computer.   I believe conditions 1. and 2. make my question specific enough to have in some sense a "right" (or at least a "not wrong") answer; but I'd be happy to clarify if this is not the case. I suppose I'm expecting an answer to come from number theory, but can see that areas like graph theory, combinatorics more generally and set theory could potentially offer suitable answers.
22623
I'd like to have my proof verified and if possible, to see other solutions that are interesting.  Proof: Suppose $n(n+1)$ is a square. Then we write $$n(n+1) = \prod_{p} p^{c(p)}$$ where $c(p) = a(p) + b(p)$ are such that \begin{align*} n &amp;= \prod_p p^{a(p)} \\ n+1 &amp;= \prod_p p^{b(p)} \end{align*} Now, by our hypothesis, $c(p)$ is even for all primes $p$. As $(n,n+1)=1$ for all $n$, it must be that $a(p)$ and $b(p)$ are even for all primes $p$ and moreover, $a(p) = 0$ whenever $b(p)&gt;0$ and reversely.  This indicates that both $n$ and $n+1$ are squares. This is impossible as there are no consecutive squares in the natural numbers.
17837
I studied propositional logic, and everyday I see applications of what I learned on the internet, in mathematical books and miscelaneous resources.        One particular case is sentences in the form $a \rightarrow b$ , that is, material implications. While I fully understand the mathematical logic approach to the study of those kinds of formulas, sometimes I get confused about what someone ( using implication sentences in the ordinary language ) is trying to say.        In ordinary language, I often see affirmations in the form of an implication.  One example would be someone affirming that "the moon is made of cheese" $\rightarrow 2+2=4$. [ Kleene, Mathematical Logic ].      I perfectly understand that if we choose the interpretation that gives the antecedent as false ( and the consequent as true ) we get that the whole implication is also true, but I would like to understand EXACTLY what he is trying to say when he AFFIRMS a sentence in the form of an implication. Is he saying that under the commonly agreed interpretation of that sentence ( antecedent = false, consequent = true ), that implication becomes true?      Another example, totally different, would be someone affirming that $x \in \mathbb{N} \rightarrow x \in \mathbb{N}$ or $x \in \mathbb{Z}_{&lt;0}$. Is he now affirming the same kind of sentence or saying something totally different?      When he affirms that sentence, is he saying that he finds the sentence to be a tautology?   Why didn't he say that?          Then, with these two examples we have an affirmation of the same kind of sentence (implication) meaning completely different things, in one case he affirms to say that under the commonly agreed interpretation of the sentence, it is true. In another case, he affirms to say that there's no interpretation that makes the sentence false.       Am I missing something? There is really that ambiguity in ordinary language, when people are affirming sentences?  Can't I just take some general instance of the affirmation of a sentence in the form $a \rightarrow b$ in ordinary language and know exactly what he's trying to say, regardless of the propositions he chooses the substitute $a$ and $b$ for?       Thanks a bunch.
53285
I found this proposition and don't see exactly as to why it is true and even more so, why the converse is false:  Proposition 1. The equivalence between the proposition $z \in D$ and the proposition $(\exists x \in D)x = z$ is provable from the definitory equations of the existential quantifier and of the equality relation. If $D = \{t_{1},t_{2},...t_{n}\}$, the sequent $z = t_{1} \vee z = t_{2} \vee z \vee ... z = t_{n}  \vdash z \in D$ is provable from the definition of the additive disjunction $\vee$.  The converse sequent $z \in D \vdash z = t_{1} \vee z = t_{2} \vee ... z = t_{n}$ is not provable.  The author goes on to say:  "We adopt the intuitionistic interpretation of disjunction. With respect to it, one can characterize a particular class of finite sets"  On the first part of the proposition, well I am not sure what the point is as if we take an element z in D, then we could just call this element x and hence this x = z.  Is there something more to this?  On the second part of Proposition 1 since $z = \text{ some } t \in D$ since t is in the set of axioms and $t = z$, then $t \vdash z$ as z is derivable from t.  For the converse if $z \in D$ then why wouldn't z = some $t \in D$?  Is this because of the Incompleteness theorem?  That perhaps there D as a set of axioms has some consequence which can not be proven by the set of axioms in D?  Or perhaps I am way off here.  Any ideas?  Thanks,  Brian
49089
If the union of two theories is not consistent there exists a sentence $P$ for which one of them implies $P$ and the other one implies $\lnot P$.  Can someone please check if this is true or not?  I used to prove this by contradiction. I assumed for every sentence $P$, if $T_1$ implies $P$, then $T_2$ satisfies $P$ or $T_2$ doesn't imply $P$ but never $T_2$ implies $\lnot P$. So i think there exists a model of $T_2$ as a substructure of a model of $T_1$( i'm not sure if this is true... I just say it intuitively ), so I take that model of $T_1$ as a model of  $T_1 \cup T_2$. Since the union doesn't have a model so there exists a sentence $P$ such that $T_1$ implies $P$ and $T_2$ implies the $\lnot P$.
49575
I am currently doing the Intro to Mathematical Thinking course on Coursera. A quiz therein, asks:  For what truth values of Φ and Ψ do we define Φ ⇏ Ψ to be T (true)?  It says the right answer is Φ is true and Ψ is false.  I understand that; but I do not follow why the reverse is not right. That is, why does Φ false and Ψ true does not make the statement Φ ⇏ Ψ to be true.  I am confused because if Ψ is true while Φ is false, the truth of Ψ does not follow from the truth of Φ and so it should be that Φ ⇏ Ψ. Could someone please explain?
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?
66158
First, I apologise for the vague title. I couldn't think of a short way to represent the problem. Also, I am aware that a similar question exists, but I have a little bit more insight.  The problem is:      A man is known to speak the truth three out of four times. He throws a   die and reports that it is a six. Find the probability that it   actually is a six.   The answer in the book is $ \frac{3}{8} $, which sounds completely off to me, given the numbers, on first glance. I decided to try it on my own. After some contemplation, it indeed is true that $ \frac{3}{8} $ is correct. But, the question's vagueness makes it interesting. It's sort of a naive answer!  First, here's the book's solution:  Let $ E $ be the event that the man reports that a six occurs, $ S_1 $ be the event that six occurs and $ S_2 $ be the event that six does not occur.  $ P(S_1) $ = Probability that six occurs = $ \frac{1}{6} $  $ P(S_2) $ = Probability that six does not occur = $ \frac{5}{6} $  $ P(E~|S_1) $ = Probability that the man reports that a six occurred when it has actually occurred (truth) = $ \frac{3}{4} $  $ P(E~|S_2) $ = Probability that the man reports that a six occurred when it hasn't actually occurred = $ \frac{1}{4} $  $ P(S_1|E) $ = Probability that a six has actually occurred when the man claims so =  $$ \frac{P(S_1)~P(E~|S1)}{P(S_1)~P(E~|S_1)+P(S_2)~P(E~|S_2)} = \frac{3}{8} $$  Link to original: Page 25 of  (link updated 22/11/2015; tends to break often).  Here's the first of my two solutions:    The question is a little vague and it doesn't tell us what the man says when he doesn't get a six. Assuming he lies every time he doesn't get a six (which is not quite what the question says), would bring up $ P(E~|S_2) $ to $ 1 $, which skyrockets $ P(lie) $ to $ \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6}.\frac{1}{4} = \frac{7}{8} $.  Also, $ P(E~|S_1) = \frac{3}{4} $ and $ P(E) = \frac{5}{6} + \frac{1}{6}.\frac{3}{4} = \frac{23}{24} $.  This brings us to, $$ P(S_1|E) = \frac{P(S_1)P(E~|S_1)}{P(E)} = \frac{3}{23} = 13.04\% $$  Please note that I don't care about the sixes rolled when he lies about it being a six, because that condition is not applicable to the question.  I'm very skeptical about my calculations! I decided to whip up a simple program and see what the probability distribution is for $$ \frac{Number~of~sixes~rolled~while ~saying~it's~a~six}{Number~of~dice~rolls} $$  Here's the result:    Considering the book says $ P(E~|S_2) = \frac{1}{4} $, which is in essence is contradictory to the question, let's also consider the other possibility:    It's even more vague in this scenario! If the man lies after any given roll, there is a $ \frac{1}{5} $ probability that he will lie about it being any other number. This creates a new branch at each lie, which splits into five. In this case,  $$ P(E) = \frac{1}{6}.\frac{1}{4}.\frac{1}{5}.\frac{5}{1}+\frac{1}{6}.\frac{3}{4} =  \frac{1}{6} $$  $ P(E~|S_1) $ still remains $ \frac{3}{4} $, but $ P(E~|S_2) = \frac{1}{4}.\frac{1}{5} = \frac{1}{20} $.  $$ P(S_1|E) = \frac{P(S_1)P(E~|S_1)}{P(E)} = \frac{3}{4} = 75\% $$  This seems like the more intuitive answer, and it is why I doubted the original answer in the first place. Given a truth probability of $ \frac{3}{4} $, there was no way that the probability of a six was $ 37.5\% $!    The ambiguity of the question is what makes $ \frac{3}{8} $ wrong to me. Entirely out of curiosity, which answer fits best with the question and are these calculations correct or baloney?