Tagged Questions

Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

-4
votes
1answer
41 views

Which if the following three propositions are logically equivalent?

Which if the following three propositions are logically equivalent? $(p \wedge q) \Rightarrow (p \wedge r)$ $p \wedge (q \Rightarrow (p \wedge r)) $ $(\lnot p) \vee (\neg q) \vee (r \wedge p)$ ...
-3
votes
0answers
49 views

Determine the truth value of the following proposition: “If it is sunny, then it is raining if and only if it is snowing.” [on hold]

Determine the truth value of the following proposition: "If it is sunny, then it is raining if and only if it is snowing."
0
votes
0answers
15 views

What is principle of duality?

What is principle of duality? What is difference between principle of duality and De Morgan's law?
2
votes
2answers
24 views

When there is a proposition $(P\rightarrow Q)$, which row in the truth table of $\rightarrow $ should I use?

I solved one question in a book of analysis, and although I used an informal method to check it, I'd like to know more about what should be done. The question was the following: $A\subset X$ ...
2
votes
4answers
68 views

Question about logical implication $P\to Q$ [duplicate]

Having come across mathematical logic, a question suddenly came into my mind. We commonly know that the truth value of $P\to Q$ given as: $\begin{matrix} P&Q&P \Rightarrow Q \\ ...
1
vote
1answer
19 views

$\sigma \in\sum^\prime \leftrightarrow \sum^\prime \vdash \sigma$

$\sum^\prime$ maximal consistent $\sigma$ is a sentence $\sigma \in\sum^\prime \leftrightarrow \sum^\prime \vdash \sigma$ answer:$\rightarrow$ if ...
1
vote
0answers
17 views

$\exists G \in L'. G \iff \mathtt{True}(gn(\neg G))$ in the language $L'$ with Godel numbering $gn$ and $\mathtt{True}$ predicate?

I am reading a paper Definability of Truth in Probabilistic Logic . Given a language $L$ with the Godel numbering $gn:L \to \mathbb{N}$ the authors extend it with a predicate $\mathtt{True}$ to a ...
0
votes
0answers
14 views

About the number of elements verifying a property

I have this question about the number of elements verifying a property: A property $Q_{m}$ is verified for all $m<a$ where $a>2$ is an arbitrary real number. Can we deduce that the number of ...
0
votes
0answers
45 views

Can we unify every pair of inner models of ZFC by a same hierarchy?

Definition: Fix a ground model $V$ of ZFC. Let $F:V\rightarrow V$ be a definable class function (we call it an operator). The hierarchy $W^F$ corresponding to $F$ is defined as follows: ...
0
votes
3answers
38 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 ...
-4
votes
0answers
18 views

show $\vdash [( \forall x\,)(P(x)) \land(\forall x \,)(Q(x)) \rightarrow (\forall x\,)\bigl ( P(x) \land Q(x)\bigr ) ]$ [on hold]

show that? $$\vdash [( \forall x\,)(P(x)) \land(\forall x \,)(Q(x))] \rightarrow (\forall x\,)\bigl [( P(x) \land Q(x)\bigr ) ]$$
-1
votes
0answers
35 views

show that$\vdash x=y \rightarrow y=x$ [on hold]

Question:show that $$\vdash x=y \rightarrow y=x$$ Answer:by $[(x_{1}=y_{1})\land(x_{2}=y_{2})\land\dots\land(x_{n}=y_{n}) ]\rightarrow(R(x_{1},x_{2},\dots,x_{n})=R(y_{1},y_{2},\dots,y_{n}))$ $E3$ we ...
2
votes
3answers
34 views

How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help. If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$. ...
-1
votes
4answers
44 views

Prove that $1+3+5+…+(2n-1)=n^2$ for every positive n integer [on hold]

Prove this statement using mathematical induction.
3
votes
3answers
92 views

Self-studying Russell's Paradox

I'm self-studying and having trouble wrapping my head around Russell's paradox, even after looking here. I'd really appreciate a more intuitive explanation of the concept before I move on to ...
0
votes
0answers
46 views

