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)

0
votes
2answers
10 views

Question about $p \implies q$ predicate logic

$T$: a set of natural numbers. $S_1$: $2$ is the only prime number that divides elements of $T$. $S_2: T = \{16, 8, 528\}.$ I'm trying to figure out which statements imply each other, i.e., does ...
0
votes
0answers
11 views

Truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ : What should my next step be?

I am working on a truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ This is what I have done so far: My next step would be to do the disjunction from the first two ...
1
vote
1answer
30 views

Theory of definitions

I am reading "Introduction to Logic" by P Suppes at the moment. In the Chapter 8 - Theory of definitions of it, I 've some confusion, actually about the Conditional Definition. The brief explanation ...
2
votes
1answer
26 views

Couple of questions from Takeuti's Proof Theory book

I am reading Gaisi Takeuti's Proof Theory (Second Edition, Dover), and I have a couple of questions: I) Right after the first (1.1.) definition, the author says that "In any case it is essential that ...
0
votes
0answers
23 views

Relations commuting with logical equivalence.

I'm looking for theorems of the form, 'Relation X commutes with logical equivalence', where X is NOT uniform substitution. What's the best place to find such theorems?
-1
votes
0answers
26 views

What does it mean?

I tried to do this but i dont know what it's exactly mean. Please help me someone i have exam soon!
1
vote
2answers
33 views

Negating the Sentence with 'because'

I have to negate the sentence "They pushed us into a big white room and I began to blink because the light hurt my eyes." My main issue is I'm unsure how the word 'because' can be negated. If P="I ...
2
votes
1answer
30 views

Is the $\varphi \to \varphi$ axiom in Hilbert calculus redundant?

When I see the Hilbert calculus in logic, I sometimes notice that $T \vdash \varphi \to \varphi$ is listed as an axiom and sometimes not. Is there some reason? Could I get it somehow from the other ...
0
votes
2answers
29 views

Negate definition of limit [on hold]

The definition for $\lim \limits_{x\to a} f(x) = L$ is the following: For all real numbers $\varepsilon > 0$, there is a real number $\delta > 0$ such that for all real numbers $x$ if $a−\delta ...
2
votes
1answer
13 views

Find X so that $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is contradiction

I have to find X so that this $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is a contradiction. Then I also have to find out whether or not I can find an X is a tautology. What's the most ...
0
votes
1answer
23 views

how to prove $ B = ( \beta \Rightarrow \gamma) \Rightarrow (\alpha \Rightarrow \beta)\Rightarrow \alpha\Rightarrow \gamma $ using natural deduction

I tried to follow a similar question solving another statement using natural deduction but it still seems hard to understand every time I get a different solution I can't figure out a methodology to ...
2
votes
1answer
37 views

Prove $\forall z\left(\left(\exists xA\rightarrow A_{x}[z]\right)\rightarrow B\right)\vDash B$

I'm doing some self-exercises on mathematical logic by myself and have come across this question which I can't seem to prove: Let $A$ be a formula with a single free variable $x$. Let $B$ be a ...
0
votes
1answer
35 views

Negation of uniform continuity

