Skip to main content

Questions tagged [quantifiers]

The quantifiers $\forall$ ("for all") and $\exists$ ("there exists") distinguish predicate calculus from propositional logic.

Filter by
Sorted by
Tagged with
1 vote
1 answer
53 views

Problem with Fitch : How to Eliminate ¬∃?

fitch problem: I've been working on a Fitch-style proof problem, and I've encountered a difficulty in a specific step (step 11). The problem restricts me to using Taut-Con rules from Con-Rules. Here’...
Bogdan Klinowitzki's user avatar
0 votes
1 answer
49 views

How to prove $\exists x (x=a)$ in intuitionistic logic

How do you prove $\exists x (x=a)$ intuitionistically, where $a$ is a constant symbol? Classically, one has $$ [\neg\exists x (x=a)]^1\vdash \forall x (\neg x=a) \vdash\neg a = a \vdash \bot \vdash^1 \...
10012511's user avatar
  • 684
1 vote
1 answer
39 views

Writing the definition of Upper Bound

Let X be an ordered set. Let $ S \subset X.$ An element $ u \in X$ is said to be an upper bound for $S$ if $s \leq u$ for all $ s \in S.$ In first-order logic, how do I write the above definition? Is ...
Dr. J's user avatar
  • 149
0 votes
0 answers
47 views

$( \exists x) (\forall y) \, P(y) \equiv \forall y \, P(y) $. [duplicate]

