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)

42
votes
14answers
4k 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 ...
3
votes
1answer
258 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
1answer
115 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
99 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 p,...
0
votes
1answer
288 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
63 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, ...
3
votes
1answer
500 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
1k 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) \...
5
votes
2answers
154 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 ...
2
votes
1answer
221 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
40 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 ...
0
votes
2answers
90 views

What is a predicate exactly in predicate logic?

I have been reading Predicate Logic couple of days and while everything has been pretty intuitive so far I understood that I do not exactly understand what the predicate is. This became clear after I ...
0
votes
0answers
121 views

Use rules of inferential logic for the following problem..

Here I have such a question related to laws of inference. The question asks to prove using the laws of inference (these rules) that the following facts give a certain conclusion. So the question is: ...
1
vote
2answers
68 views

Propositional Logic : Absorption - Why is it so?

Why is the Absorption Law of Propositional Logic so ? p $\lor (p \land q) \equiv$ p Would appreciate an intuitive explanation and not one using a Truth Table
3
votes
2answers
47 views

Is my deduction of $t$ being true logically correct?

According to the problem on my homework (yes, this is my homework), number 42 in chapter 2.3 of Discrete Mathematics with Applications by Susanna S. Epp, the following are true: \begin{align} a.)&\...
2
votes
0answers
40 views

Does the class of all periodic subsets of $\mathbb{Z}$ of peroid greater than $k$ form a field of sets?

We say that a subset $X\subseteq \mathbb{Z}$ is a periodic subset of $\mathbb{Z}$ of period $k$ if the set obtained from $X$ by adding $k$ to each element of $X$ is $X$ itself. Does the class of all ...
1
vote
1answer
58 views

Why is the set of all true first-order statements about non-negative integers in the language with only equality, $+$ and $\times$ undecidable?

Apparently Tarski and Mostowski proved this, but intuitively I'm not seeing the difference between statements in a language of non-negative integers with equality, addition, and multiplication vs ...
0
votes
2answers
314 views

What is the difference between a counter-intuitive statement and a paradox?

In mathematics and logic, what is the difference between a counter-intuitive statement and a paradox? For example, what differs something like the Banach-Tarski theorem or Gabriel's horn from ...
0
votes
1answer
132 views

L-sentence which expresses bijective function

I've stumbled upon this exercise from "Sets, Models, Proofs" and can't seem to find a solution. It goes like this: Let $L$ be a language with just one 1-place function symbol $F$. Give an $L$-...
1
vote
1answer
109 views

Use logical equivalencies to classify as tautology, contradiction, or contingency.

Classify the following as tautologies, contradictions or contingencies using logical equivalences. Can anyone let me know what I'm missing or doing wrong? I got stuck, here is what I have so far: $\...
3
votes
4answers
498 views

Meaning of symbols $\vdash$ and $ \models$

I'm confused about the use of symbols $\vdash$ and $ \models$. Reading the answers to Notation Question: What does $\vdash$ mean in logic? and What is the meaning of the double turnstile symbol ($\...
0
votes
1answer
400 views

Use inference rules to prove distributive law

I'm taking an intro logic course this semester and my prof is hard to follow and not really great at clarifying things. I'm stuck on this question in my assignment, I'm just not sure how to start. I ...
0
votes
1answer
169 views

Discrete Math Predicate Logic

