Tag Info

New answers tagged

2

I would use such a phrase to castigate someone who asked whether two theorems were logically equivalent. There is no such formal relationship. What is actually discussed sometimes is whether theorems can be easily derived from each other, using techniques that are much simpler than the original proofs. This is a human thing, the judgment of "simpler" is in ...


8

Yes, that must be what people who throw around that phrase mean: If $P$ and $Q$ are both true (or provable in some particular theory), then $P\Leftrightarrow Q$ is also true (or provable in that theory). However, this is not actually what "logically equivalent" means in logic. The usual meaning of that is that $P$ and $Q$ are logically equivalent if and ...


1

No, that's a statement derived purely from the definition of equivalence There's no deep meaning there.


0

You could write a computer program to solve these problems. Also, to check if two formulas 'p' and 'q' are equivalent, you can check and see that both Cpq and Cqp (this is Polish notation) are tautologies. A formula is either a tautology or it's not. So, assume that Cpq is not a tautology. This means that there exists some valuation of the variables in ...


0

You can work out the tableau of the negation of your sentence: $\neg\big(\exists x\forall yQxy\to\forall y\exists xQxy\big)$ $\exists x\forall yQxy$ (1) $\neg\forall y\exists xQxy$ (1) $\forall y Qay$ (2) $\exists y\neg\exists xQxy$ (3) $\neg\exists xQxb$ (5) $\forall x\neg Qxb$ (6) $\neg Qab$ (7) $Qab$ (4) $\bot$ The tableau of ...


0

Short answer: use disjunction elimination on (C V A). Longer answer: Assume ¬A. Since you have (C V A), that means if you assume A, that you'll get a contradiction. So, you can get (A → C). Get (C → C). Then use disjunction elimination to get to C. Then discharge the hypothesis and you have the result.


0

You can check some of them easily in your head. In (a), for instance, $p\,\lor\sim q$ is certainly always true whenever $p$ is true, but $p\Rightarrow q$ is not: it’s false when $p$ is true and $q$ is false. Thus, the two expressions cannot be logically equivalent. Similarly, you should recognize the second implication in (e) as the contrapositive of the ...


0

You can use DeMorgan's laws: $p \vee q$ is equivalent to $\neg (\neg p \wedge \neg q)$ $p \wedge q$ is equivalent to $\neg (\neg p \vee \neg q)$


4

There is a way to see that there is no really satisfactory, general answer. Recall that the deduction systems for first-order logic are computably effective. A theory $\Gamma$ is effective if we can computably enumerate its axioms. Because the deductive system is effective, if $\Gamma$ is an effective theory then we can also enumerate its deductive closure ...


2

Ref to : Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001), Ex.13, page 130. For $\leftarrow$ : 1) $∀x((x=t) \to \varphi)$ --- assumed 2) $(t=t) \to \varphi[t/x]$ --- from 1) and Enderton's Ax.2 : $∀xα \to α_t^x$, where $t$ is substitutable for $x$ in $\alpha$, and modus ponens 3) $\vdash t=t$ --- from equality axiom Ax.5 4) ...


1

No, your table is correct.   You may be interpreting the result wrong.   You wish to have $P$ true whenever the statements $Q\to P, \neg Q\to R,$ and $R\to P$ are all true at the same time.   That happens on the last three rows, and $P$ is true for each one. $$Q\to P, \neg Q\to R, R\to P \;\vdash\; P$$ PS: Your application of rules of ...


1

Your truth table supports the result of the proof: indeed, in all rows where all the premises are true, the conclusion is also true. Perhaps you're mixing the situation up with one where you try to prove that $P$ is a tautology?


-2

Here's one straightforward approach: \begin{array}{rll} \text{1.} & \alpha\to\beta & \text{hypothesis} \\ \text{2.} & \neg\beta\to\neg\alpha & \text{1, contraposition} \\ \text{3.} & \neg\alpha\to\beta & \text{hypothesis} \\ \text{4.} & \neg\beta\to\neg\neg\alpha & \text{3, contraposition} \\ \text{5.} & \quad\neg\beta ...


-1

