Tag: Wau
Logic on Math StackExchange
- What is the dependency of the chapters in Topoi: The Categorical Analysis of Logic October 15, 2024I'm studying this book and my main interest is the Chapter 13.3 Arithmetic, The Peano postulates. How dependent is this chapter on previous chapters? Lineally I went through Chapter 1-4 and then skipped to Chapter 6 and 8. What other chapters do I need to study to go to Chapter 13?Jared Montecinos
- Example of a class of structures not axiomatizable in any $n$-th order logic, for finite $n$ October 15, 2024I suppose these questions have already been asked here somewhere, but I haven't found it. Do we know of any class of structures that is not axiomatizable in any $n$th-order logic, for finite $n$? Or are the finite-order logics sort of exhaustive in this sense? Do we know of any class of graphs that is […]Timotej Šujan
- Are the Turing degrees on Cantor exactly the same on Baire? October 15, 2024Background: As far as I know, the Turing degrees are usually defined (considering sets of naturals) on the Cantor space $2^\omega$ as the equivalence classes induced by the Turing reducibility $\le_T$. That is for $X \in 2^\omega$: $$ \deg_T^{2^\omega}(X) := \{ Y \in 2^\omega \mid Y \equiv_T X \} = \{ Y \in 2^\omega \mid […]NON
- Looking for a textbook on logic October 14, 2024I'm preparing an introduction to logic for non-mathematicians, and in the process, I’m trying to better understand the basics myself. I came across a post on this forum: Difference between $\to$, $\models$ and $\implies$, where a textbook is mentioned but not directly referenced. In the post, @MauroALLEGRANZA provided an answer, also citing the textbook, but […]mandel_broetchen
- Does proof by contradiction construct a vacuously true statement? [closed] October 14, 2024When you are proving something using proof by contradiction, are you actually constructing a vacuously true statement? Let's say that you want to prove $P$ via proof by contradiction. First, you assume that $\lnot P$ is true. Then via direct proof, you show that $\lnot P \Longrightarrow \bot$. Since the only way for the statement […]Jon
- In the positive fragment of Naive Set Theory, does $\{x:x\in x\}$ belong to itself? [duplicate] October 14, 2024The Naive Set Theory ($\mathsf{NST}$) is an inconsistent, trivial theory, but its positive fragment was shown to be consistent and is basis of e.g. positive set theory $\mathsf{GPK}_{\infty}^{+}$ of Olivier Esser. In the positive fragment, instances of unrestricted comprehension are restricted to only positive formulas (the smallest class of formulas containing atomic membership and equality […]Timotej Šujan
- Confusion with the proof for the Halting Problem October 14, 2024I was considering the halting problem, and I'm confused about why it is impossible. As I understand it, the problem is defined as follows. There exists a program $h(x,i)$ which takes as input a program $x$ and an input to that program $i$ and then reports if the program $x$ reaches a final decision on […]Emizaquel
- What if someone proves Self referencal paradox in general [closed] October 13, 2024Good greetings I have a question that might seems stupid to one yet Is it possible to find a general solution for self referencal paradox??? Like for say a general algorithm that can help to find out the way to solve any/almost all self referencal paradox I would be incredibly grateful if one could provide […]Avantika Vats
- Is it true that there are real numbers that cannot be expressed? [duplicate] October 13, 2024This might be elementary (or obviously wrong) for mathematicians. I am an engineer. Since we write numbers using finite strings of symbols (not necessarily digits - even formulas are finite strings of symbols) does that mean that there are a lot more real numbers which cannot be written in any way, than there are real […]Censored to protect the guilty
- What exactly is (should be) a “structure” for $L_2$ (language of 2nd-order arithmetic)? October 13, 2024From Simpson’s Subsystems of Second Order Arithmetic: The language of second order arithmetic is a two-sorted language…Variables of the first sort are known as number variables…Variables of the second sort are known as set variables…Atomic formulas are $t_1 = t_2$, $t_1 < t_2$, and $t_1 \in X$ where $t_1$ and $t_2$ are numerical terms and […]NikS
Recent Comments