New answers tagged

0

With varying counterfeit weights, I don't think there's any point in weighing groups of coins against each other. So all weighings will be one coin to one coin. As soon as one balance is found, those coins are true and can be used as a reference to check all other coins (where their status is unknown) A somewhat analogous graph theory problem would be ...


0

'A implies B' means only that the proposition A and AB have the same truth value. -- E. T. Jaynes


1

my hunch is this. Each weighing can turn out one of 3 ways -- be left side heavy, right side heavy or ballance. If we put the coins in a line, there are ${11\choose 7} = 28$ ways the counterfeits could be arranged. But each coin could be one of 8 different weights! I think there are $28\cdot8!$ different distributions to identify. $n > \log_3 28\...


2

Yes, the sentence is true — the two sides are equivalent, because both are equivalent to $$\forall x \, R(x) \lor \exists y \, Q(y). $$ If either predicate used both variables this wouldn't be so: in general, $\exists\forall \to \forall\exists$ but not conversely. But here, you can rearrange the quantifiers because: If $v$ is not free in $p$ then $$\...


0

To be precise in what follows, here are what I am assuming are the axioms: $(\beta\rightarrow (\alpha\rightarrow \beta))$ $((\alpha\rightarrow \beta)\rightarrow ((\alpha\rightarrow (\beta\rightarrow \gamma))\rightarrow (\alpha\rightarrow \gamma)))$ $(((\alpha\rightarrow \bot)\rightarrow \bot)\rightarrow \alpha)$ $(\forall x (\varphi\rightarrow \psi) \...


-1

Nope; but one implication is true: \begin{equation} \exists y\forall x(R(x)\vee Q(y))\to \forall x\exists y(R(x)\vee Q(y)). \end{equation} It's more or less intuitive that this holds: when you have "$\forall x\exists y\dots$" this defines a function: given $x$, exists $x(y)$ such that $\dots$ (You need Choice to define this to be an actual function, so you ...


1

Statement $A$: for every natural number $x$, there exists a natural number $y$ such that $y$ is the successor of $x$ and there exists a natural number $z$ such that whenever $z$ is the successor of $x$, $y$ and $z$ are equal (note that this last part is vacuously true by taking $z=y$, so the whole statement becomes $\forall x\exists y\operatorname{succ}(x,y)$...


1

The set is consistent. Let $M$ be the model with domain $\{a,b\}$. $M$ interprets $P$ as $\{a\}$ and $Q$ as $\{b\}$. Now you can check each sentence is true in $M$.


0

The key to understanding the negative exponential is first understanding the interpretation of negation in linear logic. Unlike in classical logic, where negation roughly indicates the absence of something (i.e. the absence of truth), this does not carry over to the resource interpretation of linear logic. $A^{\perp}$ is best thought of as not the absence of ...


0

Recall that if $p$ and $q$ are propositions, the compound proposition $p \vee q$ can be defined by its truth table. This truth table has $4$ rows, and the truth value of $p \vee q$ will be $F$ only in the row where both $p$ and $q$ have truth value $F$. Similarly, the conditional statement $p \implies q$ is defined to be the proposition $(\sim p) \vee q$...


0

Sorry for the late reply. The property $\forall x \forall y \forall z ((Rxy \land Rxz) \to (Ryx \lor Rzy))$ says that whenever there are transition from $x$ to $y$ and $z$, there is either transition from $y$ to $z$, or vice versa. So, let us assume, that in a canonical (which is reflexive and transitive) model $M$ $(w,v) \in R$ and $(w,u) \in R$, but $(u,v) ...


0

Do a proof by contradiction. Assume that $Atom(\phi)\cap Atom(\psi)=\emptyset$ and prove that we get a contradiction. Let $v_1$ be a valuation such that $v_1(\phi)=T$ (this is possible since $\phi$ is not a contradiction) and $v_2$ be a valuation such that $v_2(\psi)=F$ (this is possible since $\psi$ is not a tautology). Since the atoms of $\psi$ and $\phi$ ...


0

Try a stronger version of the infinitude of primes! Given any natural $m$, there is a least prime bigger than $m$. Which can be stated over first-order arithmetic (with $+,\cdot,<,0,1$) as: $\def\imp{\rightarrow}$ $φ \overset{def}= \forall m\ \exists p\ ( p > m \land prime(p) \land \forall q\ ( q > m \land prime(p) \imp q \ge p ) )$. ...


0

No, modus ponens is not a conjunction. A conjunction consists of a single proposition. Modus ponens has two premises. Also, modus ponens works for implicational propositional calculi where no conjunctions exist. You can substitute a negated formula into an inference rule and obtain a derivable rule of inference provided that you substitute the negated ...


1

As suggested by @rschwieb, I sent an email to Girard. Here is his answer: Hi, The general idea is that logic should not have an adjective: look at modal, non-monotonic, paraconsistent logics in which the adjective is a sort of negation, like in « military justice ». Linear logic is just a way to do plain logic, i.e. to study pure reasoning....


1

First I will show that $\land$ can not be represented using only $\to.$ Let $\mathcal S$ be the set of all formulas $\phi$ such that $\phi$ is a consequence of some propositional variable. Of course, every propositional variable belongs to $\mathcal S;$ moreover, for any formulas $\phi$ and $\psi,$ if $\phi\in\mathcal S$ then $\psi\to\phi\in\mathcal S.$ It ...


2

The problem with using $\Rightarrow$ as the only operator is that you cannot construct an universally false statement - which is required for a set of operators to be functionally complete. You can do this with for example $\lor$ and $\neg$, for example $\neg (\phi \lor \neg \phi)$. To see why this is we can break down any statement into the form $\phi \...


0

Convert to the contrapositive:$$\exists y((\exists x.S(x))\implies S(y))$$with $S=\lnot R$, and maybe it's a little easier to analyse. Simply put, if $\exists x.S(x)$, then there exists a $y$ such that the conclusion, $S(y)$ is true, and the formula is valid. If there is no such $x$, then the formula is vacuously true.


1

There's always $(y=x)\land (w=z)$ of course. But this has the disadvantage that $w$ doesn't need to depend on $x$, though. The best I can think of where this is not the case would be something like $$(y\ne x \lor z=x) \land (z=x \to w=y) \land (z\ne x \to w=x)$$ In a structure with three elements, $w$ will have to depend on both $x$ and $z$.


0

With regards to the bulk of your question before your example: The conditional statement asserts asserts that $q$ is true on the condition that $q$ holds, but the statement itself can be wrong. I can say that my statement $r$ is "if I never study ($p$), then I will always get 100% on my exams ($q$)". Then, when I refuse to study and fail the exam, $r$ ...


1

If you are flipping this house, you should sell it for more than you spent on it (that is just good business). If you have a say in the appraisal amount, it should be $\gt\$419000$; otherwise you just wasted time and/or money. That is as much as we can help you on this site. Perhaps you should try the Home Improvement site or the Economics Site for more ...


1

The first statement is ambiguous. It could mean either "There is an infinite number of sets $E_n$ for which $x\notin E_n$", or it could mean "There is only a finite number of sets $E_n$ for which $x\in E_n$". The second statement can only mean the latter. Addendum: For the first statement, suppose $\mathscr E$ is the collection of all $E_n$ under ...


2

I would say that the first sentence, as written, is ambiguous. It could either be interpreted as A) There is not an infinite number of $E_n$'s all of which contain $x$. B) There is an infinite number of $E_n$'s such that $x$ is contained in none of them. The sentence A) is equivalent to your second sentence "it is not the case that $x$ is in an ...


