30
votes
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
18
votes
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
9
votes
The meaning of an implication with the existential quantifier
"Someone is a comedian and that means they are funny" actually means $$\exists x\, C(x)\land \forall x\,\big(C(x)\to F(x)\big),$$ which is a logically stronger assertion than $$∃x\,\big(C(x) ...
- 40.7k
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.4k
7
votes
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 ...
- 252k
6
votes
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
6
votes
Negating a multiply quantified statement
The statement is saying that there exists a single number $x$ such that the following equations all hold simultaneously:
$2x+1=7$
$2x+2=7$
$2x+3=7$
...
And so on and so forth, for every real number $...
- 6,843
5
votes
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 ...
- 252k
5
votes
The meaning of an implication with the existential quantifier
$∃x(P(x) → Q(x))$ never really makes sense.
If $~\exists x (\neg P(x))~$ (usually a reasonable assumption), this will always be true for any predicate $Q$ whatsoever. So, it kind of "makes sense,...
- 15k
5
votes
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.3k
4
votes
Negating a multiply quantified statement
There exists a real number $x$ such that for all real numbers $y,\; 2x+y=7.$
my textbook says that this statement is false.
Let's rephrase the given statement:
There is some real number $b$ for ...
- 40.7k
4
votes
Negating a multiply quantified statement
The order of quantifiers matters. That is the reason why complex assumptions must always be written in mathematical language: because it allows no ambiguity. English language (or whatever your first ...
- 1,468
3
votes
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 ...
- 491
2
votes
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
2
votes
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
2
votes
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 ...
- 252k
1
vote
Conditional or biconditional for 'except'?
Everyone likes Mary, except Mary herself.[...] I think that a
biconditional should be used instead of a conditional.
I agree.
A straightforward interpretation of this sentence is that Mary does not ...
- 15k
1
vote
Accepted
Why is this proof of the Tarski-Vaught criterion incorrect?
No issues with the proof. The problem is you are proving the wrong thing: the statement you have written is not the Tarski-Vaught criterion.
The Tarski-Vaught criterion is the more useful statement ...
- 61.3k
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
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
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
1
vote
Accepted
Using logical equivalences without propositions?
$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
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
Only top scored, non community-wiki answers of a minimum length are eligible