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
Tag: week 8
Logic on Math StackExchange
- $(\tau \setminus \{\emptyset\}, \subseteq^{*})$ is not separative February 14, 2026Let $(X,\tau)$ be a topological space. We write $A \subseteq^{*} B$ if $A \cap B$ is dense in $A$ (equivalently if $Reg(A) \subseteq Reg(B)$, where $Reg(..) := Int(Cl(..))$). It is straightforward seeing that $(\tau \setminus \{\emptyset\}, \subseteq^{*})$ defines a qoset (quasi ordered set). Given a qoset $(Q,\leq)$ we say that it is separative if for […]user1570557
- Writing a result in logic February 13, 2026I would like to see if I am translating correctly from natural language into logic with symbols. Let's say I have the following result: Let $m,n\in\mathbb{N}$, $A\in\mathbb{Q}^{m\times n}$, $b\in\mathbb{Q}^m$ with $b\neq\mathbf{0}_m$ be such that $Ax=b$ has a binary solution in $x$. Then there exists a function $f_{A,b}$ from $\{0,1\}^n$ onto itself such that the least […]Marc Dinh
- Showing the induced order on a Hilbert algebra is transitive February 13, 2026A H-algebra is an algebra $(A, \rightarrow, 1)$ of type $(2,0)$ such that the following axioms are fulfilled for every $\alpha, \beta, \gamma \in A$ : $$ \begin{aligned} & \left(a_1\right) \alpha \rightarrow(\beta \rightarrow \alpha)=1 ; \\ & \left(a_2\right)(\alpha \rightarrow(\beta \rightarrow \gamma)) \rightarrow((\alpha \rightarrow \beta) \rightarrow(\alpha \rightarrow \gamma))=1 ; \\ & \left(a_3\right) \text { If } […]NiceJJ
- Is there a consistent set of axioms sufficient to analyze basic algorithms (such as merge sort)? February 12, 2026I will focus on merge sort to make the question specific and answerable, but the spirit of my question is to allow replacing merge sort with any basic algorithm (an ill-defined term, hence the focus on merge sort). Is there a set of axioms, known to be consistent, where we can prove that: Merge sort […]Sebastian
- Are two continuum-sized structures that are "the same at all sub-continuum levels" necessarily isomorphic? (Counterexample in ZFC) February 9, 2026Now cross-posted to MO. This is a follow up to my previous question: Let $\mathcal{L}$ be a countable language and $M, N$ be two structures over $\mathcal{L}$. Suppose $|M| = |N| = 2^{\aleph_0}$ and they furthermore satisfy the following condition: For each $m \in M$ there is a countable subset $N_m \subseteq N$ and for […]David Gao
- Is any proof of $P(x)$ for incomputable number $x$ valid also for some other values of $x$? February 8, 2026Let $a$ be a non-computable real number. Suppose there is some property $P(x)$ for which $P(a)$ is provably true (within some consistent axiomatic system, say ZFC). Does that mean that this proof is valid not only for $a$, but for some strictly larger set of numbers? The intuition behind this question is that since $a$ […]kvardekkvar
- My problem with Russel paradox [closed] February 8, 2026My intuitive approach. Problem is how are defined elements of the set and question is which set. Because there is Use–mention distinction Set A and set "A". And if you ask about question membership of an element in a set in the sense of metalogic.which set A or "A" In a sense Russell's paradox is […]someone
- I can't figure out how to directly prove cut-elimination for Herbrand style proof system February 7, 2026I should clarify the proof system I am talking about. In this system we prove things in the following way: given a set $\{\Gamma_1,\Gamma_2,...\}$ of closed statements in first order logic, $\Gamma$ is implied by these statements if the following holds: "Let $\{P_1,P_2,...\}$ be predicates appearing in any of the $\{\Gamma_1,\Gamma_2,...\}$ or in $\Gamma$, let […]Pineapple Fish
- Translate "Some fragile items are transparent only if they are glass" February 6, 2026What is the predicate expression for statement : "Some fragile items are transparent only if they are glass." Let: $Fx = x$ is fragile item $Tx = x$ is transparent item $Gx = x$ is glass item Does this mean $(Fx\wedge(Tx\rightarrow Gx))$ or $(Fx\wedge Tx\rightarrow Gx)$ and why? Is it because transparent is in the […]user14271528
- How to construct this Kripke–Platek set theory with urelements (KPU) model that has nonstandard natural numbers February 5, 2026Suppose that I have a model $\mathfrak{A}$ that satisfies a set of first-order axioms (i.e. KPU Axioms). KPU is stronger than PA. I read from Admissible Sets and Structures: An Approach to Definability Theory by Jon Barwise that by ordinary compactness, there exists an elementary extension $\mathfrak{N}$ of $\mathfrak{A}$ that contains non-standard natural numbers. But […]Link L
Recent Comments