# Tag Info

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 ...
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$, ...
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 ...
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 ...
• 1,383
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$...
• 249k
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 ...

### 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 ...
• 320
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 ...
• 2,876

### 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 ...
• 55.4k
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 ...
• 249k
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 ...
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 ...
• 4,963

### 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\ ...
• 181k
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 ...
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. ...
• 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 ...
• 1,530
1 vote

• 14.8k
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’) ...
• 101k

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