New answers tagged

1

It is the same as in the normal case, but now you have to simplify some more. So as you say, in general the contrapositive of $p\implies q$ is $\neg q\implies \neg p$. For the statement $(p\wedge q)\implies(\neg q\vee p)$, let us say that $A=p\wedge q$ and $B=\neg q\vee p$. Then you know what to do, because the contrapositive is simply $\neg B\implies\neg ...


1

[This is a partial answer, but I decided to post it anyway since no one else has answered for a long time now. Very interesting question by the way!] Note that if $T = PA + \neg Con(PA)$, then $T \vdash \neg Con(T)$ and hence $T_2$ is inconsistent and proves everything, so your hierarchy collapses. So it's not enough just to assume that $T$ contains $PA$. I ...


0

1) $\phi \to \psi ∨ \chi$ --- premise 2) $\phi$ --- assumed [a] 3) $\psi ∨ \chi$ --- from 1) and 2) by $\to$-elim 4) $\psi$ --- assumed [b] for $\lor$-elim 5) $\phi \to \psi$ --- from 2) and 4) by $\to$-intro 6) $(\phi \to \psi) \lor (\phi \to \chi)$ --- from 5) by $\lor$-intro 7) $\chi$ --- assumed [c] for $\lor$-elim in the same way: 8) $(\phi \to ...


3

What you call "multiple forcing" is called "iterated forcing". And the entire amazing thing is that you can find a single forcing poset in the ground model, which accomplishes this iteration in one go. So what we do, usually, is define by recursion this partial order. We often find it easier to "access the models", because names of iterated forcing can be ...


1

Let's think about your sentence carefully: I won't go the library unless I need a book. This sounds like you hate the library, and that as a general rule of thumb, you should not be expected to be caught dead there, except for one extenuating circumstance (you need a book). Let's evaluate your proposed translations. Translation 1 ($\neg q \to p$): ...


1

"$A$ unless $B$" is usually read in English as $A$, if not $B$. Thus, for I won't go the library unless I need a book, will be: I won't go the library, if I do not need a book. With: $p$: I will go the library $q$: I need a book will be: $\lnot q \to \lnot p$ that is the same as: $p \to q$. $\lnot q \to \lnot ...


4

Asaf has given a great answer - let me give another answer which shows a sense in which the answer is no. Given a theory $T$ (in a finite language to avoid silliness), we can ask if it has a computable model - that is, if there is a $\mathcal{A}$ which is a model of $T$, has domain $\mathbb{N}$ (or a computable subset of $\mathbb{N}$), and all the ...


1

Here is another example, $$\forall x(S(x)\neq x)$$ It holds for $0$, and if it holds for $x$, then it holds for $S(x)$ as well. But it is possible to have a model with an element which is its own successor.


7

Here's an even simpler one: "Every number is either even or odd." That is, $$\forall x\exists y(x=y+y \mbox{ or } x=y+y+1).$$ The polynomial $x$ is a counterexample. Ignoring the specific model and focusing on the theory, it's also worth noting that Robinson arithmetic doesn't even prove that addition is commutative or that the successor of a number is ...


2

For a sentence true for the ordinary natural numbers, but false in the polynomials described above, we can use $$\forall w\exists y_1\exists y_2\exists y_3\exists y_4(w=y_1^2+y_2^2+y_3^2+y_4^2),$$ since by a result of Lagrange every non-negative integer is the sum of $4$ squares, but the polynomial $x$ is not a sum of $4$ squares of polynomials.


0

This riddle has a massive flaw and it pokes a massive hole in it all. Beyond the following quote "Do you believe I am the type who could ask you whether you are insane?" This means that the native is asking whether they an ask about their sanity. It does not say anything about whether it is "are you insane" or "are you not insane". Therefore, they ...


0

We can analyze this question using boolean algebra. Let $p$ represent whether the native is type A (true) or type B (false), and let $q$ represent whether Thomas is sane (true) or insane (false). The statement "Can the native ask the question 'Is Thomas insane?'" is logically equivalent to $p\oplus q$, where $\oplus$ is XOR or exclusive or. The statement ...


1

If a proposition $Q$ is true, a sane Thomas believes it, and would answer Yes to the question "do you believe $Q$?". An insane Thomas does not believe it but would answer Yes to the question "do you believe $Q$?". If $Q$ is false, a sane Thomas does not believe it and would answer No to the question "do you believe $Q$?". An insane Thomas does believe it ...


0

New answer. I think Smullyan is wrong. If the types can ask based on the correct answer and not and the responder answer than: Type A => Thomas believes. Thomas sane => native is type. => type a => Thomas insane. Contradiction. Thomas insane=> native not type. Native A => Thomas not insane. Contradiction. So native type B. So Thomas Does not ...


0

I don't follow your argument for case 3. The question as posed must be answered "No" if the native is type B; and if Thomas is sane, he will answer "No" truthfully. For if the native asks a sane Thomas, "Are you insane?", then he will answer "No." This will only work if the native is Type B.


0

The answer to "Are you insane?" will be "No" from anybody who is sane or insane The type who asks questions with the answer "No" is type B, so the original question is equivalent to "Do you believe I am type B?" This can be asked by a Type B native to an insane person, who will give the answer "No", and a Type B person can also ask "Are you insane?"


1

Your reasoning for Case 4 might be flawed: If Thomas is insane, then his answer to the question "Are you insane" must be "No". For this reason you could consider this the correct answer to the question, in which case there is no contradiction.


1

It happens that we find "interesting" to explore the conclusions that can be logically derived from a set of formal statements. It could be "interesting" for different reasons such as: maybe the statements are all true for a specific "interesting" model (such as arithmetics or set theory) that we want to study maybe the statements are all true for several ...


1

In context, if $B$ implies $A$ but $A$ does not necessarily imply $B$, we typically say: $B$ implies $A$, but the converse does not hold.


1

There does exist such a thing as propositional calculi with quantifiers. This got explored by logicians such as Lesniewski, Lukasiewicz, and Meredith. Basically, $\forall$p p is equivalent to K01, which is equivalent to 0. $\exists$p p is equivalent to A01, which is equivalent to 1. $\forall$p Cpq is equivalent to K C0q C1q. $\exists$p Cpq is equivalent ...


2

As you remark, doing formal proofs from the group axioms is not very interesting -- that won't let us prove (or even formulate) most of the theorems of what we know as group theory. So what does the group axioms have to do with axioms for general mathematical reasoning, such as the axioms of Peano Arithmetic or set theory? I would like to propose that the ...


6

No. And yes. $\sf ZF$, and by extension $\sf ZFC$, cannot prove their own consistency. Therefore within the confines of $\sf ZF(C)$ we cannot even prove that there are models of $\sf ZF$ to begin with. Not only that. The statement "$\sf ZF(C)$ is consistent" is absolute between the universe and transitive models, so if there is a transitive model, not only ...


0

No, propositional calculus does not allow for existential or universal quantification. The reason being propositional calculus is supposed to be "the most bare boned calculus" you can construct to derive "useful" things with. Interestingly enough, even solving for this simple a system is NP-complete, which means that given a formula, finding solutions take ...


0

You say: Let $$A=\{x\in \mathbb{R}|\exists\phi:\forall a\neq x: \phi(x)=true \wedge \phi(a)=false\}$$ where $\phi$ is a formula with one free variable. Consider this: For each $x$ you can always choose $\phi(y)$ to be the simple formula $y = x$. Then $\phi(x)$ is $x = x$, which is $true$, while for $a \neq x$, $\phi(a)$ is $a = x$, which is $false$. This ...


1

However, now am wondering what the roots are of propositional logic, I mean, we don't know propositional logic innately, we have to first learn it, but what are the informational prerequisites? You know English, and therefore you know the rough meaning of the words "if", "not", "and" and "or". Propositional logic is merely a precise system that assigns ...


10

Axioms Originally, "axioms" meant "self-evident truths", or at least what seemed self-evident. But the more important question is what axioms are used for. From the beginning, logic in some form has been an essential part of reasoning, and we reason about things all the time. Then whenever we want to convey our reasoning to other people, and want them to ...


-1

Axioms are actually architectural instructions for building an abstract structure which in this case is group. Every axiom is responsible for certain part of structure or even structure itself, in case you drop one axiom, the abstract structure would collapse.


0

Why are these conditions an algebraic structure has to satisfy to be called a group are called axioms? What have these conditions to do with the word "axiom" in the sense specified above? It's the same thing, you also do not prove them, you assume they are true in the respective theory you're looking at (group theory in your case). So they are also ...


1

$\begin{align}n, \neg (c\wedge n)\vdash&~ \neg c \\ h\wedge \neg s\vdash&~ \neg s \\ h\wedge \neg s\vdash&~ h \\ \neg c, \neg s\vdash&~ \neg (s\vee c)\\ h, \neg(s\vee c), h\wedge \neg (s\vee c)\to p\vdash & ~ p\end{align}$ More or less. Format and provide justifications .


2

For a collection $C$ of subsets of a set $S,$ the intersection of $C$ is the set of elements of $S$ which belong to each element of $C.$ So if $C$ is empty, it would be the collection of $x$ such that, for each set $E$ in $C,$ we have $x \in E.$ Since there are no such sets $E,$ one can say that IF $E \in C$ THEN $x \in E,$ because the part just after the IF ...


3

No, it's like the empty product or the empty sum. $$\prod_{x\in\emptyset}x=1$$ $$\sum_{x\in\emptyset}x=0$$ $$\bigcap_{x\in\emptyset}x=G$$ and through similar reasoning one would get $$\bigcup_{x\in\emptyset}x=\emptyset$$ as the operation on the empty set is always the neutral element of that operation. The reason is such that you can say "any collection" ...


0

For every $x$ and $y$ there exists $z$ such that $x−y=z$ $$\forall x~\forall y~\exists z~{(x-y=z)}$$ A predicate is a statement that has a truth value depends on the state of its variables.   The statement that $(x-y=z)$ is a predicate with three variables.


1

I won't write out an exact natural deduction proof since that seems to be the purpose of the exercise. Also, you haven't actually listed your axioms. You could translate the following outline of a proof into the a natural deduction proof though (assuming you have some version of the excluded middle as an axiom): From $\lnot (C \lor (F \land G))$ derive 2 ...


1

By definition, $P$ is closed under sucessors, i.e., $\operatorname{Sc}(P)\subseteq P$. Also, by definition $1\in P$, so $\{1\}\subseteq P$. So if we define $A=\{1\}\cup\operatorname{Sc}(P)$, it is the union of two subsets of $P$, hence a subset of $P$ itself. The proof goes on to showing that $1\in A$ and $\operatorname{Sc}(A)\subseteq A$, from which the ...


6

The nifty thing about sets is that they are things. We can talk about functions whose values are sets, or functions that take sets as inputs, or make sets of sets, or sets of sets of sets ... This is quite useful, and in fact absolutely ubiquitous in higher mathematics. The downside of this is that when sets are "things", there can't be a set for any ...


0

The predicate $S(x) = \text{True}, \forall x$ does not correspond to a set.


2

No, second-order logic over the empty language is basically as powerful as second-order logic over an arbitrary language. To see this, suppose $\varphi$ is a second-order sentence with some non-logical symbols; let $\psi$ be the sentence gotten by "universally quantifying out" the non-logical symbols in $\varphi$. For example, if $\varphi$ is the sentence ...


-1

Undoubtedly, a shorter proof exists, but here's a Prover9 proof: % -------- Comments from original proof -------- % Proof 1 at 12.05 (+ 0.88) seconds. % Length of proof is 40. % Level of proof is 14. % Maximum clause weight is 24. % Given clauses 1744. 1 P((x -> y) -> (-y -> -x)) # label(non_clause) # label(goal). [goal]. 2 -P(x -> y) | -P(x) | ...


1

Undoubtedly a shorter proof exists, but here's a Prover9 proof: % -------- Comments from original proof -------- % Proof 1 at 208.84 (+ 24.69) seconds. % Length of proof is 53. % Level of proof is 20. % Maximum clause weight is 24. % Given clauses 9783. 1 P((x -> y) -> ((-x -> y) -> y)) # label(non_clause) # label(goal). [goal]. 2 -P(x -> y) | -P(x) ...


0

The first structure is not a field because the distributive law fails to hold. If you use more familiar notation (where T is a 0 and F is a 1) then we get that $0 \cdot 1 = 1$, which seems to imply that perhaps the distributive law is violated. We can show this by computing $(T+T) \vee T$ in two ways and we get two different answers: $F \vee T = T$, and if ...


2

One way to prove this is to use the (upward and downward) Löwenheim-Skolem theorems. Suppose your sentence is true in a model of infinite cardinality $\kappa$, and suppose $\lambda$ is another infinite cardinal. By Löwenheim-Skolem, your sentence is also true in some model of size $\lambda$. But, thanks to the absence of any predicates, all models of size ...


4

You’re almost there: $(p\land q)\lor(p\land\neg q)\equiv p\land(q\lor\neg q)$ by one of the distributive laws. Can you finish it now?


-1

It helps to know: Two logical expressions are equivalent iff they have the same truth table $(a \rightarrow b) \leftrightarrow (\neg a \vee b) $ (One can proof that using the truth table) $(a \rightarrow b) \leftrightarrow (\neg b \rightarrow \neg a) $ (One can proof that using the truth table) $(a \vee \neg a) =1$ (Tautology) $\neg \neg a = a$ (Double ...


1

Negation has a few effects. For this example $\lnot (p \land \lnot q)$ becomes $(\lnot p \lor q)$.


3

In your case the commas are being used to separate propositions (premises) in an argument. In your example, the premises $\neg p $ and $p\vee q$ result in $q$.


2

The comma is not part of any propositional formula. The set before the symbol $\models$ has two elements, both formulas: $\neg\, p$ $p \lor q$ The statement $\{\neg\, p, p \lor q\} \vdash q$ means: $q$ follows from the two premises, in some particular deductive system. In LaTeX/MathJax, $\vdash$ is written as "\vdash". The symbol $\models$ means: $q$ is ...


1

"From what it seems to me, proofs by contradiction, only work where boolean logic applies, where a contradiction leads to something meaningful. If a contradiction doesn't lead to anything meaningful, then it can't constitute a proof can it?" This is a correct statement. If the contradiction isn't universal, then this isn't a "proof by contradiction". ...


1

I believe proof by contradiction is readily used in fuzzy logic, which is not Boolean, so really the question depends on what is meant by "drawing a line."


0

In general, if we are trying to prove $p \Rightarrow q$ , then we do not assume it is true. Rather, we assume $p$ and, for contradiction, we also assume not $q$. Then we (hopefully) arrive at a contradiction. This means that our assumption of not $q$ was false, so we showed that $q$ is true. If, as in your example, you are just trying to prove a statement ...


0

$$ (p \iff q) \qquad\qquad\equiv\\ (p \rightarrow q) \wedge (q \rightarrow p) \qquad\equiv\\ (\neg p \vee q)\wedge(\neg q \vee p) \qquad\equiv\\ ((\neg p \vee q)\wedge \neg q) \vee ((\neg p \vee q)\wedge p) \qquad\equiv\\ (\neg p \wedge \neg q) \vee (q\wedge p). $$



Top 50 recent answers are included