Written work, Due Tuesday, October 23, in class:
Chapter 4 p.100: 4, 5, 10, 11
Chapter 5 p.110: 1, 4, 9
Odd problems are worth 4 points, even problems worth 8 points.
WeBWorK – none
OpenLab – none
Tag: class work
Logic on Math StackExchange
- notation for quantifiers (brackets, commas, colons, etc) November 22, 2024The following are variations in expressing "there exists a natural number $n$, such that $2T = n \cdot (n+1)$": $\exists n\in \mathbb {N},\; 2T = n \cdot (n+1)$ $\exists n\in \mathbb {N}\; [2T = n \cdot (n+1)]$ $\exists n\in \mathbb {N}\; {2T = n \cdot (n+1)}$ $(\exists n\in \mathbb {N})\; 2T = n \cdot (n+1)$ […]Penelope
- L is undecidable iff there is a word w such that $w \in L$ is unprovable [duplicate] November 22, 2024$L$ is undecidable iff there is a word $w$ auch that the proposition $w \in L$ is not provable(hope I am using the right terminology, feel free to correct me). It feels intuitive and its something I thought about and I wonder if its right, unfortunatly I dont know enough logic theory to answer it. […]RT1
- Can the set of integers be constructed starting from Peano's Axioms without powersets? November 21, 2024I was able to formally construct the set of integers starting from Peano's Axioms using a powerset axiom among other ZF-like axioms (31 lines available here on request). Informally, I have: $\pm 0 = \{(0,~ 0),~ (1,~ 1),~ (2, 2), \cdots \}$ $+1 = \{(1,~ 0),~ (2,~ 1),~ (3, 2), \cdots \}$ $-1 = \{(0,~ […]Dan Christensen
- On the correct $(\forall)$-introduction rule in Natural Deduction November 21, 2024In a nutshell: is the following the $(\forall)$-introduction rule in Natural Deduction? $$\frac{\phi[t/x]}{\forall x\phi}\ \ \ \ \ \ \ \ \ \begin{matrix}\text{provided the term $t$ does not occur in $\phi$}\\ \text{nor in any undischarged assumption in the proof of $\phi[t/x]$}\end{matrix} $$ I began learning about natural deduction from these notes where the $(\forall)$-introduction rule […]Sam
- Proving $\vdash \phi(x,y,\ldots,z)$ if and only if $\vdash\forall x\forall y\cdots\forall z\phi(x,y,\ldots,z)$ using Natural Deduction November 21, 2024I suspect the following holds: $$\vdash \phi(x,y,\ldots,z)\iff \vdash\forall x\forall y\cdots\forall z\phi(x,y,\ldots,z)$$ where $\phi$ is a formula with free variables $x,y,\ldots, z$. Here is my argument using Natural Deduction : $(\Rightarrow):$ $\vdash\phi(x,y,\ldots,z)$ means $\vdash\phi(x',y',\ldots,z')$ for new variables $x',y',\ldots,z'$. Now we may use $\forall$-introduction: $$\frac{\dfrac{\phi(x',y',\ldots,z')}{\forall x\phi(x,y',\ldots,z')}}{\dfrac{\vdots}{\forall x\forall y\cdots\forall z \phi(x,y,\ldots,z)}}$$ $(\Leftarrow):$ using $\forall$-elimination repeatedly: $$\frac{\dfrac{\forall x\forall y\cdots\forall […]Sam
- Is it actually possible to prove difficult propositional theorems without using inference? [closed] November 20, 2024For the theorem $(\phi\to\psi) \to \bigl((\phi\to\xi) \to (\phi\to\psi\land\xi)\bigr),$ I can fairly easily derive any proof using Deduction Theorem, but our professor says that we are allowed to use only the Hilbert/Frege axioms and modus ponens, but not assumptions, conditions, inferences, truth tables or substitutions. Is it actually possible to prove difficult propositional theorems without using […]Whatevur m8
- Why are the ZFC -axioms written like that? [closed] November 20, 2024Question 1: Why is the Axiom of Extensionability written as: $$\forall x \forall y(\forall z(z\in x \iff z\in y) \rightarrow x=y)$$ Doesn't this read: for all $x$ and $y$, $x = y$ if for all $z$, $z$ is a member of $x$ if and only if $z$ is a member of $y$? Isn't this $$\forall […]DefinitelyNotADolphin
- Complete a natural deduction in FOL for this statement: ∃y∀xA(x,y) ⊢ ∀x∃yA(x,y) [closed] November 20, 2024I need help solving this FOL proof. I believe it needs to use change of quantifier rules, but I am having a lot of trouble.Paloma Bushofsky
- Help proving the $(\forall)$-introduction rule written in terms of $\exists$ in natural deduction November 20, 2024I'm trying to prove the $(\forall)$-introduction rule in Natural Deduction (written in terms of $\exists$): $$\frac{\phi [t/x]}{\neg\exists x\neg\phi} \ \ \ \ \begin{matrix}\text{ given that $t$ does not appear in $\phi$ nor in any}\\ \text{ undischarged assumption in the proof of $\phi[t/x]$}\end{matrix}$$ I believe the proof should go something like so: $1.\ \phi[t/x]$ $2.\ \exists […]Sam
- Proof of Deduction Theorem in Hilbert‘s system/calculus November 20, 2024Deduction Theorem: Let $\Sigma$ be an axiom system and $\psi, \varphi$ $L$-formulas. Then the following always holds: $\Sigma, \psi \vdash \varphi \iff \Sigma \vdash \psi \rightarrow \varphi$. “$\Rightarrow$” We prove this direction using mathematical induction on the length of a proof, $n \geq 1$ ($n \in \mathbb{N}$, which justifies the use of math. induction). Base […]Pippen
Recent Comments