New answers tagged

0

OK, here's an argument that avoids stability theory: Suppose we could interpret $\mathbb{R}$ in a field $K\models \text{ACF}_0$. Note that $K$ must be uncountable. By elimination of imaginaries in $\text{ACF}_0$, we may assume that the domain of the interpretation is a definable subset of $K$, defined by $\varphi(\overline{x})$, rather than a quotient of a ...


0

Okay, let us break the chain of your logic down.   It is just two steps.   You have: $$\begin{align*} \forall x\in D:P(x) ~ \implies & ~ \exists x\in D:P(x) \tag 1 \\[1ex] \exists x\in D:P(x) ~ \iff & ~ \neg \forall x\in D:\neg P(x) \tag 2 \\[1ex] ~ \\[0ex]\hline \\[1ex] \therefore \forall x\in\varnothing:P(x) \implies & ~ \neg \forall ...


0

Work both sides of the equation at the same time. Since there is only 1 rule for $\iff$ and 1 rule for $\implies$, the first 2 steps can be guessed: $$\begin{array} {c|ccc} \lnot p \iff q & p \iff \lnot q \\ % (\lnot p \implies q) \land (q \implies \lnot p) & (p \implies \lnot q) \land (\lnot q \implies p) & & \text{bi-implication}\\ % ...


2

Using double negation, from: $(¬¬p \lor q ) \land (¬q \lor ¬p)$ to : $(p \lor ¬¬q ) \land (¬q \lor ¬p)$ and by implication again: $(¬q \to p) \land (p \to ¬q)$.


1

For the axiom of comprehension the source is traditional logic. See Port Royal Logic: [for] Port-Royal [...] the significance of general ideas has two aspects: the comprehension [la comprehension] and the extension [l'étendue]. The comprehension consists in the set of attributes essential to the idea. For example, the comprehension of the idea ...


0

If $a$ and $b$ are not $\beta\eta$-equivalent, by Bohm’s Theorem there exists a context separating them. Let's call these two new terms $A$ and $B$, with $A \neq B$. Since $[a]_M = [b]_M$, we have also $[A]_M = [B]_M$ by compositionality. Now think of the term "$T \equiv \lambda v .$ if $v = A$ then true else if $v = B$ then false". So the denotation ...


1

Here is the answer I had made over on MathOverflow: Surprisingly, the answer is yes! Well, let me say that the answer is yes for what I find to be a reasonable way to understand what you've asked. Specifically, what I claim is that if PA is consistent, then there is a consistent theory $T$ in the language of arithmetic with the following properties: The ...


0

I would express this as follows using the original notation: $$ \forall c:\forall d: \mathtt{\sim} b=(S(Sc \cdot SS0) \cdot d) $$ Or equivalently $$ \mathtt{\sim} \exists c:\exists d: b=(S(Sc \cdot SS0) \cdot d) $$ Please note that negation in the first formula applies to the whole equality and that the negation in the second formula applies to the whole ...


0

General Strategy Break down what you need to prove according to the introduction rule. This is always possible for conjunction and implication. For a disjunction "$A \lor B$", it may not be possible because sometimes you can prove neither "$A$" nor "$B$", in which case you need to go by contradiction, which is to assume $\neg ( A \lor B )$ and obtain a ...


2

A definition doesn't have to be convincing or appropriate; you can define things however you want. Of course, it is better to have a convincing argument on why a definition is appropriate and corresponds to what is being modeled. You can definitely have good and bad definitions. If we did change the result for $\phi$ false, you'd get logical equivalence. ...


2

You assert that $$[(\forall x \in \emptyset)(\neg P(x))] \Rightarrow \neg [(\forall x \in \emptyset)(P(X))]$$ without providing any justification for it. It's simply false.


0

After having corrected the wrong application of the distribution law, we have the following clauses: Clause 1: $a ∨ ¬b$ Clause 2: $\lnot a ∨ c$ Clause 3: $\lnot a ∨ d$ Clause 4: $b$ and the negation of the formula to be proved: 5) $\lnot d \lor \lnot b$. Now we have to apply resolution, starting with 4)-1) and 4)-5) deriving: 6) $a$ 7) $\lnot d$. ...


0

To prove that $T \vDash \varphi$ we have to apply Resolution to the set $T \cup \{ ¬ \varphi \}$. Thus, as you correctly say, you have to consider the set of clauses: $\{ A \lor \lnot C, A \lor B \lor C, \lnot A, \lnot B \}$. The aim of the procedure is to derive the empty clause: $\bot$ or $\square$. If so, we have proved that the set is ...


