Tag Info

• 24.7k

• 40.7k
Accepted

The meaning of an implication with the existential quantifier

Example c was written: $\exists x (C(x) \to F(x))$ The answer to that example was given as "Someone is a comedian and that means they are funny" That is an incorrect translation. Imagine a ...
• 10.5k

Non-standard model of arithmetic

The official name for this is the reduct. You take the structure $\mathfrak A'$ and make a structure $\mathfrak A$ in signature $\mathcal L_{NT}$ by using the same underlying set as $\mathfrak A'$ and ...
• 61.2k
1 vote

The validity of $∀x(Bx↔∃yRxy)↔\big(∀x∃y(Bx→ Rxy)∧ ∀x∀y(Rxy→Bx)\big)$

A good practice is to conjure up a model to render the formalism meaningful, as it is expressed in the question. One may choose any model congenial to oneself as far as the context allows. ...
• 2,581

What does it mean for a predicate to be ground?

Let Domain $D=\{0,1,2,3\}$ We might have a Predicate $P_1(n):n^2<1$ Consider the Statement $S_1 \equiv \exists n : P_1(n)$ , which has a variable $n$ , hence it is not ground. Statement $S_1$ can ...
• 13.5k
Accepted

What does it mean for a predicate to be ground?

I will briefly describe how to form a first-order term or formula. I believe that will be enough to distinguish between a grounded expression and a non-grounded one. You can find more details in any ...
1 vote

The prenex form doesn't seem equivalent to the original sentence

$∀x\Big(∀y f(y) → g(x)\Big)\tag{A1}$ for all x, if for all y, f(y) is true, then g(x) is true $∀x∃y\Big(f(y) → g(x)\Big)\tag{A2}$ ...
• 40.7k
Accepted

A countable inductive first-order theory which has non existentially-closed (e.c) model has a non e.c. model of any infinite size

I'd like to answer my question. The answer is an adaption of the suggestion made by David Gao is the comment above, and the details can be found fully in Hodges' book in the section on relativisation. ...
• 318
Accepted

Hilbert style proof systems vs Natural deductions: Some naive questions

A: The first thing to note is that the 'hypotheses' that the website talks about are not the statements in $\Gamma$. The statements in $\Gamma$ are often referred to as premises. Both natural ...
• 102k
Accepted

How to reduce to reduce to the case where the class $C$ is a set in this model theory exercise

Use the cumulative hierarchy! There must be some ordinal $\alpha$ such that for every $\mathcal{M}\in C$, there is an $\mathcal{M}'\in C\cap V_\alpha$ with $\mathcal{M}\equiv\mathcal{M}'$; this is ...
• 251k

Strong Completenss vs Finitely Strong Completenss

The canonical example of this is the logic $L(Q)$ gotten by adding the quantifier $Q\equiv$ "There exist uncountably many" to first-order logic. Improving on earlier work of Vaught, Keisler ...
• 251k

Can you give me an example of an implicit use of Godel's Completeness Theorem, say for example in group theory?

It's worth noting that we rarely care about the existence of a first-order proof from a given set of axioms. A first-order proof is a very messy object, and if we're not already interested in them for ...
• 251k

Can you give me an example of an implicit use of Godel's Completeness Theorem, say for example in group theory?

A simple example might be something like the following: Proposition: An element $g \in G$ of a group and any of its conjugates $hgh^{-1} \in G$ have the same order. This is a collection of first-...
• 442k

Is a cyclic relation symmetric?

For any ${\mathrel R}\subseteq A\times A$, cyclicity is defined as: $\forall a{\,\in\,} A\,\forall b{\,\in\,}A\,\forall c{\,\in\,}A~(a\mathrel Rb\wedge b\mathrel Rc\to c\mathrel Ra)$. Cyclicity does ...
• 131k
1 vote

Valid and logically valid formula in first-order logic?

$\Gamma\vdash\phi$ means set $\Gamma$ syntactically entails $\phi$ by some proof system. This is called valid, or syntactically valid, when a rigorous proof can be composed correctly applying the ...
• 131k

