New answers tagged

0

$$\def\fitch#1#2{~~~\begin{array}{|l} #1\\\hline #2\end{array}}\fitch{~~1.~~\forall x~(A\to B)}{\fitch{~~2.~~\exists x~(A\land\lnot B)}{\fitch{\hspace{-4ex}\boxed n~~~~3.~~(A\land\lnot B)[n/x]}{~~4.~~A[n/x]\;\land\lnot B[n/x]\\~~5.~~A[n/x]\hspace{15ex}{\land}\mathsf e~4\\~~6.~~\lnot B[n/x]\hspace{13.5ex}{\land}\mathsf e~4\\[1ex]~~7.~~(A\to B)[n/x]\hspace{8ex}...


0

Let $V$ denote the partial function from the question. Suppose $n\notin A$. Then $\exists x_0 \forall y_2 \neg T(n, x_0, y_2)$. Then the domain of $V(n,-)$ is a subset of $\{x\in N: x < x_0 \}$ (hence finite). Here's why nothing outside this finite set can lie in the domain. If $x \ge x_0$, then the condition $$\forall y_1 < x \exists y_2 T(n,y_1,y_2)$$...


3

Let $L = \{\leq\}$, and let $T$ be the complete theory of $N = (\mathbb{N}^*,\leq)$, the reverse order on the natural numbers. Let $M = ((\mathbb{N}\cup \{-1\})^*,\leq)$, so $M$ adds a new maximal element $-1$ on top of $N$. Then $M$ is an end extension of $N$, and it is also a model of $T$ since it is isomorphic to $N$, but it is not an elementary extension:...


0

