Tag Info

New answers tagged

0

This statement can be proved in minimal logic. The statement is $$ ((\alpha \to \bot) \land ((\alpha \to \bot) \to \bot) \to \bot $$ which is really of the form $$ (X \land X \to Y) \to Y $$ which is just a form of modus ponens. The provability of the statement has nothing to do with negation, really, apart from rewriting the negations as implications in the ...


0

$$ \mathbb{HELLO, FRIEND :)} $$ I am wonder what is purpose of question. Classical logic, Yes efinitely, please just take double negative out. Intuitive logic not quite so sure how is obvious, but I would say so, think of using double nnegative in sentence https://www.google.com/?q=double%20negative You have said as much yourself. Given lemma's one and 2 ...


0

I have posted an extended solution on my blog: Solution to my transfinite epistemic logic puzzle. My answer agrees with that of Joe and Kellen and Paul on the other answers here, namely, that Albert has $100\frac38$ and Bernard has $100\frac7{16}$.


0

In the second line of your second paragraph, you assume the statement $Con(ZF+AD)$ and then get a set model of $ZF+AD$ by Gödel's completeness theorem (in $ZFC$ or $ZF$, as our meta theory). Then, you claim that $ZF+AD$ is consistent relative to $ZFC$. Why would the statement $Con(ZFC) \rightarrow Con(ZF+AD)$ follow? Your assumption to get the model of ...


0

What Asaf Karagila says in the second paragraph of his answer is basically what you are overlooking in your argument. Namely, it is implied in your argument that the statement $''\text{Con}(ZF+AD)\implies ZFC\vdash\text{Con}(ZF+AD)''$ is true in the meta-theory. But this is not necessarily true. What is true in the meta-theory is that $''\varphi\implies ...


1

Consider just two propositional variables, say $p$ and $q$, and let's see what truth-functions of these we can express using $\neg$ and $G$. Using just $\neg$, we have $p,q,\neg p,\neg q$. Now let's apply $G$ to any triple of these, say $G(x,y,z)$. If two of $x,y,z$ are the same, the $G$ just produces that same one of $p,q,\neg p,\neg q$ as its output. So ...


0

