# Tag: Open Lab 8

### Handy Links

### Logic on Math StackExchange

- Regarding the question of translating the verbal descriptions of definitions and theorems into propositional logic July 19, 2024I am studying discrete mathematics and recently trying to describe mathematical definitions or theorems in the form of propositional calculus or predicate calculus. I am not sure if my approach is correct. For example, for a many-to-one function, the definition is that there exist two different elements in the domain mapping to the same element […]咪苦力怕
- Simple logic question $∀a ∈ A, [(∃b ∈B : P(a,b)) \Rightarrow Q(a)]$ July 19, 2024I would like to ask you for help with logic $\forall\ a \in A,\ \left[\,\left(\,\exists\ b \in B : \operatorname{P}\left(a,b\right)\,\right) \Rightarrow \operatorname{Q}\left(a\right)\,\right]$ $\forall\ a \in A,\ \left[\,\exists\ b ∈ B : \left(\,\operatorname{P}\left(a,b\right) \Rightarrow \operatorname{Q}\left(a\right)\,\right)\,\right]$ Do these two expressions mean the same thing ?. I think so but I would like to be sure, so I'm […]calippo
- Gödel Incompleteness theorems - gap between first order logic and arithmetic July 19, 2024I have a doubt concerning Gödel's incompleteness theorem which might be stupid but that makes me uneasy. If I'm not mistaken, Gödels proof is broadly undertaken using first order formulas, numbering them (where arithmetic kicks in), and then, using first order formulas in the shape of numbering, reaching a number which in first order logic […]user1358735
- (When) are recursive "definitions" definitions? July 19, 2024This is a "soft" question, but I'm greatly interested in canvassing opinions on it. I don't know whether there is anything like a consensus on the answer. Under what conditions (if any) are recursive definitions of arithmetical functions truly definitions worthy of the name? By "recursive definition" I mean a pair of axioms taking the […]ac2357
- Is the law of non-contradiction part of formal mathematics? July 19, 2024I am seeking hereby to clarify whether the law of non-contradiction is part of the framework in which mathematicians work or not. Wikipedia says only that this is a principle in "logic", and my understanding is that mathematics uses first order logic. I couldn't find a clear answer online as to whether or not first […]Princess Mia
- Existence quantificator introduction rule in predicates July 18, 2024Suppose that I have the axiom: $ \forall x\colon x=x. $ Which formal rule can be used to derive: $\forall x \exists y\colon x=y$. I need to apply existence introduction, but not at the top level, but inside a quantified predicate... added clarification by the answer and comments I understand that my problem is something […]Emanuele Paolini
- Decidable but incomplete arithmetical theories? July 18, 2024There are celebrated examples of theories that are both decidable and incomplete (the theory of algebraically closed fields, various toy theories with only finite models). But are there any examples of arithmetical theories that are both decidable and incomplete? I'm not entirely sure what I mean by "arithmetical theory", but at a first pass I […]ac2357
- Is the First-Order Theory Over Reals with Uninterpreted Functions Decidable? July 18, 2024While I understand that the first-order theory of real-closed fields $(\langle \mathbb{R}, +, \cdot, < \rangle)$ is decidable via Tarski's theorem and quantifier elimination, I'm curious about the impact of adding uninterpreted functions. I also know that by Nelson and Oppen, the quantifier-free fragment of the union of decidable theories is decidable. However, I am […]bytemouse
- Is there such a thing as the reverse of an implication $A \implies B$? What is it? July 18, 2024Is there any standard/common definition of the reverse of an implication $A \implies B$? Or is this term not used? One note claims that Consider the implication formula $A \implies B$. Its reverse is $B \impliedby A$. ... By definition, the reverse of an implication means the same as the original implication itself.user182601
- Does Löwenheim-Skolem require Foundation in any way? July 17, 2024As title states, I'm curious whether Löwenheim-Skolem (in either of its upward or downward versions) necessitates some implicit use of Foundation. The usual presentation makes quite clear the reliance of LS on $\mathsf{AC}$ / Zorn's Lemma and as far as I've understood, LS itself is basically equivalent to $\mathsf{DC}$. Is there any reliance on Foundation […]Sho

## Recent Comments