Tag: Doodling
Handy Links
Logic on Math StackExchange
- Horn sentences and power structures August 8, 2024It is well-known that Horn sentences are "preserved" under products (see for instance Show that the direct product of structures satisfies a Horn sentence). I was wondering what happens with the converse. I.e. if a Horn sentence is true in the product is it true in the components? What if all components are equal (i.e. […]user1868607
- Examples of statements provable in PA whose corresponding propositional tautologies don't seem to admit short extended Frege proofs August 8, 2024Bounded arithmetic has been studied because if a statement provable using certain forms of bounded arithmetic is transformed into a family of propositional tautologies (which can be done if the statement is of a certain form), the proof can be transformed into a family of polynomially-long proofs in certain propositional proof systems. For example, as […]Duyal Yolcu
- The well-ordering number of second-order logic August 8, 2024The definitions and referred pages are from (Model-Theoretic Logics, Barwise 1985), primarily from chapter II. A free version is available here: Chapter II Definition (pinning down ordinals): Let < $\in$ $\tau$ and $\Phi$ $\subseteq$ $\mathscr L$[$\tau$] for $\mathscr L$[$\tau$] is the class of all $\mathscr L$-sentences of vocabulary $\tau$. We say that $\Phi$ 'pins down' […]SJe967
- For all integers a, b and c, if a | (bx + cy) for all integers x and y, then a | b and a | c August 7, 2024I encountered this question in an online textbook (page 51) I was using to self study. The proof given considered two cases: when x=0 and y=1, then the hypothesis gives a|($0\cdot b$ + $1\cdot c$) = a|c and when x=1 and y=0, a|($1\cdot b$ + $0\cdot c$) = a|b. At this point the book says […]WeWillConquer
- Phrasing an instruction involving the "for all" quantifier August 7, 2024I did a number theory course where the instructor sometimes phrased an exercise in a way that seems slightly wrong. For example, he wrote the exercise Check if the following statement is correct: for every positive integer $n$ we have that $q=p_1p_2\cdots p_n+1$ is prime where $p_n$ is the $n$th prime. as For every positive […]MSEU
- Suppes–Lemmon-Style $\Diamond$-Introduction and -Elimination Rules for Modal Logics? August 7, 2024I'm trying to find natural-deduction introduction and elimination rules for $\Diamond$ (possibility) in popular modal logics (e.g., K, T, S4, and S5) in the style of Suppes and Lemmon, where on each line of the proof you have a dependency set, a line number, a formula, and a citation, e.g., $\begin{array}{1111}&\{1\} &1. &P &\text{Premise}\\ &\{1\} […]Spailpín
- How many satisfiable assignments does the following compound statement have? August 7, 2024I want to count satisfiable assignments to the following compound proposition: $((p→q)∧(¬q∨r)∧(¬s→¬r))→(¬p∨s)$ Is there any particular formula to calculate this? For small compound proposition we can do it manually, but the given compound proposition is huge. Any hint or suggestion would be of great help.monalisa
- Is there a structure or abstraction that genuinely generalizes both field extensions and (Cohen) forcing? August 7, 2024I'm just starting with the topic so I don't know much. But I'm always told that the similarity with field extensions is just an analogy and we shouldn't take it so seriously. However, I just must ask if this is so.Julián
- Composition of Boolean Functions in CNF August 7, 2024Suppose that I have some $n$ variable Boolean function that is in CNF and has $m$ clauses $$ f(x_1,x_2,\ldots,x_n) = (x_1\lor x_2)\land(\lnot x_1\lor x_6 \lor x_7\lor x_3)\land\ldots $$ Now suppose that each $x_j$ itself is now to be replaced by another boolean expression, itself in CNF. For example suppose that $x_1=A\land B$, we would now […]wjmccann
- Why ‘if not the citizen is ≥ 35’ ≡ ‘if the citizen is not ≥ 35’? [closed] August 6, 2024Baronett, Stan. Logic (5th ed, 2022). For brevity, let "president" be POTUS. In order to translate the statement “A citizen cannot be president unless the citizenis at least 35 years old,” we need to understand how the word “unless” gets translated. In most statements, the word “unless” means if not. Substituting […]user16249
Recent Comments