Tag: OpenLab7
Logic on Math StackExchange
- Prove: Neighbourhood of Spanning Tree is exact October 12, 2024In my lecture the neighbourhood of a spanning tree f is defined as: N(f) = {g element of F | g can be obtained from f as follows: Add an edge to the tree f, producing a cycle, then delete any edge from the cycle}. Where F is the set of feasible solutions. In the […]Franka
- $∀xP(x)∧Z(x) \equiv ∀x(P(x)∧Z(x))\,?$ [closed] October 11, 2024Without more parentheses, I don't know the scope of the universal quantifier in $$∀x P(x)∧Z(x).$$ Does it apply to both $P$ and $Z:$ $∀x(P(x)∧Z(x))$ ?Bob School
- Trying to proof two XOR instances [closed] October 11, 2024I have proof (truth table) that both instances of XOR are correct. Which means both instances have to be equal to each other. Yet, I am missing the insight to get from one to the other. My (math) background is rather modest but I would be pleased if someone could help me apply the laws […]fabio-dc
- How to logically formalize two-player with imperfect information? October 11, 2024It is known that any first-order formula with no free variables is equivalent to a perfect information game with finitely-many turns, that is, for example, the formula $\forall x, \exists y, x\neq y$ describes the game « Alice plays $x$ first, and then, Bob, knowing that Alice played $x$, plays $y$, and then the referee […]Plop
- A question about tautologies in zero order logic [closed] October 10, 2024Assume τ be a well formed formula that has the property that (A → τ ) is a tautology for every sentense symbol A. Prove that τ is a tautology.Rohit Mutyala
- Is the class of all Hamiltonian graphs axiomatizable in second-order logic? October 10, 2024Is the class of all Hamiltonian graphs axiomatizable in second-order logic? Definitions: Hamiltonian graph is a graph s.t. there exists a cycle that goes exactly once through all vertices a class is axiomatizable in second-order logic if there is a set of second-order sentences $T$ s.t. (using standard semantics) $G\models T \iff G\text{ "is Hamiltonian"}$ […]Timotej Šujan
- 1-fragments of the Naive Set Theory with independent self-membership of the main set October 9, 2024I'm doing some research in non-trivial fragments of Naive Set Theory ($\mathsf{NST}$). By fragment of $\mathsf{NST}$ I mean that some instances of unrestricted comprehension (UC) are left out. UC is for me the following schema: $\exists y\forall x(x\in y \leftrightarrow \varphi(x))$ s.t. $y$ is not free in $\varphi$. The base fragment $\forall\mathsf{CL{+}ext}$ is then just […]Timotej Šujan
- Is there an effective procedure to find a Gödel sentence? [duplicate] October 8, 2024Let $\def\N{\mathcal{N}}$ $\N$ be some (powerful enough) theory of arithmetic. Is there an effective procedure to find a Gödel sentence $A$ in $\N$? That is, a sentence for which $$\vdash A \iff \neg P(A).$$ To be clear, this means building a computer program that runs through all sentences in $\N$, expressed as finite strings of […]Sam
- Solving $P \implies Q, \neg R \implies \neg S, \neg Q \lor S $ [closed] October 8, 2024Steps for solving \begin{align} P \implies Q \\ \neg R \implies \neg S \\ \neg Q \ \lor \ S \end{align} The teacher said $\therefore \neg P \ \land \ R $, however I got $\therefore \neg P \ \lor \ R $ If my notation is confusing or wrong, here's the statement in English: […]ConfusedButterfly
- "If there exists $Y {\subsetneq} X$ such that $P$ holds, then there exists $x {\not\in} Y$ such that $Q$ holds" October 8, 2024Let $X$ be a nonempty set. If there exists a subset $Y \subsetneq X$ such that property $P$ holds, then there exists an $x \not \in Y$ such that property $Q$ holds. I'm trying to determine the contrapositive of the above conditional statement. My initial guess: If for every $x \not\in Y$, $\neg Q$ holds, […]A.Z
Recent Comments