Conjecture:
“What restrictions can be placed on the maximum and minimum number of visits per vertices?” Continue reading
Tag: Open Lab #6
Logic on Math StackExchange
- Mathematical Logic Book Recommendation for Beginner June 29, 2024In my discrete math course we went over the basics of propositional logic and predicate logic. We covered things like truth tables, connectives, and quantifiers. I am interested in studying more mathematical logic, but I don’t know which book to choose. I’ve looked at Peter Smith’s Guide but I’m still having a hard time knowing […]Dr. J
- Proof of ((A→B)→A)→A using axioms and hypothetical syllogism June 29, 2024Problem: Prove ( ( 𝐴 → 𝐵 ) → 𝐴 ) → 𝐴 ((A→B)→A)→A using axioms and hypothetical syllogism (HS). Relevant Axioms: Axiom 1 (A1): 𝐴 → ( 𝐵 → 𝐴 ) Axiom 2 (A2): ( 𝐴 → ( 𝐵 → 𝐶 ) ) → ( ( 𝐴 → 𝐵 ) → ( 𝐴 → […]daniel ph
- Valid iff $Q\iff P$ June 28, 2024In Problem set 1, exercise 3(b) from Mathematics for CS MIT OpenCourse, we are asked to describe a formula R using only elements from {Q, P, or, and, not}, but in such a way that R is valid iff Q and P equivalent. Definition of valid from the accompanying textbook: A valid formula is one […]Lina
- Predicate formula of proposition, author lacks precision in explanations June 28, 2024I have a problem: Consider the two following propositions: All persons have a mother. There is one mother of all persons. Now consider the predicate formulas of both propositions: $\forall x \exists y \Bigr[ M \bigl( x,y \bigl) \Bigr]$ $\exists y \forall x \Bigr[ M \bigl( x,y \bigl) \Bigr]$ The author of my logic textbook […]Noah Wurtz
- Proof calculus for second-order logic June 28, 2024In the comments of a recent question of mine, Alex Kruckman wrote: It is not at all clear what would count as a suitable collection of proof rules for SOL. I know there is no hope for a SOL calculus to be complete, but isn't the calculus obtained by adding substitution rules to the FOL […]richardIII
- How does type theory deal with the lack of completeness, compactness, etc.? June 28, 2024As far as I understand, type theory (let's say Simple Type Theory or one of its extensions such as Homotopy Type Theory) is a computational view of $\omega$th-order logic. See this question: Type theory vs higher-order logic However, I thought that when you go beyond first-order logic (FOL) you lose a number of important model […]richardIII
- How to prove $\exists x (x=a)$ in intuitionistic logic June 28, 2024How do you prove $\exists x (x=a)$ intuitionistically, where $a$ is a constant symbol? Classically, one has $$ [\neg\exists x (x=a)]^1\vdash \forall x (\neg x=a) \vdash\neg a = a \vdash \bot \vdash^1 \exists x (x=a)$$ but this fails intuitionistically. I'm confused since by the definition of the rules, one cannot simply do existential generalization only […]10012511
- Problem with negating a definition June 28, 2024$X$ is disconnected if and only if there exist open sets $A$ and $B,$ both non-empty and disjoint, such that $A∪B=X$. I would write this as: $X$ is disconnected if and only if there exist $A, B$ such that $A$ and $B$ are non-empty and $A∩B=Ø$ and $A∪B=X$. If I want to negate this, it […]Damien
- Example of undecidable recursive set of formulas in Propositional Logic June 28, 2024What would be an example of a set $T$ of formulas in propositional logic that is undecidable but recursive? By undecidable I mean that the set of all formulas provable from $T$ is non-recursive.kevin.spacey
- For which cardinals $\kappa$ is the theory of a single bijection lacking cycles $\kappa$-categorical? June 28, 2024I'm currently stuck on Exercise 2.5.13 of David Marker's model theory text. The full statement of the exercise is as follows: Let $\mathscr{L}$ be the language containing a single unary function symbol $s$, and let $T$ be the $\mathscr{L}$-theory asserting that $s$ is a bijection with no cycles (i.e., for each $x$, $s^n(x) \neq x$ […]doghousereilly
Recent Comments