Skip to main content
8 votes
Accepted

Does Löwenheim-Skolem require Foundation in any way?

No, there is no use of the Axiom of Foundation in standard proofs of the Löwenheim-Skolem theorem. To see this, you could of course just read a proof and check for yourself. But here's another way to ...
Alex Kruckman's user avatar
4 votes
Accepted

Proving that the set of sentences that are true using the symbols $+,<,=$ is the same over all ordered fields

Let $R$ be an ordered field. Then the reduct of $R$ to the language $L_{\mathrm{og}} = \{<,+\}$ is an ordered abelian group. Moreover, $R$ is divisible: Every ordered field has characteristic $0$, ...
Alex Kruckman's user avatar
4 votes
Accepted

Proving a simple consequence of the Compactness Theorem

"finite model" is incorrect. Are you sure the exercise doesn't say "finite subtheory" or "finite subset"? There are a number of basic logical errors in your two arguments ...
Alex Kruckman's user avatar
3 votes
Accepted

Prove $(B \implies (C \implies D)) \implies (C \implies (B \implies D))$ without the Deduction Theorem

Your proof is correct, but you don’t really need T1 either. It’s easiest, in my opinion, to just prove Hypothetical Syllogism as a meta-theorem, and then proceed. If you’re unfamiliar with the proof ...
PW_246's user avatar
  • 1,383
3 votes
Accepted

Decidable but incomplete arithmetical theories?

Take the language $\{+,<,s\}$ and the theory consisting of: All true sentences in $\{+,<\}$ (so basically, Presburger arithmetic without successor). The sentence saying "Either for all $x$...
Noah Schweber's user avatar
3 votes
Accepted

(When) are recursive "definitions" definitions?

This answer elaborates on my comments above. My impression from your question is that you are interested in definitions in the technical sense of mathematical logic (rather than the informal notion of ...
Alex Kruckman's user avatar
2 votes

Is implication true if two statements are always the case?

I think some people misunderstand that if a statement $C$ implies both $B$ and $A$, then in general $A \Leftrightarrow B$ does NOT hold. Therefore, in my opinion, you need to specify your question a ...
Noctis's user avatar
  • 320
2 votes
Accepted

Which statement form is right?

The only difference between "$P$ or $Q$" and "$P$ xor $Q$" is that if $P$ and $Q$ are both true, then "$P$ or $Q$" is true but "$P$ xor $Q$" is false. That ...
Dan Velleman's user avatar
  • 2,876
2 votes

Existence quantificator introduction rule in predicates

Just at each stage do the obvious thing! $\forall x\ x = x\quad\quad$ premiss $a = a\quad\quad\quad\ \ \forall$E $\exists y\ a = y\quad\quad\ \exists$I $\forall x\exists y\ x = y\quad\ \forall$I The ...
Peter Smith's user avatar
  • 55.4k
2 votes
Accepted

Is the First-Order Theory Over Reals with Uninterpreted Functions Decidable?

No, we do not keep decidability. (This uses a trick closely related to this old answer of mine.) Letting $\alpha$ be a "fresh" function symbol, consider the sentence $\theta$ which says that ...
Noah Schweber's user avatar
2 votes
Accepted

Examples of index set not Turing equivalent to the Halting Problem?

No. This is because any non trivial index set must compute the halting problem, and the only c.e. sets that compute the halting problem are Turing equivalent to it. Let $I\subseteq\mathbb{N}$ be a non ...
Giorgio Genovesi's user avatar
2 votes
Accepted

Proofs with Hypotheses Containing "or" statement

To upgrade my comment to an answer: You only need to check the first two cases, i.e. "if $p$ is true, then so is $r$" and "if $q$ is true, then so is $r$." Why? Because one of ...
Ben Steffan's user avatar
  • 4,963
2 votes

A question that has a disjunction in it

Maybe I can summarize the discussion. I think we all agree that $Q=2$. Also, that the roots of $x^2+x-6$ are $x=2$ and $x=-3$. The problem is in the statement, $$ P {\rm\ is\ defined\ by\ the\ value\ ...
Gerry Myerson's user avatar
1 vote

Is implication true if two statements are always the case?

There are multiple ways you can prove a statement such as this: The fact that $d1,d2$ are equivalent metrics won't play much of a role in the structure of your proof, consider this schema: Your ...
Bertrand Wittgenstein's Ghost's user avatar
1 vote
Accepted

logic puzzle birth year

Since A died 129 years after B was born, and at least one of A,B was alive for exactly 100 years, there must have been a gap of exactly $~129 - 100 = 29~$ years, from the time B died until A was born. ...
user2661923's user avatar
  • 37.3k
1 vote

Which statement form is right?

$p\oplus q$ this would imply that $x>3$ or $x=3$ , but not both simultaneously. While in practical terms, $x$ cannot be both greater than and equal to $3$ at the same time, the exclusive OR ...
Antony Theo.'s user avatar
  • 1,530
1 vote

Is there such a thing as the reverse of an implication $A \implies B$? What is it?

Its reverse is $B \implies A$. ... No, it says the reverse is $B \impliedby A$.. Notice the direction of the implication arrow. That is what is reversed. $B\impliedby A$ means the same as $A\...
Graham Kemp's user avatar
1 vote
Accepted

Regarding the question of translating the verbal descriptions of definitions and theorems into propositional logic

To fully formalize your definition of $P$ in predicate logic, you might consider something like: $~~~~~\forall f: \forall d: \forall c: [\forall a:[a\in d \implies f(a)\in c]\\ ~~~~~\implies [P(f,d,c) ...
Dan Christensen's user avatar
1 vote
Accepted

Simplifying Sentences that Precede a Conditional

They are logically equivalent. The relevant equivalence principle is: Exportation $P \to (Q \to R) \Leftrightarrow (P \land Q) \to R$ Still, one statement may be preferred (and thus be more ‘proper’) ...
Bram28's user avatar
  • 101k

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