Tag: .999
Logic on Math StackExchange
- 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) 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? 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
- If $\models \phi \lor \psi$ then not always $\models \phi$ or $\models \psi$ [duplicate] October 6, 2024Task is to give an example in propositional logic which shows that if $\models \phi \lor \psi$ then not always $\models \phi$ or $\models \psi$. How can I write it? Any help would be much appreciated. EDIT: So if $\models p \lor \neg p$, then it always holds for any evaluation, but $\models p$ does […]Mateusz Struk
- For each of the following sets, determine whether 2 is an element of that set: {{2},{{2}}} [closed] October 5, 2024{{2},{{{2}}} I think that 2 belongs to {2} (because has the element 2). But 2 has no elements in {{2}} (because the only element that explicitly possesses is {2}, no the element 2 itself). Am I right?PEREZ MONSIVAIS JOSE DE JESUS
- Universal quantifier over disjunction in intuitionistic logic October 5, 2024I have a question about the following sequent, valid in classical logic: $$\forall x [\phi(x) \vee \psi] \vdash \forall x [\phi(x)] \vee \psi$$ Importantly, we assume $\psi$ does not contain any free $x$. Is this sequent valid also in intuitionistic logic? The converse sequent is not hard to prove, but with this direction I am […]Tony Dolezal
Recent Comments