Consider truth assignments involving only the propositional variables $x_0, x_1, x_2, x_3$ and $y_0, y_1, y_2, y_3$. Every such truth assignment gives a value of $1$ (representing true) or $0$ (...
0
votes
3answers
41 views

Discrete Math Logical Equivalence

x∧ ∼ y → ∼ z is logically equivalent to x ∧ z → y. I can't figure it out, especially the negations are throwing me off.
1
vote
2answers
51 views

Logical form of statement

I'm reading the book How to Prove It and a question is given to write out the logical form of the below definition in set-theoretic notation. Definition: $y \in \{\sqrt[3]{x} \mid x\in\mathbb{Q}\}$ ...
1
vote
1answer
92 views

Order of quantifiers

I was reading about quantifiers from this book. I decided to jot down all implications due to different orders of quantifiers. While talking about the orders of the quantifiers the author states ...
1
vote
1answer
483 views

Convert universal quantification to existential quantification

I came across following problem "Every intelligent student is not honest." And I have to convert this in quantifiers. Straight conversion will be: ∀x [(S(x)∧I(x)) → ¬H(x)] ...(i) However the ...
0
votes
0answers
101 views

Question about the foundation of mathematics [duplicate]

I have studied mathematical logic and set theory as an undergraduate. I studied mathematical logic (propositional and predicate logics) before set theory. When I studied mathematical logic, I was a ...
0
votes
1answer
26 views

I need to relate strings of implications.

Let's say we have a string of implications $p_0\Rightarrow p_1\Rightarrow\cdots\Rightarrow p_n$. What can be said about $p_n\Rightarrow p_{n-1}\Rightarrow\cdots\Rightarrow p_0$ from the original ...
1
vote
2answers
138 views

First Order Logic vs First Order Theory

What is the difference between a First Order Logic and a First Order Theory. Can anybody please describe what each one precisely (formally) is? For a bit more elaboration on the question, I think ...
1
vote
1answer
35 views

Using quantifier get truth value

In each case below say whether the given statement is true for whcih universe $(0,1)={{(x\in R: 0<x<1})}$ $[0,1]={{(x\in R: 0\le x \le1})}$ $\exists y(\forall x( x>y)$ This means there ...
0
votes
0answers
50 views

How do we express higher arity predicates and functions in terms of membership?

It's been noted by others that higher order logic is similar to set theory. We can express the second order statement $\forall$R$\forall$x(R(x)) as a first order statement $\forall$R$\forall$x (x $\in$...
1
vote
5answers
522 views

Which can be logically inferred from the given statements?

All women are entrepreneurs. Some women are doctors. Which of the following conclusions can be logically inferred from the above statements? (A) All women are doctors. (B) All doctors are ...
0
votes
2answers
82 views

Show this language structure models this sentence.

In an effort to educate myself, I am attempting the second problem in first chapter of the book "Model Theory" by Marker. The problem is reproduced below: Let $\mathcal{L} = \{\cdot, e\}$ be the ...
1
vote
1answer
90 views

Show every boolean combination of $\mathcal{L}$-formula is equivalent one with quantifiers.

This is part 2 of a question I asked here: Prove this claim about language and structures. The setting is that suppose $\phi_1,\ldots,\phi_n$ are $\mathcal{L}$-formulas and $\psi$ is a Boolean ...
4
votes
2answers
231 views

Proof by Iteration

It seems that I suffer the "too-much-logic-too-pedantic-too-confused"-disease. (You know? This very disease which lets you doubt everything and lets you yell for formalized proof. It's annoying, ...
2
votes
2answers
166 views

First-order logic representation

I am having trouble translating these clauses to first order logic. 1) The only difference between a cat and a tiger is that a tiger kills. 2) If someone likes only people of the same sex then he is ...
1
vote
1answer
107 views

Prove this claim about language and structures.

I have a very thin background in logic and I am attempting the first problem in first chapter of the book "Model Theory" by Marker. The problem is reproduced below: Suppose $\phi_1,\ldots,\phi_n$ are ...
1
vote
5answers
669 views

Necessary but not sufficient in logic

I am working through sample questions and am having a bit of trouble understanding the solution. Write using logical connectives: p : Grizzly bears have been seen in the area. q : Hiking is safe on ...
1
vote
1answer
39 views

Is it impossible for a quantifier-free formula to contain free variables?

A first-order language must specify its signature to fix its alphabet of non-logical symbols. A signature $\Sigma$ contains the set $\Sigma^F$ of function symbols and the set $\Sigma^P$ of predicate ...
0
votes
1answer
64 views

Determining the equivalence of different subsets, unions and intersections?

I'm currently working on some discrete mathematics work and I've encountered a question I'm not sure how to answer exactly. Precisely, I'm trying to prove that three separate statements are logically ...
1
vote
1answer
128 views

Write the proposition in words - $\urcorner\left(\forall x P\left(x\right)\right)$

Hi here is the problem and my answer attempt. $\urcorner\left(\forall x P\left(x\right)\right)$ Let P(x) denote, "x is taking a math science course". Domain is the set of all students. Write the ...
1
vote
1answer
62 views

Are these two statements logically equivalent?

Are the statements $D \Rightarrow H \vee S$ and $(D \Rightarrow H) \vee (D \Rightarrow S)$ logically equivalent?
3
votes
2answers
685 views

Why don't we use Presburger's arithmetic instead of Peano's arithmetic?

I was reading about quantifier elimination and discovered the Presburger Arithmetic, the article mentions two points about it: It is decidable, complete and consistent. It omits multiplication ...
3
votes
1answer
44 views

prove that $\Sigma \vdash \phi_1$ and $\Sigma \vdash \phi_2$ leads to $\Sigma \vdash \phi_1 \wedge \phi_2$.

I try to prove that if $\Sigma \vdash \phi_1$ and $\Sigma \vdash \phi_2$ then $\Sigma \vdash \phi_1 \wedge \phi_2$. Notice that, the ONLY rule of inference of the system is modes ponens and the set ...
0
votes
1answer
50 views

prove this theorem $\vdash (\exists x_i (A\to B)\to (A\to \exists x_i B))$

Here is my thought to prove the theorem we should get $\{\exists x_i (A \to B), A\} \vdash \exists x_i B $ then, I don't know how to process...
0
votes
2answers
2k views

Discrete Math - Determine if the argument is valid

Can you guys please check my work and syntax. Question: Determine if the argument is valid. p $\rightarrow $ q $\underline{\urcorner{q}}$ $\therefore \urcorner$p Answer: T $\rightarrow $ T $\...
0
votes
1answer
108 views

Discrete Math - Determine truth value of each proposition

If 3 + 5 < 2, then 1 + 3 $\neq $ 4 Can someone kindly check my work? Let p: 3 + 5 < 2 and q: 1 + 3 $\neq $ 4 (3 + 5) < 2 $\rightarrow$ (1 + 3) $\neq$ 4 8 < 2 $\rightarrow $ 4 $\neq $ ...
1
vote
1answer
98 views

Expressing continuity and differentiability in a given language

Let $f,g$ be binary function symbols, $P$ a binary predicate symbol, $c,d$ constant symbols and let $\mathcal{L} := \{f,g;P;c,d\}$. Consider $\mathcal{R}:=\langle\mathbb{R};+,\cdot;<;0,1\rangle$ ...
1
vote
2answers
236 views

What are some applications of model theory?

In an attempt to "broaden my horizons", I am taking a class on model theory, which follows this book: http://u.math.biu.ac.il/~dahari/download/Mathematical%20Logic/Elad%2022.pdf Skimming through the ...