how to show and prove the above axioms are valid

at this theorem: the logical axioms are valid. i want to check the equlity axioms and quantifier axioms. i consider $x=x$ for each variable $x$. $(E1)$ ...
11
votes
2answers
198 views

What does it mean to say that a particular mathematical theory is a foundation for mathematics?

We usually hear that set theory is a foundation for contemporary mathematics. Category theory is also another foundation of maths. There are other theories which deemed to be a foundation for maths. ...
-1
votes
0answers
27 views

$ \phi$ is a propositional consequence of $\boldsymbol{\Gamma}$?

let $\boldsymbol{\Gamma}$ be the set $\{\forall P(x)\rightarrow \exists yQ(y) ,\exists yQ(y)\rightarrow P(x), \lnot P(x) \leftrightarrow(y=z)\}$ $ \phi$ is $\forall P(x)\rightarrow \lnot(y=z)$. ...
6
votes
4answers
266 views

Motivation for natural deduction

I've been learning natural deduction recently. I've seen many problems and am starting to be able to solve problems more easily. For some reason I feel the need to ask what high school math students ...
1
vote
1answer
31 views

Are these two notions of “computable function” the same or related?

From http://en.wikipedia.org/wiki/Semicomputable_function, we have: "If a partial function is both upper and lower semicomputable it is called computable." Is this the same kind of "computable ...
6
votes
1answer
67 views

Why are models in logic called models?

A model is an interpretation of a given formal language under which any wff in a given set of wffs of this formal language is true. Why are models called models? What's the reasoning behind the name? ...
0
votes
0answers
49 views

Divisibility lattice and duality with topological spaces

Consider the integers $\mathbb{N}$ seen as a poset with divisibility as an order relation. See it as a distributive bounded lattice with gcd and lcm, with gcd being the meet and lcm the join. Clearly, ...
2
votes
1answer
70 views

Problem with proving formally tautology using given rules

Using the rules below prove that the following assumeptions leads to the following conclusion by tautology. $A\vee B \vee C, A\to C, B\to C \Rightarrow C$ What I did: $A\vee B \vee ...
5
votes
3answers
106 views

Is there such a thing as the number of axioms?

This question was inspired by this question. Does it really make sense to say that a formal system has some number of axioms, say three, or ten, etc? E.g., take a formal system that admits ...
-1
votes
0answers
33 views

for each of the followingdecide if $\phi$ is a propositional consequence of $\Gamma$ justify your assertion [on hold]

