Questions concerning predicate calculus, i.e. the logic of quantifiers.

learn more… | top users | synonyms

1
vote
2answers
38 views

when does $a\in\mathbb{R}$ does $\neg(a\leq 15\implies a>1)$ hold? [duplicate]

How can I formally write down for which $a\in\mathbb{R}$ the statement $\neg(a\leq 15\implies a>1)$ holds?
2
votes
1answer
34 views

Consistency vs Inconsistency in a set of sentences: which is more common

I'm curious whether there is any research in the "probability" that a set of sentences in a first-order logic is consistent. Obviously, there are an infinite number of inconsistent sets and an ...
1
vote
1answer
40 views

is this formula provable in predicate logic? ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1))

"Can you prove ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1)) in predicate logic? explain." I'm saying no, but I'm not sure why. Is it because it's not a tautology? and how would Godel's ...
-1
votes
0answers
32 views

Predicate calculus using inference rule

I am unable to solve the following propositional logic: \forall x : T \dot P(x) \land Q(x) <=> (\forall x : T \dot P(x)) ^ (\forall x : T \dot Q(x)) I need ...
3
votes
3answers
85 views

Is there a concise way to notate 'There are exactly 482 x, such that Px…' in logical notation?

My prof has taught us that we can express the proposition $⟦$there are exactly two entities characterized by $P$$⟧$ thus: That proposition looks verbose, despite the fact that it references just ...
2
votes
0answers
31 views

Predicate Logic Interpretation/Modelling help

I'm having trouble creating models for predicate logic statements. I am going to give an example, I hope you guys can help me out. $$\forall x(P(x) \text{^} Q(x,a) \to Q(x,b) )$$ Let $M_1$ be the ...
2
votes
4answers
176 views

The Order of Mixed Quantifiers

How can we derive the implication: $$ ∃y∀xP(x,y) \implies ∀x∃yP(x,y) $$ In other words, when quantifiers in the same sentence are of the same type (all universal or all existential), the order in ...
0
votes
1answer
30 views

Skolem Function and one Exam Challenge [closed]

we know if P implies Q (and show it by $P \Longrightarrow Q$ ), The Predicate Q is weaker than P. i want to check it which of the following is weaker than others? F1 is a Skolem function and F2 is a ...
1
vote
1answer
57 views

Does theory have the smallest model

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
1answer
37 views

Does theory have uncountably many pairwise non-isomorphic models?

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
1answer
43 views

Find some complete theory $U \supseteq T$

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
1answer
15 views

Help with English to Predicate Logic

