On  in XI Free Models and Logic Programming of Ebbinghaus' Mathematical Logic:  In general, the following statement is false: (*)  If $\Phi \vdash \exists x \phi$  then there is a term $t$  with $\Phi \vdash \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\} \vdash \exists x R x $, then there is no term $t$   with $\{\exists x Rx\} \vdash R t $? On  or  the $(\exists S)$ sequent rule says $$  \frac{\Gamma \quad \phi \frac{t}{x}}{\Gamma \quad \exists x \phi}$$ Is this $(\exists S)$ rule the converse of (*) in the quote at the beginning? Thanks. I mistook $\vdash$ as $\models$ in
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.
87884
I have a mathematical proposition of the form "If $A$, then $B$". I'm thinking about this problem from several different perspectives, so I will segment these different perspectives into separate paragraphs as follows.   If I have a statement $A \implies B$ that is true by definition (no proof provided), is it then correct to say that the contrapositive statement $\neg B \implies \neg A$ (NOT $B \implies$ NOT $A$) must also be true, without providing any proof?  In other words, if $A \implies B$ that is true by definition, then does this imply that the contrapositive statement $\neg B \implies \neg A$ is also true by definition? Trying to think of this from the perspective of logic notation and truth tables, would it be correct to write that $(A \implies B) \implies (\neg B \implies \neg A)$? This way, since we know that $A \implies B$ is true, we must logically have (according to truth tables) that $\neg B \implies \neg A$ is also true, right?   I would greatly appreciate it if people would please take the time to clarify this.
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)?
121041
Given the set of standard axioms (I'm not asking for proof of those), do we know for sure that a proof exists for all unproven theorems? For example, I believe the Goldbach Conjecture is not proven even though we "consider" it true.  Phrased another way, have we proven that if a mathematical statement is true, a proof of it exists? That, therefore, anything that is true can be proven, and anything that cannot be proven is not true? Or, is there a counterexample to that statement?  If it hasn't been proven either way, do we have a strong idea one way or the other? Is it generally thought that some theorems can have no proof, or not?
109026
Given $x$ occurs free in $P$. If $x$ does not occur free in $Q$, then $∀x(P(x)→Q)$ is semantically equivalent with $∃xP(x)→Q$. How to understand this statement. And also, need an example to show that the formula will not necessarily be equivalent if $x$ does occur free in $Q$.  I guess what struggles me is I'm not quite understand what does "free" mean in this case. But it would be better to have answer for the above question.
11482
Using the Fitch system, how do I prove $((p \implies q) \implies p)\implies p$? I started with the hypotheses $(p \implies q) \implies p$ and $\sim p$. However, from these hypotheses I did not get the desired contradiction to solve the question.  Thanks sb45
69943
I found a statement that says  $$\forall x[P(x) \rightarrow Q] \equiv \exists x[P(x)] \rightarrow Q$$  Where $Q$ is a formula that does not contain $x$. I need to know when exactly would the equivalence hold. Can we just convert $\forall$ quantifiers to $\exists$. Is there a way to prove the right hand side statement from the left hand side?
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.
82384
The answer seems to be yes, judging from the following exercise I found in the book Mathematical Logic by H.D. Ebbinghaus, J. Flum, and W. Thomas:     Let $S$ be a finite symbol set and let $\mathfrak{U}$ be a finite $S$-structure. Show that there is an $S$-sentence $\varphi _{\mathfrak{U}}$ the models of which are precisely the $S$-structures isomorphic to $\mathfrak{U}$.   I think I have an idea of how to solve this exercise, but I seem to be unable to materialize it. Thanks.
81369
I was recently reading Griffiths' Introduction to Quantum Mechanics, and I stuck upon a following sentence:     but $\Psi$ must go to zero as $x$ goes to $\pm\infty$ - otherwise the wave function would not be normalizable.   The author also added a footer: "A good mathematician can supply you with pathological counterexamples, but they do not arise in physics (...)".  Can anybody give such a counterexample?
9495
Here is something I'm trying to prove:     Conjecture: Suppose $f'(x) \leq \phi(f(x), x)$ and $f(a)=\alpha$. Suppose $g'(x)=\phi(g(x),x)$ and $g(a)\geq \alpha$. Then $f(x)\leq  g(x)\,\,\forall x$.   It definitely seems like it should be true, and I don't think we even need continuity of $\phi$.  (Edit: a user has correctly pointed out that we should require $\phi$ be locally Lipshitz in the first variable, uniformly with respect to the second variable. Let's add that assumption.)   I can prove it in the case that the inequality is strict. I'll place my proof below the fold. How can I extend it to weak inequality?  If it's wrong, I'd love to see a counterexample. A reference is fine; I have the book by Teschl, for example.  A similar question with stronger assumptions was asked .     Proposition: Suppose Suppose $f'(x) &lt; \phi(f(x), x)$ and $f(a)=\alpha$. Suppose $g'(x)=\phi(g(x),x)$ and $g(a)\geq \alpha$. Then $f(x)\leq  g(x)\,\,\forall x$.  Proof: Suppose not. Suppose WLOG there is a $b&gt;a$ such that $f(b)&gt;g(b)$. Let $c:=\inf \{x&gt;a:f(x)&gt;g(x)\}$. By definition of the derivative we have $f'(c)\geq g'(c)$, a contradiction, since $f'(c)&lt;\phi(f(c),c)=\phi(g(c),c))=g'(c)$.
84831
Can you answer me , please.  1- Show that (p→r)∧(q→r) and (p∨q)→r are logically equivalent  2- show that (p → r) ∨ (q → r) and (p ∧ q) → r are logically equivalent  without truth table .
101067
This is exercise 1.2.19 from Chang &amp; Keisler's Model Theory, which has been giving me a headache for some time now.  Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. the set of sentence symbols is allowed to have any cardinality). Call a theory simply any set $\Gamma$ of sentences from $\mathscr{S}$. A set $\Delta$ of sentences is said to be a set of axioms for $\Gamma$ iff $\Gamma$ and $\Delta$ have the same consequences (i.e. they are equivalent). Finally, a set $\Sigma$ of sentences is said to be independent iff for each $\sigma \in \Sigma$, $\sigma$ is not a consequence of $\Sigma - \{\sigma\}$. Exercise 1.2.19 asks us to prove that a theory $\Gamma$ always has an independent set of axioms.  Now, if $|\Gamma| \leq \omega$, the proof is more or less simple; for the finite case, cf. , whereas, if $\Gamma = \{\gamma_0, \gamma_1, \dots\}$, one first constructs a set $\Gamma' = \{\psi_0, \psi_1, \dots\}$ such that $\psi_0 = \sigma_0$ and $\psi_n = \bigwedge_{i \leq n} \sigma_n$ (i.e. the conjunction of all $\sigma_i$ such that $i \leq n$). Then one constructs another set $\Delta = \{\delta_0, \delta_1, \delta_2, \dots\}$ such that $\delta_0 = \psi_0$ and $\delta_{n+1} = \psi_n \rightarrow \psi_{n+1}$. It's not difficult to show that $\Gamma'$ is a set of axioms for $\Gamma$ and that $\Delta$ is an independent set of axioms for $\Gamma'$.  But I'm completely lost about how to proceed in the transfinite case. It's clear to me that the above construction will not work directly; any ideas about how to adapt that strategy? Or should I look for an entirely different strategy?  EDIT: Notice that this question is different from ; the other question (and answer) is only asking about the countable case, the solution of which I have already provided a rough sketch in my own question. The general case, however, for theories of any cardinality, is, as C&amp;K remark, much harder.
7756
Problem. Let $(\mathscr{L},\vdash)$ be a logic and $\Gamma\subseteq\mathscr{L}$ be a set of formulas such that for some $\varphi\in\mathscr{L}$ we have $$\Gamma\vdash\varphi\to\neg\varphi$$ $$\Gamma\vdash\neg\varphi\to\varphi$$Then show that, $$\Gamma\vdash(\varphi\to\neg\varphi)\to\varphi$$using only the following, $\color{crimson}{\text{Axiom 1.}}\  P\to (Q\to P)$ $\color{crimson}{\text{Axiom 2.}}\  (S\to (P\to Q))\to((S\to P)\to (S\to Q))$ $\color{crimson}{\text{Axiom 3.}}\  (\neg Q\to\neg P)\to(P\to Q)$ $\color{crimson}{\text{Rule of Inference.}}$ . $\color{crimson}{\text{Theorem.}}$ .  I have tried for some hours to find a proof of the claim but couldn't succeed. Can anyone help?
57788
I have the following problem from the book "How to Prove it" by Daniel J.Velleman.  Prove that $$ \exists z\in \mathbb{R} \forall x \in \mathbb{R}^+ \left[\exists y \in \mathbb{R} (y-x=y/x) \leftrightarrow x \neq z \right]. $$  I have no idea how to deal with the existential quantifier at the beginning. I tried to negate it, but the rest is too complicated. Do you have strategic hints how to proceed? Allowed is first-order logic.  EDIT  Based and the response, I would propose the following proof and kindly ask the community to check if it is correct.  Proof: Let $z=1$, and let x be some arbitrary real number.   $(\rightarrow)$ Suppose $\exists y \in \mathbb{R} (y-x=y/x)$ and choose $y_0$ to be some real number such that $(y_0-x=y_0/x)$. Suppose $x=z$. Since $x=z$ and $z=1$, $x=1$. However, plugging $x=1$ into $y_0-x=y_0/x$ yields a contradiction, and thus, $x\neq z$. Hence, $\exists y \in \mathbb{R} (y-x=y/x) \rightarrow x \neq z$. Since $x$ was arbitrary, it follows that $\forall x \in \mathbb{R}^+ \left[\exists y \in \mathbb{R} (y-x=y/x) \rightarrow x \neq z \right]$. ($\leftarrow$) Suppose $x \neq z$. Since $z=1$, $x \neq 1$. Let $y_0=\frac{x^2}{x-1}$, which is defined because $x \neq 1$. Plugging into the equation $y_0-x=y_0/x$, we can verify that the equation holds for this particular value $y_0$. Hence, $x \neq z \rightarrow \exists y \in \mathbb{R} (y-x=y/x)$. Since x was arbitrary, it follows that $\forall x \in \mathbb{R}^+ \left[\exists y \in \mathbb{R} (y-x=y/x) \leftarrow x \neq z \right]$.   Therefore, the theorem follows.
111322
Show Kripke's model proving that the following formula isn't tautology in intuitionistic logic. $ \neg ( p \wedge q ) \implies (\neg p \vee \neg q) $  Please help/hint me ;)
75256
My current understanding:  $\vdash$ is "syntactic consequence", e.g. if we have $a \vdash b$ it means if we've written down $a$ as something we know, we can immediately write down $b$ as something we know. This is saying nothing about whether any of these pieces are true, false, something else, etc, it's just saying that we can say something about $b$ by virtue of being able to say something about $a$.  $\vDash$ is "semantic consequence", e.g. if we have $a \vDash b$, then it (usually) means if $a$ is always true in every interpretation (i.e. no matter how we mess with any of the underlying variables driving $a$'s valuation), then $b$ is true as well. However I don't know if this is necessarily just a "true"-only thing. It seems conceivable that we could make one for falsehoods too, i.e. if $a \vDash b$ might mean if $a$ is always false then $b$ is always false, of if $a$ is always "dog" then $b$ is always "dog", etc. But I am unsure of this one.  $\to$ is material implication, which exists solely within the logic system (as opposed to the previous two metalogical relations) and has a specific semantic meaning / definition in terms of a truth table in something like prepositional logic ($a \to b$ is always true unless $a$ is true and $b$ is false). It's defined this way simply because it is a helpful / useful model to describe things like "whenever $a$ is true, $b$ is true".  Do I have the right idea so far?