How do one justify $( \exists x) (\forall y) \, P(y) \equiv \forall y \, P(y) $. ? I came across a proof using this justification and i am unclear. Thanks Context: $\tag 1 \exists x \; [P(x) \...
Darren 's user avatar
1 vote
1 answer
69 views

correct notation for quantifier logic formulae

My question is about the correct way to write such statements like $$\exists y \forall x f(x) \leq y,$$ which means "there exists an $y$, such that for all $x$, $f(x)$ is less than or equal to $y$...
Penelope's user avatar
  • 3,325
0 votes
0 answers
39 views

How do I prove this in symbolic logic if the premise is just a tautology?

I'm working on some proofs in symbolic logic and I pretty much get it, but I'm having an issue with the last one. Usually the premise sets up the proof and I can walk through it, but this one just ...
Daniel's user avatar
  • 71
0 votes
1 answer
41 views

Prove $\exists z\in \mathbb{R} \,\forall x \in\mathbb{R}^+ \,\left[ \exists y \in \mathbb{R}\, (y - x = \frac{y}{x}) \leftrightarrow x \neq z \right]$

My solution: (->) Let $z$ be 1. I will prove by contradiction by letting $z=x$. Given $y-x=y/x$, it follows that $y=x^2/(x-1)$. If $x=1$, the statement $y=x^2/(x-1)$ does not exists, hence a ...
Darren 's user avatar
3 votes
4 answers
186 views

Why am I obtaining $ \neg \forall x A(x) \equiv \forall x\neg A(x)$?

Here is the proof of the theorem $$ \neg (\forall x) A(x) \equiv (\exists x)\neg A(x) $$ Proof: Let the universe of discourse be $U$. The sentence $ \neg (\forall x) A(x)$ is true in $U$ $\implies (\...
Mystic mystic's user avatar
5 votes
3 answers
161 views

Choosing between the 'and' and 'implies' connectives

$pol(x): x$ is a politician $liar(x): x $ is a liar All politicians are liars : $\forall x(pol(x) → liar(x))$ Some politicians are liars : $\exists x(pol(x) \land liar(x))$ No politicians are liars :...
user1327299's user avatar
0 votes
1 answer
56 views

Combined quantifier notation

For many years I've had this notion that all kinds of expressions where you pick out a variable to vary over, the expression ought to be reducible to a single form. I'm talking about expressions like $...
David Gudeman's user avatar
0 votes
0 answers
29 views

Mathematical Hierarchies Collapsing at Level 2

I am looking for (many) examples of mathematical hierarchies like the arithmetical or the polynomial hierarchy that collapse precisely at level 2 (3 is also fine, but the level should be at least 2 ...
blk's user avatar
  • 281
1 vote
0 answers
45 views

Why can't we derive the Left Contraction Rule in predicate logic?

Suppose we only have all the standard left and right logical inference rules ($∧L_{1}$, $∧L_{2}$, $∨L$, $→L$, $¬L$, $∨R_{1}$, $∨R_{2}$, $∧R$, $→R$, $¬R$) and on top of that 4 quantifer rules (see the ...
Alessandra12342's user avatar
-2 votes
1 answer
99 views

Probability of events containing quantifiers [closed]

At Brzezniak, Zastawniak, Basic Stochastic Processes, pp. 192-193 we find that $ξ(t),ζ(t), t\in T\subseteq \Bbb R$ are modifications of one another, if $$P\{ξ(t)=ζ(t)\}=1, \rm for~all~t\in T ~(1).$$ ...
SK_'s user avatar
  • 653
3 votes
1 answer
157 views

Who used the term "existential quantifier" in his work for the first time in the history of mathematical logic?

Who used the term "existential quantifier" in his work for the first time in the history of mathematical logic? I am sure that Peirce did not use the term in his book "Studies in Logic&...
Amandoros's user avatar
2 votes
1 answer
97 views

How do I write this Theorem with quantifiers?

Here is the theorem from Steven Abbot's Understanding Analysis. Theorem. Two real numbers $a$ and $b$ are equal if and only if for every real number $\epsilon > 0$ it follows that $|a - b| < \...
Dr. J's user avatar
  • 149
2 votes
3 answers
85 views

Proving $\exists x P(x) \rightarrow \forall x P(x)$ from $\forall x\forall y(x=y)$

Problem: Using identity axioms, prove $\exists x P(x) \rightarrow \forall x P(x)$ from $\forall x\forall y \, x=y$. So far: I'm quite stuck on where to even begin. Working backward, I know we want $P(...
categoricallystupid's user avatar
0 votes
4 answers
146 views

First order logic, why are the quantifier rules of inference reasonable?

This picture is from the book "Mathematical Logic, 2nd edition, Christopher C. Leary, Lars Kristensen" : I have two questions : Why are the quantifier rules of inference reasonable as they ...
user394334's user avatar
  • 1,262
3 votes
2 answers
117 views

Universal Quantification over Disjunction

I know that $\forall x [R(x) \rightarrow S(x)]$ is NOT equivalent to $\forall x R(x) \rightarrow \forall x S(x)$, because universal quantification does not distribute over disjunction. However, it ...
atonaltensor's user avatar
0 votes
1 answer
40 views

Quantifiers uniform continuity

According to this answer: https://math.stackexchange.com/a/2582334/1098426 We know $\forall x \ \exists y \ \forall z$ differs from $\forall x \forall z\ \exists y$ insofar as $y$ depends on $x$ ...
isaac's user avatar
  • 335
2 votes
2 answers
99 views

Understanding predicates and quantifiers ∀ , ∃ (my reasoning)

So lets say we are trying to figure out if: P(x, y) is the predicate of $x^2 < y$ as defined for x, y ∈ Z. This means using quantifiers: ∀ and ∃, I can logically say: 1. ∀x∃y of P(x,y) is ...
coolcat's user avatar
  • 147
4 votes
2 answers
235 views

Is $\forall x\exists x(x < x)$ a sentence?

Going through my notes on predicate logic, I read the following inductive definitions: Definition: An atomic term is either a variable or a constant. If $f$ is an $n$-place function symbol and $t_1, . ...
Sam's user avatar
  • 5,166
0 votes
0 answers
14 views

Is $\exists(a,b)\in S^2P(a,b)$ always equivalent to $\exists\{a,b\}\subseteq S\,P(a,b)$ for a binary predicate $P$ with domain $S^2;S\neq\emptyset$?

Is the following second-order statement true or false? (Assume $P$ is a binary predicate statement which is always defined for two members of $S\neq\emptyset$.) $$\forall P\left( x,y \right)\forall S \...
Next-Door Tech's user avatar
-1 votes
1 answer
46 views

Counting the numbers of quantifiers, how are there 4?

From the book "Gentle Introduction to Art of Mathematics": How many quantifiers does this have and what kind? "Everybody has some friend that thinks they know everything about a sport.”...
Yanjan. Kaf.'s user avatar
0 votes
0 answers
27 views

Convergence almost surely of random variables [duplicate]

I would like to prove that $X_n \rightarrow X$ almost surely iff $\forall \varepsilon >0 \ \lim_{N \to \infty} P \left( \bigcap_{n=N}^{\infty} \{ \omega: |X_n(\omega)-X(\omega)| \le \varepsilon\} \...
Kinder Zabawki's user avatar
0 votes
3 answers
209 views

Is this proof of the principle of recursion theorem proving anything?

The following is presented as an example to motivate my question. It's my paraphrase of the principle of recursion theorem and proof. From Fundamentals of Mathematics Foundations of Mathematics: The ...
Steven Thomas Hatton's user avatar
1 vote
1 answer
54 views

How to determine the truth value of a propositional function with free variables?

$x,y \in \mathbb{N}$ $\exists x \exists y (x + y = 0) \lor (x * y = 0)$ In this propositional function, is it true that the $x$ and $y$ in $(x * y = 0)$ are free variables? If so, am I allowed to ...
MaskTM's user avatar
  • 13
1 vote
0 answers
70 views

Propper way to express a Set Equivalence in logical form

This is my first post on the Math Stack Exchange so i'm sorry if questions of this nature are supposed to be tagged in a specific way, if they are please let me know and I will try to update my post ...
Cibo's user avatar
  • 11
3 votes
1 answer
99 views

Question about quantifiers in the proof of the cut eliminiation theorem

Lately I have been reading about the cut elimination theorem, I think I get the idea however I have been struggling with some technical details concerning quantifiers. Consider the following rule: ...
Le Grand Spectacle's user avatar
-1 votes
2 answers
51 views

Is $\exists x [(P(x) \vee Q(x))\rightarrow R(x)]$ logically equivalent to $\exists x [(P(x) \rightarrow R(x)) \vee (Q(x)\rightarrow R(x))]$?

Is $\exists x [(P(x) \vee Q(x))\rightarrow R(x)]$ logically equivalent to $\exists x [(P(x) \rightarrow R(x)) \vee (Q(x)\rightarrow R(x))]$? What about if I replace $\exists$ with $\forall$?
CroW's user avatar
  • 129
1 vote
1 answer
45 views

Definition of non-monotonic sequence

I am working on other proofs, namely for so-called "quasi-increasing" but non-monotonic sequences. But, my question: is the following a sufficient definition of non-monotonic? For all $N \...
isaac's user avatar
  • 335
1 vote
1 answer
66 views

Do the "nothing" and "unique existence" quantifiers respect or at least semi-respect ordered pairs?

Let $Nx$ be the quantifier "for no $x$", and let $\exists!x$ be the quantifier "there is one and only one $x$". Do those quantifiers respect ordered pairs? That is, is $NxNyP(x,y)$ ...
user107952's user avatar
  • 21.5k
2 votes
1 answer
249 views

Changing the definition of almost sure convergence

Following my previous question, let $0 \lt c \lt 1$ and consider the statements $$\mathbb{P}[\{\omega\in \Omega: \forall \epsilon\gt 0 \ \exists N\in \mathbb{N} \ \forall n\ge N \ |X_n(\omega) - X(\...
S.H.W's user avatar
  • 4,359
0 votes
1 answer
63 views

Quantifiers and the meaning of the statement

There's two statements: (i) ∃x (PresentKingFrance(x) → Bald(x)); (ii) ∃x (PresentKingFrance(x)) → ∃x (PresentKingFrance(x) ∧ Bald(x)). I'm not an expert in FOL, but I still understand a little bit. A ...
Егор Галыкин's user avatar
0 votes
1 answer
209 views

The quantifiers in the definition of almost sure convergence

Let $X_1,X_2,X_3,\dots$ be a sequence of random variables, defined on the probability space $(\Omega, \mathcal{F} , \mathbb{P})$. We say that this sequence converges almost surely to random variable $...
S.H.W's user avatar
  • 4,359
1 vote
1 answer
79 views

$\forall x(P(x) \rightarrow Q(x))\stackrel{?}{\equiv}\neg\exists x(P(x) \rightarrow \neg Q(x))\stackrel{?}{\equiv}\neg\exists x(P(x) \wedge\neg Q(x))$

Statement $1$: The statement $\forall x(P(x) \rightarrow Q(x))$ reads "For all $x$, if $P(x)$, then $Q(x)$". Statement $2$: The statement $\neg\exists x(P(x) \rightarrow \neg Q(x))$ reads &...
beyondinfinity's user avatar
5 votes
1 answer
676 views

Example of a quantifier which is not compatible with ordered pairs.

Let $P(x,y)$ be a binary predicate. I have noticed that the string of quantifiers $\forall x \forall y P(x,y)$ is equivalent to the single quantifier $\forall (x,y) P(x,y)$. Also, $\exists x \exists y ...
user107952's user avatar
  • 21.5k
5 votes
3 answers
117 views

Is "there exists at least $0$" the tautological quantifier?

Is "there exists at least $0$" the tautological quantifier, that is, it always holds, no matter what? And also, is the negation of that quantifier the contradictory quantifier, that is, the ...
user107952's user avatar
  • 21.5k
4 votes
3 answers
170 views

$\exists!x\exists!yP(x,y)$ is not the same as $\exists!y\exists!xP(x,y)$?

Suppose $P(x,y)$ is a property pertaining to any object $x$ and $y$. Let $\exists!$ be the unique existential quantifier. Then I just found that $\exists!x\exists!yP(x,y)$ is not necessarily ...
OSCAR's user avatar
  • 573
0 votes
3 answers
110 views

Showing that an implication is false

Let $a,b\in \mathbb{R}$ be two real numbers. Suppose that $$\forall \epsilon \gt0: a\le b+\epsilon$$ holds. I'm aware that the correct implication is $$\forall \epsilon \gt0: a\le b+\epsilon \implies ...
S.H.W's user avatar
  • 4,359
0 votes
1 answer
34 views

Particularization rules of premises with multiple quantifiers

I have this reasoning with multiple quantifiers and I need to prove it's validity $\exists x : [F(x) \wedge S(x)] \rightarrow \forall y : [M(y) \rightarrow W(y)]$ $\exists y : [M(y) \wedge \neg W(y)]$ ...
Robin's user avatar
  • 13
1 vote
3 answers
51 views

How to symbolize this statement with multiple quantifiers?

I need to symbolize this statement "Any natural number $n$ can be written either in the form of $2k$ or in the form of $2k+1$ for some natural number $k$". I tried with $\forall n \in \Bbb N,...
Robin's user avatar
  • 13
0 votes
1 answer
68 views

Using and Rather than Implies

I am trying to understand the difference between and $\wedge$ and $\rightarrow$. Consider $$x=y\Longleftrightarrow \forall z(z\in x \ \rightarrow z \in y)$$ However, I think we can use and notation ...
Tunay Sabri Yüksel's user avatar
2 votes
2 answers
80 views

Prove the formula $(\forall x Px \wedge \forall x Qx) \leftrightarrow \forall x [Px \wedge Qx]$

I'm sure this implication is correct. However, are there rules on how one can manipulate with quantifiers? It might somehow be related to whether no free variables are becoming bounded after the ...
Seeker's user avatar
  • 347
1 vote
0 answers
27 views

Set representations of double quantifications

This might be a silly question, but somehow I cannot get my head around it. Suppose there are two sets of sets, $X_p$ for all $p \in P$, and $X_q$ for all $q \in Q$. If it holds that: $$ \forall p \in ...
Acad's user avatar
  • 149
0 votes
2 answers
259 views

Do ∃x(Dog(x)) and ∃x(¬Dog(x)) contradict each other? [closed]

Formally, ∃x(Dog(x)) and ∃x(¬Dog(x)) look like they contradict each other. However, in the real world, there exist objects which are dogs i.e. ∃x(Dog(x)) there exist objects which are not dogs i.e. ∃...
Boris Rusev's user avatar
1 vote
0 answers
91 views

Proof Explanation - Introduction to Mathematical Logic by Samuel Buss Example III.$42$

In the book Introduction to Mathematical Logic of Samuel Buss, example III.$42$ says: Assume that $\mathfrak{A}\not\vDash C[\sigma]$. (...) since $x$ is not free in $C$, $\mathfrak{A}\not\vDash C[\...
Esteban Saldarriaga's user avatar
0 votes
1 answer
40 views

Navier-Stokes: clarification with quantifiers of the initial condition (4) in CMI official problem definition

I am a bit lost. The Clay Mathematics Institute has written an $n$ dimensional Navier-Stokes problem description here. On the first page, an initial condition $(4)$ is: $$\vert \partial_x^\alpha \, u°(...
someone's user avatar
  • 63
1 vote
0 answers
29 views

When to use Conditional vs Conjunction [duplicate]

I'm studying proofs with Vellemans book "How to prove it". I am having trouble understanding when I am supposed to use the "conjunction" vs "conditional". My confusion is ...
Max's user avatar
  • 11
1 vote
1 answer
103 views

Changing the ∀ quantifier to the ∃ quantifier

I am tasked with changing the $\forall$ quantifier with the $\exists$ quantifier. However, I am not sure, whether I understood it correctly, and would like to ask for help. As I understood, the ...
Mike M.'s user avatar
  • 29
1 vote
1 answer
31 views

Confusion regarding order of quantifiers probability

Suppose I have a random variable $W$ that can take values $w_1,w_2,w_3$ with probability $p_1,p_2,p_3$ with $p_1+p_2+p_3=1$ (exhaustive) mutually exclusive. What is the difference between the ...
DuttaA's user avatar
  • 283

1
2 3 4 5
37