The definition of uniform continuity is: Given any $\varepsilon>0\ \exists\delta>0\ \forall x\in I \ \forall y\in I\ \left(\text{if }|x-y|<\delta\text{ then }\ ...
0
votes
0answers
11 views

EC,PC elementary class,pseudolementary class,omitting types

What are the typical examples of PC (pseudoelementary class) with and without omitting types, which are not elementary with and without the omitting types, respectively?
0
votes
0answers
16 views

Contrapositive/contradiction of statement with quantifiers

In general how does one formulate a proof by controposition or contradiction for the following general form: $\forall x\exists ! y (P(x)\wedge Q(y) \rightarrow R(x,y))$ Or more specifically: $\forall ...
4
votes
4answers
65 views

Show that $(p \to q) \lor (q \to p)$ is a tautology

i tried to prove that $(p \to q) \lor (q \to p)$ is tautology i used p and not-q as conditions. (Premises 1 and 5) I managed to get to a solution but I'm not sure if it's right. can you please check ...
0
votes
2answers
35 views

How can i get a tautology truth table from using 3 variables?

I am looking to use the variables p, q and r to create a truth table which concludes to a tautology.
0
votes
1answer
38 views

Proving an “OR” statement

If one wants to proof $P\vee Q$, is it sufficient to proof $\lnot P \rightarrow Q$? Because it makes intuitively more sense to me that $P\vee Q$ would be logically equivalent with $(\lnot P ...
0
votes
0answers
18 views

How do I prove double negation elimination in a propositional logic axiom system?

Here are my axioms: $X \rightarrow (Y \rightarrow X)$ $(X \rightarrow (Y \rightarrow Z)) \rightarrow ((X \rightarrow Y) \rightarrow (X \rightarrow Z))$ $(\lnot Y \rightarrow \lnot X) \rightarrow ...
-1
votes
0answers
31 views

Double Negation in Propositional Logic [on hold]

Given only modus ponens and the following axioms: $$ (@>(\$>@) \\ (@>(\$>\#))>((@>\$)>(@>\#)) \\ (\sim\$>\sim@)>((\sim\$>@)>\$) \\ $$ How do I show $P$ given ...
0
votes
0answers
24 views

Logic - Is it safe to state the following?

say that ∀x∃y in all possible integers (negative integers, 0 and positive integers) is x*y = x is it safe to say that ∃y∀x is also true. If not can someone explain why its not true. The way I'm ...
3
votes
1answer
78 views

How is induction justified in intuitionistic logic?

This question might be extremely naïve for which I apologise in advance. The induction principle can be stated as: If $A ⊂ ℕ$ such that $1 ∈ A$, and $ν(A) ⊂ A$ (where $ν\colon ℕ → ℕ$ is ...
1
vote
1answer
30 views

Computational tree logic satisfiability.

In the model I pasted above where $S_0$ and $S_1$ are starting states, is the $EXp$ formula satisfiable? $$M,s\vDash EXp$$ Does it have to be satisfiable for all the starting states given the $M$, ...
0
votes
3answers
92 views

If $A\rightarrow B$ and $ C \rightarrow B,$ does $(A \land C )\rightarrow B$ [on hold]

If A implies B and C implies B, do A and C together imply B? I need a clarification regarding this question.
0
votes
1answer
28 views

How to transcribe the following statement into a predicate wff?

There was a disagreement in my college class regarding what the following statement would be in a predicate wff format: It is always a sunny day only if it is a rainy day. Where D(x) is "x is a ...
-1
votes
0answers
74 views

What is a Horn Clause? [on hold]

I am not an expert in Mathematics :) thus if someone can let me know What is a Horn Clause in layman's terms? I know it is used in First order Logic but I am unable to understand what is it and how to ...
0
votes
1answer
57 views

A version of Zorn's lemma

The version of Zorn's lemma that I have found more often is Zorn's Lemma (1) If every chain belonging to the partially ordered set $S$ has an upper bound in $S$ then $S$ contains a maximal ...
2
votes
2answers
61 views

Principle of explosion: Other arguments?

I've come across a proof-theoretic argument for explosion on Wikipedia, which is as follows: $A \ \ \wedge\sim A$ $A$ $ \sim A$ $ A \lor B$ $B$ $(A \ \ \wedge \sim A) \implies B$ I've thought of ...
2
votes
2answers
39 views

Logic - Logically implies question

$\forall x(A(x) \rightarrow B(x))$ logically implies $\exists x(A(x) \land B(x))$ Is the above statement true or false? I have no clue on how to start figuring this out. Can someone help me please?
3
votes
2answers
90 views

Logic - how to write $\exists !x$ without the $\exists !$ symbol [duplicate]

What is $\exists !$ equivalent to? I need to write $\exists !x \,P(x)$ without using the $\exists !$ symbol; thus, I am wondering what the $\exists !$ symbol is equivalent to.
3
votes
2answers
28 views

Difference between “necessary” and “necessary but not sufficient”?

This is from Discrete Mathematics and Its Applications: Let $p, q,$ and $r$ be the propositions: $\quad p:$ Grizzly bears have been seen in the area. $\quad q:$ Hiking is safe on the ...
0
votes
1answer
35 views

Question about mathematical logic ∀x ∈ S, ∀z ∈ S, ∃y ∈ C

∀x ∈ S, ∀z ∈ S, ∃y ∈ C,(x != z) ⇒ ¬(T(x, y) ∧ T(z, y)) I'm trying to express this in English, but I can't use the variables x or y in my sentence. Basically it means for elements x in S, and all ...
0
votes
1answer
30 views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
1
vote
2answers
43 views

Proving contradiction with logical identities

We know that p → q is not equivalent to q → p. But suppose we make a proof system that has all the rules of logical identities plus the rule (“commutativity of implies”) p → q ≃ q → p. (We are using ...
1
vote
3answers
319 views

Is there a quicker way to check if this proposition is self contradictory?

I have been trying to refresh my memory with regards to classical logic. As a result, I am currently going over the basics. The following proposition seems to be false in all possible worlds. ...
-2
votes
0answers
15 views

Give an example of two relational systems $A$ and $B$ and a homomorphism $h : A\rightarrow B$, which is not a strong homomorphism. [on hold]

Give an example of two relational systems $A$ and $B$ and a homomorphism $h : A\rightarrow B$, which is not a strong homomorphism.
0
votes
2answers
68 views

Can anyone help me with a solution? [on hold]

Write down the assumptions in a form of clauses and give a resolution proof that the proposition $$\Big((p \rightarrow q) \land ( q \rightarrow r) \land p \Big) ...
31
votes
13answers
3k views

An easy example of a non-constructive proof without an obvious “fix”?

I wanted to give an easy example of a non-constructive proof, or, more precisely, of a proof which states that an object exists, but gives no obvious recipe to create/find it. Euclid's proof of the ...
2
votes
1answer
17 views

What is the difference between weak and strong completeness in many valued logic?

I know a bunch of facts about weak and strong completeness in many valued logic, that there is strong completeness for the finite mv logic, and that for the infinite ones you can either only have weak ...
0
votes
2answers
55 views

Can someone verify my assertion from this english sentence? [duplicate]

This is from Discrete Mathematics and its Applications This is the book means when mentions a list of common ways to express conditional statements After going through the list, I immediately ...
2
votes
4answers
58 views

Clarifying on how if p,q is logically equivalent to p only if q [duplicate]

Here is what my book says about the different ways implications are worded I am struggling with how "if p, then q" is logically equivalent to "p only if q" The example I came up with With "if ...
0
votes
1answer
28 views

How to tell the difference between interval and coordinate notation from context?

I am working on a practice problem with sets. (the answer key) At first I was confused by the notation Ai = (0,i), i is a natural number. I looked up the use of paranthesis and saw that they could ...
2
votes
1answer
43 views

Please help me to understand domain of interpretation

In the literature on Description Logic, when interpretations are explained, we encounter expressions like, $$\mathcal{I} = (\Delta^\mathcal{I}, \cdot^\mathcal{I})$$ (Actually, I am talking about, ...
1
vote
1answer
32 views

Negation of a Statement with Quantifiers — If Then?

I need to find the negation of a statement on my homework, specifically problem 19 of secton 3.2 in Discrete Mathematics with Applications by Susanna Epp. The problem is as follows: \begin{align} ...
2
votes
1answer
41 views

How to adapt proof by contradiction showing that a sqrt(2) is irrational for sqrt(20)?

This example is from Discrete Math and its Applications I understand the steps the author is taking. First he assumes sqrt(2) is rational meaning that there exists integers a, and b such that ...
2
votes
1answer
38 views

Show that the conditional statement is a tautology without using a truth table

I have been attempting to use identities to get to the answer but I am unable to get anywhere. Here is the equation I am trying to prove tautological without using truth tables: $[(p\rightarrow q) ...
0
votes
0answers
18 views

Is it necessary to write out the whole truth table to show system specification is consistent?

This is an example from Discrete Mathematics and its Applications Basically the way I see this problem is "is there a combination of propositions that will make all of these specifications true". ...
5
votes
1answer
90 views

How can you come to the truth of a statement without proving it?

I was reading a bit about Gödel's incompleteness theorems. I haven't took the time to really study it, but I'm very curious about statements like these: In other words, if our axioms are ...
1
vote
1answer
38 views

What is the difference from a theorem and a meta-theorem?

I'm confused about what a meta-theorem exactly is and if a meta-theorem can be used to prove a theorem. To illustrate my confusion i give an example. Given the three statements: Every vector space ...
2
votes
1answer
33 views

odd logical structures

How you find contrapositive and converse of these sentences. Only if John chops down the tree, will he be a lumberjack. You can't win if you don't fight. All people that root for the Ducks are from ...