New answers tagged

1 vote

Modal Logic Question: In S5 modal logic is p and □◊¬p a contradiction?

No. Consider the Kripke frame with two worlds, both accessible to themselves and each other. And let one world have $p$ true, and the other false. The world where $p$ is true has $p\land\square\...
0 votes

Solve |a + b| where |a| < 1 and |b| < 1?

I don't know how you got to $a^2+b^2 < 4-2ab$, but if you have, you're almost there. Bring the $2ab$ to the left hand side to get $$a^2+2ab+b^2 < 4.$$ Then observe that the left hand side is $(a+...
6 votes

The proof of the Keisler-Shelah theorem

I attended a course taught by Tom Scanlon in Spring 2015, in which we actually went through all the gory details of Keisler-Shelah in class (this is even more astonishing when you consider that the ...
0 votes

Are the two statements equivalent?

I wish to to take up the question in a broader setting not limited to mathematics. The divergence between two formulas can be discussed from the point of the contrast between open formula/closed ...
  • 1,105
3 votes

Logic behind equations and inequalities involvin absolute values

You can get the lower results from the upper ones. For example: $\begin{array}{c}&&& |x - a| & \leq & D \\ \implies & -D & \leq & x - a & \leq & D \\ \implies &...
  • 15.5k
1 vote
Accepted

Semantics of propositional logic

The distinction between interpretation and valuation is not very clear-cut; different authors use the terms differently. The word "interpretation" tends to have a wider scope, meaning a ...
  • 9,620
0 votes

Are the two statements equivalent?

Since you assumed that m,n are arbitrary, once you’ve actually derived something you can use the Universal Quantifier because arbitrary names/sets allow you to make statements/inferences without loss ...
0 votes

Converting formulas to Skolem form.

Yes, you can drop the $\forall z$ in the $\forall x \exists y \forall z \exists w (¬Q(f(x),y) \land P(a,w))$ formula Also, no need to introduce an existential for a constant ... only to have it ...
  • 91.9k
0 votes

Converting formulas to Skolem form.

The usual presentations of first-order predicate logic syntactically allow vacuous quantification.Rewriting a formula deleting vacuously binding quantifier leaves the formula logically equivalent. ...
  • 1,105
3 votes

Does $\Sigma_1$-separation over $L_\alpha$ admissibility?

In fact we can get $\Sigma_1$-collection directly! The following argument is pulled from a set of handwritten notes by Ronald Jensen, which seems to be called "Admissible Sets". Jensen ...
  • 529
3 votes

Using double inclusion to show $(A △ B) ∪ C = (A ∪ C) △ (B \setminus C)$

There are a number of errors in the first part of your proof, so I'm going to just deal with those in this answer. If $x ∈ C$, then $x ∈ A ∪ C$, therefore, $x ∈ (A ∪ C) △ (B \setminus C)$. This is ...
  • 10.4k
0 votes

True or false? $x^2\ne x\implies x\ne 1$

If you'd like a more informal understanding of why the statement given is indeed true, consider the argument of the proposition. It's purely stating that if $x^2 \neq x$, then $x \neq 1.$ This ...
1 vote

Are the converses of the following mentioned theorems also true?

The first converse is true if both sets are nonempty or both sets are empty. The second one is always true. The statement you say is not necessarily an implication actually is. Let me prove you the ...
  • 3,599
0 votes

Why is the "implication" operation in mathematical logic called "implication"?

The best way to understand the material conditional P->Q is just to say “if you assume P, then Q follows.” This might be true because other assumptions are involved. The way we usually think of ...
0 votes

Chiswell/Hodges Exercise 3.5.5 -- Inequality for the number of truth values in truth table

Let us discuss the calculation over a parsing tree example from the book. The formula $\phi$ is $(p_{1}\wedge (\neg(p_{0}\rightarrow p_{2})))$, depicted as: So, the number of nodes, $n$, is $6$. The ...
  • 1,105
0 votes

Can ultrapowering add choice?

If $M^\mathcal{U} \models$ extensionality, then the answer is "no". I claim the following are equivalent: $M^\mathcal{U} \models$ extensionality $M \models$ "For all families $\{A_i\}_{...
  • 23.2k
1 vote

Struggling with theorem proof involving only disjunctions

$(r\lor p)\land(r\lor q)\land(s\lor\neg p\lor \neg q)\implies(\neg r\implies s)$ $(r\lor p)\land(r\lor q)\land(s\lor\neg p\lor \neg q)\land\neg r\implies s$ $(r\lor (p\land q))\land(s\lor\neg p\lor \...
1 vote

Struggling with theorem proof involving only disjunctions

Assume $\lnot r$. Since $r\lor p$, we must have $p$. Since $r\lor q$, we must have $q$. Since $s\lor \lnot p\lor \lnot q$, we must have $s$. Thus $\lnot r\rightarrow s$.
1 vote

Proving that $p \implies q$ and $\neg p \implies \neg q$ are not equivalent, without using truth tables

Taking $q=\neg p$ we get $$(p \Rightarrow \neg p) \Leftrightarrow (\neg p \Rightarrow \neg \neg p)$$ $$(p \Rightarrow \neg p) \Leftrightarrow (\neg p \Rightarrow p)$$ $$(\neg p \lor \neg p) \...
  • 36
1 vote

Proving that $p \implies q$ and $\neg p \implies \neg q$ are not equivalent, without using truth tables

$0$ indicates "false", and $1$ indicates "true". $\forall p,q\in\{0, 1\}(p\implies q\iff\neg p\implies\neg q)$ $\implies(1\implies 0\iff\neg 1\implies\neg 0)$ $\iff(1\implies 0\iff\...
-1 votes

Does the LNC imply the LEM?

Everything implies that which is a tautology (LEM in this case):
0 votes

Translating Logical Statements

The first two statements are correct. In the third statement, notice that you can replace "..but if..." with "...and if..." without changing the meaning, so you should be using the ...
0 votes
Accepted

what's the truth value of this statement

$\forall x\in\mathbb{R}(\frac{x^2+2}{x^2-1}\in\mathbb{R})$ $\implies\frac{1^2+2}{1^2-1}\in\mathbb{R}$ $\iff\frac{1+2}{1-1}\in\mathbb{R}$ $\iff\frac{3}{0}\in\mathbb{R}$ $\iff$ false
3 votes
Accepted

A logic with no axioms or no inference rules

(1) Where did $\Gamma$ come from? Ultimately it must have come from an axiom (if it is not an axiom itself). (2) You are using a rule of inference: from $\Phi$ deduce $\neg(\neg\Phi)$. And BTW, "...
  • 78.1k
0 votes

How can I prove (A − C) ∩ (C − B) = ∅ using set-builder notation and propositional logic?

Define a suitable universal set $U$, say, $U=A\cup B\cup C$, so that we could use the complement operation. Then $(A-C)\cap(C-B)=(A\cap\overline{C})\cap(C\cap\overline{B})=A\cap(\overline{C}\cap C)\...
1 vote
Accepted

Represent the statements into symbolic form as follows

Let f(x)=x^2+x+2 and g(x)=x-2. If you want to be less precise, let ‘H(x,y)’ be the predicate “x is a graphical point of intersection with y”. Then, we can define your sentence as: ∀x∀y(x,y∈ℝ—>~(H(f(...
0 votes

What's a good rigorous Arithmetic book? Specifically one on which the classic arithmetic algorithms are rigorously proven?

I'd recommend Understanding Numbers in Elementary School Mathematics by Hung-Hsi Wu. Be sure to reference the errata listing on Wu's website.
  • 1,678
0 votes

A variable whose domain is one value.

Apart from the relevant syntactic characterisations, taken generally, there is a significant difference between an individual constant $\alpha$ and a variable $x$ that is bound to be interpreted as $\...
  • 1,105
0 votes

What's a good rigorous Arithmetic book? Specifically one on which the classic arithmetic algorithms are rigorously proven?

I would check out Set Theory: The Structure of Arithmetic by Hamilton and Landin. I love this book. They define addition formally and prove the addition tables and all the usual properties of ...
2 votes

Proof of undefinability of the "Most" quantifier in first-order logic

I think your claim follows from this zero-one law for first-order sentences in finite models. If $\sigma$ consists of a single unary predicate $P$, then the probability that a random $\sigma$-...
  • 7,046
0 votes
Accepted

Proof of undefinability of the "Most" quantifier in first-order logic

I shall sketch out a proof on a line of an argument that I learnt from Fred Landman's Structures for Semantics (Kluwer Academic Publishers, 1991). Let us first construe the grammatical quantifier most ...
  • 1,105
1 vote

Using logical equivalences to show $(A \Delta B) \cap C = (A \cap C) \Delta (B \cap C)$

Always work with both the LHS and RHS to make your life simpler. RHS := $(A \cap C) \Delta (B \cap C) = (A \cap C) \cup (B \cap C) \setminus ((A \cap C) \cap (B \cap C))$ which becomes $= (A \cup B) \...
1 vote

Using logical equivalences to show $(A \Delta B) \cap C = (A \cap C) \Delta (B \cap C)$

Suppose that x is in (A XOR B) $\cap$ C. Two cases, WLOG assume that x is in A, not in B and in C. But then x is certainly in A $\cap$ C, and since it is not in B, it cannot be in B $\cap$ C. But ...
  • 231
3 votes
Accepted

How can I prove (A − C) ∩ (C − B) = ∅ using set-builder notation and propositional logic?

Note that $$A-C=\{a : a\in A\text{ and } a\notin C\}$$ $$C-B=\{c : c\in C \text{ and } c\notin B\}$$ By definition of $A-C$ we have that $(A-C)\cap C=\emptyset $ as if that were not true, then there ...
  • 1,527
2 votes

What are proofs in constructivist logic?

The difference lies in semantics; a constructivist says that mathematical theorems are not proofs, but rather proofs of provability. This is not accurate. As far as I know, no one believes that ...
  • 23.2k
-1 votes

Proof of undefinability of the "Most" quantifier in first-order logic

When we state "most" , it has multiple meanings in finite cases (infinite cases have more meanings) & "Cardinality Comparing" (restricting to what you state) is one specific ...
  • 1,122
2 votes
Accepted

Extending empty set + adjunction to interpret PA

I think it helps to reason semantically here. Let $\Phi$ be the usual interpretation of $\mathsf{Q}$ in $\mathsf{N}$, and suppose $\mathcal{M}\models\mathsf{N}+\epsilon\mathsf{Ind}$. Then we can show ...
0 votes

Give a counter example of:

ok, i have a simpler solution: $\{x\in N:x \bmod 2 =0\}\implies \{x+1\in N:(x+1) \bmod 2=1\}$ the intersection of evens and odds is empty. so i have no inclusion.
  • 176
4 votes
Accepted

Why does this meta-theorem about relativization directly speak of the elements in the model rather than the constants available in the language?

The quantifiers in Proposition Scheme 6.1 are all ordinary quantifiers, not "meta-theoretic" quantifiers. The only "meta" quantifier here is over the formulas $\varphi$ (which is ...
2 votes

What is the scope of a variable in set-building notation?

In logic, set builder (or, set abstraction) operator is syntactically a variable-binding term operator. Variable-binding term operators constitute a class by themselves: They form terms from terms ...
  • 1,105
1 vote

Different versions of Duality principles

Let us consider $2$ dimensional projective geometry. With respect to a certain basis, A point is defined as a $3 \times 1$ matrix (column vector) with coordinates $X=\begin{pmatrix}x\\y\\t\end{...
  • 67.1k
4 votes

What is the scope of a variable in set-building notation?

The variables inside the set definition are dummy ones. For instance if you define the set $S=\{a\mid \exists x\in\mathbb N, a=x^2\}$ Then $x\in S$ means $x$ is a square integer, i.e. it is actually ...
  • 25.5k
0 votes

Inference proofs using direct proofs

From what you're given, $s \implies p$ by the contrapositive of 3, and $s \implies q$ by 2. So $s \implies p \wedge q$ and $p \wedge q \implies r$ by 1. Thus $s \implies r$.
1 vote

Name for Logical Principle $(\varphi \to \psi) \to ((\neg \varphi \to \psi) \to \psi)$

The given proposition bears a kinship to the argument schema historically known as consequentia mirabilis, expressed in propositional form as $$(\neg\psi\rightarrow\psi)\rightarrow\psi$$ A nice ...
  • 1,105
1 vote
Accepted

Setting the domain of discourse in quantification logic

In the context of predicate logic (where we use quantifiers) we have the fundamental concept of Interpretation: "the assignment of meaning to the symbols of the formal language." In order to ...
0 votes

Do nonconstructive proofs of isomorphism exist?

There are non-constructive techniques for Graph Isomorphism, such as Weisfeiler--Leman (WL). While it is known that WL cannot place Graph Isomorphism into $\textsf{P}$, it serves as a complete ...
  • 14.1k

Top 50 recent answers are included