New answers tagged logic
1
What you are looking for is replacing a function symbol $f$ with the corresponding graph, which is the relation $R_f$ characterized by $R_f(x,y) \iff f(x) = y$.
So we can replace $f(x) = y$ with $R(x,y)$ if $x$ and $y$ are variables. But what do we do about $f(t)$ where $t$ might contain futher occurrences of $f$? That's the tricky bit.
The idea is to use ...
0
Should we just believe that there are uncountably many problems even
if we would never want to solve uncountably many of them?
Yep. Thats the thing, we want to talk about all possible problems - why would we want to restrict ourselves to theoretically analyzing only a small portion of problems? So essentially what you are saying (and I totally agree with ...
1
According to Wikipedia,
A powerful and nontrivial metatheorem states that any theorem of 𝟐 holds for all Boolean algebras. Conversely, an identity that holds for an arbitrary nontrivial Boolean algebra also holds in 𝟐. Hence all the mathematical content of Boolean algebra is captured by 𝟐.
What this means is that if $\phi = \psi$ is an equation in ...
4
Let $\land_p$ be a gate with error $p$ only when the inputs are $1$ and $0$. What can we say about
$$
(x \land_p y) \land_p (x \land_p y)?
$$
If $x=y=1$ then we always get $1$. If $x = 0$ then we always get $0$. When $x = 1$ and $y = 0$, we get the wrong answer $1$ with probability
$$
p \cdot p + p \cdot (1-p) \cdot p = p^2(2-p).
$$
Call that function $f(p)$....
2
Finite graphs don't compute pi; circuits do.
No single circuit computes pi. Rather, when we say that pi is computable, this means that there exists an infinite family of circuits $C_1,C_2,\dots$ such that $C_i$ outputs the first $i$ digits of pi.
A standard measure of complexity for a circuit is its size: specifically, let $f(i)$ denote the size of $C_i$, ...
1
Just learned about Bunched Logic which seems to fit the bill too.
0
To reason safely about provability, you need to fix some kind of formal proof system. It usually won't matter at all what system you pick (barring some basic sanity checks), but it is important that "proving" should mean the same thing everywhere in your argument.
Here, "proof" in the last paragraph suddenly jumps from referring to ...
4
I feel like there is a kind of circularity in the last part of your argument (and I think the conclusion is wrong, there are undecidable problems which we cannot prove to be undecidable).
You are basically making a case distinction:
if $\alpha$ can be proved or $\neg \alpha$ can be proved: Then $P(\alpha)$ can be proved and thus $P(P(\alpha))$ is true. (I ...
Top 50 recent answers are included