1

$$ \newcommand{\DeductionBox} [1]{\begin{array} {l|} #1 \\ \hline \end{array}} $$ $$\begin{array} {l} \DeductionBox{ \begin{array} {rlr} \quad (1) & \exists \langle x,~ \forall \langle y,~ Mxy \rangle ~ \rangle \quad & \text{New Assumption} \\ \end{array} \\ \\ \DeductionBox{ \begin{array} {rlr} \quad \quad (2) & \forall \...


0

No. Take a look at the definition of universal set (of some gates and constants) again. It means that every propositional formula can be computed via a circuit that uses only gates and constants from such a set. So "i need to simplify the function and show that the function is using NAND and NOR gates" is false. The nand gate is universal already, so ...


1

Take any consistent first-order theory $T$ that is nice enough (has decidable proof validity). Let $T' = T + \neg Con(T)$. Then $T'$ is consistent and $T' \vdash \neg Con(T)$ and hence $T' \vdash \neg Con(T')$. So $T'$ would prove 'its own inconsistency', but interpreting this correctly is slightly subtle (see this post). $\def\prov{\square}$ Now it is ...


0

If you want to prove that $s$ is false in some context, then you can (in that context) ask whether it is possible that $s$ is true or not. If there is no way that $s$ can be true in that context, then it must be that $s$ is false. (Related to this is proof by contradiction, in that the underlying reasoning is the same.) For concreteness, here is how the ...


2

Well, it is a little unclear what you mean by nonconstructive proof still. But you can think of what models of $ZFC+\neg{Con(ZFC)}$ looks like when you consider $ZFC+\neg{Con(ZFC)}$ as a formal theory, which seems to be part of the question you are asking. First of all a model of the sort of theory you are looking at would have non-standard natural numbers ...


1

$$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma, A \vdash B}{\Gamma \vdash B}$$ This axiom is basically modus ponens, a little prenexing, and universal elimination combined into 1 statement. Suppose I gave you: $$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma \vdash (\exists x ~ A) \implies B}{\Gamma \vdash B}$$ That is just a trivial application of ...