excuse my unfamiliarity with the formal expression of propositional calculus, but i hope the following reasoning may be of assistance suppose the proposition false. then we have: $$ (A \to (B \to C)) \land ¬ ((A \to (C \to D) \to (A \to (B \to D))) = \\ (A \to (B \to C)) \land ((A \to (C \to D)) \land ¬(A \to (B \to D)) = \\ (A \to ((B \to C) \land (C \to ...


0

Suppose $(A\implies (B\implies C))$. Then not $A$ or $(B \implies C)$. Case 1: If not $A$, then $(A⟹(B⟹D))$. So $((A⟹(C⟹D))⟹(A⟹(B⟹D)))$ is true. Case 2: $A$ is true. So $(B \implies C)$, then not $B$ or $C$. Case a) If not $B$, then $(A⟹(B⟹D))$ is true. Case b) $B$. So $C$. Case bi) If $D$ is false, $C⟹D$ is false, so $(A⟹(C⟹D))$ is false. So ...


0

There must be something wrong with your rewritings -- what you have arrived at is false when all of the propositional variables are true (as well as when they're all false), whereas the original formula is true in that case.


1

$$({\sim} p\vee{\sim}q)\vee(p\vee q)={\sim}p\vee({\sim}q\vee(p\vee q))\text{ by associativity}\\={\sim}p\vee(({\sim}q\vee p)\vee q)\text{ by associativity} \\={\sim}p\vee((p\vee {\sim}q)\vee q)\text{ by commutativity} \\={\sim}p\vee(p\vee ({\sim}q\vee q))\text{ by associativity} \\=({\sim}p\vee p)\vee ({\sim}q\vee q)\text{ by associativity}$$


1

The operation $\vee$ is associative: $$(p \vee (q \vee r)) \leftrightarrow ((p \vee q) \vee r)$$ and commutative: $$(p \vee q) \leftrightarrow (q \vee p)$$ so you can change the order and distribute the parentheses as you please. Intuitively, no matter how the parentheses are distribute or what order $p,q,r,s$ are written in, the statement $p \vee q \vee r ...


0

A way to approach it is to consider constructing the transitive closure in stages - what relation is formed if we take the set of $(x,y)$ such that either $(x,y) \in D_r$ or there is some $z$ such that $(x,z),(z,y) \in D_r$? Then what happens if you include longer chains like this? Slightly more detailed hint (but still only hinting):


0

Hint You have to use : THEOREM 35F [page 239] A relation is recursive iff both it and its complement are recursively enumerable. and the definition [page 206] of a [unary] relation $R$ being representable in $A_E$ : $a \in R \ ⇒ \ A_E \vdash ρ(S^a0)$, $ a \notin \ R ⇒ \ A_E \vdash ¬ρ(S^a0)$. Now, the r.e. set $Q$ is such that : $a ...


1

It is meant to prove the sequent $\vdash\phi\rightarrow (\psi\rightarrow\phi)$, but the derivation is not complete. The first $(\rightarrow I)$ needs the assumption $\psi$ (and repeating the assumption $\phi$): From "Logic in computer science" (Huth & Ryan) page 20: Also note that your derivation is in Natural Deduction and it's different from ...


1

As reminded by Trevor, another approach is to go through Moschovakis set induction. $\text{pos}\Sigma^0_1(A)$ is the smallest monotone $\Sigma$-collection containing the evaluation-in-$A$ relation: $$E(w,x,B) \text{ iff } A(w).$$ Here $E$ is a set relation. All terminologies are according to Moschovakis's book. $\text{pos}\Sigma^0_n(A)$, ...


2

Neither. The sequent proved is : $\vdash (\phi \to (\psi \to \phi))$. It is the last formula and the only assumption of the derivation : $\phi$, has been discharged (it is crossed with the "dandah"). The derivation is correct; see the discussion in : Jan von Plato, Elements of Logical Reasoning (2013), page 22, or see the relevant parts quoted ...


3

Do you mean "irreflexive" instead of "not reflexive"? A relation is reflexive if $\forall x\in A, xRx$. It's irreflexive if $\forall x\in A, \neg (xRx)$. However, if it's not reflexive, you only know that $\exists x \in A, \neg(xRx)$. I ask, because the result you have to prove is wrong. Take a relation on the set $A=\{x,y,z\}$ with $\neg (xRx), ...


1

All of this is problematic. You claim that the theory is inconsistent. Okay. So by contradiction it is not inconsistent, therefore the working assumption is that the theory is consistent. But a theory being consistent does not mean consistent relative to $\sf ZF$. it means consistent. Moreover the fact there is a model of $T$ in a universe of $T'$ is not a ...


1

First of all, we are considering formulae (like $\beta, \sigma$) in first-order language of arithmetic; thus, their "standard" interpretation are assertions about numbers. We can think of $\beta(v_1)$ with $v_1$ free, as a sort of "function" (a propositional function) that maps numbers into assertions about them; i.e. $\beta(\mathbf S\mathbf 0)$ is an ...


0

$$ a \bar b \bar e f + \bar a \bar b ef + ac \bar d \bar e + \bar a c \bar d e + \bar b \bar c f + \bar b df = ac \bar d \bar e + \bar a c \bar d e + \bar b \bar c f + \bar b df$$ $$a \bar b \bar e f + \bar a \bar b ef + ac \bar d \bar e + \bar a c \bar d e + \bar b \bar c f + \bar b df$$ Look for common terms and duplicate as needed. Once you check this ...


1

From the point of view of the history of science there is difference between the concepts described by the OP. The ancient Greeks considered those statements to be axioms that they saw to be self explanatory, intuitively clear, not requiring proof..., etc. It turned out, however, that certain theorems could replace certain axioms and vice versa. So, the ...


0

Let's call the first statement "$x=a$" : $A$ and the second statement "$x \neq a$ : $B$ So clearly, $ B = A'$ Hence, $A \vee B = A \vee A' = true$


0

It's not clear in your question what are we allowed to do, anyway here is a hint: First note that $x \neq a$ is nothing but $\neg x = a$, hence we should prove that: $$\vdash \forall x (x=a \vee \neg x=a)$$ Now recall that $\alpha \rightarrow \beta \equiv \alpha \vee \neg \beta$ Now isn't there an implicational tautology you could easily prove ...


0

It is not difficult at all to compare boolean equations like this via truth table, if we have nothing more than any spreadsheet (Gnumeric, Excel) at hand. Note that the boolean equation can be easily transformed into arithmetic one, e.g.: \begin{align} ab'e'f+a'b'ef+acde' &= \max(a(1-b)(1-e)f,(1-a)(1-b)ef,acd(1-e)) \end{align} First define the ...


0

If you want to be picky, any two "problems" which we do not say have a relation to eachother does not. What we should do (however often ignored) is to allways put equivalence arrows and implications between equations/problems. So if we write $4x+1 = 1 \Leftrightarrow x = 4$ we imply that the statement/problem $4x+1=1$ is equivalent with the statement ...


1

Well, let's look at the structure of the problem: There is a set $S$ of suspects (three in the original problem, a countably infinite number of them in Hilbert's hotel). There's a subset $G\subset S$ of guilty suspects. And there's a mapping $f:S\to P(S)$ where $P(S)$ is the power set (set of subsets) of $S$, where $M\in f(s)$ means "If $s$ says the ...


0

It sounds to me like you are asking about Infinitary logic. I've pondered this idea myself a fair bit. For instance, we can make sense of the 'limit object' of this sequence $$ a_1 \wedge a_2, (a_1 \wedge a_2) \wedge a_3, (((a_1 \wedge a_2) \wedge a_3) \wedge a_4$$ where $\wedge $ denotes logical and. In this case the limit object has a value of true if and ...


5

I'd suggest proving $\Sigma\vdash D\to Y$ and $\Sigma\vdash H\to Y$ (and $\Sigma\vdash Y\to Y$), then using (4). Here's a proof of $\Sigma\vdash D\to Y$, first in a "friendly" form, then the (fairly mechanical) translation to a form using just the tools you've listed. Friendly form: Suppose $D$. Suppose further that not $Y$. By (1), $H$ would follow. ...


2

The pointclasses $\Sigma^1_1(A)$ for some set $A\subseteq \mathbb{R}$ are defined as follows: a set $B$ is $\Sigma^1_1(A)$ iff there are $\Sigma^1_1$ sets $C$ and $D$ such that $B(x) \leftrightarrow C(x) \vee \exists y (\forall n (y)_n\in A \wedge D(\langle x,y\rangle))$. Notice that $A\in \Sigma^1_1(A)$ and the pointclass $\Sigma^1_1(A)$ is closed under ...


2

In the literature on constructive and linear logic it is the other way around, although $\to$ doesn't strictly belong to either group because it isn't monotone. Troelstra's Contructivism in Mathematics defines the almost negative formulas of Heyting arithmetic as formulas that have no $\vee$ and limited use of $\exists$. In linear logic the terminology made ...


1

Skolem proved a quantifier elimination result for Peirce's "Calculus of Classes". See this article in the Stanford Encyclopaedia of Philosophy for some references. This calculus amounts to the first-order theory over the signature $(\subseteq; \emptyset, -, \cup, \cap)$ of type $(2; 0, 1, 2, 2)$ whose intended interpretation is the set of subsets of some ...


0

You have too many literals. In this case you have 6.Your truth table should have 2^6 rows (interpretations). To show it's false. The given logical formula should be false for all 2^6 interpretations which is extremely tedious to work by hand. Instead, you use truth tree method to show its falsity. The video explains how to do it Truth Tree. You have to use ...


0

Regardless of any reasonable mathematical formulation for the italicized assertion, let's see what happens when $F=PA$. Arguing inside of $ZFC$: "Since there is a model for $PA$ (the standard model of first-order arithmetic), then we have $\text{Con}(PA)$ by the completeness theorem. Therefore $PA\nvdash\text{Con}(PA)$ by the second incompleteness ...


5

There have been some comments about this requiring memorization or it being different from the way the word is used in normal conversation, but this simply isn't true. It's English. You can walk the dog only if you have a leash. Therefore, if you can walk the dog, it follows logically that you must have a leash. Can walk the dog implies have a leash. You ...


0

It should be noted that there exists transformations, such as Tseitin transformation, which allows for a transformation from any propositional formula to CNF while avoiding an exponential blow up in terms.


1

Assume that $T$ satisfies the Hilbert-Bernays conditions and that: $T\vdash A \leftrightarrow (\Box A \to \bot)$ for some sentence $A$. Call this the diagonal sentence. By the first and third conditions it follows that: $T\vdash\Box A \to \Box(\Box A \to \bot)$ and thus by another application of the third condition: $T\vdash\Box A \to (\Box\Box A \to ...


3

I understand "A only if B" as "A can be true only in those possible worlds where B is true also".


0

Hint: this is an explanation of why it is true, which you can cast into a structural induction if you wish to. If $\phi$ is a pure formula, in the sense of your question, and $v$ is a propositional variable in $\phi$, define an assignment that makes $v$ true if $v$ is not negated in $\phi$ and makes it false if $v$ is negated. This is possible by the ...


0

Don't use set-theoretic notation for the barber paradox. The proof is just: Take any barber who cuts the hair of exactly those who don't cut their own hair. Either the barber cuts his own hair or he does not. If he does cut his own hair, then by his own rule he is not supposed to cut his hair. If he does not cut his own hair, then by his own rule he is ...


0

If the set $\{0,1,2,3,4,5\}$ is a domain of discourse, and $P(x,y)$ is a predicate with two arguments from that domain, then : $$\forall y\; \neg P(2,y) \;\iff\; \neg P(2,0)\wedge \neg P(2,1)\wedge \neg P(2,2) \wedge \neg P(2,3)\wedge \neg P(2,4)\wedge \neg P(2, 5)$$


0

This question leads to Open world assumption. According to the definition of OWA, anything that is not stated as false explicitly, then it's not false. In the definition, you are defining P(x,y) and not $\neg$ P(x,y). So whatever be the definition of P(x,y), if you query $ \forall y \neg P(2,y) $, then result is empty. If you have definition of $\neg ...


2

A slightly different way to see this $$\begin{align}\neg q \to \neg (q \wedge (p \to \neg q)) &\color{red}\equiv (q \wedge (p \to \neg q)) \to q \\&\equiv (\neg q \vee q )\vee \neg( p\to \neg q)\\&\equiv T \vee \neg (\neg p \vee\neg q) \\&\equiv \color {red} T\end{align}$$


6

In the second to last step, you commited an error \begin{align*} ¬q→¬(q∧(p→¬q)) &\equiv ¬¬q∨¬(q∧(¬p∨¬q))\\ &\equiv q∨¬q\color{red}\lor¬(¬p∨¬q)\\ &\equiv T \color{red}\lor ¬(¬p∨¬q)\\ &\equiv T. \end{align*}


1

The answer depends on your definition of nonlogical symbols. In the more reasonable case where you require a symbol to be expressible, or in other words countable (so you might have a language with finitely many nonlogical symbols, or nonlogical symbols that can be defined in a formal language, etc), then there are only countably many finite sets of ...


2

You are right about A not being equal to E, so long as you are sure that $\mathbb{Z}_+$ is the intended domain. If the domain were $\mathbb{N}$, A would equal E, so I'd double check that, but if it is presented just like you presented it, the Chegg solution is wrong.


0

A property (also called a "predicate" or "propositional function") is simply something that can be true or false of some objects. In logic, the notation $P(x)$ represents the statement that "object x has property P." We could even have predicates that take multiple arguments, like P(x,y); usually a predicate with more than one argument is called a relation. ...


1

Are you familiar with the definitions of reflexive, symmetric and transitive relations? A reflexive relation is a binary relation on a set for which every element is related to itself. As you can clearly see $(0,0),(1,1)$ etc. are not contained in your relation, so it is not reflexive. A relation is symmetric if $aRb \implies bRa$. Once again, ...


0

A relation is reflexive $\iff$ $\forall_{\alpha}(\alpha \in A)$$(\langle\alpha,\alpha\rangle \in T)$. This is clearly not the case for T. A relation is symmetric $\iff$ $\forall_{\alpha, \beta}(\alpha \in A)([\langle\alpha,\beta\rangle\in T] \rightarrow [\langle\beta,\alpha\rangle \in T])$. This isn't the case for T either. A relation is transitive $\iff$ ...


0

To be Reflexive you should have (0,0) (1,1) (2,2) (3,3) To be symmetric if you have (0,1), then you should have (1,0) To be transitive if you have (1,2) (2,4), then you should have (1,4) To answer your question NO for Symmetric and Reflexive Yes for transitive because no counter example



Top 50 recent answers are included