Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

1
vote
1answer
48 views

Elimination of quantifiers for the theory of equivalence relations with two infinite classes by back-and-forth

As I said in an earlier question, I'm trying to understand how to obtain elimination sets by way of back-and-forth arguments. Since I'm not totally sure I understood how it works, I wanted to check my ...
1
vote
3answers
48 views

logic: order of quantifier with free variables

Take the sentence, "You can't win them all." This could be logically written as "For all people, there exists a thing they cannot win at." $\forall x.\exists y.(\neg win(x,y))$ Now suppose I was ...
0
votes
0answers
27 views

Predicate logic example..

I've got this predicate symbol: $(\forall x R(x,y)) \implies (\forall y Q(x,y))$ $R=\{(x,y) \in Q \times Q \hspace{0,2cm}|\hspace{0,2cm} x<y\}$ $Q=\{(x,y) \in Q \times Q ...
0
votes
0answers
17 views

Mathematical logic: Predicates, formula

I've got universum $A = \{0,1,2\}$ Predicate: $R^{A}=\{\{x,y\} \in A \times A \hspace{2mm} | \hspace{2mm} x \neq y \} $ Terms: $f^A(x) = 1$ $g^A(x,y) = min(x,y)$ Constant $c^A = 2$ Valuation: ...
0
votes
1answer
32 views

Is the conjunction of all necessary statements sufficient? What about the converse?

A necessary condition for consequent $q$ is a proposition $p$ such that: $$\neg p \implies \neg q$$ let $P:= \{p_i: \neg p_i\implies \neg q\}$ What I want to know is if $$\bigwedge_{p_i\in P} p_i ...
0
votes
1answer
52 views

Gödel number for contradicting modus ponens?

When Gödel numbered statements, for instance modus ponens and connectives got their own numbers, does it matter which number each connective gets as long as they are different? Sometimes I'm not ...
2
votes
1answer
34 views

Graded back-and-forth systems and unnested Ehrenfeucht-Fraïssé games

I'm trying to work my way through back-and-forth systems and elimination sets by reading the relevant sections in Hodges' Model Theory and I'm a bit confused by one of his lemmas (specifically, it's ...
0
votes
1answer
32 views

Translating comparison operators into logic

I have $P: x > 30$; $Q: x < 20$ Write simply as you can: a) $P \land Q$ My answer: $x > 30 \;and \; x < 20$ Which is always false: So if I write: $30 < x < 20$ is it still ...
0
votes
0answers
23 views

Negation of a quantified statement regarding an implication.

I am trying to improve my understanding of the negation of a quantified statement where the statement is an implication. I am doing a practice problem which I dont have the answer to from the textbook ...
2
votes
0answers
56 views

Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch ...
3
votes
4answers
71 views

Question about conditional statements as applied to math?

I was being bothered by the fact that $p \implies q$ is defined when $p$ is false, so I thought I would try an example in math terms to help me understand it; but I got a stuck: Let's define $p: x ...
1
vote
1answer
67 views

Examples of the use of $(p \vee q) \wedge (\neg p \vee r) \Rightarrow (q \vee r)$ in “real” mathematics?

Here, a proof is requested for the following tautology: $$(p \vee q) \wedge (\neg p \vee r) \Rightarrow (q \vee r)$$ Its pretty easy to prove; nonetheless, I don't find the formula at all intuitive, ...
-2
votes
0answers
30 views

Prove this sequent using just i/e rules? [closed]

I've just been doing some revision and it's going well, but this one question is stumping me. It's been a while since I have done it so I'm not surprised but if anyone could walk me through it I'd be ...
1
vote
1answer
18 views

Question on negation of a quantified statement

There is a slight confusion I am having when comparing my answer to a solution for a problem. Basically, the question asks me to state the negation of For every integer $n$ such that if $n$ is ...
0
votes
0answers
23 views

proof : the set of all logical consequences $S,\{F:S \models F\} $ is a maximal set. [closed]

prove that the set of all logic consequences $S,\{F:S \models F\} $ is a maximal set.
1
vote
3answers
58 views

changing the order of the logical symbols $(\forall \epsilon) (\exists\delta)$ by $(\exists \delta)(\forall\epsilon) $ in limit definition

Some time ago a professor told the class, which I was in, to analyze why this definition of limit is not good (or if it is a good definition to argument why): There exists a $\delta>0$ for all ...
1
vote
2answers
23 views

Propositional formula to represent set of binary strings

I'm "getting acquainted" with mathematical logic and found an exercise online whose solution I don't understand. It asks for the most compact representation of a set of binary strings ...
0
votes
1answer
13 views

Is there a Relationship Between Multi-Valued Logic and n-Satisfiability?