2

The problem is really to measure out $2$ kg of flour in one bag. The second bag simply receives all the remaining flour. If you are allowed to put two bags on the scale and then transfer flour between them until the scale balances, you can use the scale to divide a bag of flour in half in one step. Put the bag to be divided on one side of the scale, put an ...


-1

I'm not sure if I am allowed to answer on my question but I solve it. First I combine the 250 and 50g weight and I got a bag of 300g. Then I combine the bag of 300g and the weights of 250g and 50g - I get a bag of 600g. Then lastly I combine the 600g and 300g bag the 250 weight and put the 50g weight on the other side of the balance. I got a bag with 1100g. ...


2

Your answer is correct; it's exactly equivalent to the given statement.


0

I can see how to do it in five steps; maybe someone else can suggest how to condense it further. Start with all the flour in bag $A$. Put the $250$ g weight on one side of the scale. Pour flour from $A$ into bag $B$ on the other side of the scale until it balances the weight. $B$ now contains $250$ g of flour. Put $B$ and the $250$ g weight on one side of ...


1

1) $[P∧(P→Q)∧(Q→R)]→R$ 2) $[P∧(\lnot P \lor Q)∧(\lnot Q \lor R)] \to R$ --- by Material Implication 3) $[(P \land \lnot P) \lor (P \land Q) \land (\lnot Q \lor R)] \to R$ --- by Distributivity 4) $[(P \land Q) \land (\lnot Q \lor R)] \to R$ 5) $([(P \land Q) \land \lnot Q] \lor [(P \land Q) \land R]) \to R$ 6) $([P \land (Q \land \lnot Q)] \lor [P \land ...


0

Recall the equivalence $$ (P \rightarrow Q) \Leftrightarrow (\neg P \vee Q),$$ write the left hand side $$ P \wedge (P \rightarrow Q) \wedge (Q \rightarrow R) $$ as $$ P \wedge (\neg P \vee Q) \wedge (\neg Q \vee R). $$ See what this simplifies to and then see how this means the original statement is a tautology.


1

(2) does not imply (1), because we could take $T$ and $T^*$ both to be $PA$. Then, trivially, Con(PA) implies Con(PA), but we know that PA does not prove Con(PA). (1) will imply (2) given a few additional assumptions about $T$, such as the assumption that $T$ proves all true sentences of primitive recursive arithmetic. Then $\mathit{Con}(T^*)$ can be ...


2

$\neg(\forall x \, P(x))$: "it is not true that $P(x)$ holds for all $x$. This means that there may be some $x$ for which $P(x)$ is true, but there must be at least one for which $P(x)$ is false. On the other hand $\forall x\, \neg P(x)$ says that for all $x$, $P(x)$ must be false. There is no $x$ for which it is true. A similar thing holds for the ...


1

$\neg \forall x \,P(x)$ is equivalent to $\exists x\,\neg P(x)$ (not everything is blue is equivalent to something is not blue), and $\neg \exists x \,P(x)$ is equivalent to $\forall x\, \neg P(x)$ (nothing is unequal to itself means the same thing as everything is equal to itself). Each of the two equivalences implies the other. Here's another way to look ...


2

As far as I can tell, your 'proof' involves an existential elimination to witness ($a$), then universal introduction to discharge this witness.   This is not sound, because a witness is not an arbitrary value. $\require{enclose}\require{cancel}\begin{array}{l|l:l:l} 1 & \exists x\in T: (A \to P(x)) & \text{assume} & +1 \\ \quad 2 & ...


1

HINT By definition, a well- ordered set is a set $X$ with a total ordering '$\leq$' with the property that every non-empty subset of $X$ has a minimal element. So if $A$ is a non-empty subset of $X$ then obviously it has a minimal element. Now suppose $a$ and $b$ are two minimal elements of $A$ what does total ordering say?


0

I apologize for being late to the game, but here goes: Since due to the identity rule, then . Now distribute to get . is a contradiction, or a negation law. Thus . So we now have . we can now use the identity law of , assuming . Thus is the definition of Decomposing a conjunction in the laws of Tautology. Please refer to page 7 of the ...


0

Here's how to do it, not in full gory detail — three of the steps below appeal to simple equivalences; each has to be expanded to establish the particular case of the cited equivalence: $$ \begin{array}{r|ll} \text{step} & \text{Formula} & \text{How obtained} \\ \hline 1 & (\neg p \land r)\to (q \lor s ) & \text{assumption} \\ 2 & ...


0

If $C$ represents $¬p$, then that means both $A$ and $B$ represent the same proposition ($p$).   If this is possible, then why does the rule specify three distinct propositions ($A$, $B$, and $C$)? The tokens $A, B, C$ may represent distinct propositions, but they are not required to be so.   The rule applies to any three propositions, whether ...


1

In the study of logic, there are two approaches. You can start with just logic and a few axioms, or you can start with the mathematics you like, and prove within it the validity of logical definitions (in particular, this approach gives reverse mathematics). You can read the introduction of the Cori-Lascar book for this complementarity. Suppose you did not ...


1

So, as you've noticed, this notion is absolutely ubiquitous. There's a general notion of "isomorphic objects are equal (for all intents and purposes)". Particularly for categorists, notions that distinguish between isomorphic (or more generally, equivalent) objects are often referred to as "evil". In category theory, the principle you describe is called ...


0

Definition 2 is defining a shortened form to express domain restrictions. "Anything in D, makes P true" iff "Anything, when it is in D, then it makes P true". $$(\forall x\in D)(P(x)) \iff (\forall x)(x\in D\to P(x))$$ "There's something in D, that makes P true" iff "There's something, that is in D and makes P true". $$(\exists x\in D)(P(x)) \iff ...


0

Yes, that's the correct approach, and your missing argument begins If $B = A\cup B$ is assumed, this means that if $x\notin B$, then $\underline{\qquad}$ (by definition of union).


1

My suggestion for proving is to begin with what you want to prove and in the middle, try to use the assumption. I mean if you want to show $A \subset B$, begin with that $x \in A$ and try to reach $x \in B$. I write the proof for some cases: Assume $B^c \subseteq A^c$ to prove $A \subseteq B$: $x \in A \Rightarrow x \not \in A^c \Rightarrow x \not \in ...


0

Your answers are correct. For the third implication, assume $A \cup B =B$, and let $x \in B^c$. By the definition of complement, $x \in A$ or $x \in A^c$. Suppose towards contradiction that $x \in A$. Then $x \in A \cup B$. But by our assumption this means $x \in B$, a contradiction. Hence $x$ is not in $A$, and so it must be that $x \in A^c$. It follows ...


1

$\exists x ~:~ (S(x) \land \lnot E(x, \text{Calculus II})), x\in \text{People}$ Two notes: While defining the predicates, you may as well use $C$ for "is enrolled in Calculus II"; particularly since the domain of discourse is "people" then such should be the only variables and constants in play. The domain restriction should be attached directly to ...


1

For Part (1), I suggest instead of using $E(x, y)$, just use $C(x)$ and have it mean that a student $x$ is in Calc II. But your answer is correct still. For part 2, writing $$\forall x ~:~((P(x) \land \forall y ~:~(H(y))) \implies Y(x,y))$$ Means "Every person is a primary school student, and every high school student is older than him". That is not ...


0

This is what I came up with in the end: $\neg \forall x(P(x)\land Q(y)\implies \exists zR(z))$ $\exists x\neg (P(x)\land Q(y)\implies \exists zR(z))$ DeMorgan's $\exists x\neg (\neg (P(x)\land Q(y))\lor \exists zR(z))$ Implication $\exists x(P(x)\land Q(y)\land \neg \exists zR(z))$ DeMorgan's $\exists x(P(x)\land Q(y)\land \forall z\neg R(z))$ DeMorgan's ...


2

This is a circular graph with the statements $x_i$ as vertices and the implications $x_i \implies x_j$ as directed edges $(x_i, x_j)$. This means you can reach any two statements $x$, $y$ via a finite number of implication, or $x \implies y$, because of the transitivity of the implication: If $x \implies y$ and $y \implies z$, then $x \implies z$. As $x ...


1

Implication is a transitive relation. A transitive relation is a relation such that if $a \sim b$ and $b \sim c$, then $a \sim c$. So if $a \Rightarrow b$ and $b \Rightarrow c$ then $a \Rightarrow c$. Thus $a \Rightarrow c$ and $c \Rightarrow d$ imply that $a \Rightarrow d$ and $a \Rightarrow d$ and $d \Rightarrow a$ imply $a \Rightarrow a$.


5

Just write this chain two times: $a \Rightarrow b \Rightarrow c \Rightarrow d \Rightarrow a \Rightarrow b \Rightarrow c \Rightarrow d \Rightarrow a$ (this is true, it follows from what you have) Now from here it's obvious that $x \Rightarrow y$ for any $x,y\in\{a,b,c,d\}$


1

Here is an informal approach: (By 'is equivalent to', I mean 'has the same truth table'.) Suppose you have some formula $\phi(x_1,...,x_n)$ created with the connectives mentioned. Then either $\phi(\lnot x_1,...., \lnot x_n)$ is equivalent to $\phi(x_1,...,x_n)$ or $\phi(\lnot x_1,...., \lnot x_n)$ is equivalent to $\lnot \phi(x_1,...,x_n)$. This is not ...


4

HINT: By induction on the complexity of a formula $\varphi$ in two propositional variables $p, q$ built from $\neg$ and $\iff$, we can show that there are an even number (0, 2, or 4) of truth assignments making $\varphi$ true. Actually, you use induction to completely classify the possible $\varphi$ which can be built in this way; this is a case of needing ...


0

$\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$ By DeMorgan, we have $\exists x\neg (P(x) \wedge Q(y) \implies \exists zR(z))$ Use the equivalence $(p \implies q )\iff (\neg p \vee q)$ to get $$\exists x\neg (\neg(P(x) \wedge Q(y) )\vee \exists zR(z)) $$ Keep using your properties to continue simplifying. Can you take it from here?


0

It seems you mean: Assuming a fixed finite universe, how do you express a sentence like $\exists x Sing(x)$ as a "string" of propositions? Let's assume you have names for all the intended elements of the universe. For the sake of concreteness, assume $a,b,c$ are constants that will denote $x,y,z$ respectively. Then $\exists$ corresponds to disjunction: in ...


2

There are a total of 25 possible arrows in your "directed graph," assuming self-love is allowed. So the number of possible graphs is $2^{25}$. Then we want to remove the one case with zero edges. So the total is $2^{25}-1$. If love is symmetric and no self-love, there are $10$ possible edges, and the total is $2^{10}-1$. Basically, any non-empty subset ...


2

Yes, this is true. Suppose $s(x_0,x_1,\dots,x_n)$ and $t(x_0,x_1,\dots,x_n)$ are terms in the language of addition such that $s(r,x_1,\dots,x_n)=t(r,x_1,\dots,x_n)$ for all $x_1,\dots,x_n\in\mathbb{R}$. We can choose $a_1,\dots,a_n\in\mathbb{R}$ such that $r,a_1,\dots,a_n$ are linearly independent over $\mathbb{Q}$. Let $F\subset\mathbb{R}$ be the ...


1

I don't have the book, but this must go with a definition of substitution of $t$ for $x$ in $\phi$, which I'd write $\phi[t/x]$ and which you are writing as $\phi^x_t$. The definition goes like this (where $y$ denotes any variable other than $x$): $$ \begin{array}{tcl} x[t/x] & = & t \\ y[t/x] & = & y \\ (\lnot\alpha)[t/x] & = & ...


1

However, my problem has 2 variables (instead of one, like in the aforementioned example). I'm not sure how to handle that. a) $[P(a,a)\lor P(b,a)\lor P(c,a)]\land [P(b,a)\lor P(b,b)\lor P(b,c)]\land [P(c,a)\lor P(c,b)\lor P(c,c)]$ Almost as you did; but not quite (you muddled up the first grouping). (Also, mind your Pees and Queues.) When in ...


0

Use the following: $\begin{array}{l:c:l} 1. & A\bar\vee B = \neg(A\vee B) & \bar\vee \textsf{ is nor} \\ 2. & (A\vee B)= \neg(\neg A\wedge \neg B) & \textsf{by deMorgan's Law} \\ 3. & A\barwedge B = \neg(A\wedge B) & \barwedge \textsf{ is nand} \\ 4. & \neg A = A\barwedge A & = A\bar\vee A \textsf{ also} \end{array}$


2

Note that $$(p \operatorname{NOR} q) \equiv (\neg p \land \neg q), $$ so that $$ \neg p \equiv (p \operatorname{NOR} p) $$ and therefore $$ (p \land q) \equiv (\neg p \operatorname{NOR} \neg q). $$ Now, $\operatorname{NAND}$ is defined as: $$\begin{align} (p \operatorname{NAND} q) &\equiv \neg(p \land q), \end{align}$$ so by the above, it's clear how ...



Top 50 recent answers are included