Tag Info

New answers tagged

1

See Stephen Cole Kleene, Mathematical logic (1967 - Dover ed 2002), page 293 : $\forall x \lnot R(x,x) \land \forall x \forall y \forall z (R(x,y) \land R(y,z) \to R(x,z)) \land \forall x \exists y R(x,y)$.


1

Given any sentence with equality which is satisfied only in infinite structures, you can get one without equality by replacing $=$ with an equivalence relation everywhere. That is, replace every instance of $=$ by a new binary relation symbol $R$ and add a subsentence saying $R$ is an equivalence relation to your sentence.


1

Here's another way to think about it. Starting from the assumption: $$\lnot R \rightarrow (P \rightarrow \lnot Q)$$ $$R \lor (P \rightarrow \lnot Q) $$ $$ R \lor (\lnot P \lor \lnot Q)$$ $$ (R \lor \lnot P) \lor (R \lor \lnot Q) $$ Now, assume $P$. We have two cases: $R\lor \lnot P$ or $R \lor \lnot Q$. If we assume the former, $R \lor \lnot P$, then because ...


0

There are a few conceptually motivated attempts to apply paraconsistent logic to quantum theory, but little actual technical work on connections between quantum and paraconsistent logic has really been done yet. However, this is something I've been working on recently (here's a preprint of a relevant paper ...


3

The proof runs as follows : 1) $P$ --- assumed [a] 2) $\lnot R$ --- assumed [b] 3) $\lnot R \to (P \to \lnot Q)$ --- premise 4) $P \to \lnot Q$ --- from 2) and 3) by modus ponens 5) $\lnot Q$ --- from 1) and 4) by modus ponens 6) $\lnot R \to \lnot Q$ --- from 2) and 5) by Deduction Th (or Conditional Proof), discharging [b] 7) $Q \to R$ --- from 6) ...


-1

$ \neg R \implies \neg Q \Leftrightarrow Q \implies R$


1

An other approach by the writing the negation of your statement and the book's statement : The negation of $\exists x \ \forall y \ \ (M(x,y)\implies x \neq y) $ is : For all $x$ there exist $y$ such that $x$ sent $y$ an email and ($x$ and $y$ is the same person). In other word : For all $x$, $x$ sent an email to himself. The negation of ...


1

Your question mixes syntax and semantic and it is not completely understandable to me. Below I restate Tarki's paradox keeping the two levels well-separated, maybe this helps. Fix a model $M$ and a positive integer $n$. By $L(M)$ we denote the set of all formulas with parameters in $M$. Let $x$ be a tuple of variables of length $|x|=n$. An $n$-truth ...


1

They are the same. $\{X \; : \; P(X)\}$ is the set of all $X$ that satisfy the condition $P(X)$. You may consider $$\{X \in A \; : \; P(X)\}$$ as a convenient abbreviation for $$\{X \; : \; X \in A \ \text{and}\ P(X) \}$$ Similarly, $$\{f(X) \; : \; P(X)\}$$ is a convenient abbreviation for $$\{Y: Y = f(X)\ \text{for some}\ X\ \text{such that}\ P(X)\}$$


1

I don't see way you want to solve your problem using the truth table. Firstly, here is an intuitive approach that I believe the first thing to do when you have suchf problems. $$ ``\mbox{Warning lights is on}" \Longleftrightarrow ``\mbox{Pressure is high}" \wedge \ `` \mbox{Relief valve is clogged }" $$ is equivalent to : $$ ``\mbox{Warning lights ...


1

The following map $f:\mathbb{N}^* \to \mathbb{N}$ should be a bijection. If $u$ is the empty word, let $f(u) = 0$ and if $u = (n_0, n_1, \dotsm, n_k) \in \mathbb{N}$, let $$ f(u) = 10^{n_0}10^{n_1} \dotsm 10^{n_k} $$ where the right hand side is the binary representation of an integer.


3