Is binary (Boolean) logic related at all to the two-satisfiability problem? And is ternary logic related in some way to the three-satisfiability problem? Would it follow then that if one were to ...
0
votes
2answers
20 views

Predicate logic definable sets question

Let L = L0 ∨ {R} where L0 is the basic language with equality and R is a binary relation symbol. Consider the L-structure X which has underlying set X = {a, b, c, d, e} and where RX ...
0
votes
1answer
31 views

Prove or disprove in propositional calculus

I have the following question - and would like to make clear some definition via it's answer - Prove of Disprove - If $\\X\models\alpha$ and $\\Y\models\alpha$, then $X\cap Y\models\alpha$ ...
0
votes
1answer
44 views

What is the negation of a logical expression? [duplicate]

If I have for example the following: $p$ is $ x > 4$ $\lnot p$ is $x < 4$ ?
1
vote
3answers
50 views

Is this proof for “If $2x+y$ is odd then x is odd or y is odd.” sufficient.

My proof: Consider the contrapositive: "If x and y and both even, then 2x+y is even. 2x+y = even*even + even = even. The contrapositive is logically equivalent, hence the statement is true.
1
vote
2answers
40 views

How to prove facts regarding sentential logic

Recently I have been very fascinated by the claim and impact of Godel's incompleteness theorem. To understand the proof given by Godel, I felt the need to read an introductory book in logic to begin ...
1
vote
0answers
27 views

Example of “semi-definite” question?

I read that mathematical logic can have a "semi-definite" question but what does it mean and is there an easy example? Is it a yes-or-no question where there is no method for one of the answers? For ...
-2
votes
3answers
92 views

Prove $\sqrt{x^{2} + y^{2}} \le |x| + |y|$ [closed]

How do I prove this? x and y are real numbers. Thanks for the help.
1
vote
0answers
20 views

Deductive closure from Completeness

the prompt asks to show that if $\Sigma$ is complete, then it is deductively closed. I know that deductive closure means $\Delta \vdash \sigma$ implies that $\sigma \in \Delta$. and that since ...
0
votes
1answer
22 views

Proving a theorem in predicate logic without the use of metatheorems

I'm trying to prove: $$\forall x (\phi \rightarrow \psi) \rightarrow (\forall x (\phi) \rightarrow \forall x (\psi))$$ and $$\forall x \forall y (\phi) \rightarrow \forall y \forall x (\phi) $$ using ...
3
votes
3answers
125 views

On “why” questions in mathematics

In response to the question How would one be able to prove mathematically that $1+1 = 2$?, Asaf Karagila explains: In a more general setting, one needs to remember that $0,1,2,3,…$ are just ...
0
votes
1answer
13 views

Show that it is possible to prove every proposition ( $\vdash \gamma$) in the following proof system

