# Tag Info

0

My solution for 1) \begin{align} & (A+B)(C+B)(D'+B)(ACD'+E) \\ & (AC+B)(ACD'+D'E+BE) \\ & (ACD'+BE) \end{align} Rather than multiplying out everything and simplifying at the end, I have simplified intermediate factors to reduce the length of my calculation. Simplification rules: $$x + x = x$$ $$x + xy = x$$ $$x x = x$$ $$x x' = ... 0 "n is composite" can be tested and proved relatively efficiently for large n but finding a prime factor of a large composite number is a notoriously difficult computational problem. 1 Suppose that we examine rolling a 6 sided die. Let P_1 be getting a 1 and let P_2 be rolling a 2. These are mutually exclusive events. Say that rolling a 1 or 2 guarantees winning \20 (A) and getting a new haircut (B). But any other roll does not guarantee these things. So A and B might not necessarily always hold. 5 No; given that P_1 and P_2 are mutually exclusive conditions, it is still possible that they're both false, and so we cannot deduce anything from P_1\rightarrow Q, nor from P_2 \rightarrow Q. Explicitly (note that false implies false), the following is a counterexample to the conjecture:$$P_1 = \mathrm{False}, \;P_2 = \mathrm{False}, \;Q = ...

1

Consider the false statement, "All numbers are algebraic." The set of algebraic numbers is countable, but $|\mathbb C|=2^{\aleph_0}>\aleph_0$. Therefore we know there are $2^{\aleph_0}$-many transcendental (i.e. non-algebraic) numbers without needing to identify any in particular. In this case, actual counterexamples, like $\pi$ and $e$, are obviously ...

3

Besides the very good books on topos theory already mentioned, I highly recommend Categorical Logic by Andrew Pitts for an introduction to the categorical semantics of type theories (you can find it online here. See Section 5 for the treatment of predicate logic). The more advanced Categorical Logic and Type Theory by B. Jacobs, from the series Studies in ...

1

I recommend Goldblatt's Topoi: A Categorical Analysis of Logic. (Have a look at this question of mine.) This MO question is also relevant.

4

I'm not sure what the most recent texts would be, but most of what you are asking about would probably fall into the general category of topos theory. Mac Lane and Moerdijk's Sheaves in goeometry and logic (1992) is probably still the best place to start, although if you find it tough going, you could try McLarty's Elementary Categories, Elementary Toposes ...

0

My opinion is that set theory law is just a special case of the logic law. For example, we can note $a\in A$(in set domain) as $\mathcal{A}$(in logic domain) and $a\notin A$ noted as $\lnot\mathcal{A}$.

9

The explanation can be seen in the following chain of equivalences: \begin{align}(A \cap B)^C & = \{x\mid x \notin (A \cap B)\}\\ \\ & = \{x\mid \lnot [x\in (A\cap B)]\} \\ \\& = \{x\mid \lnot (x \in A \land x \in B)\} \\ \\ & = \{x\mid \lnot(x \in A)\lor \lnot (x \in B)\} \\\\& = \{x \mid x \notin A \lor x \notin B\}\\ \\ & = ... 0 Are there any situations where we can prove that either A or B (or some element of a finite set) is a counterexample, but we don't know which one? What about if the limit of some infinite sequence can be shown to be a counterexample, but we can't find the limit - as long as we know it exists. That would become philosophical. What does it mean to "know" a ... 2 This apparent paradox has nothing to do with ordinals, or metalanguage. It is a time travel/omniscience paradox. Let's strip away the unnecessary bits. How many words will the longest sentence I personally will say tomorrow be? Maybe I predict seven, but that doesn't stop me from saying a sentence with eight words. No matter my prediction, I can break ... 0 The CNF is a special type of POSE. We take max terms, which are negations and ORs of variables that evaluate to 1. We then AND the max-terms together. With a POSE, the terms don't have to be max-terms. 47 Statement: "There are no primes greater than 2^60,000,000" No known counter-example. Counter example must exist since the set of primes is infinite (Euclid) 1 Use xAy for A(x,y), and your first two axioms are reflexivity and transitivity. You may as well take the assumption of the third formula as another axiom, i.e. that A is "connected": any two elements may be compared, and ask about whether there has to be a maximal element in the (finite) set. Now take a maximal chain (with distinct b_j)b_1A b_2 A ...

2

I'd say that it's most likely a mistake on part of the authors of those documents, and it's only true if the interpretation is exact (it's not standard terminology as far as I know) in the sense that an $S$-sentence is true iff its interpretation in $T$ is true (and not only in the one direction). The two definitions are, however, equivalent if $S$ is ...

