# Tag Info

0

Your doubts can be explained by the following theorem: $$\left(A\Leftrightarrow B\right) \Rightarrow \left(A\Rightarrow B\right)$$ Same holds for the other direction, of course. Practically spoken, this means that if two statements are equivalent, it is not a false statement to use an implication there. The reason why most people do this is because in many ...

0

$\square p\land p\to p$ is a theorem; therefore $\square(\square p\land p\to p)$ by necessitation, and so $$\square(\square p\land p)\to \square p$$ by $\mathbf K$ (and modus ponens). Now apply $p\land\cdot$ to both sides and use the equivalence of $a\land b\to c$ and $a\to(b\to c)$.

0

What if one of the Knights draws the $N$ card?

0

Strong induction means following: suppose $P(0)$ and that $P(k),k<n$ implies $P(n)$. Then $P(n)$ for all $n\in\mathbb{N}$. For this question, our base is $n=2$, which is prime, so the statement holds. Now assume $n>2$ and that every $k<n$ is either prime or a product of primes. If $n$ is prime then there's nothing to prove, so assume $n$ is not ...

0

Let M be a structure and T a theory that it models. A substructure N of M need not model T. if N models T, then we say that N is a submodel of M relative to T. Otherwise, if N is a substructure of M that is not a submodel relative to T. Thus the only distinction comes when a theory lurks in the background. As an example, consider the signature S = (+, 0) ...

1

Hope this reference helps: "Broadening the Iterative Conception of Set" by Mark F. Sharlow, Notre Dame Journal of Formal Logic, Volume 42, Number 3, 2001, pp.149-170. According to the abstract, "the modified conception maintains most of the features of the iterative conception of set, but allows for some non-wellfounded sets. It is suggested that this ...

1

Order of quantifiers matters! We claim that the first statement is false. To see this, we will prove its negation, namely: $$(\mathbb N, +) \models \exists x \, \forall y \, \exists z \, [x + y = z]$$ Let $x = 3 \in \mathbb N$. Given any $y \in \mathbb N$, let $z = 3 +y \in \mathbb N$. Then $x + y = 3 + y = z$, as desired. The second statement is true. ...

1

The first is false. It says that for any natural number $x$, there is a natural number $y$ such that $x+y$ is not a natural number (for all natural numbers $z$, $x+y$ differs from $z$). Note that in your explication of the sentence, you implicitly read $\exists y\forall z$ as $\forall z\exists y$. Now perhaps you can deal with the second.

0

First off, even though this kind of puzzles usually appear under names such as "logic puzzles", they're not really about what mathematicians call "logic". It is possible to write down the contents of the puzzle in the language of mathematical logic, but doing so will rarely be of any help in solving the puzzle -- and conversely, being skilled in solving ...

1

A finite set has even size exactly if its elements can be paired up two by two. A natural way to express this pairing when you have only a function to express it with would be to require that the function should map each element to its partner. Can you write down the conditions "$f$ maps every element to something that maps back to the element we started ...

2

If you think about $R$ being a partial order, then these mean: $\exists x\forall y(x\mathrel R y)$, there is a minimum. $\exists x\forall y(y\mathrel R x)$, there is a maximum. $\forall x\exists y(x\mathrel R y)$, every element is related to someone. Of course, if you want $R$ to be a partial order, then for $x$ being the maximum element the only $y$ ...

3

Hint: There is not a single negation symbol to be seen in $\Gamma$.

3

The following Haskell program: import Control.Monad; remove1 x [] = [] remove1 x (h:t) = if (x == h) then t else h : remove1 x t remove xs ys = foldr remove1 ys xs digits = [0..9] numeral = foldl (\a b -> a * 10 + b ) 0 solutions = do s <- remove [0] digits; e <- remove [s,0] digits; v <- remove ...

5

This is what happens when you abbreviate. Recall that $a,b\in\mathcal P(A)$ is really a shorthand for $a\in\mathcal P(A)\land b\in\mathcal P(A)$. I think that now you can finish the negation properly.

0

No, you haven't provided a contradiction. Suppose that $A = \{1,2,3\}$ and $B=\{3,4,5\}$ and let $a\in A, b\in B.$ Then it is true that $a+b \geq 4.$ Now, let $P$ be the proposition that $a\geq 0,b\geq0$ for any $a\in A, b\in B$. Then $P$ implies $a+b \geq 0.$ This does not contradict $P$, which is reassuring since $P$ is definitely true! For the ...

0

Your argument after step 3 is not correct. The conditional : $(∃z(x=y*z)⇒(y=x)∨(y=1))$ is universally quantified by $∀y$. This means that : for any $y$ we have to "test" if the antecedent $∃z(x=y*z)$ holds. Thus, for the sake of argument, assume $x = 3$; we have that $x \ne 1$ and thus the first conjunct is true. For the second conjunct, we have to check, ...

1

A formal proof is a sequence of statements such that every statement in the sequence is either an instance of an axiom; or a deduction from two previous statements using modus ponens. The latter means that if you have statements $\phi\to\psi$ and $\phi$, you can write down $\psi$. If you think about it, this is really nothing more than expressing the ...