for each of the followingdecide if $\phi$ is a propositional consequence of $\Gamma$ justify your assertion. (a)$\Gamma$ is $\{(\forall x P(x))\rightarrow Q(y) , (\forall x P(x))\vee (\forall x ...
-2
votes
0answers
39 views

Are formulas equivalent? [on hold]

Check if $\forall x (\psi \Leftrightarrow \phi)$ is equvalent to $\psi \Leftrightarrow (\forall x \phi)$ Thanks for help!
0
votes
0answers
21 views

Logic negate and simplify

Negate and Simplify: [(pvq)->~r]v~q Can someone show me step by step how to go about this. I am a little confused about negating over an implication.
2
votes
0answers
25 views

Confusion on particular step in this weak induction proof

I am studying for a midterm, and I came across this proof. Use mathematical induction(weak) to show that for all integers n $\geq$ 2 , if x$_{1}$, x$_{2}$, ... x$_{n}$ are strictly between 0 and 1 ...
0
votes
1answer
25 views

Logical formula with natural numbers

How to write a formula using only quantifiers, variables, brackets, logical operators and $\in$, $\mathbb{N}$, $+$, $\cdot$, $=$, $\leq$ : Among any three natural numbers exist pair of them such ...
1
vote
1answer
23 views

(∀x ∈ X, P(x)) or (∀x ∈ X, Q(x)) ⇒ ∀x ∈ X,(P(x) or Q(x)) where X is nonempty and P(x) and Q(x) are statements.

I know this is an obvious statement but how would one go about in showing that this is true ? My answer is : Consider the 2 cases; Case 1) ∀x ∈ X, P(x) holds. Then clearly ∀x ∈ X, P(x) or Q(x) ...
0
votes
1answer
45 views

Propositional calculus logic question

In my assignment I have the following question: For every proposition $\theta$ let $E(\theta)$ be the set of basic propositions. Prove the following: For every two propositions, $\alpha$ and ...
5
votes
1answer
46 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 ...
0
votes
1answer
61 views

How much conservative ZF+AC and ZF+DC are over ZF?

A logical theory $T_2$ is a (proof theoretic) conservative extension of a theory $T_1$ if the language of $T_2$ extends the language of $T_1$; every theorem of $T_1$ is a theorem of $T_2$; and any ...
-4
votes
0answers
39 views

Counterexample for proof that a number is prime [closed]

Find the counterexamples to the following statement: “If $q$ is an odd positive integer the sum of whose digits is 4 and none of whose digits is 0, then $q$ is prime.
1
vote
0answers
24 views

Some doubts regarding decidable sets

I've been working at one of the problems, related to the decidability. Let's denote $ f: \mathbb{N} \rightarrow \mathbb{N}$ as a computable increasing function, $A \subset \mathbb{N}$ is a ...
1
vote
2answers
24 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
41 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
2answers
29 views

How to find the contrapositive of this statement?

$if \ \ \ \forall a \forall b \in Q, \ \ \ xy \notin Q \ then \ (a \lor b) \notin Q$ I hope I wrote that correctly. In English terms, it would be: " If a and b are real numbers and ab is irrational, ...
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 ...
0
votes
1answer
24 views

How can I translate it into Logic sentence? [closed]

Let $p$ denote "it is snowing." So how can I translate the following into symbolic logic? "It is not snowing, but snowing." Please help me.
2
votes
1answer
54 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...
0
votes
1answer
21 views

Logic proof using contrapositive

If n=ab is the product of two integers $a$ and $b$, then either $a\leq n^{(1/2)}$ or $b\leq n^{(1/2)}$. Use the proof by contrapositive method. The new statement is: if $a>n^{(1/2)}$ or ...
1
vote
2answers
43 views

Prove the two logic expressions are equal

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$ It makes sense when I think about it, but how does one prove it? Also is there a relationship with the above and saying: $(a \implies ...
0
votes
0answers
24 views

Decision method for a partial mapping

Assigned this definition: A decision method for a partial mapping $F$ from $A$ to $B$ is a method which, if applied to an element $a$ of $A$, will give the value $F(a)$ if $a$ is in the domain of $F$ ...
0
votes
4answers
132 views

Two plus two equals four when earth has one moon?

As is well known, we have the least intuitive of basic operations, the 'implication' or '=>'. Consider 'A => B'. Most beginners get stumped on the vacuous truth, that implication could be true even ...
0
votes
1answer
43 views

Logic behind continuity definition.

I have a question regarding the definition of continuous functions : from wikipedia and my book : $f$ is said to be continuous at the point $c$ if the following holds: For any number ...
0
votes
0answers
39 views

Find $\varphi$ of language $L$

I have the following symbols P - functional, airity=2, N - functional, airity=0, J - functional, airity=0, V - predicate, airity=2, K = functional, airity=2. I need to find closed formula $\varphi$ ...
10
votes
0answers
104 views

What does it take to divide by $2$ (or even $3$)?

Theorem 1 [ZFC, classical logic]: If $A,B$ are sets such that $\textbf{2}\times A\cong \textbf{2}\times B$, then $A\cong B$. That's because the axiom of choice allows for the definition of ...
0
votes
1answer
36 views

What does First Godel's Incompleteness theorem mean?

I am terribly confused what really "Incomplete" mean in terms of the Godel's theorem. Does it mean there are some theorems that are definable in First order theory of natural numbers and true but ...