7

This is essentially Jules Richard's paradox. You define an ordinal in a language and then talk about its consequences in the metalanguage. But it's not problematic in the original language and doesn't have the desired property in the metalanguage. Basically, the difficulty comes from the imprecision of natural language ("the largest finite ordinal that will ...

4

Interpreting "A when B" as $A \Rightarrow B$ isn't really consistent with the english language. If I say "I get wet when it rains", that means (at least to me) that rain implies getting wet, not the other way around. I.e., whenever it rains I get wet, but I might get wet even if it doesn't rain (if I, say, jump into the pool). I'd thus read "A when B" as $B ... 2 Be very careful here: Wittgensteins tractatus Wittgensteins tractatus was written long before Gentzens "Untersuchungen uber das logischen schliessen" (1916 vs 1933) so there is no real relation between them. (I think it is doubtful that Gentzen read Wittgenstein but that is another matter) Natural deduction: Gentzen found axiomatic logic not very like ... 2 I don't think there's necessarily anything deep going on here. Your initial observation seems to be simply that we can trade logical axioms for rules of inference and vice versa. A Hilbert-type system tries to have as few rules of inference as possible (namely modus ponens; it needs at least one in order to be able to do anything) and puts all the work in ... 0 "Prove that a counterexample exists without knowing one". The existence of continuous nowhere differentiable function can be proved without constructing one. In fact, a "typical" continuous function has this property. 1 Accepting the axiom of choice, for$n\ge1$let $$S(n) := \mathbb{R}^n \;\text{ has no well-ordering}".$$ I believe it's provable that a well-orering of$\mathbb{R}$cannot be constructed, although the axiom of choice indicates it exists. 2 If we require that$S(n)$must be decidable by a known algorithm, then how about:$S(n)$iff either there is a comparison-based sorting strategy for$16$elements that uses at most$n-1$comparisons, or every comparison-based sorting strategy for$16$elements uses at least$n+1$comparisons in the worst case. This can be determined simply by by ... 6 Let$S(n)\equiv$"$n$appears only finitely many times in the decimal development of$\pi$". We know that certainly this cannot be true for all$n$. We also know that at least two counterexamples are in$\{1,2,3,4,5,6,7,8,9,0\}$but we don't know any counterexample. Of course this relies, as other answers, on facts that are still unknown (no number can be ... 8 Assume some enumeration of all formulas in first-order peano arithmetic, and let$S(n)$be the statement The$n$-th formula is not provable in, but consistent with, first-order peano arithmetic, and isn't any of the known such formulas$\mathcal{F}$." Assuming that the set of known such formulas$\mathcal{F}$is recursive (meaning that for any given ... 20 According the Wikipedia article on Skewes' number, there is no explicit value$x$known (yet) for which$\pi(x)\gt\text{li}(x)$. (There are, however, candidate values, and there are ranges within which counterexamples are known to lie, so this may not be what the OP is after.) Another example along the same lines is the Mertens conjecture. A somewhat ... 5 Define$k$to be 42 if the Riemann Hypothesis is true, and 108 if it is false. Now consider$S(n) \equiv n\ne k$. Alternatively consider$S(n)$to be "$n$is larger than$\mathit{BB}(100)$which is the longest running time of a terminating two-symbol Turing machine with 100 states when started on an empty tape". 2 Yes. These are well-defined functions. Just don't confuse between a function being well-defined, and us being able to evaluate its output for every given number (or any number, for that matter). 0 I will draft two separate sub-derivations (A) and (B) :$A \rightarrow A$--- Axiom$\lnot \lnot A, A \rightarrow A$--- Weakening-left$A \rightarrow \lnot \lnot A \supset A$---$\supset$-right --- (A)$A \rightarrow A$--- Axiom$\lnot A, A \rightarrow$---$\lnot$-left$\lnot A \rightarrow \lnot A$---$\lnot$-right ... 1 @MauroALLEGRANZA has given an answer that are valid in classical logic, but the result actually holds intuitionistically too. This is just a simple, intuitionistically valid modification of his proof: \begin{eqnarray} A&\vdash& A \\ A,\neg A & \vdash & \\ A, \neg A & \vdash & B \\ \neg A & \vdash & A\to B \end{eqnarray} ... 1 I will use the LK system [see Gaisi Takeuti, Proof Theory (2nd ed - 1987), page 9-on] :$A \rightarrow A$--- Axiom$\Gamma, A \rightarrow A$--- by n Weakening-left$\Gamma , A \rightarrow A, B$--- by Weakening-right$\Gamma \rightarrow A, A \supset B$--- by$\supset$-right$\Gamma, \lnot A \rightarrow A \supset B$--- by ... 2 In many cases$a<b$is defined as saying that$a\le b$is true and$a\neq b$is true. Thus if$a<b$is true, so is$a\le b$. 2 Indeed it is !! If$a < b$, then surely$a ≤ b$, as$≤$implies less than or equal to. If any one of the conditions, i.e.$<$or$=$, is true then$a ≤ b$is true. Therefore$a ≤ b$will always be true, if$a<b$. 1 I assume the intention is to find a countable set of sentences that has no countable model. That is essentially the negation of the Lowenheim-Skolem theorem. Most modal logics have the Lowenheim-Skolem property, because they can be translated into first-order logic. This method can also be used to prove a compactness theorem for these logics. So these ... 0 A standard example of this method of proof would be to show something like this Theorem: The square of every non-zero real number is greater than$0$. Let's say you have already proved that the product of two positive numbers is positive. Then (using the letters in the original question) :$P$is the statement "$x$is positive" and$Q$is ... 0 It looks to me like McGee is making the following error. Suppose, for a moment, that$A \to (B \to C)$is a tautology. Because of this, we know $$A \vdash B \to C$$ which means, among other things, that $$\mathcal{M} \models A \quad \text{implies} \quad \mathcal{M} \models B \to C$$ However, McGee seems to have fallen into a trap of some sort, and is ... 0 I'm not sure if this relates to your question. In propositional logic, for example, a truth valuation is a function$v$from sentences to the boolean algebra$\{ T, F \}$satisfying the obvious properties, such as$v(P \wedge Q) = v(P) \wedge v(Q)$. Truth valuations (often seen as rows of "truth tables") are often used in propositional logic; e.g. one can ... 1 There's plenty of logico-philosophical research concerning logical truth. Just to name some recent articles: H. Wansing: A Non-Inferentialist, Anti-Realistic Conception of Logical Truth and Falsity. Topoi 31 (2012), 93-100. W. H. Hanson: Actuality, Necessity, and Logical Truth. Philosophical Studies 130 (2006), 437 - 459. M. Bremer: Do Logical Truths ... 1 If (p⇔q), then (p→q), as well as (q→p). Thus, if (p⇔q), and ($\lnot$p→q), since [(p→q)→(($\lnot$p→q)→q)] is a theorem or axiom in any complete system of propositional calculus, we can obtain "q". Since we have (q→p) and "q", we can also obtain "p" by detachment. Therefore, if (p⇔q) and ($\lnot$p→q), then, yes, it comes as valid to infer both "p" and "q". ... 9 This is a standard method of proof called proof by cases (or proof by exhaustion). It works for any finite number of cases. Suppose you know that$P_1$or$P_2$or ...$P_n$must be true, i.e. at least one of the$P_i$is true. If you can prove that$Q$is true in each case (assuming each of the$P_i$in turn is true), then$Q$must be true. In your ... 3 "Formally" it works. From the two proofs [in all the argument, I left implicit a "common set" of assumptions :$\Gamma$] :$\vdash P \rightarrow Q$and$\vdash \lnot P \rightarrow Q$by the tautology :$\vdash (P \rightarrow Q) \rightarrow [(\lnot P \rightarrow Q) \rightarrow Q]$we may have, by modus ponens twice :$\vdash Q$. ... 2 Is not(not B, A) = (B, not A) ? Now, $$\lnot(\lnot b, a) \iff \lnot(a \rightarrow \lnot b) \iff \lnot(\lnot a \lor \lnot b) \iff a \land b$$ $$(b, \lnot a) \iff \lnot a \rightarrow b \iff a \lor b$$ You decide: $$\text{Is}\;a \land b \overset{?}{\equiv} a \lor b\;?$$ (Consider the case when$a$is true,$b$is false, and evaluate each side of the ... 5 This proposal seems like an amazingly roundabout method of proof. The theorems that led to this question use RH (and$\neg$RH) in important but not critical ways. For example, we need to bound the growth of some function; both RH and$\neg$RH provide different ways to bound that growth. If we could find a way to bound the growth using neither, then we ... 1 If we use the definitions in the question, the answer is yes. Take any common propositional modal logic (e.g. S5) that has the finite model property for sentences. Work in a language with infinitely many propositional variables$X_i$, and consider the set$T$of sentences that contains, for every finite set$D$of propositional variables and every function ... 1 The two statements :$\exists x (P(x) \Rightarrow S(J,x))$and$\exists x (P(x) \land S(J,x))$are not equivalent in general, as you have verified through truth-tables. The first one is true when$Jane$saw a man (call it$m$) which is a$Doctor$, because in this case$P(m)$is false and so$P(m) \Rightarrow S(J,m)$is a true ... 1 The problem is where you assume that "if x is a police officer then Jane saw x" is the same as P(x)∧S(j,x) being true. It isn't. The "if..then" statement neither claims that there actually is a police officer nor that Jane actually saw one. It states a certain relationship between two facts exists, not the facts themselves. 0 Defining a subset, or a relation,$A$over$M$means to find a formula in the language$L$which the right number of free variable (one for subset, two for a binary relation, and so on), such that:$A=\{x: M\models\varphi[x]\}$(and similarly for the ordered pairs and whatnot). I'll help with the simplest one, $$\{2\}=\{x: M\models x=c\}$$ 1 If you are working with propositional logic (I assume it from the text of your answer) and$Set_1$is a finite set of formulas (like your :$A \lor B \rightarrow C$), you can use the Method of analytic tableaux : the semantic tableau (or truth tree) is it is a decision procedure for sentential and related logics. In case$Set_1$is consistent, it gives ... 3 The most useful technique for proving$\Sigma$consistent is to provide a model for it -- that is, an interpretation of the primitive symbols in it that makes every formula in$\Sigma$true. If the logic is sound, it cannot conclude something false from true, so whenever$\Sigma\vdash A$, then$A$will also be true in that model. Since$A$and$\neg A\$ ...

0

It is a quite nice notation , not sure which other notation you mean (but i would like to know , please give me a reference) the layout is called the Fitch or Graphical style of natural deduction Lets start with that there is an error: Line 1 ia a premisse not an assumption (some writers don't make any difference between them, but assumptions are ...

Top 50 recent answers are included