Tag Info

Hot answers tagged predicate-logic

5

If general, a statement $F$ is told stronger than another statement $G$ if the implication $F \Rightarrow G$ holds (i.e. if $G$ holds whenever $F$ holds) but the converse implication $G \Rightarrow F$ does not hold (i.e. it is possible that $G$ holds but $F$ does not hold). As you said, this is the case for $F = \exists y \in B \, \forall x \in A \, P(x,y)$...

4

Your interpretation of the first clause has the time qualifier following the people qualifier, so it means that for every person, there is some time -- dependent on the person -- at which you can fool that person. Since the time is dependent on the person, this doesn't mean there is any single time at which you can fool all the people. It seems to me Lincoln ...

3

No. Euclid makes additional assumptions that aren't explicit. For example, he assumes two crossing lines have a common point (essentially the completeness axiom for real numbers). Hilbert did work on building euclidean geometry on firm axiomatic basis, and if I recall correctly he needed around 20 axioms for it.

3

The negation of a statement like $\mathscr{A} \neq \mathscr{B}$, where $\mathscr{A}$ and $\mathscr{B}$ are any permissible formulas, is just $\mathscr{A} = \mathscr{B}$. $\underline{\textbf{Note that neither$\mathscr{A}$nor$\mathscr{B}$changes; only the$\ \neq\ $changes to a$\ =\ $}}$. So the negation of $N(a, \epsilon) \cap S \neq \emptyset$ is just ...

3

I would say the function has: multiple rational fixed points or no fixed point at all or at least one irrational fixed point Not sure if we can make this more "compact".

3

Yes. Each step is well reasoned and checks out okay.

2