Here is an idea which should work. Let $n >0$ be a positive integer. Define $k_0=n$, and recursively, as long as $k_j \neq 0$ define $$ k_{j} =2^{k_{j+1}} m_{j+1} \, \mbox { with } m_{j+1} \mbox{ odd } $$ This process ends after $t$ steps, when $k_t=0$, or equivalently $k_{t-1}$ is odd. Now define $$f(n) =( \frac{m_1-1}{2}, \frac{m_2-1}{2},.., ...


1

The claimed conclusion is not $W\leftrightarrow R$ as you wrote but rather it is $W\leftrightarrow P$. From the given $\neg R$ we can conclude that $P\land R$ is false and hence the equivalent $W$ is also false. If the claim were correct,we could infer $\neg P$, but we certainly can't. Incidentally, your mistake in encoding the claim as $W\leftrightarrow R$ ...


2

Statement $1$ is $\exists x\forall y (M(x,y) \implies x\ne y)$ This can be interpreted as: There exists a student such that for all students, if student $x$ has sent student $y$ an email, student $x$ is not student $y$. This doesn't implies that the student has sent everyone but themselves an email, or even any student an email, just that they haven't ...


1

Since $CC′=0$ $$ABCC′=AB\cdot0=0$$ Also $$ B+A′B=B(1+A')=B\cdot 1=B $$ So $$ ABCC′+B+A′B=0+B=B $$


3

I'll assume that, by $C'$, you mean $\bar{C}$, the negation of $C$. If that's the case, then the entire expression evaluates to just $B$. Here's why: in the first term, $CC'$ is always false (it's the AND of a variable and its negation), so the entire first term is always false (it's the AND of $AB$ and false). So we only need to look at the last two ...


1

Yes, a proof from the two premisses $P, Q$ to the conclusion $R$ is evidently also a proof from the premiss $P$ to the conclusion that if $Q$ also holds, then $R$. So far so good. As Colm Bhandal comments, you now have the serious work left to do. But it is rather alarming that you are appealing to Wolfram here! If you are unsure about this sort of thing, ...


0

"Much" is an ambiguous measure. How much is "much"? But however much is "much", the negation of "There is much X in Y" is "There is not much X in Y". We might further interpret that "not much" would mean "little-or-none".


1

No $m$ need not be equal to $g(n)$. In fact $g(n) = m + f(n)$. The construction is concerned with the sequences of lenght $n$ that follow $x_1 \ldots x_m 1\ldots 1$ we are not appending $n - g(n)$ digits (as far as I understand). For example $m = 2$ $n = 4$ $g(n)=2$ $2^{n-g(n)}-1=3$. The sequences we have are $$x_1 x_2 1 1\\ x_1x_2 10\\ x_1x_2 01\\ $$ note ...


1

One major source of ambiguity in your statement, taken as is, is that "much" could technically refer to "much in terms of $X$" or "much in terms of $Y$." I.e., when you say there is "much $X$ in $Y$," which set, $X$ or $Y$, does "much" refer to? Even more than that though, "much" could be interpretted as either a relative percentage/measure/cardinality or ...


2

Every child has a father, but there is not a father for all children.


1

$\forall x \in \mathbb{R} \exists y\in\mathbb{R}\,[x>y]$ is true, but $\exists y\in\mathbb{R}\forall x\in\mathbb{R}\,[x>y]$ is false.


1

Have a look at Amy Felty's $\lambda$-Prolog tutorial. Essentially universal refers to quantification by either a universal quantifier in a positive position in a formula or an existential quantifier in a negative positive. So in $(\exists x(x = 1)) \Rightarrow (\forall y(y = 1))$, both $x$ and $y$ are essentially universally quantified. The point is that ...


1

Proof in the forward direction $\forall x \; (\phi(x) \implies \psi(x)) \implies(\forall x \, \phi(x) \implies \forall x \,\psi(x))$. $\forall x \; (\phi(x) \implies \psi(x))$ $\forall x \, \phi(x)$ $\phi(a)$ (U.I. 2, a\x) $\phi(a) \implies \psi(a)$ (U.I. 1, a\x) $\psi(a)$ (M.P. 3, 4) $\forall x \, \psi(x)$ (U.G. 5) $\forall x \, \phi(x) \implies \forall x ...


2

For a counterexample to show that the two forms are not equivalent, you can let $\varphi(x)$ mean "$x$ is even" and $\psi(x)$ mean "$x$ is odd" (say, in an universe where the quantifiers range over $\mathbb N$).


1

The argument you give is broken, for reasons stated in the comments. Here is a hint for how to approach the problem: Suppose we assume both $$(*)\quad\forall x(\varphi(x)\implies \psi(x))$$ and $$(**)\quad \forall x(\varphi(x)).$$ What do we know if $\forall x(\psi(x))$ happens to fail? Well, by definition this would mean $\exists x(\neg\psi(x))$. Let $a$ ...


1

Note that before the question originally was to: Prove $\big[(\neg M\wedge R)\wedge\neg P\big]\wedge D, \;\neg M\to Q \;\vdash\; Q\vee T$ Hint 1: The proofs mainly rely on two basic rules of inference. Conjunction-Elimination ($\wedge{-}$ , $\wedge \rm E$, or similar abreviation ): $\quad A\wedge B \vdash A$ and Disjunction-Introduction ($\vee{+}$, ...


1

$\forall x : \phi(x) \implies \gamma(x)$ (premise) $E\subset X$ (premise) $\forall x \in E :\phi(x) \implies \gamma(x)$ (by 2) $\forall x \in E : \phi(x)$ (premise) $\phi(x)$ (U.I, 4) $\phi(x) \implies \gamma(x)$ (U.I, 3) $\gamma(x)$ (M.P, 5, 6) $\forall x \in E : \gamma(x)$ (U.G, 7) $\forall x \in E : \phi(x)\implies \forall x \in E : \gamma(x)$ ...


1

What do you mean by "solve"? If to "solve" something of the form $A \vdash B$ means "produce a proof in the formal proof system in My Logic Text from premiss $A$ to $B$" (which is the natural reading) then we need to know which text you are using! In this case you have $M \vdash M \lor X$. And it doesn't matter what $X$ is, for in any standard logical ...


-1

Consider the parity tables. Addition $+$ $$ \begin{array}{cc|cc|cc} + & & a & a & b & b\\ & & o & \bbox[4px,border:2px solid #008000]e & o & \bbox[4px,border:2px solid #008000]e\\ \hline a & o & e & o & e & o\\ a & \bbox[4px,border:2px solid #008000]e & o & \bbox[4px,border:2px ...


1

This is correct. Note that you can go a little bit further: $\forall x(\varphi(x)\implies\psi(x))$ implies $\forall x(\varphi(x))\implies\forall x(\psi(x))$. This is one direction of distributivity of $\forall$ over $\implies$. As a cautionary note, let me point out that similar-looking principles may not hold, e.g.: it is not the case that $$[(\forall ...


1

I think the following argument works to show that generic conditions do extend to totally generic ones. As mentioned in the comments, a poset $Q$ is totally proper iff it is proper and countably distributive. I will only need the forward direction and this isn't difficult to see: given a condition $p$ and a name $\dot{f}$ for a countable sequence take a ...


0

Let us say $X\leq \min(A, B)$. If so, then $X\leq A$ and $X\leq B$. If a number is at most as great as the least of two other numbers, then it must be at most as great as one of them (their minimum) and it must be at most as great as the other (which is at least as great as their minimum). OTOH: Let us say $X\leq \max(A, B)$. If so, then $X\leq A$ or ...


13

The contrapositive of the statement If $\overbrace{\text{$ab$ and $a+b$ have the same parity}}^{\large P}$, then $\overbrace{\text{$a$ is even and $b$ is even}}^{\large Q}$. is If $\overbrace{\text{$a$ is odd or $b$ is odd}}^{\large\lnot Q}$, then $\overbrace{\text{$ab$ and $a+b$ have different parities}}^{\large\lnot P}$. Note that $Q$ is the ...


3

What would the proper negation look like? It turns out that, in this case, there are a number of ways you can go in how you want to prove this claim, not just via direct proof or contrapositive but also how you frame the question logically as well. I'll outline what I think is the clearest and easiest way of going about it. Claim: Let ...


7

No (assuming there are standard models at all). $\operatorname{Con}\sf(ZF)$ is always true in standard models, and $\sf ZF$ proves that $\operatorname{Con}\sf(ZF)$ is always true in standard models. But of course that $\operatorname{Con}\sf(ZF)$ is not provable from $\sf ZF$ itself. The reason is that standard models agree with the universe about the ...


3

You have the contrapositive right. You must negate $P$ and $Q$ separately and prove that the negation of $Q$ implies the negation of $P$. To expand on this, for "$a$ and $b$ are even" to be false, you only need one of $a$ and $b$ to be odd, so the negation is "$a$ is not even or $b$ is not even". And for the statement "$a+b$ and $ab$ have the same parity" ...


6

We explain the reduction, and later, if questions arise, explain $\psi$. A formula $\alpha(x_1,x_2,\dots, x_k)$ is existential if it has the shape $$\exists t_1\exists t_2\cdots \exists t_l\beta(x_1,\dots,x_k, t_1,\dots,t_l),\tag{1}$$ where the formula $\beta(x_1,\dots,x_k, t_1,\dots,t_l)$ is quantifier-free. Sometimes, informally, as in the definition ...


3

In general, if $A\subseteq B$, then $\mathscr P (A)\subseteq \mathscr P (B)$ because every subset of $A$ is a subset of $B$. More formally, if $a\in \mathscr P (A)$, we need to show that $a\in \mathscr P (B)$. But this is trivial, since if $x\in a$, then $x\in B$ which implies that $a\subseteq B$ which is the same as $a\in \mathscr P (B)$. Now take ...


3

$X\subset Y$ implies every element of X is an element of Y, so subsets of X are subsets of Y, so $\mathcal{P}(X)\subset\mathcal{P}(Y)$. Finally, for $Y=\mathcal{P}(X)$ you have $\mathcal{P}(X)\subset\mathcal{P}(\mathcal{P}(X))$.


9

Your result is an immediate consequence of the following proposition. Proposition. Suppose $X\subseteq Y$. Then $\mathscr P(X)\subseteq\mathscr P(Y)$. Proof. Let $E\in\mathscr P(X)$. Then $E\subseteq X\subseteq Y$ so that $E\subseteq Y$. Hence $E\in\mathscr P(Y)$. This proves $\mathscr P(X)\subseteq\mathscr P(Y)$. $\Box$ Do you see how your problem is now ...


0

If this piece of iron is placed in water at time t , then the iron will dissolve. Why is it considered false even if its antecedent is false - that is, the iron is not placed in water at time t ? Because when we express such a statement in natural language, it is often implicitly a modal logic statement; a claim of the necessity of the ...


0

This is what we have: $G\circ L \Rightarrow H\circ M$ $K\circ N \Rightarrow H\circ M$ (where $\circ$ is one of the symbols $<, =, >$) If, for example, $G<L$, then also ($*$) $H<M$. What do we know about $K$ and $N$? Could $K>N$? No, because then by (2) also $H>M$, contrary to ($*$). Could $K=N$? No, because then by (2) also $H=M$, ...


2

From wikipedia: $\:$ "In particular Krivine (1969) showed there was a model of ZFC in which every ordinal-definable set of reals is measurable, ..." Therefore ZFC does not prove that there is a definable nonmeasurable set. Using an explicit definable well-order on $\mathbb{R}\hspace{-0.04 in}\cap$OD to run a Vitali construction gives an explicit set ...


2

If you can prove that your definition defines something, then will in particular define something in Solovay's model, and that something will in particular not be a nonmeasurable set. So the best you can hope for is an explicit definition of a subset of $\mathbb R$, such that the thing defined will in some models of ZF be a nonmeasurable set. And this is ...


9

Mendelson is after the fact that the conditionals we use in everyday language are often not at all like material implication ($\to$) in logic. The example sentence (intuitively) expresses that iron has a certain disposition (click) rather than being a regular implication. Example: Let "$x$ is lethally poisonous" be defined as "If someone eats $x$, then he ...


0

Exactly. The first two equivalences are correct. I assume that by the third you mean that this: (i) $\forall i\in\{0,..,n\} \exists k\in \{1,\ldots,m\}\;\;a+ib\le k$ is equivalent to this: (ii) $\max_i(a+ib)\le j$ for some $j\in\{1,\ldots,m\}$. That is true as long as $b$ is non-negative, otherwise (i) only implies (ii), but not the converse.


1

The former formula is the correct statement. $\exists X \,(\lnot P(X)) \land \exists X \, (\lnot Q(X))$ $\lnot P(x) \land \exists X \, (\lnot Q(X))$ by existential instantation $\exists X \, \left[\lnot P(X) \land \exists X \, (\lnot Q(X))\right]$ by existential generalization note that we cannot apply existential generalization to the wff $\lnot P(X) ...


0

Givens $x\neq 0$ $y = \frac{3x^2+2y}{x^2+2}$ Goal $y=3$ Proof sketch: Suppose $x\neq 0$. Suppose $y = \frac{3x^2+2y}{x^2+2}$. This means that $y (x^2+2)=3x^2+2y \Rightarrow x^2y+2y=3x^2+2y $. $\qquad \quad$ [Proof of $y=3$ goes here.] $\qquad$ 3. Therefore $y=3$ Thus, if $x\neq 0$, then if $y = ...


1

One could try defining the statement $\mathbf{({Q_{x_1 \dots x_n} / p})R}$ (where $\mathbf{p}$ is $n$-ary) as the statement obtained by simultaneously replacing in $\mathbf{R}$ all occurrences of terms of the form $\mathbf {p a_1 \dots a_n}$ with $\mathbf{{{Q}_{x_1 \dots x_n}}(a_1, \dots, a_n)}$. For this to be defined, one needs all the $\mathbf{a_i}$ to ...



Top 50 recent answers are included