Intereting Posts

If $X$ is linearly independent, then $T(X)$ is also linearly independent?
Simplify : $( \sqrt 5 + \sqrt6 + \sqrt7)(− \sqrt5 + \sqrt6 + \sqrt7)(\sqrt5 − \sqrt6 + \sqrt7)(\sqrt5 + \sqrt6 − \sqrt7) $
An exercise in infinite combinatorics from Burris and Sankappanavar
How to show an infinite number of algebraic numbers $\alpha$ and $\beta$ for $_2F_1\left(\frac13,\frac13;\frac56;-\alpha\right)=\beta\,$?
Fixed points of contractions in metric spaces
Is the non-existence of a general quintic formula related to the impossibility of constructing the geometric median for five points?
Uniform convergence of real part of holomorphic functions on compact sets
Rigorous book on bootstrapping, boosting, bagging, etc.
Why are projective spaces over a ring of different dimensions non-isomorphic?
the nonexistence of a division algebra on $\mathbb R^{2n+1}$
How to solve this question related to Definite Integration
First-order logic and second-order logic confusion
Divisibility question for non UFD rings
Bochner Integral vs. Riemann Integral
Krull dimension of $A/\langle x^2 + 1 \rangle$

How do we decide whether the formula in predicate logic is a tautology? Is there some universal way to decide?

Let’s have an example:

```
Vx(P(x)&Q(x))<->VxP(x)&VxQ(x)
```

My solution (not correct and not complete)

- Logic behind continuity definition.
- “If P, then Q; If P, then R; Therefore: If Q, then R.” Fallacy and Transitivity
- Łoś's Theorem holds for positive sentences at reduced products in general?
- If the union of two sets is contained in the intersection, then one is contained in the other ($\implies A \subseteq B$)
- Learning how to prove that a function can't proved total?
- Ultrafinitism and the denial of existence of $\lfloor e^{e^{e^{79}}} \rfloor$

So the first thing I do is to rename some variables on the right side.

```
Vx(P(x)&Q(x))<->VxP(x)&VyQ(y)
```

No, I can do this:

```
Vx(P(x)&Q(x))<->Vx(P(x)&VyQ(y))
```

And this:

```
Vx(P(x)&Q(x))<->VyVx(P(x)&Q(y))
```

So my question is:

How can I decide and proove, whether it is a tautology?

- Can I construct a complete (as a Boolean algebra) saturated elementary extension of a given Boolean algbera?
- When is de-Skolemizing statements appropriate?
- What is the justsification for this restriction on UG?
- Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?
- Why is the universal quantifier $\forall x \in A : P(x)$ defined as $\forall x (x \in A \implies P(x))$ using an implication?
- difference between some terminologies in logics
- Deduction Theorem + Modus Ponens + What = Implicational Propositional Calculus?
- What is the name of the logical puzzle, where one always lies and another always tells the truth?
- Discrete math logic question
- FO-definability of the integers in (Q, +, <)

I quote from Wikipedia:

A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable).

In propositional logic a tautology is a formula which evaluates to be true for every possible substitution of truth values of its variables.

In the example

$$\forall \,x \,(P(x) \land Q(x))\iff \forall \,x \,P(x) \land \forall \,x\,Q(x)\tag 1$$

we have the following different first order formulas:

- $\forall \,x \,(P(x) \land Q(x))$
- $\forall \,x \,P(x)$
- $\forall \,x\,Q(x)$

These will be replaced by $A,B$, and $C$, respectively. We get

$$A \iff B\land C$$

which is **not** a tautology; its truth value depends on the truth values of the variables.

$(1)$ would be a tautology of first order logic if we could create it by the reverse substitution from a tautology of propositional logic.

For another example take the propositional tautology

$$A\land B \Rightarrow A\lor B$$

and let’s do the following substitutions:

- $A$ : $\forall \,x \,(\exists \,y \,Q(x,y))$
- $B$ : $\exists \,y \,P(y)$.

Now, we have

$$\forall\, x \,(\exists \,y \,Q(x,y))\, \land \,\exists \,y \,P(y) \Rightarrow \,\forall \,x \,(\exists \,y \,Q(x,y)) \lor \exists \,y \,P(y)$$

which is a tautology of the first order logic because it could be obtained by a substitution of first order expressions into a propositional tautology.

To tell whether the formula is true in every interpretation, the first step is to think through what each side of the formula says about an interpretation. The left side

$$

(\forall x)[P(x) \land Q(x)]

$$

says that $P$ and $Q$ hold of every object $x$ in the interpretation. The right side

$$

(\forall x)[P(x)] \land (\forall x)[Q(x)]

$$

says that $P$ holds for every object $x$ in the interpretation, and so does $Q$. Since the right and left sides both say that $P$ and $Q$ hold of all objects, the right and left sides will be equivalent in every interpretation.

Here is an example that is not valid in every interpretation:

$$

(\forall x)[P(x) \lor Q(x)] \Leftrightarrow (\forall x)[P(x)] \lor (\forall x)[Q(x)]

$$

The left side says that, for each object $x$, at least one of $P$ or $Q$ holds. The right side says that either $P$ holds of every object, or else $Q$ does. That is clearly not the same thing! And it naturally suggests an interpretation: let the objects be natural numbers, let $P(x)$ say “$x$ is even”, and let $Q(x)$ say “$x$ is odd”. Then the left side of the compound formula above holds in this interpretation, but the right side does not. You should treat falling back on formal proofs to verify a formula as a kind of last resort when more intuitive methods fail.

This method (think through what the formula means) is much faster than blindly trying to use inference rules to deduce a formula.

- Four fractions of certain factorials give another factorial
- Calculating a Lebesgue integral involving the Cantor Function
- relation between integral and summation
- Fixed point iteration convergence of $\sin(x)$ in Java
- Can any function of the second moment of a random variable be recovered from its quantile function?
- How do I explain the Fundamental Theorem of Calculus to my teacher?
- Existence of the absolute value of the limit implies that either $f \ $ or $\bar{f} \ $ is complex-differentiable
- Cokernel of a Composition.
- How to prove if log is rational/irrational
- $A\otimes_{\mathbb C}B$ is finitely generated as a $\mathbb C$-algebra. Does this imply that $A$ and $B$ are finitely generated?
- What is the Pontryagin dual of the rationals?
- Number of ways to join the points
- Calculating fundamental group of the Klein bottle
- How can I show that $y'=\sqrt{|y|}$ has infinitely many solutions?
- Equicontinuity if the sequence of derivatives is uniformly bounded.