Valid and logically valid formula in first-order logic?

$\Gamma \vDash \phi$ means that $\phi$ is true whenever all statements in $\Gamma$ are true. We can say that $\Gamma$ implies (or better put: logically implies) $\phi$, or that $\phi$ logically ...
• 102k
1 vote

Valid and logically valid formula in first-order logic?

Regarding "valid" and "logically valid" respective meanings: yes, they are synonymous. Regarding the example with group theory, we say that the theorem follows from or is a logical ...
• 95.3k

Is a cyclic relation symmetric?

Hint: Find a relation that is cyclic, but not symmetric. Hence, there must be an error in your proof that any cyclic relation is symmetric. As indicated in the comments, the "substitute $c$ by $b$...
• 72.1k
Accepted

Clarification on the dot notation in formulas

Once a usual element of notation, dot has long faded away from the formal language of logic. The following excerpt that describes its twofold use is from the second edition of Principia Mathematica by ...
• 2,581
1 vote
Accepted

$x\in A\cup(B\cap C)$ $\Leftrightarrow x\in A$ or ($x\in B$ and $x\in C$) $\Leftrightarrow$ ($x\in A$ or $x\in B$) and ($x\in A$ or $x\in C$) $\Leftrightarrow$ ...... To use the logical equivalence $... • 40.7k 0 votes Proving$\vdash \neg \neg P \to P$(double negation elimination) in first order logic, preferrably without deduction theorem Minimal proof (17 steps) You're asking for *2.14 from Metamath's pmproofs.txt database, which has a condensed detachment proof DD2DD2D13DD2D1311 in D-notation (that ... • 282 0 votes What does 'imply' mean in maths? I'm not sure we need another answer here. But most of the other answers follow classical logic closely. I think the constructive logic meaning may be more intuitive. It's simply: We say that$A$... 0 votes What does 'imply' mean in maths? Adding to the other answers (which have pointed out that$\boldsymbol P$implies$\boldsymbol Q$means that$P$being true necessitates that$Q$be true): When we know that$\boldsymbol P$is false ... • 40.7k 0 votes What does 'imply' mean in maths? It means the same as it means in regular English. If we say “A implies B”, it means that the truth of B is a consequence of the truth of A. There are many different ways of expressing this. For ... • 43.8k 0 votes How to determine if a restriction on a class in description logic that uses concrete domains is valid? Not sure if the question I asked was overly simple. But the process I found is: If$C_1$is a class and$C_2$is a class, then$\neg C_1$is a class,$C_1 \cup C_2$is a class, and$C_1 \cap C_2$is a ... 8 votes Accepted A first order theory of$\mathbb{R}$The first-order theory of$\mathbb{R}$is well-understood. It is one of the oldest and most important examples in the field of model theory. An ordered field$R$is real closed if every positive ... • 80.3k 3 votes Unsure about using nested quantifiers There are several things wrong with your: $$\forall x(Mx \forall y My \rightarrow\exists w(Tw \& Gxtw)$$ First, it is not grammatical: you need a connective between$Mx$and$\forall y My$. You ... • 102k 0 votes Is "Alice loves candies" actually necessary for "Alice loves all sweet foods"? The English-language statement "Alice loves candies" may either be taken to imply that Alice loves all candies, that Alice loves at least some candies, or most typically that Alice loves ... • 563 1 vote Accepted Unsure about using nested quantifiers Required to translate: Every man gave every woman some toy. Consider instead:$~\forall x(Mx \to \forall y (Wy \to \exists t(Tt \land Gxyt))) $where Mx = x is a man Wy = y is a woman Tt = t is a ... 6 votes Is "Alice loves candies" actually necessary for "Alice loves all sweet foods"? It seems like the analysis is made more complicated by thinking about negations. More simply, consider the implication$B \implies A\$; that is, "If Alice loves all sweet foods, then Alice loves ...
• 8,668

Top 50 recent answers are included