Tag Info

New answers tagged

1

Zorn's lemma implies the axiom of choice. But we can ask whether or not we can restrict Zorn's lemma to a seemingly smaller class of partial order, and still have the axiom of choice (which would then suggests that the restricted version is equivalent to the full version, since choice implies Zorn's lemma in full). The answer is positive. For example, it ...


1

You can recognize any minor-closed graph class in cubic time (Robertson–Seymour theorem), but it might be undecidable to actually find such an algorithm. Since the minor-ordering is a wqo, any minor-closed graph class $\mathcal{G}$ has a finite set of forbidden minors $\mathcal{H}$. Hence, if we want to check whether a graph $G$ is in $\mathcal{G}$, we ...


1

Baire's category theorem can be used to establish non-constructive existence proofs in a parsimonious and elegant way. Theorem (Baire)$\phantom{---}$No complete metric space is a union of countably many nowhere dense subsets. As Folland (1999, p. 162) puts it, “[Baire's] category theorem is often used to prove existence results: One shows that objects ...


1

In cryptography there are many times when I wish to prove that I have some private key, but need to make it impossible (or really difficult) for you to construct that key yourself. Take factoring, the basis of RSA. Claim: There exist integers P and Q such that P * Q = 651041 Proof: If 651041 is prime, then 2^651040 mod 651041 = 1 2^651040 ...


2

Many existence theorems related to algebraically closed fields are inherently non-constructive. 1) Every field has an algebraic closure. Try to make this explicit for $\mathbf C(x)$ or for $\mathbf Q_p$. 2) Any two algebraically closed fields with the same characteristic and uncountable cardinality are isomorphic as fields. To take a special case, any ...


4

$$\exists!x\,P(x)\Leftrightarrow\exists x\forall y[P(y)\leftrightarrow y=x]$$


0