1

A3 with $\phi = p$, $\psi = q$ gives $((\lnot p) \rightarrow (\lnot q)) \rightarrow (q \rightarrow p)$. A2 with $\phi = ((\lnot p) \rightarrow (\lnot q)), \psi = q, \chi = p$ gives $(((\lnot p) \rightarrow (\lnot q)) \rightarrow (q \rightarrow p)) \rightarrow ((((\lnot p) \rightarrow (\lnot q)) \rightarrow q ) \rightarrow ( ((\lnot p) \rightarrow (\lnot q)) ... 1 I always think of it in terms of sets. In the picture above, for an element to be purple, it's necessary to be red, but it is not sufficient. The same holds for the blue set, to be in the blue set is a necessary condition in order to be purple, but it is not enough, it's not sufficient. A sufficient condition is stronger than a necessary condition. If ... 1 If you go straight for the$n$th digit (after the decimal point) of$x$, something like this should work $$\left\lfloor 10^{n+1}|x| - 10\left\lfloor 10^n |x|\,\right\rfloor \right\rfloor$$ Encoding the floor function and other necessary arithmetic as set theory is left as an exercise for the reader. 1 You can consider the decimal expansion to be a sequence of natural numbers. Then the graph of the sequence can be made into a set $$\{(1,x_1),(2,x_2),\ldots \}.$$ This works nicely for all real numbers between$0$and$1$. You can fix it up so that it works for all real numbers. I should also mention that you have to take equivalence classes. 1$\forall x \in \mathbb{R}:[x\ne 0\implies \exists y \in \mathbb{R}: xy=1]$1 My question is what happens to the truth value if the premise in a universal implication is false eg:$\forall x : ((Purple(x) \land Mushroom(x)) \implies Poisonous(x))$(assuming outer brackets) If in the universe, x is not purple or not a mushroom, what happens to the implication? Then the implication would tell you nothing.$x$may or may not be ... 1 Since the variable$x$is bound by the quantifier, the truth value of the sentense does not depend on any choice of value for$x$. That's what the quantifier says:$\forall x(\cdots)$is true if "$\cdots$" is true no matter what we bind to$x$. For those particular choices of$x$that are not purple mushrooms, the formula to the left of$\Rightarrow$is ... 1 It is quite easy with Natural Deduction. (i)$∃xA(x) \rightarrow ¬∀x¬A(x)$(1)$∀x¬A(x)$--- assumed [a] (2)$¬A(x)$--- from (1) by$\forall$-E (3)$∃xA(x)$--- assumed [b] (4)$A(x)$--- assumed [c] for$\exists$-E (5)$\bot$--- from (4) and (2) by$\rightarrow$-E (6)$\bot$--- from (3), (4) and (5) by$\exists$-E, discharging [c] (7) ... 1 Neither :$(α→β) → (∃xα→∃xβ), x \notin FV(β)$is valid. In order to manufacture a counter-example, we can "re-cycle" that of Tetori's answer. We refer to Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001), page 88 for the definition of : Logical Implication : Let$\Gamma$be a set of wffs,$\varphi$a wff. Then$\Gamma$logically ... 3 You can't prove it. Consider the field of rationals. Take$\alpha(x)$as$x=0$and take$\beta$as$\exists y(y\cdot 0=1)$. Then$\exists x (\alpha(x)\to\beta)$holds (just take$x=1$) and$\exists x\alpha(x)$also holds, but$\exists x\beta$is false. 1 The answer is mostly yes - there is an algorithm that will determine whether or not most complex numbers are in the Mandelbrot set or not. The algorithm definitely works for all points that lie in the basin of attraction of some attractive orbit and for all points that lie on the boundary of the Mandelbrot set, as proved in this paper. Whether there are ... 0 Here is another characterization of$\Delta^0_n$. A subset of the natural numbers is$\Delta^0_n$if and only if both it and its complement are$\Sigma^0_n$. A subset$X$of the natural numbers is$\Sigma^0_n$if and only if$X$can be defined as follows,$k\in X$if and only if$\exists m_1\forall m_2\exists m_3\dots Q_n m_n R(k,m_1,\dots m_n)$, where$R$... 1 Yes, the article means to say$\Delta^0_{n+1}$and$\Delta^{0,C}_{n+1}$. 0 A necessary and sufficient condition for a function$f$to be an infinity producer is that on the inductive set$\omega^f$given by$\textbf{Inf}^f$,$f$is injective and does not have$0$in its range. For necessity: If$f$is not injective on$\omega^f$, there are some$x \neq y$in$\omega^f$with$f(x) = f(y)$. By the inductive definition of ... 1 For$x=7$,$2x=14$is true and$x\ne 7$is false, so that$2x=14\iff x\neq7$does not hold. For$x\ne7$,$2x=14$is false and$x\ne 7$is true, so that$2x=14\iff x\neq7$does not hold. This covers all real numbers. 3 $$2x = 14 \iff x = 7$$ Logically, you're statement can be simplified to $$x = 7 \iff x\neq 7$$ which is a contradiction: it is false no matter what$x$is. Recall that$a \leftrightarrow b$is true if and only if both$a, b$are true, or both$a, b$are false. In the example above, if we put$a: x = 7$, and$b: x\neq 7$, then if$a$is true,$b$must ... 0 When you're in characteristic$\;2\;$, your equation is $$0=2x=14=0\rlap{\;\;\;\;/}\implies x=7=1\pmod 2$$ In any other case one can either divide by two and then$\;x=7\;$, or else$\;2\;$isn't invertible in a particular algebraic structure. 0 See this lecture notes by Vann McGee. 2 The Wikipedia article on the Mandelbrot set suggests that the answer to your question is not yet known. In the paragraph Further results, it says: At present it is unknown whether the Mandelbrot set is computable in models of real computation based on computable analysis. If the Mandelbrot set turned out not to be computable, then there would indeed ... 2 This theory axiomatizes the class of graph of degree$2$such that for all positive integers$n$there exists a path of length$n$. Needless to say, such a graph has to be infinite to satisfy the last condition. To prove that the theory is not contradictory, it suffices to come up with a model. An example of a model is the infinite path on$\mathbb Z$where ... 2 The theory is of a graph of degree$2$with arbitrary long paths. The theory is not complete. Do there exists cycles ? For example is there a cycle of length$4? This is first order and not decided by the axioms. 3 \begin{align} (p\land q) \rightarrow (p \land r) & \equiv \lnot(p \land q)\lor(p \land r) \tag{1} \\ \\ &\equiv (\lnot p \lor \lnot q) \lor (p\land r)\tag{2}\\ \\ &\equiv \lnot p \lor \lnot q \lor (p \land r)\tag{3} \\ \\ &\equiv \lnot p \lor \lnot q \lor (r \land p)\tag{4}\end{align}(1)$follows because$a \rightarrow b \equiv \lnot a ...

2

If I understand you correctly, you want to know the following: I want to prove $$(A\subset X \land B \subset X) \land ((A\subset Y \land B\subset Y) \rightarrow X\subset Y)\implies X=A\cup B$$ since the proposition $P \implies Q$ is formally true in the cases \begin{matrix} {P}&{Q}&{}&{P\implies Q}\\ ...

0

You should prove (i) $A \cup B \subset X$ and (ii) $X \subset A \cup B$. You can prove (i) from the first statement. To prove (ii), use the second statement with $Y=A \cup B$.

2

When we say, if it is raining, then it is cloudy, there is often the erroneous suggestion that either cloudiness causes rain, or rain causes cloudiness. Neither is the case. It means only that it cannot be both raining and not cloudy. There is no suggestion of a causal relationship. To answer your question, suppose it is not raining. Then it doesn't matter ...

1

In plain English, "$P\rightarrow Q$" is the same as "If P is true, then Q must be true". So, if you know that this kind of relation holds for two propositions, P and Q and someday i tell you that i observed P to be true and Q to be false in some situation, you will greet me in a second by "liar". But if i say, that i observed P is false and Q is true, then ...

0

Remember that $P \rightarrow Q$ has nothing to do with whether $Q$ is true. It only means: If $P$ is true then $Q$ is true. This always holds if P is false becasue if we assume that $P$ is true, while knowing that $P$ is false, we get: $\neg P \wedge P$ And we can prove anything starting from this. So $Q$ is true.

1

Let's say there's a sign outside a basketball court that says: "If you're not wearing shoes, you cannot play basketball." The negative of the antecedent is if I were wearing shoes. And if I were wearing shoes, I'm not violating what the sign says no matter whether or not I play basketball. I only violate the sign if I'm not wearing shoes AND playing ...

0

Imagine, philosophically, mathematical foundation needs to build up a language bridging finiteness at A and countable infinity at B. ACC is such a language leading us jumping from A right to B, while induction is a never ending process leading us to go through each mile in an infinite mileage, but just never get to the end point B. In a single nonempty set, ...

1

For $\rightarrow$, it should be $\Sigma'\cup{\{\neg\sigma\}}$ is consistent. Then the rest is fine. For $\leftarrow$, If $\sigma\notin\Sigma'$, then maximality tells us that $\neg\sigma\in{\Sigma'}$. After this what can you say about $\Sigma'$?

0

To avoid Choice, you need to have a definitive way of choosing an element from each set. For example, if each $A_n$ is a pair of shoes, you may always choose the left. A typical useful case is when each $A_n$ has a distinguished member such as a unique minimum that you can choose. For example, Baire Category Theorem for a complete SEPARABLE metric space ...

0

The statement is best read as (using inclusion in a set instead of a predicate; it doesn't really matter): If $x$, $y$, and $z$ are all in $A$, then there is some pair of them which are equal. Clearly, this cannot hold for any set $A$ containing three distinct members - hence, we know that the above statement implies that $A$ has size no more than $2$. ...

0

P is a property that defines A. For Case 1: Objects x,y, and z exist in the Universe but since (Px∧Py∧Pz) was false, no candidate was held true for the property P that defines A thus their existence has no identity in A because they are not members of A; therefore, A is empty if the antecedent is false always -the consequent has no effect on defining ...

Top 50 recent answers are included