Written work, due Tuesday, December 3rd, in class:
Chapter 10 p167: 1, 2, 5, 10, 15
WeBWorK – none
OpenLab – none
Project – Final Draft of paper due in class on Thursday, 12/5.
Group Presentations on Thursday, 12/5.
Logic on Math StackExchange
- A property of $\lt$ in Primitive recursive arithmetic July 11, 2024In Primitive recursive arithmetic (PRA), we can introduce $\lt$ by introducing its representing function $K_{\lt}$, where $K_{\lt}(x,y) =sg(x+1-y)$. Here "sg" and "-" are the functions defined by $sg(0)=0\land sg(x+1)=1$, $pred(0)=0\land pred(x+1)=x$ and $a-0=a\land a-(b+1)=pred(a-b)$. In this situation, I want to prove in PRA that if $K_{\lt}(x,y+1)=0$, then $K_{\lt}(x,y)=0\lor x=y$. If $K_{\lt}(x,y+1)=0$, then $sg( (x+1)-(y+1))=sg(pred(x+1-y))=0$. Note […]nilpotent
- First-Order Logic With Extensional Set Membership July 11, 2024It is common to sometimes present First-Order Logic with equality and sometimes without. Adding equality has some nice benefits, including the ability to talk about some number of things, e.g. $\exists x \forall y (A(y) \leftrightarrow y=x)$ is enough to capture “exactly one thing is $A$.” Given that, is there any use to going a […]PW_246
- Paradox in Prisoner's dilemma July 11, 2024I have come across a curious paradox concerning The Prisoner's Dilemma Suppose 4 things : prisoners A and B are rather stupid people and decide to use an artificial intelligence program to decide through a logical proof whether it is better to cooperate or defect. the AI program is deterministic both prisoners use the same […]Arnaud
- in definition of assigment, what's means 'except possibly a'? July 11, 2024in frist-order logic, part of assignments practice represent like this "if 𝜙is ∀𝛼𝜓, where 𝛼 is a variable, then ⊨vℳ 𝜙 iff for every assignment 𝑣' that agrees with 𝑣 on the values of every variable except possibly 𝛼, ⊨v'ℳ'𝜓 " here I don't understand except possibly 𝛼, because I understand 'for all x...' means […]유준상
- Prove: Let α be a proposition containing only Boolean connectives ∧,∨. Then any assignment satisfying α must also satisfy f(α) July 10, 2024The question: Let f be a mapping that takes as input a Boolean proposition (no quantifiers) and outputs the same proposition but with all ∧ symbols replaced by ∨. For example: $$ f(x_1 ∧ (x_2 → ¬x_5) = (x_1 ∨ (x_2 → ¬x_5) $$ Prove: Let α be a proposition containing only Boolean connectives ∧,∨. […]User33975329257439645
- Is this restricted variant of predicate logic decidable, but expressive enough to be encoded by STLC ($\lambda \to$)? July 10, 2024As in the question, is it the case that a predicate calculus with these properties is decidable? n-ary predicates quantifiers finite domain of discourse impredicativity disallowed no function terms If so, is it possible to encode the semantics of this logic in Simply Typed Lambda Calculus ($\lambda\to$)?Vivek Joshy
- If a contrapositive can be shown, then is a direct proof always possible? July 10, 2024If we can prove that $¬Y \implies ¬X,$ then is it always possible to prove that $X \implies Y$ without first proving that $¬Y \implies ¬X$ ? Motivation: when studying analysis, there are some problems/theorems where we must prove $X\implies Y$ and then I try to prove it directly, spend hours stuck without being able […]Red Banana
- Marked numbers on a circle [closed] July 9, 2024On a circle, write all the numbers in ascending order from $1$ to $1000$, clockwise. Starting from $1$, colour in all the numbers in a clockwise direction $k$-th number ($1$, $k + 1$, $2k + 1$, ...). The procedure continues until a number is reached which is already is already coloured. At the end of […]Pálfi Kincső
- Proving "if Q is derivable from P, then all sentential interpretations of P->Q are true" from Suppes criterion I July 9, 2024Question. I have trouble understanding how Patrick Suppes in his "Introduction to logic" derives the important sentence (A2) from another two, (A1) and (CrI). Introduction. He uses criterion I: (Cr1): "Given a set of premises, the rules of logical derivation must permit to infer ONLY those conclusions which logically follow from the premises." He also […]Alex Alex
- Incompleteness Proof Theory and Hypercomputation July 9, 2024Has anyone systematically studied how powerful hypercomputation can overcome "incompleteness proof theory"? For example: A deductive system for second-order logic in standard semantics with soundness and completeness, How powerful hypercomputation can correctly decide whether a given sequence of symbols is a proof or not? A deductive system for Infinitary logic with soundness and Barwise completeness, […]Ember Edison
Leave a Reply