4

The set of even numbers is in fact not definable as a subset of $\omega$, considered as a structure in the language of set theory. Here's one quick way to prove it using a little model theory. Let me write $<$ for the $\in$ relation, since on $\omega$ this relation is the usual strict total ordering of natural numbers. By the compactness theorem, there ...


4

To put this in context, one of Girard's several claims to fame is being the inventor of linear logic, a specialized kind of logic with applications in theoretical computer science and several other places. If he denies being a "linear logician", it could either be understood as a way to distance himself from that particular system (it's old hat to him, he ...


0

Think of the theorem as being rewritten as follows: If $m$ is a natural number, $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators, the string $u_1\dots u_n$ has exactly $m$ symbols, and $u_1\dots u_n$ and $u_1'\dots u_n'$ are compatible, then $u_i$ is $u_i'$ for $i=1, 2,\dots,n$. The proof is by induction on $m$. In the proof, the induction hypothesis is: ...


0

One way to prove that the statements $p \rightarrow q$ and $p \vee q \iff q$ are logically equivalent is as follows. It suffices to show that their truth tables (which have $4$ rows each) are the same. Recall that the only assignment of truth values for $p$ and $q$ for which $p \rightarrow q$ evaluates to $F$ is when $p$ is $T$ and $q$ is $F$. For which ...


0