I found a 33 step, level 15 proof using OTTER of the needed tautology. Everything is in prefix notation with "C" standing for $\implies$ and "N" for $\lnot$: ----> UNIT CONFLICT at 24.34 sec ----> 39325 [binary,39324.1,2.1] $F. Length of proof is 33. Level of proof is 15. ---------------- PROOF ---------------- 1 [] -Thesis(C(x,y))| ...


3

It's not clear how to phrase "compute the Hanf number" as a problem for which decidability makes sense. The Hanf number problem takes in a logic, and outputs a cardinal; decidability, or computability, makes sense in the context of natural numbers. In certain cases, the Hanf number is completely understood. For example, for a first-order language $L$, the ...


1

Were you hoping that the failure of exchange would give some sort of non-structure result? This is not necessarily an answer to your question, but here's an example showing that this can't happen (or this hypothesis alone is not enough). It's an $\aleph_0$-categorical theory in which $\text{acl}$ does not satisfy exchange, but which is $\omega$-stable (i.e. ...


3

Step $2$ is an instance of Axiom $6$ of formal deduction (see Enderton's A Mathematical Introduction to Logic page $112$): $\vdash (x=y)\to(\alpha\to\alpha ')$, where $\alpha$ is atomic and $\alpha '$ is obtained from $\alpha$ by replacing $x$ in zero or more places by $y$. In your case (where $\equiv$ replaces $=$), the atomic formula is $Pb$ and, ...


2

Step two could actually be $b\equiv a \rightarrow (Pb\leftrightarrow Pa)$. If two items are equal, they have the same properties.


2

A counterexample to the claim is: $$ K(A) = \Omega \text{ for all } A$$ Then $P(\omega_0)=\varnothing$ for all $\omega_0$ because it is the intersection of a class that includes $\varnothing$. At first I read the claim as being $\omega\in K(P(\omega))$. But that is not true either; here's a counterexample to that: $\Omega$ is infinte. $\displaystyle ...


2