Torched90, you seem to be asking a lot of questions concerning quantifiers (your question history suggests this anyway) and their properties concerning relations such as $\to, \lor$, and $\land$. I would like to give you six claims that you can explore for yourself concerning their truthfulness (truth or falseness will appear in an enumerated list below the ...


1

I feel like vacuous truths would disprove this. For example, I could let $A(x)$ be "$x\in \emptyset$" and $B(x)$ be "$x$ is a seven-headed purple fire-breathing dragon." The first statement of yours ($\forall x(A(x)\to B(x))$ is true (since there are no members of the empty set). However, the second statement is false since there does not exist $x$ such that ...


5

We say that there exists a unique $x$ with property $P$ provided two things are true. First, there exists $x$ with property $P$, and second, for all $x_1$ and $x_2$, if $x_1$ and $x_2$ both have property $P$, then $x_1$ and $x_2$ are the same. In other words, the logical statement $(\exists !x)(P(x))$ is defined by $$ [(\exists x)(P(x))]\land[(\forall ...


0

"For any two different elements of the set $S$, there is an element of set $C$ which is not in the $T$ relation with both of them."


0

The statement that the condition is necessary is an implication in one direction, and the statement that this condition is not sufficient is the negation of the implication in the other direction. Thus, we have the structure (safe $\to$ conditions) $\land \neg$ (conditions $\to$ safe). Fleshing this out gives the answer: $$ [p\to(\neg r \land \neg p)]\land ...


0

You aren't entirely correct in your translations. In your example of 27, you keep "will" in the same part of the sentence, but they should be part of the proposition that you're moving around. I know, this seems small and pedantic, but to be completely concise and accurate, it's an important detail. I will mention, however, that your translation is probably ...


0

As suggested, let’s start with $$\text{false}\to\text{true}\simeq\text{true}\to\text{false}\;,$$ which follows immediately from the new rule. From Implication we get $$\neg\text{false}\lor\text{true}\simeq\text{false}\to\text{true}\simeq\text{true}\to\text{false}\simeq\neg\text{true}\lor\text{false}\;.\tag{1}$$ You have a Simplification rule that you can ...


0

We assume that if $\phi \equiv \psi$, then $\phi \simeq \chi$ if and only if $\psi \simeq \chi$ (and similar for the right-hand side). Otherwise, we can do nothing meaningful with $\simeq$, and this rule of substitution is one of the cornerstones of propositional logic, so it seems reasonable to use it here. For brevity, denote $\top$ for true and $\bot$ ...


7

DeMorgan's laws: $\sim (x \vee y) = (\sim x ) \wedge (\sim y)$ $\sim (x \wedge y) = (\sim x ) \vee (\sim y)$ In some notations where the overline indicates the complement, the rule is "break the line, change the sign": $\overline{x+y} = \overline{x} \ \overline{y}$ $\overline{xy} = \overline{x} + \overline{y}$ By only manipulating the right hand ...


4

I'll show you why the left-hand side and left hand side of the claim are contradictory: $$\begin{align} \left[p \wedge (q \lor r)\right] &\equiv \left[( \sim q \ \ \lor \sim p) \wedge (\sim r \ \ \lor \sim p)\right]\\ \\ \iff (p\land q )\lor (p \land r) &\equiv \sim(q \land p) \land \sim(r \land p)\\ \\ \iff (p\land q )\lor (p \land r) &\equiv ...


3

The left hand statement is equivalent to $$(p\land q)\lor (p\land r)$$ Its negation is precisely the right hand statement. So this is indeed a self-contradictory proposition.


0

I think that there are different kinds of examples, some cited in the other answers. Tu see the difference I give three examples. 1) The number $a$ so defined : $a=1$ if the Goldbach's Conjecture ($G$) is provable in ZFC, $a=0$ if $\neg G$ is provable in ZFC, a=2 if $G$ is undecidable in ZFC. This number is not today known, but it can eventually be known ...


0

Uncountability of the real numbers. Since the set of all finitely-describable numbers (in any formal language) is countable, by definition uncountability implies the existence of numbers that are not finitely describable. To illustrate my point, here are some examples of finitely-describable numbers: Any natural number or integer Any rational number Any ...


5

The intermediate value theorem, in the form that for a continuous function on $f:[a,b]\to\Bbb R$ with $f(a)<0<f(b)$ there exists $x\in(a,b)$ with $f(x)=0$, is not valid constructively. See for instance here or here. The fundamental difficulty with the obvious classical proof of the IVT is that one cannot prove constructively that for $c\in(a,b)$ ...


1

Here is how I decode the notation in the Wikipedia link you gave. It is describing a fairly typical setting where an interpretation comprises operations that map syntactic constructs (here, individuals, concepts and role names) to values drawn from some set. $\Delta^{\cal I}$ is a symbol denoting the domain of the interpretation: a set used for the values ...


2

The negation of the goal has the following conjunctive normal form: $$ \lnot(((p \rightarrow q) \land ( q \rightarrow r) \land p) \rightarrow r) \equiv (\lnot p \lor q) \land (\lnot q \lor r) \land p \land \lnot r $$ I.e., you have four clauses: $$ \begin{array}{cl} A:& \{\lnot p, q\}\\ B:& \{\lnot q, r\}\\ C:& \{p\}\\ D:& \{\lnot r\} ...


29

Some digit occurs infinitely often in the decimal expansion of $\pi$.


1

Well, you have $p$ in the antecedent, and you have $p\rightarrow q$, and together, by modus ponens, you get $q$. Now, $q$, with the implication $q\rightarrow r$ give you $r$, again, using modus ponens. So the conjunction in the antecedent (i.e. the three conjuncts in the antecedent) imply $r$. Can you now use this to complete your assignment? Remember, ...


25

Claim: There exist irrational $x,y$ such that $x^y$ is rational. Proof: If $\sqrt2^{\sqrt2}$ is rational, take $x=y=\sqrt 2$. Otherwise take $x=\sqrt2^{\sqrt2}, y=\sqrt2$, so that $x^y=2$.


12

There is a standard kind of example here. Let $T$ be any open question that requires substantial work to resolve. Consider: There is a natural number $n$ such that $n = 0$ if and only if $T$. That statement is clearly true, via a "simple" non-constructive proof: if $n = 0$ is not an example, then $n = 1$ is an example. But if we could produce an ...


9

Definition: A real number $x$ is called normal if for every $b>1$ the digits $0,1,2,...,b-1$ are equally distributed in the $b$-adic expansion of $x$. Theorem: Normal numbers exist. The standard proof is non-constructive as it proceeds by showing that the set of non-normal numbers has Lebesgue-measure zero, hence must have non-empty complement. ...


0

Strong completeness of a calculus establishes its suffciency for capturing the logical consequence; namely, whenever a sentence follows logically from a set of hypothesis, there is a proof of this sentence in the calculus. While the weak completeness says that we have proofs for all validities. ...


0

Your statement is almost correct. In mathematics "only if" would mean "the only path to promotion includes washing the boss's car". Don't forget that "washing the boss' car" may not be enough to get "a path to promotion".


0

p -> q [implication] wash car -> promotion...if (wash car) then (promotion) promotion (q) can also be gotten without washing the boss's car (maybe you deserved it) p <-> q [equivalence] wash car <-> promotion ...if and only if (wash car) then (promotion) which is the same as "You can get promoted only if you wash the boss's car".


1

"If $p$ then $q$" means "Whenever $p$ is true, $q$ is true as well" which means "It is impossible for $p$ to hold true while $q$ does not hold" which means "In order for $p$ to hold true, $q$ must hold true as well" which means "$p$ holds true only if $q$ holds true", or, for short "$p$ only if $q$"


1

It is unfortunate that there is a limited set of delimiter symbol and these symbols are reused in many different contexts. $\langle\,\rangle, (\,), [\,], \{\,\}$ Thus context is required to distinguish between the representations for things such as the open interval, $(a, b)$, and the coordinate point, $(a, b)$. The key to context in this case is the set ...


0

"If $p$ then $q$" certainly seems to be logically equivalent to "$p$ only if $q$. See here and here, for example.


1

Your example is a little difficult to work with because there is only one "Russell". Let $p$ = "$x$ plays in the band" and $q$ = "$x$ is interested in music". The statement $p \to q$ asserts that: if someone plays in the band, they are interested in music if someone plays in the band then they are interested in music if someone plays in the band implies ...


0

"If $p$ then $q$" is definitely not the same as "$p$ only if $q$". The latter statement has the phrase "if $q$" built into it, which could be seen as an indication that it is not the same as the former. In fact, "$p$ only if $q$" is logically equivalent to "$q$ implies $p$". I'm guessing that the textbook was misread? But if you textbook is really asserting ...


0

Several of these are the kind of sentences that people look at when they are interested in monadic second-order logic, which only allows quantification over unary predicates. These sentences have facets that makes them difficult to express in first-order logic with only equality (not set theory). This is closely related to the concept of plural ...


3

No, $(2)$ is wrong. Consider the simpler case : $$ \neg(\forall n\in\mathbb Z)(P(n)\to D(n)). $$ Since $P(n)\to D(n)$ is equivalent to $\neg P(n)\vee D(n)$ we get : $$ \begin{align} \neg(\forall n\in\mathbb Z)(P(n)\to D(n))&\iff\neg(\forall n\in\mathbb Z)(\neg P(n)\vee D(n))\\ &\iff(\exists n\in\mathbb Z)\neg(\neg P(n)\vee D(n)). \end{align} $$ ...


1

In your approach, you made a mistake in the derivation on the third line, it should be: $$[\lnot (\lnot p \lor q) \lor \lnot (q \rightarrow r)] \lor (p \rightarrow r)$$ so that your fourth line becomes: $$[(p\land \lnot q) \lor (q \land \lnot r)] \lor (p \rightarrow r)$$ At this point, there isn't really much to be done except for a tedious case-by-case ...


3

The matter of "evenness" (which means nothing more than being a multiple of $2$) is something that was important in the original problem regarding $\sqrt 2$. In your case, you should not necessarily be concerned with evenness. Continuing from where you left off, i.e., $10b^2 = 2c^2$, we can divide both sides by $2$ to get: $$5b^2 = c^2.$$ From here you can ...


1

True and false are relative to a structure, these are semantics properties of a sentence in a given interpretation of the language. In some cases, like in the case of arithmetics, when we say that a statement is true we mean that it is true in a very specific model. In the case of arithmetical theories (like $\sf PA$ for example) we take the model to be ...


4

Theorems are things proved from a theory. Meta-theorems are things proved about the theory. The statement: If $\sf ZF$ is consistent, then $\sf ZF$ does not prove $\sf AC$. Is a meta-theorem about the theory $\sf ZF$. It quantifies over all proofs that we can write from the axioms of $\sf ZF$. If you like to think about it semantically, proofs are not ...


1

HINT We have to rewrite 1) as : "Only if John chops down the tree, will he be a lumberjack" as : if John will be a lumberjack, then he chops down the tree. This one has the "logical form" : $p \rightarrow q$; thus, its converse ($q \rightarrow p$) will be : if John chops down the tree, then he will be a lumberjack, while its contrapositive ...


1

If we have an equality of sets that is abstract, in the sense that it holds for any sets we choose to plug in for $A, B, C$ etcetera, then the answer is yes. In order to establish this, we need to investigate truth tables in a more abstract manner. Let $P = \{p, q, r, \ldots\}$ be the set of proposition symbols, and let $2 = \{0,1\}$ be the set of ...


2

In first-order logic, a predicate is a symbol of the language. According to Gottlob Frege - one of the "founding fathers" of modern logic - the meaning of a predicate is exactly a function from the domain of objects to truth-values : "the True" and "the False". Thus, the predicate $philosopher(x)$ denotes a function such that : ...


1

Let us assume that equality is built into the formalism you are using, so that we can use it -- otherwise, the exercise makes no sense. Now, $F$ is bijective if and only if it is both injective and surjective: $F$ is injective iff $F(x) = F(y)$ implies $x = y$ for all $x$ and $y$; equivalently, iff $x \ne y$ implies $F(x) \ne F(y)$. $F$ is ...


0

When we have an or statement either the left hand side or the right needs to be true for it to be true. In this case we have p on the left and $ (p \land q)$ on the right. But $ (p \land q)$ can only be true if p and q are both true. But if p is true we can immediately deduce that the or statement is true without knowing the value of q (since the LHS will be ...


3

From a Venn Diagram standpoint, all of $A$ plus any subset of $A$ will still just be $A$


1

To my understanding, if we square 2 and 3, their difference is 5, but O need to prove this statement being correct.


2

Your step $p\wedge s$ is unjustified. I would go from $u\wedge s$ to $s$, then combine that $s$ with the earlier $p$ to get $p\wedge s$.


3

The conclusion is valid. And you were very careful along the way, which is why I was surprised that you jumped a couple steps when citing $p\land s$. From $u \land s$, you get $s$ by conditional elimination (simplification). Then you need to use conjunction-introduction to infer $p \land s$. Apart from that, just as important as writing the steps is ...



Top 50 recent answers are included