FOL equivalence, operations and usage of quantifiers

Question

I'll start by saying that I searched for a discussion about this topic but I couldn't find the exact answers I'm looking for, so if you have a link to a previous discussion with the relevant answers I'll be much obliged.

I'm a student and I'm taking an intro course about mathematical logic (among other topics such as set theory and group theory). Recently we started studying FOL and I'm having a bit of trouble understanding how to properly use and write WFFs. The part I'm struggling with is how much difference is there between FOL and propositional logic when it comes to the behaviour of variables, quantifiers and logical operations. Mainly:

1. How much freedom do we have with the placement of quantifiers (while keeping them in proper order) in a given formula, and also how does this affect the logical operations we use. For example, are the following formulas equivalnet? $$\exists x \forall y \bigr(\lnot P(x) \lor Q(y) \bigr) \equiv \exists x \forall y \bigr(P(x) \to Q(y)\bigr) \equiv \exists x \biggr(P(x) \to \Bigr(\forall y\bigr(Q(y)\bigr)\Bigr)\biggr) \equiv \biggr( \exists x \Bigr(P(x)\Bigr) \to \forall y\Bigr(Q(y)\Bigr)\biggr) $$

2. This is sort of a follow up to the previous question. How do I properly "translate" from english to FOL when describing specific definitions or sentences. Let's take the definition of a limit for example: Let $f: \mathbb{R} \to \mathbb{R}$ be a function and let $L \in \mathbb{R}$ be a real number. We say that $lim_{x\to\infty}f(x) = L$, if for every $\epsilon >0 $ there exists an $M >0$ s.t. for every $x>M$ it holds that: $|f(x) - L| < \epsilon$. Honestly, I'm not sure I could write this down properly as a WFF. Is there a relation between the placment of quantifiers and variables to their dependency on other variables? (in this example, x is dependent on M which is dependent on epsilon)

Techincally there are still a few things I'm not 100% sure about, but first I want to clear this because I feel like until I wrap my head around this I shouldn't move on to bigger questions.

Thanks in advance to all who share their wisdom and time!

Answer 1

For (1), the answer is yes (partially).
Since $(p \to q) \iff (\lnot p \lor q)$. En fact, this is true for any formula that if $\alpha$ was a sub-formula of a formula $\phi$, then obtaining a formula $\psi$ incurs if we replace one or more instances of $\alpha$ by some $\beta$; it follows that: $$(\alpha \iff \beta) ~ ~ ~ \iff ~ ~ ~ (\phi \, \iff \, \psi)$$ This is the called the substitution theorem. Here, us saying: $\exists x \; \forall y \; (\lnot \phi(x) \; \lor \; \psi(y)) \; \iff \; \exists x \; \forall y \; (\phi(x) \to \psi(y))$ is permissible.
"As for the third formula, this is wrong. Unless you say that: $\forall y \; \phi(y) \to \psi(x)$ when $\psi(y{\setminus}x)$ with $\lnot(x \in \text{free}(\psi))$, then that won't be true, and also no need for the quantifier anymore if it is not free. The same thing goes for the last formula too. (Thus, only the first one is logically equivalent.)", the last paragraph is obsolete upon an edit to the question, for any reader, check the comments to get context, and an apt answer.

For (2), the answer will be given, and then some notes; here: $$\forall \epsilon \; \bigg(\epsilon > 0 \to \Big(\exists N \; \big(N > 0 \; \land \; \forall x \; (x > N \; \to \; |F(x) - \ell| < \epsilon)\big)\Big)\bigg)$$ It is largely self-explanatory, although note the order of the quantifiers, and also that the greater than & less than signs are relations (constant predicates) which give out Boolean values (as opposed to functions, which gives out variables [terms]).

Answer 2

Partial answer:

We say that $lim_{x\to\infty}f(x) = L$, if for every $\epsilon >0 $ there exists an $M >0$ s.t. for every $x>M$ it holds that: $|f(x) - L| > < \epsilon$. Honestly, I'm not sure I could write this down properly as a WFF.

Not standard ZFC or FOL, but this may help:

$~~~~~~\forall f, L: [\forall a \in \mathbb{R}: [f(a) \in \mathbb{R}] \land L\in \mathbb{R}$

$~~~~~~\to [\text{ Lim}_\infty(f, L)\leftrightarrow \forall \epsilon \in \mathbb{R}: [\epsilon > 0 \to \exists M\in \mathbb{R}:\forall x\in \mathbb{R}: [x>M \to|f(x)-L|< \epsilon]]]] $

where $f$ is a unary function, and $\text{ Lim}_\infty$ is a binary predicate.

Or equivalently:

$~~~~~~\forall f, L: [\forall a: [a \in \mathbb{R} \to f(a) \in \mathbb{R}] \land L\in \mathbb{R}$

$~~~~~~\to [\text{ Lim}_\infty(f, L)\leftrightarrow \forall \epsilon [\epsilon \in \mathbb{R}\to [\epsilon > 0 \to \exists M: [M\in \mathbb{R} \land \forall x:[x \in \mathbb{R} \to [x>M \to|f(x)-L|< \epsilon]]]]]]]] $