Tag: perfect circle
Logic on Math StackExchange
- 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
- Reversing the order of implication. October 8, 2024Let $X \neq \varnothing$ be a set. Suppose we have the statement: If there exists a subset $Y \subsetneq X$ such that property $P$ holds, then there exists a $x \not \in Y$ such that property $Q$ holds. What would be the contrapositive here. My initial guess is: If for all $x \not\in Y$, $\neg […]A.Z
- Is ZFC-FA+$\{x:x\in x\}$ consistent? (relative to ZFC) October 8, 2024Let ZFC-FA be ZFC without the Axiom of Foundation (Regularity). It is well-known that asserting the existence of the Russell's set, $\{x:x\notin x\}$, makes the theory trivial. The same is true of, e.g., asserting the existence of the universal set, $\{x:x=x\}$, when combined with restricted comprehension. My question is the following: Is the theory ZFC-FA+$\exists […]Timotej Šujan
- Why is $\exists y \ \forall x \ \forall z \ :y + z^2 \geq x$ false in $\mathbb{Z}$? October 8, 2024Let $P$ be the predicate $P(x, y, z) = y + z^2 \geq x, \quad x, y, z \in \mathbb{Z}.$ The professor grading my exam said that this statement is false: $\exists y \ \forall x \ \forall z \ :P(x, y, z)$ But I think that the statement is true, because you can choose […]willaayy
- Do different variables imply different elements? ($\exists^{< n}$ quantifier) [closed] October 8, 2024I was asked to define the quantifier $\exists^{< n}$. My idea was the following: $$ \exists^{user123456
- Is my proof that "everything exists" correct? [closed] October 7, 2024Let $E(x)$ mean that $x$ exists. Then the proposition $∀x(E(x))$ means "everything exists." Its negation is $∃x(¬E(x)),$ and means "something that doesn't exist exists." This is a contradiction, and thus false. Therefore, the original proposition "everything exists" is true. Is the above argument valid?Display name
- Does it make sense to define a set using a property that is not defined for all the possible values of its argument? October 7, 2024This is a merely formal question. I'll explain with an example: say I want to denote the set of all the real numbers which have a reciprocal greater than $1$. I would write it like this: $$S = \left\{x\in\Bbb R:\frac1x>1\right\}$$ The problem is, the statement $$\frac1x>1$$ doesn't make sense when $x=0$, since $1/0$ doesn't have […]Elvis
- Can we neatly describe all fast growing functions in countable many increasing sets? October 6, 2024Given a function from naturals to reals, can I pick countable many functions $$f_1,f_2,f_3, \ldots$$ Such that $$O(f_1) \subseteq O(f_2) \subseteq O(f_3)\subseteq\ldots$$ and every function is in $O(f_n)$ for some $n$? If not countable, what is the smallest cardinal in which we can? I initially thought we cannot, but then I figured why not define […]Scezory
- Simple true $\Pi^0_1$ statements unprovable in weak arithmetics October 6, 2024There is an explicitly known 745-state Turing machine where, assuming $\mathrm{ZFC}$ is consistent, the machine never halts, but $\mathrm{ZFC}$ cannot prove this fact. (This is shown in Riebel's thesis The Undecidability of $\mathrm{BB}(748)$. I am wondering if there is a much smaller machine whose halting is unprovable in some much weaker system, like $\mathrm{EFA}$ (exponential […]C7X
Recent Comments