Suppose $$\exists y\in B,\forall x\in A,P(x,y).$$ Let $x_0\in A$. According to the previous assertion, there exists $y\in B$ such that for all $x\in A$, $P(x,y)$. In particular for $x=x_0$, we have $P(x_0,y)$. We just proved that for all $x_0\in A$, there exists $y\in B$ such that $P(x_0,y)$, which can be rewritten \forall x_0\in a,\exists y\in B,P(x_0,... 2 It is stronger in the sense that anything you can prove with \forall x \ \epsilon \ A,\ \exists y \ \epsilon \ B, \ P(x,y), can also be proven with \exists y \ \epsilon \ B, \ \forall x \ \epsilon \ A, \ P(x,y) because the latter implies the former. As an analogy: Every nut you can crack with a rubber hammer can also be cracked with a sledge hammer. But ... 2 There is an easy, informal, way to prove that \exists x A(x) \to \forall x B(x) implies \forall x (A(x) \to B(x)). It is well-known that \exists x A(x) \to C is equivalent to \forall x (A(x) \to C), provided that the variable x does not occur free in C. So, from \exists x A(x) \to \forall x B(x) it follows that \begin{align}\tag{1} \forall x ... 2 The sentence can be interpreted in two ways, depending on whether "unique" refers to "fixed point" or "rational fixed point": "Unique" refers to "fixed point": The function f has a unique fixed point a, and moreover a is rational. The logical form of this sentence is \begin{align} \exists a : a \in \mathbb{Q} \land a = f(a) \land \forall z (z = f(z) \... 2 You cannot open up the paranthesis with \exists. Here is an example: P(x)=1 :\Leftrightarrow x \text{ is an even number}, G(x):\Leftrightarrow x \text{ is an even number}. Now take a look at \exists x[P(x)\land \lnot G(x)]. This is false. There are no numbers that are even and not even at the same time. However, \exists x P(x)\land \exists x \... 2 Your answer is correct. Let \forall x \in \mathbb{R}, \, g(x) = \int_a^x f(t) dt As you noticed \begin{align} \displaystyle \int_a^\infty f(t) \, dt \text{ is convergent} &\iff (\exists L,\lim_{x \rightarrow + \infty} \int_a^x f(t) \, dt =L)\\ &\iff (\exists L,\lim_{x \rightarrow + \infty} g(x) = L) \end{align} Notice that g is just function. ... 2 It is from the idempotence identities, which are p\vee p\equiv p and p\wedge p\equiv p. So \quad(p\vee p)\wedge\neg(p\wedge p)\\ \equiv (p)\wedge\neg(p) That is all. You may be encountering a confusion of terminology. Truth (\top) is known as the conjunctive identity, and falsity (\bot) as the distributive identity . However, the ... 2 In the language of my first order logic text, x,y,z are individual variables, not propositional variables. They don't represent truth values, they are merely arguments for the predicate variables that do return truth values. Perhaps it's clearer to write the sentence without the infix inequality symbols:\exists x,y,\neg(\neg Lxy\vee\exists z(Lxz\...

2

I suspect the $\ni$ symbol may be used by your text to indicate "such that" after an existential quantifier.   This is not usually used. Rather [quantifier][term] [predicate] is written for both universal and existential quantifiers.   Optionally, a comma, dot, or colon may be used to separate the term and predicate if a space does not feel ...

2

An existential quantifier around an implication doesn't really correspond to a common phrase structure; we just translate the logical symbols directly. The example you give is just There is something which, if it's a cube, is small. We can rewrite this a little more clearly using the definition of (material) implication: There is something which ...

2

If your question is whether it's legitimate to change a recently renamed variable for an existential quantifier into a function symbol - sure, there's nothing wrong about that; there is no difference in whether the variable name has been changed at some point or not; the elimination of $\exists$ is independent of that step.

1

Let $p$ be $(a,b)\in R$, $q$ be $(b,a)\in R$, and $r$ be $a=b$. $(p\wedge q)\to r$ is equivalent to $p\to( q\to r)$ is equivalent to $p\to( \neg r\to \neg q)$ is equivalent to $(p\wedge \neg r)\to \neg q$.

1

Part A What if $P(n)$ stands for "$n>164$"? And what if it stands for "$n>163$"? Part B seems ok Part C Reat it loud: "Property $P(n)$ is true for $n=165$, or there exists some number $n$ smaller than $165$ such that $P(n)$ is false". You can think in cases: either $P(165)$ or $\lnot P(165)$. What does Part B tell you? Part D You can assume that $... 1 ...and now brackets are useless : $$\exists x [P(x) \land \neg G(x)]\lor \forall x \neg P(x) \lor \exists x G(x)$$ Hint: double negation and de Morgan's. $$\neg\neg\big(\exists x~(P(x) \land \neg G(x))\lor \forall x~\neg P(x) \lor \exists x ~G(x)\big)\\[3ex]\neg\big(\forall x~(\neg P(x)\vee G(x))\land\exists x~P(x)\land\forall x~\neg G(x)\big)\\[2ex]... 1 There are x^n possible lists of n objects, where there are x different possible objects. So on average, over all possible such lists, a (non-lossy, optimal) compression algorith will give a file of size n\log_2 x bits. Of course, many decent algorithms will either know which objects are common in general, and make those take less space, or have an ... 1 The question is: Can I say \forall_x A(x) \rightarrow \forall_x B(x) \implies [ \exists_xA(x)\rightarrow \forall_x B(x)] \implies \forall_x [A(x) \rightarrow B(x)] Running the first conditional in a tree proof generator resulted in a countermodel: Since A is only true for 0, \forall x Ax is false, but \exists xAx is true. Since B is not ... 1 The formula \forall a \in M : \varphi(a) is syntactic sugar for \forall a \ (a \in M \to \varphi(a)) and \forall a, b, c \in M : \varphi(a,b,c) is syntactic sugar for \forall a \in M \ \forall b \in M \ \forall c \in M : \varphi(a,b,c) which according to the former syntactic sugar means \forall a \ (a \in M \to \forall b \ (b \in M \to \forall c \ (... 1 (1) Every Element of M is negative My response: \forall m \in M : m<0 with the negation \exists m \in M : m\geq 0 Yes. (2) Between two different elements of M there is another element of M. My response: \forall m,n\in M:m \neq n \exists z\in M: m<z<n \vee m>z>n with the negation \forall z \in M : m=z=n \exists m,... 1 Your negations of statements (2) and (4) are wrong, essentially for two reasons: the negation of a universal quantifier is an existential quantifier, and you cannot invert the order of an existential and a universal quantifier (if you invert their order you change the meaning of the sentence: think of the difference between \forall m \exists n \, m < n ... 1 Here is a natural deduction proof using a Fitch-style proof checker: Since A is used to code \forall in this tool, I replaced A with P. The proof uses in this order conjunction elimination, existential introduction and existential elimination. Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.... 1 Here's a proof using a Fitch-style proof checker: As Graham Kemp mentioned in the comments below, I did not prove what the OP requested. The OP wanted a proof for the following:$$ \forall x(Px \lor \exists y Py)\leftrightarrow \exists x Px$$Here is that proof: Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://... 1 Here is a proof using a Fitch-style proof checker for the first part: Most of this is an exercise in using disjunction introduction and elimination rules. Note that I added parentheses to disambiguate the propositions. This put a constraint on how I would have to construct the proof. For the second part, various attempts to bind the variables generated ... 1 Here is a proof of the result by cases using a proof checker: Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/ 1$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline #2\end{array}}\$ The thing about natural deduction is that if something is provable, you can often reverse engineer the proof by deciding what needs to be, and may be, introduced or eliminated, step by step. Okay, so our goal is to prove that a conditional statement is a theorem (that it holds with no ...

Only top voted, non community-wiki answers of a minimum length are eligible