Alex likes anything that contains chocolate. a - Alex L(x,y) - x likes y C(x) - x contains chocolate $1. \forall x \space (C(x) \implies L(a,x)) $ $2. \forall x \space (C(x) \space \text{^} ...
0
votes
1answer
23 views

Exactly one in Predicate Logic

Could anyone tell me how to translate the following sentence into predicate logic. E : the set of elephants A : the set of animals G(x) : x is green E(x) : x is an elephant N(x; y) : name of x is ...
0
votes
1answer
24 views

Prove, that predicate is inexpressible in the given signature

I have a predicate $y=x+1$. I want to prove, that this predicate is inexpressible in $(\mathbb{Z}, {=}, f)$, where $f = x\mapsto(x+2)$. I understand, that I need to come up some automorphism, in ...
2
votes
2answers
42 views

Questions regarding well formed expressions in the Theory of types

I'm dealing with a question in type theory: Is it possible to assign types to $\alpha$, $\beta$, and $\gamma$ in such a way that both $(\alpha (\beta))(\gamma)$ and $\alpha (\beta (\gamma))$ are ...
1
vote
3answers
48 views

How to determine if this is true or false?

$$\exists x \in X, (P(x) \to Q(x))\hspace{0.2cm} \iff (\exists x \in X, P(x))\to (\exists x \in X, Q(x))$$ $$\forall x \in X, (P(x) \to Q(x))\hspace{0.2cm} \iff (\forall x \in X, P(x))\to (\forall x ...
0
votes
2answers
32 views

Proving that universal quantification distribute over conjunction

show $$\vdash [\forall x(P(x))\wedge \forall x(Q(x))]\to \forall x[P(x)\wedge Q(x)]$$ answer: by Q_{1}:$\forall x \phi\to\phi_{t}^{x}$ so we have $\forall x P(x)\to P(t)$ $\forall x Q(x)\to Q(t)$ ...
1
vote
2answers
23 views

Pre-nex normal form. Correct way to distribute negations among quantifiers

Start point: $$(¬∀x P(x) ∨ ¬∀y Q(y)) → ¬∃x G(x)$$ Implication to Disjunction (DeMorgans Laws): $$¬(¬∀x P(x) ∨ ¬∀y Q(y)) ∨ ¬∃x G(x)$$ Now I am at the point where I need to move in the negations to ...
0
votes
0answers
33 views

show that if $x$ is not free in $\Psi$ then $\phi \rightarrow\Psi\vDash [(\exists x \phi)\rightarrow\Psi]$

show that if $x$ is not free in $\Psi$ then $$\phi \rightarrow\Psi\vDash [(\exists x \phi)\rightarrow\Psi]$$ answer: by QR $$\phi \rightarrow\Psi\vdash [(\exists x \phi)\rightarrow\Psi]$$ so ...
2
votes
3answers
43 views

Is the order of four quantifiers in a predicate formula relevant?

Is the formula: $$\forall x \exists y \forall z \exists u (F(x) \lor G(y) \to F(z) \lor G(u))$$ Equivalent to formula: $$\forall z \exists u \forall x \exists y (F(x) \lor G(y) \to F(z) \lor ...
0
votes
1answer
9 views

Discrete Structures : predicate logic (negation)

I got part 1 wrong but can't seem to figure out why. All farmers -> not all farmers, grow corn -> grow only corn. When I put it together it made sense. Am i missing something? Write the negation of ...
1
vote
3answers
22 views

Discrete Structures : predicate logic (negations)

Could someone please explain why the negation makes "nobody" into "someone" and not "everyone" Which of the following is the correct negation for “Nobody is perfect.” 1. Everyone is imperfect. ...
0
votes
2answers
21 views

Discrete Structures : predicate logic

Can anyone help me understand why this might be wrong? You can’t fool all of the people all of the time. (∀x) [P(x) /\ (∀y)(T(y)-> ~ F(x,y))]
0
votes
2answers
25 views

Trouble understanding surjective function proof

I'm studying for my discrete math exam and I'm having some trouble understanding this practice problem and solution. I know what surjective functions are, but I can't really understand the way this ...
0
votes
0answers
14 views

Proving that a predicate calc wff with a bi conditional [duplicate]

Prove: ∀x(C → D(x)) ↔ (C →∀xD(x)) resources: axiom 1:∀XA →Axt axiom 2:∀X(A→B) → (∀XA→∀XB) axiom 3:A→∀XA; Hilbert Generalization rule my attempt: ...
1
vote
1answer
34 views

Proving a bi-conditional predicate calculus formulae

Prove the following: ∀x(C → D(x)) ↔ (C →∀xD(x)) I am looking at the axioms I can use under hilberts deductive system as well as the Generalization rule but I ...
6
votes
5answers
194 views

Is a proposition about something which doesn't exist true or false?

Let S = {x | x is not an element of x } The set S doesn't exist. Then, would a proposition such as "The cardinality of S is 1," be true or false? Equivalently, I could have made a proposition, "the ...
1
vote
1answer
29 views

How would one prove that satisfaction of closed formulas is valuation-independent? (In FOL)

Consider this proposition in first-order logic: For any interpretation $I$, any closed formula $\phi$ and any two valuations $\rho$, $\sigma$. $I\rho \models \phi \iff I\sigma \models \phi$ This is ...
0
votes
1answer
97 views

Trouble with by-contradiction proof

I'm studying for an exam and I'm having trouble with one of these problems. ...
1
vote
1answer
19 views

translating a sentence into predicate calculus

I am supposed to translate the following sentence into predicate calculus: No Student likes the classroom. S(x) : x is a student C(x) : x likes the classroom I ...
1
vote
1answer
74 views

Is $\lnot\forall x\;\lnot\forall y\;A$ the same as $\forall x\;\forall y\;A$?

Is $\lnot\forall x\;\lnot\forall y\;A$ the same as $\forall x\;\forall y\;A$? And if so, by what rule? I am trying to find a rule where the above would apply. I am currently using Hilbert deduction ...
1
vote
0answers
38 views

Predicate Logic and Negation Assistance

I just want to make sure I'm on the right path with these: Using the predicate symbols shown and appropriate quantifiers, write each English language statement in predicate logic. (The domain is ...
0
votes
0answers
51 views

Is this an accurate description of structures and interpretations.

I read about structures and interpretations today. I've described them below this paragraph. Have I accurately described them? If not, what have I incorrectly described? A structure, $\mathscr{A}$, ...
4
votes
2answers
102 views

Formalize the sentence: “Earth is the only planet inhabited by mathematicians”

I have to formalize the sentence: "Earth is the only planet inhabited by mathematicians" Let: $P(x)$ stands for 'x is a planet' $M(x)$ stands for 'x is a mathematician' $I(x,y)$ stands for 'x ...
1
vote
1answer
38 views

Given an open statement determine if their quantification is true

The Question My Work/Question My book says for part a, iv is true. I disagree. To show an existential statement is false we have to show that for all x that statement is untrue. There are no ...
0
votes
1answer
25 views

Language and Finite Models

Let us consider the language consisting of one symbol $R$ for a binary relation. Let $\sigma$ denote the following sentence: $\forall x \exists y \exists z \ x\neq y \wedge y \neq z \wedge x \neq z ...
0
votes
1answer
20 views

A predicate logic question about write down a sentence

Let $\mathcal{L}=\{f\}$ be a first-order language containing a unary function symbol f, and no other non-logical symbols. Write down sentences $φ$ and $ψ$ of $\mathcal{L}$ such that for any ...
0
votes
1answer
35 views

what is the meaning of this predicate statement

This question appeared in the GATE exam 2011 Q.32 Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate P(x) = ...
-2
votes
1answer
28 views

a formal logic proposition about real numbers

I have the following informal statement about real numbers: Every real number except zero has a multiplicative inverse. Can this be expressed as: $$ \forall x \exists y(x\neq 0 \implies xy=1) ...
0
votes
0answers
20 views

Formalize: “Every mail message larger then one megabyte will be compressed” [duplicate]

Formalize: Every mail message larger then one megabyte will be compressed
0
votes
2answers
46 views

what happens in a universal implication when the premise is false

I have just started learning Mathematical logic and couldn't figure out the answer to the above question . my question is what happens to the truth value if the premise in a universal implication is ...
2
votes
1answer
68 views

How to write “there exists an infinite number of”?

We all know that means “there exists” and ∃! means “there exists exactly one”. Is there a similar notation for existence of an ...
0
votes
2answers
67 views

Is this theory complete?

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
3answers
40 views

At Most Two Distinct Members of A

The quantified predicate logic statement that describes at most two distinct members of A, where A, is some arbitrary set is: $\forall$xyz( (Px $\land$ Py $\land$ Pz) $\Rightarrow$ (x=y $\lor$ x=z ...
0
votes
0answers
15 views

Predicate logic truth value same?

Consider the predicate $$P(x,y,z) = xyz = 1",$$ for $$ x,y, z \in R,$$ $$x; y; z > 0.$$ $1 - \forall x; \forall y; \exists z; P(x; y; z). $ $2 - \exists x; \forall y; \forall z; P(x; y; z). $ ...
5
votes
1answer
58 views

Compactness Theorem / Set made of formulas of infinite size

Could someone give me an example of an infinite countable set, where formulas contained in it are under the form of a conjunction or disjunction of infinite size, for which the compactness theorem ...
0
votes
1answer
40 views

What we can infer from there exists x satisfying P

If it is known that there exists x satisfying P, can we infer that there also exists x not satisfying P? I ask this question since I have a problem as follows. Given three premises: (1)if a student ...
1
vote
2answers
29 views

Inequality with respect to transitivity

Given a relation R, R is said to be transitive if aRb ∧ bRc, then aRc. The unequal relation (≠) is not transitive, for instance a≠b ∧ b≠c, then a≠c is an invalid consequent of the antecedent (a≠b ∧ ...
2
votes
2answers
42 views

Have I properly used $\,\exists !\,$ in this statement?

I want to express the following in logical notation. For every natural number, there is a unique natural number that succeeds it. Does the following statement express that proposition? ...
0
votes
1answer
29 views

Prove by contrapositive: Φ∪{β} ⊨ α & Φ∪{¬β} ⊨ α iff Φ ⊨ α

We are to prove this by contrapositive (by the way: Φ is a set of formulas of predicate logic and α a formula of predicate logic) I've managed the Right to Left proof, but I struggle with the Left to ...