How can I prove that $\vdash\gamma$ in my proof system that has the following axioms and inference rules: Ax1: $\alpha \rightarrow (\beta \rightarrow \alpha)$ Ax2: $(\alpha \rightarrow (\beta ...
1
vote
0answers
20 views

From Propositional Calculus Proof to Predicate Calculus Proof

PROVE: If {$\Delta_{i}$} are all deductively closed set of formulae, so is $\cap \Delta_i$. Show with predicate Calculus. Definition: {$\Delta_{i}$} a set $\Delta$ of formulae is deductively closed ...
1
vote
0answers
25 views

Proof from axioms of $\mathsf{PA}$: every natural number has remainder $0$ or $1$ or $2$ when divided by $3$

Using only the axioms of $\mathsf{PA}$, I want to prove this fact. It came up in a previous year's exam paper, and seems more difficult than I had anticipated... The question was to sketch the idea, ...
0
votes
1answer
51 views

Deductive Closure as intersection of all Sets of sentences that are true in a Structure?

A set $\Delta$ of Formulae is deductively closed iff $\Delta$ $\vdash$ $\sigma$ implies that $\sigma$ $\in$ $\Delta$. $\Gamma$ is a set of sentences. Define $\Sigma_{\mathcal{A}}$ as all sentences ...
3
votes
2answers
83 views

How many taxicabs are there in New York City?

There is some unknown number $x$ which represents the amount of taxicabs in New York City. These taxicabs are randomly distributed throughout the city, so you are equally likely to find any of them. ...
-1
votes
0answers
22 views

Intuitive relation between set theory and logic? [closed]

How would you intuitively explain connection and interaction of classic set theory and classic logic?
0
votes
0answers
19 views

Prove\disprove that if $X \vdash \alpha$ or $Y \vdash \alpha$ then $X\cup Y \vdash \alpha$

I found this statement at my of my books, if $X \vdash \alpha$ or $Y \vdash \alpha$ then $X\cup Y \vdash \alpha$ Now, I want to prove it but I don't really know how, may be I will prove it with ...
0
votes
0answers
14 views

Prove that $\vdash (\lnot \alpha \rightarrow \lnot \beta) \rightarrow (\beta\rightarrow\alpha)$ in HPC proof system

If I need to prove that $\vdash (\lnot \alpha \rightarrow \lnot \beta) \rightarrow (\beta\rightarrow\alpha)$ in the HPC proof system, can I simply say that it is an axion?
-1
votes
0answers
20 views

Resolution, substitution. [closed]

http://www.csee.umbc.edu/courses/graduate/691/spring12/03/notes/19resolution.pdf and I have the problem with understanding with slide number 10. Especially, I cannot undesrstand what does it mean: ...
1
vote
1answer
31 views

Is $\forall x \in U: f(x) \in V$ the same as $x \in U \implies f(x) \in V$?

As the title says, do the following two statements have the same meaning? $$\forall x \in U: f(x) \in V \text{ (for all $x \in U$, $f(x) \in V$)}$$ $$x \in U \implies f(x) \in V \text{ ($x \in U$ ...
7
votes
1answer
107 views

Is ZFC ω-consistent over ZF?

Gödel proved that if ZF is consistent, then ZFC is also consistent. He did this by showing that his constructible universe is a model of ZFC. Gödel also introduced the notion of an $\omega$-consistent ...
31
votes
7answers
2k views

Do the axioms of set theory actually define the notion of a set?

In Henning Makholm's answer to the question, When does the set enter set theory?, he states: In axiomatic set theory, the axioms themselves are the definition of the notion of a set: A set is ...
4
votes
1answer
63 views

Show forcing condition compatibility by induction

Say that we have a countable support forcing iteration $ \mathbb{ P}_{ \alpha }$ ( using Jech's definition ) where $ \alpha $ is a limit ordinal, and consider two conditions $ f , g \in \mathbb{ P}_{ ...
0
votes
1answer
27 views

Prove that $\{A\rightarrow \sim B, B, C \vee A\} \vdash C$ in this proof system

I have this proof system: $$Ax: \alpha \rightarrow (\beta \rightarrow \alpha)$$ $$IR: \frac{\alpha \vee \lnot \beta, \beta }{\alpha} \space \space \frac{\alpha \rightarrow \beta , \lnot \beta}{\lnot ...
1
vote
0answers
18 views

Skolemization algorithm for a formula

I'd like to know if I my Skolemization is right: $$(\exists x(P(x)\lor R(x)))\to((\exists xP(x))\lor(\exists xR(x)))\\(\exists x(P(x)\lor R(x)))\to((\exists yP(y))\lor(\exists zR(z)))\\(\exists ...
3
votes
0answers
33 views

Strict order on propositions and interpolation

We can define a strict order on the set of propositions in countably many propositional letters in the following way: $$\varphi\sqsubset\psi \iff (\models \varphi\rightarrow\psi)\, \land (\not\models ...
0
votes
0answers
27 views

Let $A \subseteq \mathbb{R}$ and $|A|=\omega$, prove $|\mathbb{R}\setminus A| = 2^\omega$. [duplicate]

Let $A \subseteq \mathbb{R}$ and $|A|=\omega$, prove $|\mathbb{R}\setminus A| = 2^\omega$. Hint: $\mathbb{R}\sim \{0,1\}^\mathbb{N}$ I'm somewhat stuck trying to prove this, could someone ...
0
votes
4answers
89 views

Why is “$A$ unless $B$” equivalent to $A \lor B$?

$A$ unless $B$ surely means, 'given that $B$ does not happen, $A$ will happen'. So if $B$ happens, $A$ does not happen. Yet I've read, by those officially accredited, that $A$ unless $B$ = $A$ or ...
-1
votes
2answers
72 views

Should we change the truth table for the material conditional?

Having studied logic, I still cannot understand the conditional. At first, it was because (as with most things I learn) it was a problem with my understanding. I now believe it is because there is an ...
5
votes
2answers
71 views

On logic vs information theory

If the statements All crows are black and All non black things are non crows are equal, then why is the former so much easier to communicate by giving examples? What implications does this ...
2
votes
0answers
22 views

Why don't the quantifiers split in linear logic?

Every presentation of linear logic I've seen seems to either omit or treat quantifiers as an after-thought. Even Girard says that there is "little to say" about them. However, if we view universal ...
0
votes
1answer
11 views

Need some help with matlab syntax for logical equivalence/inference

I've got a maths question that I need to translate into matlab syntax to run through and I'm slightly stuck so hopefully someone here can help since I can't seem to find my answer online. The ...