Written work, Due Tuesday, October 17th, in class:
Chapter 4 p.100: 1, 6, 7, 15, 16
Chapter 5 p.110: 1, 4, 9, 20*
Odd problems are worth 4 points, even problems worth 8 points.
* (Chapter 5 Problem 20 is optional – solutions will receive extra credit)
WeBWorK – none
OpenLab – none
Logic on Math StackExchange
- Simple true $\Pi^0_1$ statements unprovable in weak arithmetics October 6, 2024There is an explicitly known 745-state Turing machine where, assuming $\mathrm{ZFC}$ is consistent, the machine never halts, but $\mathrm{ZFC}$ cannot prove this fact. (This is shown in Riebel's thesis The Undecidability of $\mathrm{BB}(748)$. I am wondering if there is a much smaller machine whose halting is unprovable in some much weaker system, like $\mathrm{EFA}$ (exponential […]C7X
- If $\models \phi \lor \psi$ then not always $\models \phi$ or $\models \psi$ October 6, 2024Task is to give an example in propositional logic which shows that if $\models \phi \lor \psi$ then not always $\models \phi$ or $\models \psi$. How can I write it? Any help would be much appreciated. EDIT: So if $\models p \lor \neg p$, then it always holds for any evaluation, but $\models p$ does […]Mateusz Struk
- λP2 versus second-order logic October 6, 2024Based on my understanding from reading Wikipedia and the Stanford Encyclopedia of Philosophy, there seems to be considerable debate about second-order logic (SOL). It is said that SOL lacks its own deductive system and is sometimes not even recognized as a genuine logic. On the other hand, in the context of the Curry-Howard isomorphism, second-order […]richardIII
- For each of the following sets, determine whether 2 is an element of that set: {{2},{{2}}} October 5, 2024{{2},{{{2}}} I think that 2 belongs to {2} (because has the element 2). But 2 has no elements in {{2}} (because the only element that explicitly possesses is {2}, no the element 2 itself). Am I right?PEREZ MONSIVAIS JOSE DE JESUS
- Universal quantifier over disjunction in intuitionistic logic October 5, 2024I have a question about the following sequent, valid in classical logic: $$\forall x [\phi(x) \vee \psi] \vdash \forall x [\phi(x)] \vee \psi$$ Importantly, we assume $\psi$ does not contain any free $x$. Is this sequent valid also in intuitionistic logic? The converse sequent is not hard to prove, but with this direction I am […]Tony Dolezal
- Truth-tabling $\left[\,(p\lor q)\land(p\to r)\land(q\to r)\,\right]\implies r $ [duplicate] October 5, 2024Our professor assigned this homework. By constructing a truth table, prove this logical implications: $$\left[\,(p\lor q)\land(p\to r)\land(q\to r)\,\right]\implies r $$ How to handle two AND's in one bracket?Alix
- can self-referential statements be regarded as statements(propositions)? [closed] October 5, 2024By definition, a proposition (statement) is a declarative sentence that is either True or False, but not both. Hence the question, is a referential statement, such as "This sentence is false" can be regarded as a statement? BestBurakhan Aksoy
- "Every Cat loves its mother or father" October 5, 2024"Every Cat loves its mother or father" $\forall x ( \operatorname {Cat}(x) \land (\operatorname {Loves}(x,\operatorname{Mother}) \lor \operatorname {Loves}(x,\operatorname {Father}) )$ Although I know that a universal quantifier cannot be used with conjunction (not because of syntax error), I have issues understanding why the above translation is incorrect. I mean, it does sound correct: for every […]dikshank
- The logic subtlety behind solving differential equations. October 5, 2024Let me first explain what has led me to ask this question. When solving functional equations, it is often the case that through a link of implications (that is, uni-directional implications), we get several possible solutions for the functional equation. Then, we have to plug these functions into the original equation to see whether each […]The_Eureka
- Possible Error in Poizat's A Course in Model Theory (Chapter 7, Arithmetic) October 4, 2024I was reading Chapter 7 on Arithmetic in Bruno Poizat's A Course in Model Theory and noticed a potential error in Section 7.1 regarding the axioms defining the successor function. The axiom is given as: ($\forall x) (x \neq 0)$ This seems incorrect since it should express that 0 is not the successor of any […]Jackson Willoughby
Leave a Reply