Expand the definition of $\mathcal{M}\models\phi_1\land\phi_2$ and use the induction hypothesis: \begin{align}\mathcal{M}\models\phi_1\land\phi_2&\Leftrightarrow\mathcal{M}\models\phi_1 \text{ and } \mathcal{M}\models \phi_2\\&\Leftrightarrow\mathcal{N}\models\phi_1 \text{ and } \mathcal{N}\models \phi_2 \qquad \text{ (by induction ...


-1

Following Mauro's comment: $T\vdash\alpha\to\beta$ --- Given $T\vdash\neg\alpha\to\beta $ --- Given $T\vdash(\alpha\to\beta)\to\big((\neg\alpha\to\beta)\to\beta\big)$ --- Axiom $1$ (tautology) $T\vdash(\neg\alpha\to\beta)\to\beta$ --- Modus Ponens $1-3$ $T\vdash\beta$ --- Modus Ponens $2-4$ Alternatively, using the fact that ...


1

Hint: Let $T\vdash (α→β)$ and $T\vdash (¬α→β)$. Recall that $\vdash \alpha \lor \neg \alpha$. Now try to apply the disjunction elimination rule. Can't you conclude $T\vdash β$?


0

The 'trick' to remember is that when using universal elimination you can alpha-replace the bound entity with any entity, including a non-arbitrary entity.   If a predicate is true for all things it is true for any specific thing.   Just remember you can't use universal reintroduction when you don't choose an arbitrary entity. You can use: $\forall ...


0

I think you are mistakenly determining actual truth values for each of the pairs. In the first question, it isn't important that normally every multiple of three is not odd. I think the real point is that IF it were the case that every multiple of three were odd, then it would also be the case that some multiples of three are odd. Thus the two statements ...


1

You don't actually need to apply the identity rules. Note that in your givens you have $P(b)$ and $∀x∀y(P(x)∧P(y)→x=y)$, a sentence that merely asserts that one and only one object has $P$. Now since $P$ is predicated of $b$ already, why don't try some instantiation of them? You can try something simpler: $P(b)$, $\;\;\;\;\;\; \text{premise}$ ...


2

Recall the derivative of $f$ exists at $x$ when the $\lim_{h \to 0} \frac{f(x+h)-f(x)}{h}$ exists. The set of all such $x$ is definable by this formula: $$\exists L \forall \epsilon > 0 \exists \delta > 0 \forall h : (0 < |h| < \delta) \rightarrow (|\frac{f(x+h)-f(x)}{h} - L| < \epsilon) $$ We still are not done, because we don't have ...


0

I wouldn't bother instantiating $x_0$ or $y_0$. I would instantiate the $y$ in your second premise to be $b$ itself. Then since you have $P(b)$ as a premise, you know that $P(x) \land P(b)$ is equivalent to just $P(x)$, and you're done. More explicitly, start with $$\forall x\forall y(P(x)\wedge P(y) \rightarrow x=y$$ Then since this is true for every ...


0

Consider the claim C: For all $n$ , if $x,y$ is in $A_n$ , then $x^{(y+1)}$ is in $A_n$ . Are the $x,y$ used here arbitrary ("any $x,y$...") or have they been defined earlier ("these $x,y$...")? If they are predefined constants, then we have: $$\forall n\; \Big(n\in \Bbb Z\wedge x\in A_n\wedge y\in A_n \;\to\; x^{y+1}\in A_n\Big)$$ If they are ...


1

The answer to 0^0 = not defined. https://www.youtube.com/watch?v=BRRolKTlF6Q explains it with more detail.


2

Under the premise $\neg\exists x P(x)$, assume $P(x)$ and follow from this contradiction.


2

I'm not sure why you want to talk about structures (or assume completeness, for that matter), so here's a purely syntactic proof. $T\vdash(\phi\to\psi)\Longrightarrow T\cup\left\{\phi\right\}\vdash\psi$ Let $T\vdash(\phi\to\psi)$. Then there is a deduction $D=\langle\gamma_1,\ldots,\gamma_n\rangle$ of $(\phi\to\psi)$ from $T$, where ...


3

This statement is not quite vacuous as it seems. There is a difference between $\vdash$, which means "proves" and $\models$ which means "logically entails". The former is about the existence of a proof, the latter is about the truth value in models. The completeness theorem for first-order logic, however, says that the two are very related. How related? ...


3

Your statement is more known in the non-contrapositive form of the model existence lemma: If $T$ is a consistent set of sentences, then $T$ has a model. Its proof from is easily found in most logic textbooks, such as van Dalen, Goldrei and others. Note, however, that it's not a matter of the statement being vacuosly true. The point is because if $T$ ...


1

If $\mathcal M\vDash T\cup \{\phi\}$ then $\mathcal M \vDash \phi$, so $\mathcal M\not\vDash \neg\phi$ (i.e. $\phi$ is false in $\mathcal M$). This implies $$\mathcal M \vDash (\neg \phi \vee \psi) \to \psi$$ By assumption we can then say $\mathcal M \vDash \psi$ as claimed.


0

Clarity seems to be a rare commodity in the literature on linear logic. However, Girard's Proofs and Types is the place to start for coherence spaces.


2

Your formula is false in the structure whose carrier set is $\{42\}$ and the interpretation of $A$ and $B$ are both $\varnothing$. Since there is a structure where the formula is false, it is not logically valid. If you looks at the possible models of your formula, with interpretaions $\hat A$, $\hat B$ of the predicates $A$ and $B$, the part $\forall ...


3

Since you didn't specify a context, I'll assume the question is about ultrafilters on arbitrary semigroups. Then the answer is yes. Just take a semigroup that has an identity element $e$ (i.e., a monoid, for example a group) and let $\mathcal V$ be the principal ultrafilter that contains $\{e\}$.


1

Sorry I said symmetric, it is a translation error. In English this property is known as self-dual: function is self dual if $f(x) = \neg{f(\neg{x})}$, which is the case for your function. A complete set must contain a non-self-dual function. The self-duality is inherited under composition: any composition of self-dual functions is self-dual as well. ...


0

The Rules: Convert NOT-operator: $\bar{X} = X\oplus X$ Convert AND-operator: $X\cdot Y = (X\oplus Y)\oplus (X\oplus Y)$ Convert OR-operator: $X+Y=(X \oplus X)\oplus (Y\oplus Y)$ The Procedure (Brute Force Method): Step 1: Convert all NOT-operators Step 2: Convert all AND-operators (left to right) Step 3: Convert all OR-operators (left to right) ...


0

There is a single sentence in the second-order language of equality whose contents is something like "There are relations and function symbols and a fixed element which satisfy the second-order axioms of Peano arithmetic with the elements of the universe". Since second-order Peano has a unique model, $\Bbb N$, saying that a set satisfies this axiom means ...


0

If you already know that the valid second-order sentences over the signature $S_\infty$ are not enumerable, you only have to construct from a $S_\infty$-sentence $\varphi$ a $\emptyset$-sentence $\varphi'$ such that $\varphi$ is valid if and only if $\varphi'$ is valid. You can do this by replacing all distinct function symbols in $\varphi$ by distinct ...


0

$\varphi_4$ is false, the rest is okay. $\varphi_4$ only defines $1$. The proper solution would be $$\varphi_4(x) : (\forall y\ \forall z ((\varphi_3(y) \wedge \varphi_1(z))\implies (\varphi_2(z,x) \wedge \varphi_2(x,y)))) \vee \phi_1(x)$$ More concise: $$x\in [1,\sqrt 2) \Leftrightarrow x=1 \vee (1 < x \wedge x < \sqrt 2)$$ We translate $1<x$ to ...


0

Thanks Ove! I think these make sense. φ1(x): ∀y(x⋅y = y) φ2(x,y): ∃z(P(z) ∧ (x+z = y)) φ3(x): ∀y(φ1(y) → ((y+y) = (x⋅x))) ∧ P(x) φ4(x): (∀y∀z(φ3(y) ∧ φ2(x,y) ∧ φ1(z) ∧ φ2(z,y))) ∨ φ1(x) Please correct me if I'm wrong! :)


0

Answers in the form of guidance as it seems like what you're asking for: A formula $\varphi(x)$ which defines a set needs to be open. We say that $\varphi(x)$ defines the set ${1}$ if $M\models \varphi(c)$ if and only if $1=c \in R$. Thus your answer to (i) is not really correct but it is if you remove the quantifier for $x$. i.e. $\forall y (x \cdot y = ...


3

1) As we usually define them: A theory $T$ is a set of sentences such that $\varphi \in T \Leftrightarrow T \vdash \varphi$ (derivability closure). A set $\Gamma$ is the axiom set of a theory $T$ iff $T = \left\{ \varphi | \Gamma \vdash \varphi \right\}$ If $T \vdash \varphi$, we say that $\varphi$ is a theorem of $T$ (that is, axioms are 1-line ...


2

This is basically all correct, except that I regard axioms as theorems (they're theorems with 0-line proofs). Ergo, the theorems of $T$ are just the elements of $T$. This is kind of like how if $V$ is a vector space, then the vectors of $V$ are just the elements of $V$. Adjoining a new axiom can never make the theory smaller, although it can potentially ...


1

The notions of eliminability and conservativeness are necessary conditions for one theory to be a "definitional extension" of another. Suppose you have two theories, $T$ and $T_1$, such that the vocabulary of $T_1$ includes the vocabulary of $T$, and everything provable in $T$ is provable in $T_1$. Informally, "eliminability" means that $T_1$ can ...


2

Hint: reduce the theory of $\mathbb{N}$ to the theory of $\mathbb{Z}$: that is, find a way to turn a sentence $\varphi$ into a new sentence $\psi$ such that $$\mathbb{N}\models\varphi\iff\mathbb{Z}\models\psi$$ (you also need this transformation to be recursive, but put that off for now). If you can do this, then the theory of $\mathbb{Z}$ must be at least ...


2

While I second Noah Schweber's recommendation to read 'Computability and Logic', I also recommend this free textbook recently put together by a group of logicians aimed at providing a free and rigorous introduction to logic which goes into computability theory and meta-logic as well. http://people.ucalgary.ca/~rzach/static/open-logic/open-logic-complete.pdf ...


2

By far my favorite book on mathematical logic is "Computability and Logic" by Boolos, Burgess, and Jeffries, now in its fifth edition (I learned logic from the fourth ed., which is available used for cheap). I cannot recommend it highly enough. A brief outline of the book: the first 8 chapters cover basic computability theory. This nicely complements the ...



Top 50 recent answers are included