Written work, Due Thursday, October 17th, in class:
Chapter 4 p.100: 1, 6, 7, 15, 16
Odd problems are worth 4 points, even problems worth 8 points.
WeBWorK – none
OpenLab – OpenLab #5 Due Thursday 10/24. NOTE: Please complete the writing portion on the OpenLab, but bring your Conjecture to class on 10/24 (do not post your Conjecture to the OpenLab)
Tag: week 8
Logic on Math StackExchange
- Computationally weak set with computationally strong jump April 12, 2025There exists a set $A \subseteq \mathbb{N}$ with the following properties: $A \ngeq_T \emptyset'$, $A' \geq_T \emptyset''$. (Take, for example, any high set that is not $\Delta^0_2$-complete.) This set $A$ is computationally weak, but its jump is computationally strong. How far can we take this idea? For example, does there exist a set $A$ with […]Gavin Dooley
- How to solve: ¬¬(P∨¬Q)⊢(P→¬Q)∨(¬Q→P) with natural deduction without De Morgan's laws. (Tomassi) April 12, 2025Here is what I have, I know its way off, but I don't know how to bring the premise in or what do do about the dependency numbers for the conditional. Any help would be appreciated. (Couldn't find the question elsewhere but will delete if its a duplicate.) (1) 1. ¬¬( p ∨ ¬q ) […]TTT
- Clarity on proof insolubility of decision problem for logical implication April 12, 2025I am currently reading Computability and logic by George S. Boolos and other authors, in chapter 11, section 1&2(pg 126-134) two proofs of the insolubility of the decision problem for logical implication are given the i have questions about both proofs but are they essentially the same question so i will mention only the first, […]Abel Marnk
- Why doesn't Cantor's diagonal argument prove only that the reals are not recursively enumerable? April 10, 2025In this answer to the question Why are the total functions not enumerable? the following argument is made: Because of diagonalization. If $(f_e: e \in \mathbb{N})$ was a computable enumeration of all total computable functions from $\mathbb{N}$ to $\mathbb{N}$, such that every $f_e$ was total, then $g(i) = f_i(i)+ 1$ would also be a total […]janekb04
- What does PA think it knows about ConPA? April 10, 2025By Gödel's Incompleteness Theorems, PA doesn't prove ConPA. However, does PA prove or refute Pr(ConPA), where Pr(x) is the provability predicate? If neither is true... what would be an example of sentence A such that PA does not prove A but PA proves Pr(A). Clarification: For any A, if PA proves A, then PA proves […]Zergicov
- Listable (by an effective method) but undefinable set of natural numbers? April 10, 2025For a formal system $F$ to which Godel's incompleteness theorem applies and a provability predicate $provF(x)$ that is a $\Sigma^{0}_1 -formula$, if we have a predicate $pr(x)$ , such that $ext(pr)$ = { $⌈A⌉ : ℕ⊨ A$ and $F ⊬ A ⇔ ¬provF(⌈A⌉)$ } $n ∈ ext(pr)$ ⇔ $ℕ⊨pr(n̅)$ Then the following set is not […]Logician Meta
- Quantifiers vs set operations April 10, 2025When studying probability theory, I noticed that there often is some kind of mapping between symbols $\forall, \exists$, and set operations $\cap, \cup$, for example: The logical sentence: $f$ is continuous on $\mathbb{R}$ can be expressed as:jrg
- Propositional variables vs. metavariables in finitely axiomatized propositional calculus April 9, 2025I've been trying to wrap my head around different foundations of mathematics, and I've come across two different approaches: finite and infinite axiomatizations. There are "layers" to axioms: propositional calculus, predicate calculus, set theory... (type theory and other foundations are outside the scope of this question), and they don't even need to follow the same […]Primož
- Are rules of inference in first order theory proven? April 8, 2025I am currently reading Shoenfield's book as an introduction to logic, and towards the ending of chapter two he states the three properties of a first order language:- We can now define the class of formal systems which we are going to study. A first-order theory, or simply a theory, is a formal system T […]Abel Marnk
- Can $\mathsf{PA}$ prove the Completeness Theorem for $\mathsf{PA}$? April 8, 2025As title states, I'm wondering whether $\mathsf{PA}$ could "prove" the Completeness Theorem for, well, $\mathsf{PA}$ (or other similar enough theories). I know that $\mathsf{PA}$ by itself is totally unable to prove the regular Completeness Theorem, as it seems to make use of Zorn's Lemma and other stronger axioms. I think I've seen it stated that […]Sho
Recent Comments