As usual the key is to work backwards. To introduce the universal, assume an arbitrary variable, $a$, then derive $P(a)\to\lnot Q(a)$. To introduce that conditional, assume $P(a)$ then derive $\lnot Q(a)$. To introduce that negation, assume $Q(a)$, then derive a contradiction. To derive that contradiction under the assumptions of $\lnot\exists x~(P(x)\land Q(...


0

∀x∃y∃z (3x=150y-39z)≡T For all integer x, Let y=6x, z=23x LHS=3x RHS=150(6x)- 39(23x) ∴LHS=RHS,for ∀x∈Z


1

$\lnot \exists x (P(x) \land Q(x))$ --- premise $P(a)$ --- assumed [a] $Q(a)$ --- assumed [b] $\exists x (P(x) \land Q(x))$ $\bot$ $\lnot Q(a)$ $P(a) \to \lnot Q(a)$ $\forall x (P(x) \to \lnot Q(x))$


1

Universal elimination when $∀$ is not the main operator. You cannot apply UE when the quantifier is not the main operator. You have to derive $\forall x A(x)$ in order to use it to "detach" $B$ using ($\to$-E): $\forall x A(x) \to B$ --- premise $\lnot \exists x (A(x) \to B)$ --- assumed [a] $\lnot A(y)$ --- assumed [b] $A(y)$ --- assumed [c] ...


3

The quantifiers $\forall x\in D~$ and $\exists x$ each bind all free occurrences of $x$ inside their scope. However, any such occurrence can be bound to only one quantifier, and its immediate container has precedence. Since such occurrences of $x$ inside the scope of $\exists x$ are bound to that quantifier, therefore they are not considered free inside the ...


1

See Universal generalization. The rule formalize the intuitive sound argument that, if we can assert that a "generic" object $x$, i.e. an object whatever, has property $P$, then everything has that property. The "generic" restriction must be expressed with the restriction that nothing must be asserted in the "context" [the ...


0

So, to get an intuition for logical formulae I can't quite get my head around, I usually try to rewrite them into something that's easier for me to reason about. If you're using classical FOL, then you could apply $(\varphi \Rightarrow \psi) \Leftrightarrow (\neg \varphi \vee \psi)$ and $\neg (\forall x \in A. \phi) \Leftrightarrow (\exists x \in A. \neg\phi)...


0

I will assume, alhough you should probably make this clearer in your question, that you are quantifying over nodes and you have a binary predicate $E$ stating that two nodes are connected by an edge. Your formula $\exists v\forall b E(v,b)$ just says that there exists an element (let us call it center) which connects to every other element, but it doesn't ...


1

Part (a) asks for two things. You have only provided the first of the two. You have not addressed "Also, by convention, subtracting one from zero has no effect." For part (b), you might benefit from introducing some notation. For instance $\mathbf{next}^3(\mathbf{\tilde{0}}) = \mathbf{\tilde{3}}$. Notice that the problem does not deny the ...


0

This reduces to: $\exists x \colon y \in \{\} \implies P(x)$. But $y \notin \{\}$. The truth table of material implication/conditionals ('IF') definitionally maps False to True. QED.


0

You could restate the claim as $\exists x\in S\neg\exists y\in\emptyset\neg P(x)$, which is trivial for each $x\in S$.


0

I don't know why you insist that $(n,x)$ not be defined when it doesn't take the value $1$. I prefer to think of it as a total function that takes the value $0$ when $\forall y_1 \le x, \exists y_2 T(n,y_1,y_2)$ is not true, i.e. when $\exists y_1 \le x, \forall y_2, \neg T(n,y_1,y_2)$. Then the question is whether the set of $x$ for which $(n,x)$ maps to $1$...


2

Per the comments, your main interest is in the behavior of Hanf numbers when we drop equality from a logic. (Below we suppose $\mathcal{L}$ is a "reasonable" logic since we need some meaningful syntax to even talk about equality-free fragments after all.) For reasonably simple logics - including first-order logic and its infinitary veresions - the ...


3

Concerning your first question, the upward Löwenheim-Skolem theorem in FOL without equality is much simpler (and less interesting). Let $M$ be an infinite model, and pick an element $m\in M$. Then you can always adjoin an arbitrary collection $\{m_i|i\in I\}$ of copies of $m$ to the model $M$ by stipulating that the $m_i$'s satisfy the same relations as $m$, ...


2

Assume your proof ends with $D \cdots \forall v_1 \phi(v_1) \vdash \phi(t)$. [EDIT: The following paragraph is a correction following a comment from Albert.] If $v_1=v$, first rename all bound occurences of $v_1$ in the derivation $D \cdots \forall v_1 \phi(v_1)$ to a variable $v_1'\neq v$ which does not yet occur in the proof. All rules remain sound, and $D$...


0

Asaf Karaglia's question in comments is very relevant: what predicates and constants do you have in your language? Meaning, can I write $\#X=n$ in a formula to mean that the cardinality of $X$ is $n$? Can I write $\mathbb{N}$ for the set of natural numbers? Can I use the order of natural numbers as a given? I assume I can use all of this, although it would ...


2

The second formula is ok. The first one isn’t. It isn’t even a well formed first order logic formula.


1

No; for example, let $a,b$ be two distinct variables and $P$ a unary predicate. Then the $(\forall L)$ inference $$ { P(a)\vdash P(b) \over \forall x P(x) \vdash P(b) } $$ satisfies the eigenvariable condition ($a$ does not occur freely in the lower sequent) and its conclusion is valid, while its premise clearly is not.


1

To make this question self-contained, these are the rules in question: $$\forall L: \frac{\Gamma, A[t/x] \vdash \Delta}{\Gamma, \forall x A \vdash \Delta}$$ $$\forall R: \frac{\Gamma \vdash A[y/x], \Delta}{\Gamma \vdash \forall x A, \Delta}$$ In the case of $\forall R$, you are trying to conclude $\forall x A$. Therefore your assumption must be $A[y/x]$ ...


0

$\def\fitch#1#2{~~~~~\begin{array}{|l}#1\\\hline #2\end{array}}$ It might be worth noting that any proof will necessarily involve something like excluded middle or double negation elimination - the statement is not valid in intuitionistic first-order logic. Here's Mauro ALLEGRANZA's LEM proof, reformatted. $$\fitch{~~1.~~Pa\to\exists y~Qy\hspace{21ex}\...


0

The basic fact is to define what does it mean for a structure (or: interpretation) $\mathfrak A$ to satisfy formula $\varphi$ with variable assignment function $s$. In symbols: $\mathfrak A,s \vDash \varphi$ (alternatively: $\mathfrak A \vDash \varphi[s]$). Intuitively, the definition means that the "translation" of $\varphi$ determined by $\...


0

The definition is not that there is a different succession. The definition is that there is some succession. This may be different or identical to the original one.


1

There exists some $x_0$ such that $Px_0$, which implies $Qx_0$, which implies $(Rx_0,y_0)$ for some $y_0$. But because of $\forall x \forall y \neg (Rx,y)$, we simultaneously have $\neg(Rx_0,y_0)$, so you have a contradiction.


1

The logical form of the definition of satisfiability is: (the sentence) “Plato is a Philosopher “ is true iff Plato is a philosopher. Thus, the locution “is satisfiable”, that like “is true” applies to a linguistic expression, is on the left side of the definition: formula ... is satisfiable iff..., while on the right side we have a fact, to which “it holds”...


1

An $n-$place relation is just a set of $n-$tuples. The $n-$tuples in the set are the ones the relation is true for. As an example, a nice one is $\lt$ over the integers. In the language of set theory, $\lt$ is a set of ordered pairs. We have $(1,2) \in \lt, (2,1000)\in \lt, (4,2) \not \in \lt$ and so on. From this point of view, $(A^n_k)^M(s^*(t_1) , ......


3

Let $f:\mathfrak A\rightarrow\mathfrak B$ be a surjective homomorphism. Then $\mathfrak A\models\Phi(a_1,\dots,a_n)\Longrightarrow\mathfrak B\models\Phi(fa_1,\dots,fa_n)$. This is false. Your argument works for the inductive step of adding a universal quantifier, but not for the inductive step of adding a negation. We say that a map $f:\mathfrak A\...


2

Yes, quantifiers of the same type are commutative: $$\forall u \forall v \phi \equiv \forall v \forall u \phi \text{ and }\exists u \exists v \phi \equiv \exists v \exists u \phi$$ for all variables $u, v$ and formulas $\phi$. If two subformulas are logically equivalent, so are all formulas they occur in, so $\forall x \exists y \exists z \phi \equiv \forall ...


3

$x=\Lambda.p$ means $(x=\Lambda).p$, the conjunction of two statements. For any statement $\phi(x)$ about $x$, the notation $\hat x\,\phi(x)$ means what we'd nowadays write as $\{x:\phi(x)\}$.


1

In the system you're studying (first-order logic), a language has a fixed "universe" (also called a "domain of discourse"), and the quantifiers $\forall$ and $\exists$ always range over (i.e. "apply to") all the objects in that universe. If the universe is just birds (i.e. if our language is only for talking about birds and ...


1

There are two ways to look at this. In the first statement about birds that can fly, the implication, B->F, just as any other implication can be written as F or -B, or else, -(B and -F). In the second statement about men geniuses, it concerns the existence of a man who is a genius. It is the same as stating that there is a genius who is a man. Here, being ...


0

The first one is more appropriate, and "if" is more conventional than "iff" in definitions (i.e. sentences introducing terminology with "is called" / "we say that" / etc.). Your concern is that if our definition defines "even" only for natural numbers, then writing "1.5 is even" is a sort of "...


1

To be rigorous about this you need to understand the distinction between the metalanguage in which we are reasoning about the semantics and the object languages whose semantics we are reasoning about. The statement that the set of all sets does not exist is relative to the closure properties that we require of the set of all sets: we may assume stronger ...


0

You have a working translation but there are a few notes I might add. First, your sentences are not entirely in predicate logic, they are still using the English convention "such that" and they are using restricted quantifiers. These are phrases like $\forall x\in\mathbb{Z}$ as opposed to $\forall x$. They are not a part of the language of ...


1

The difference is that in the first statement the proposition is that there exists an $x$ such that the statement $(Px\rightarrow \forall yPy)$ is true. This is indeed tautological since, if $\forall yPy$ the implication is true for each $x$. If not $\forall yPy$ there exists an $x$ such that $\neg Px$. implying that for given $x$ the statement $Px\...


Top 50 recent answers are included