so we must prove: $(p\Rightarrow q)\Leftrightarrow [(p\vee q)\Leftrightarrow q)]$. suppose $(p\Rightarrow q)$ and prove the equivalence $(p\vee q)\Leftrightarrow q$ $\Rightarrow$): $ (p\Rightarrow q)\Rightarrow[ (p\Rightarrow q) \wedge (q\Rightarrow q)] \Rightarrow [(p\vee q)\Rightarrow q]$. $\Leftarrow$): $q\Rightarrow(p\vee q)$ obvious suppose $(p\vee ...


0

$\overline X\ \overline Y + XYZ + \overline XY + XY$ $\overline X\ (\overline Y + Y) + XY (1 + Z)$ Distributive Law. $\overline X\ + XY$ Complement Law: $\overline A + A = 1$ and Annulment Law: $1 + A = 1$ $\overline X\ + Y$ Redundancy Law: $A + \overline A B = A + B$ Second one: Look for common terms (Distributive). Duplicate terms as needed (...


0

(a): Correct. (b): Sketch of proof: If there are finitely many books, but at least one book, then each book has a finite number of books on top of it. Let $b$ be the book with the least number of books on top of it (this exists by the well-ordering principle, which is equivalent to induction). Then $b$ cannot have zero books on top of it, otherwise it would ...


2

$(p\lor q)↔q$ $=((p\lor q)→q)\land((p\lor q)←q)$ $=(\overline{(p\lor q)}\lor q)\land((p\lor q)\lor \overline {q})$ $=((\overline{p}\land \overline{q})\lor q)\land(p\lor (q\lor \overline {q}))$ $=((\overline{p}\land \overline{q})\lor q)\land(p\lor T)$ $=((\overline{p}\land \overline{q})\lor q)\land T$ $=((\overline{p}\land \overline{q})\lor q)$ $=(\...


1

You got this far: $$p \vee q \equiv (\sim p \vee q) \wedge (p \vee q)$$ Use distributivity: $$p \vee q \equiv (\sim p \wedge p) \vee q$$ By Law of Contradiction, we know that the former part of this disjunction is always false, so using disjunctive syllogism we can conclude: $$p \vee q \equiv q$$


1

Well in your sentence you're missing the fact that x is a cube So to stick with the solution notation i would go $A(x)$="$x$ is a cube" $B(x)$="$x>$something else" Then the solution is indeed correct


4

There is no equivalence (or 'bi-implication'), only the following implication: If $G$ is a group acting on a non-empty set $A$, then the relation $\sim$ on $A$ defined by $$a\sim b\qquad\Leftrightarrow\qquad (\exists g\in G)(a=gb),$$ is an equivalence relation. The 'iff' in your question only serves to define the relation on $A$.


3

Double-negation introduction: $B\supset \neg\neg B$. You know how to derive $\neg B\supset \neg B$, which is an abbreviation for $\neg\neg B\lor \neg B$. Then A3 gives you $\neg B\lor \neg\neg B$, which is the same as $B\supset \neg\neg B$. Double-negation elimination: $\neg\neg A \supset A$. You know how to derive $A\supset A$, which is just $\neg A\lor A$....


1

I think this is in part because I am a little confused as to what "{ϕ1,ϕ2}" means - can this be read as "the set of assumptions we take to be true contains ϕ1 and ϕ2" ? - or maybe "the set of assumptions we take to be true is exactly ϕ1 and ϕ2" ? Indeed I think that's the only problem you're having here. We write "$S \vdash φ$" to mean that we can derive ...


2

I don't follow how this involves if-and-only-if. Hint A) For: if $\{ (φ_1 ∧ φ_2) \} \vdash ψ$, then $\{ φ_1, φ_2 \} \vdash ψ$. 1) $φ_1$ --- assumed 2) $φ_2$ --- assumed 3) $(φ_1 ∧ φ_2)$ --- from 1) and 2) by (∧I) So far we have: $\{ φ_1, φ_2 \} \vdash (φ_1 ∧ φ_2)$. Thus, by Sequent Rule (Transitive Rule) [page 8], from it and $\{ (φ_1 ∧ φ_2) \}...


-1

Partial solution: If there are only a finite number of hats of a certain color, then everyone would see that and should say the opposite color.


4

There are some subtleties buried in the concept of "definable number". What exactly does it mean to you? If you call a number "definable" if it satisfies a formula $\varphi(x)$ in the language of set theory such that $\forall x\forall y(\varphi(x)\land\varphi(y)\to x=y)$ is true, then you run into the problem that "definable" is not itself a property that ...


2

I have some set $S$ of strings over a certain alphabet, defined in a complicated way. There are two basic ways for $S$ to be uninteresting: maybe $S$ is empty, or maybe $S$ is the set of all strings. Taking $S$ to be the set of strings corresponding to theorems of (say) $PA$, clearly the former case doesn't happen; so you can think of the formalist ...


0

A formal system is defined to be inconsistent if all formulae are provable, i.e., if every formula is a theorem. If (as in Nagel and Newman) the formal system includes the usual rules of propositional logic, then a system is inconsistent iff there is a formula $S$ such that both $S$ and $\lnot S$ are theorems (because by those rules you can derive any ...


1

A proof system is usually called also calculus (like: propositional calculus) and we can handle it "mechanically", i.e. avoiding any interpretation. Of course, it is "useful" because we can interpret it (for example, as a way to formalize logical arguments). It is the same with the addition algorithm of elementary arithmetic: with it you can perform ...


0

Maybe I understand it now... Your concern is right: what the exercise proves is something like: if $\Gamma \vdash \phi$, then $\Gamma [r/y] \vdash \phi[r/y]$, i.e. every occurrence of formulae $\phi$ must be replaced with $\phi[r/y]$. At node $\nu$ of the corresponding tree, we have the left leaf $ϕ[t/x]$ and we have to replace it with $ϕ[t/x]′$. But ...


2

Vacuous truth "all elements of A are not elements of B" is NOT the same as saying "there is an element of A that is not an element of B". $\forall x \in A; x \not \in B$ is NOT enough to show $A \not \subset B$. To show $A \not \subset B$ you must show $\exists x \in A; x \not \in B$ and you can not do that if $A = \emptyset$. To pound it home. $A \...



Top 50 recent answers are included