7
votes
Relations that ensure continuity
This answer was simplified by a lot from the original one.
Consider a relation defined as follows: $x \sim y$ if $x > y$, or $y = x + 2^{m}$ for some $m\in\mathbb{Z}$.
The idea is that the first ...
- 93
6
votes
Accepted
Confusion about the consistency of $\mathsf{ZFC}+\neg\mathsf{Con}(\mathsf{ZFC})$
Yeah, you're mixing up the levels.
We formalize it as $$ \sf \lnot Con_{ZFC}\to \forall p\in Sentences_{LST}\; Prov_{ZFC}(p),$$ where $\sf Prov_{ZFC}$ is the same provability predicate that goes into $...
- 55.4k
5
votes
Accepted
Does $\omega$-consistency depend on the encoding?
This is a great question! In general, "reasonably strong" theories will always have distinguished implementations (the jargon is actually interpretations, but meh) of the natural numbers, ...
- 236k
4
votes
What does "because" mean, in the context of an answer to a mathematical problem?
A true story (just for fun).
Once upon a long time ago, the logician Geoffrey Hunter (the author of that excellent old book Metalogic) told me that he used to give a low-level logic course. Near the ...
- 53.1k
4
votes
Accepted
How to turn a $p \Rightarrow q$-type statement into a $\neg q \Rightarrow \neg p$-type one?
You have hidden quantifiers that aren't being accounted for. Let us take a closer look at "$\lim_{x\to\infty}f(x)\neq\infty$".
$$(\forall R>0)(\exists r>0)(|x|>r\implies|f(x)|>R)$...
4
votes
What are some sets uncountable in ZF but countable in ZFC?
As the comments have already pointed out, since ZFC includes ZF, there is no set for which ZF proves it's uncountable but ZFC proves it's countable.
But perhaps what you have in mind is this: there ...
- 8,487
6
votes
Is "non-rigid" first-order axiomatisable?
Let $L' = L\cup \{\sigma\}$, where $\sigma$ is a unary function symbol not in $L$. Let $T'$ be $T$ together with axioms asserting that $\sigma$ is a non-trivial-automorphism (non-triviality is $\...
- 72.3k
3
votes
Accepted
How to prove $\phi \models \psi$ iff $\phi \cup \{\neg \psi\}$?
I want to prove $\phi \models \psi$ iff $\phi \cup \{\neg \psi\}$ unsatisfiable.
What's the meaning of the union operator w.r.t. satisfiability in FOL?
We have to be careful with symbols. $a\models b$...
- 12.4k
3
votes
Axioms as PARTIAL information givers of primitive terms - Enderton's Elements of Set theory
The axioms specify properties we are assuming about the undefined terms, but it is not necessarily true that they allow us to answer any question we could ask about the undefined terms. If you start ...
- 32.7k
2
votes
Accepted
Are $\Sigma_1$-sentences which are true in any transitive model of $\sf ZFC$ necessarily theorems of $\sf ZFC$?
In fact, every arithmetical sentence $\varphi$ is $\Delta_1$ in the Levy hierarchy:
Some/every structure satisfying [basic properties of $(\omega;+,\times)$] satisfies $\varphi$.
The point is that &...
- 236k
2
votes
The definition of proposition and the principle of the excluded third
A better way to state the first definition is that a proposition is the sort of thing that is eligible to be judged true or false. That is, they are the sort of things $P$ about which it at least ...
- 3,360
2
votes
Accepted
The definition of proposition and the principle of the excluded third
A proposition is defined as a statement or assertion that can either be true or false.
Here's a more direct definition:
A proposition/sentence is a string of symbols that is well-formed according to ...
- 37.9k
2
votes
Accepted
Understanding indexed families of sets
First, the starting statement
every $x\in[0,1]=\{y\in R\;|\;x_{0}\neq 0\ \text{AND} \ x_{0}\leq y\leq 1 \}$
is questionable. Notice that $x\in[0,1]$ is $x\in\{y\in\mathbb{R}\;|\;0\leq y\leq 1 \}$ by ...
- 2,001
2
votes
Accepted
How to show that $p∨q, q∨r, p\to ¬r ⊢ q$?
Heavens! If I'd been setting this as a natural deduction exercise, I'd have expected to see this as the most obvious derivation:
$$
\begin{array}{llll}
1)&p\lor q&&\text{Premise}\\
2)&...
- 53.1k
2
votes
Logic: If $\frac{1}{x} > 0.5$, then $x$ can be any real number smaller than $2$?
The statement to (dis)prove is of the form: "If A , Then B."
Since in your case, statement A is equivalent to the result $0 < x < 2$, we can rewrite it as:
"If $\:0<x<2$, ...
- 33
2
votes
Accepted
Growth of Complete Binary Decision Trees
The answer is no. Since any formula equivalent to $\alpha_n$ must contain each of the $2^n$ distinct variables $p_1$, $\dots$, $p_{2^n}$, it must have length at least $2^n$.
- 16.2k
2
votes
There is some integer $n$ such that if $n > 2,$ then $n^2 = 2n.$
Expanding on Robert's observation:
This is the given sentence, which is true:
there is some integer $n$ such that if $n > 2,$ then $n^2 = 2n$
$\exists n{\in}\mathbb Z \:\big(n > 2\:\to\: n^2 = ...
- 37.9k
2
votes
Accepted
Confused about saying every "statement" is vacuously true in an inconsistent arithmetic (terminology)
I think this is just s function of how we talk about theorems in mathematics in general. That is, whenever we prove something in mathematics we regard that theorem to be ‘true’ … though you are right ...
- 97.3k
2
votes
Proving the sentence $X \lor Y {\implies}Z$
I want to prove that $$\color{brown}{(\neg b \lor \neg c) {\implies} \neg a}.$$
is there anything logically incorrect about using both $\neg b$ and $\neg c$ to show $\neg a$?
if $\color{brown}{(X \lor ...
- 37.9k
1
vote
Proving the sentence $X \lor Y {\implies}Z$
If you want to prove $(\neg b \lor \neg c) \to \neg a$, you could also try proving proving the equivalent $a \to (b \land c)$
(I wonder if maybe that's where the $(\neg b \lor \neg c) \to \neg a$ came ...
- 97.3k
2
votes
Is "non-rigid" first-order axiomatisable?
Yes, you can add a new unary function symbol $g$ and then write down a schema that says "$g$ is a nontrivial automorphism" and add that to the schema saying "$M$ is infinite" and ...
- 55.4k
1
vote
Is it OK if a proposition contains $\frac{1}{0}$?
Let's simplify the problem. Suppose we have at least $0\in X$ and $1\in X$, and $f$ such that:
$~~~~~~\forall a:[a\in X \land a\neq 0 \implies f(a)=1]$
This definition of function $f$ does not give us ...
- 14.1k
1
vote
Understanding implication
It seems you want to prove that $\neg A \to (A \to B)$. In words: If proposition $A$ is false, then it must be true that $A\to B$ for any logical proposition $B$, be it true or false.
It can be proven ...
- 14.1k
1
vote
Accepted
Why can we plug complex numbers into maclaurin series?
What is typically done is some variation of the following:
We define limits of complex functions similarly to their real counterparts but using the modulus in place of the absolute value - so $\lim_{...
- 21.2k
1
vote
Understanding implication
The statement if A, then B is always true when A is false.
Suppose that A is false. Then as ...
- 37.9k
1
vote
Finding the relationship (equivalence or implication) between two expressions
To check the conditional relationship between two sentences, making sense of them is usually faster than formal proof methods:
$$\exists X \; (p(X) ∧ q(X))$$
Some object is both pink and quirky.
$$\...
- 37.9k
1
vote
Accepted
Finding the relationship (equivalence or implication) between two expressions
The formula $\exists x Px \wedge \forall x Qx$ states "There exists at least one $x$ such that $x$ is $P$, and for every $x$, $x$ is $Q$."
The formula $\exists x [Px \wedge Qx]$ states "...
- 4,614
1
vote
Finding the relationship (equivalence or implication) between two expressions
The second implies the first. Suppose we have the second already. Then we can get in our context the following $x_0 \in X$ and $p(x_0)$ as well as $\forall x \; q(x)$. Combining the first and third ...
- 4,989
1
vote
Accepted
Tautological statements
Since no one seems to be mentioning it and since I'm actually having some trouble finding an English-language source for what I'm talking about, I'll describe here the method of reductio ad absurdum. ...
- 616
1
vote
How to show that $p∨q, q∨r, p\to ¬r ⊢ q$?
For the sake of variety, I offer a proof by contradiction.
$
\begin{array}{lllll}
\{ 1 \} & 1. & p ∨ q & \text{premise} & \\
\{ 2 \} & 2. & q ∨ r & \text{premise} & \\
\...
- 4,614
Only top scored, non community-wiki answers of a minimum length are eligible