Written work: NOTE: The following suggested problems are for practice only, and will NOT be collected.
Section 11.4 p194: 2, 3, 5, 6, 7
Handout: Theorem NT 6.2, 6.3
WeBWorK – none
OpenLab – none
Project Reflection – Due before the final exam, Thursday 12/20.
Logic on Math StackExchange
- Demonstrating that an Induction Hypothesis is too weak. December 5, 2024My background is in Computer Science. Proofs by induction are ubiquitous here, especially in programming languages. As a running example, let us take proving things about the natural numbers. To prove that a predicate P holds for all natural numbers (∀n:Nat, P(n)), you prove P(0) (base case) and ∀n:Nat, P(n) => P(n+1) (inductive step). In […]Suraaj K S
- The Hanf number of higher-order logic December 5, 2024The reduction of second-order logic (SOL) to a $\Pi_1^1$-fragment on the Stanford Page of Higher-Order Logic (Section 4) is as follows: From this we get that the Hanf and Löwenheim number of SOL is the same as a $\Pi_1^1$-fragment of SOL (the Hanf number of SOL is also the supremum of $\Sigma_2$-definable ordinals). The intuition […]SJe967
- Inconsistency in a logic question by Brilliant.org December 5, 2024For context: I wanted to try out brilliant.org for a while after seeing it on numerous sponsored videos by educational YouTubers. I decided to try its level 1 logic course and everything seems to make sense until this question came along. I am posting this because I feel that something is slightly off about this […]Singaporean Hermit
- Reference Request: A general approach to forcing, and some clarification December 4, 2024I've wanted to understand forcing for quite some time now, but I wish to understand it in the general sense of formal logic, rather than just the specific case of set theory, which I find quite confusing anyways. However, I'm struggling to find sources which take this approach, making me doubt it exists. I recall […]Joseph_Kopp
- Any way to show that second-order logic is incomplete by means other than using Gödel's incompleteness theorem? December 4, 2024I know a way to show second-order logic is incomplete (in the sense of full semantics). the proof is as follows. the second-order arithmetic $\mathbf{Z}_2$ or the second-order peano arithmetic $\mathbf{PA}_2$ are consistent r.e. theories and the Robinson arithmetic $\mathbf{Q}$ can be trivially translated into these theories, so there is an arithmetic formula $G$ for […]Rosser
- (p, q) ∈ S only if p ∧ q is a tautology. Assessing the relation S. [closed] December 4, 2024This is the first time I come across a question that combines relations and logic. It is said that: “Let $𝑆$ be a relation, which is defined on the set of propositional formulas as follows $$ \left(𝑝,𝑞\right) \in 𝑆\quad {\bf iff}\quad 𝑝 \wedge 𝑞\ \mbox{is a}\ tautology”. $$ I need to assess if $S$ is […]matinaros
- Axiomatizability of inclusion over any powerset December 4, 2024Is class $(\mathcal{P}(A),\subseteq)$ for arbitrary $A$ axiomatizable? One of the assignments I got was to prove that it is not, but a friend of mine suggested this structure is a complete atomic Boolean Algebra (strictly speaking isomorphic to one) and thus axiomatazible since Boolean Algebras are axiomatizable. So my question is whether his reasoning holds […]Rikimaru
- Best tool for proving that a (big) first order model is actually the model of some (big) first order theory. [closed] December 4, 2024I have to check that a (big: several hundreds axioms) first order logic theory is satisfiable. There are various authomated provers for first order logic (e.g. Vampire) that could tell me if the theory is satisfiable or not. However, they all fail (they never terminate or run out of resources), due to the size of […]kataph
- $x\lt Sy\iff x\lt y\lor x=y$ can be deduced from Robinson arithmetic $Q$? December 4, 2024We can define new predicate symbol "$\lt$" in Robinson arithmetic $Q$ by adding the axiom $x\lt y\iff\exists z (x+Sz=y)$.With this definition, $Q$ can prove that (1) $\lnot(x\lt0)$ because for all $x$, $x+Sz=S(x+z)\neq 0$ by the axioms Q1 and Q5. And we can also prove in $Q$ that (2) $x\lt Sy\iff x\lt y\lor x=y$. It is […]smooth manifold
- Question About Axiom Group 5 in Enderton's Logic Textbook December 3, 2024In Enderton's Textbook "Introduction to Mathematical Logic", he specifies 6 Axiom Groups on Page 112 Chapter 2.4 which are used in conjunction with their generalizations, a set of hypothesis $\Gamma$ and Modus Ponens to form deductions in first order logic. The Axiom Group I am confused about is Axiom Group 5, i.e for any variable […]NiraDoesMath
Leave a Reply