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
0answers
52 views

On correctness of induction proof

I want to prove a certain property $\mathsf{P}$ on every multiaffine polynomial in $\Bbb R[x_1,x_2,\dots,x_{n-1},x_n]$. Supposing I show property $\mathsf{P}$ to be valid at $n\geq9$ variable ...
2
votes
2answers
52 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
20 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} ...
1
vote
1answer
28 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) ...
2
votes
1answer
29 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 ...
0
votes
0answers
10 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
80 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
36 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
29 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 ...
2
votes
1answer
38 views

How can I prove this relation between the elementary set theory and the elementary logic?

If you need to prove an equality like $A\Delta B=(B\setminus C)\cup[C\cap (B\Delta A)]$ we can first prove $p\underline{\lor} q\Longleftrightarrow (q\land\overline{r})\lor(q\underline{\lor}p)$ (with a ...
0
votes
1answer
18 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
1answer
46 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 ...
0
votes
0answers
30 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
35 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
0
votes
0answers
20 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 ...
-5
votes
1answer
25 views

Prove the statement. Logic and Set Theory. [on hold]

There are no natural numbers that are squares and differ 5.
3
votes
2answers
33 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} ...
2
votes
3answers
193 views

When and where the concept of valid logic formula was defined?

I was stimulated by a recent question about Gödel Completeness Theorem. All my citations are from Jean van Heijenoort (editor), From Frege to Gödel : A Source Book in Mathematical Logic (1967). ...
1
vote
1answer
33 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
35 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 ...
1
vote
1answer
29 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: ...
1
vote
1answer
33 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 ...
2
votes
4answers
120 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
91 views

Verify these logical equivalences by writing an equivalence proof?

I have two parts to this question - I need to verify each of the following by writing an equivalence proof: $p \to (q \land r) \equiv (p \to q) \land (p \to r)$ $(p \to q) \land (p \lor q) \equiv q$ ...
0
votes
0answers
25 views

Logic problems and Venn Diagrams [on hold]

In a class of 32 pupils: 5 pupils live in New Town, travel to school by bus and eat school dinners. 3 pupils live in New Town, travel to school by bus but do not eat school dinners. 9 pupils do not ...
23
votes
0answers
448 views

What does it take to divide by $2$?

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
50 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 ...
1
vote
2answers
35 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
78 views

Brute-force searches for counterexamples

Gödel's completeness theorem says that for every statement in first-order predicate caluculus with equality, there is either a proof that it holds in all structures, or a counterexample --- a ...
0
votes
1answer
65 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 ...
-3
votes
1answer
25 views

boolean simplification , help please [on hold]

If we begin with $\;\bar A\,\bar C+ \bar B\,\bar C + A\, B\;$ how can we transform to $\;\bar B \, \bar C + B \,\bar C + A\, B\;$. I'm so lost please help.
0
votes
3answers
32 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.
-5
votes
0answers
85 views

There is a student who has been in at least one room of every department - formalize this [on hold]

My teacher gave me this exercise to do, but noone in my class has any idea how to solve it. So I would require some help, please, and maybe also an explanation.
1
vote
1answer
58 views

Proof in sequent calculus without cut

I met an exercise in Gaisi Takeuti, Proof Theory [Exercise 2.7, page 14]. How to construct a cut-free proof of$\ \forall xA(x)\rightarrow B\vdash \exists x(A(x)\rightarrow B)$, where A(a) and B are ...
-1
votes
1answer
60 views

Write theorem conditions concisely

Let $Z$ be a set, $x$ be some object. Let the following statements hold (for some logical formulas $P,P_1,\dots,P_n$ and some logical formula $Q$): $\forall z\in Z:(P(x) \Leftrightarrow Q(x,z))$ ...
2
votes
1answer
62 views

Interpreting logical forms involving quantifiers

I have been trying to translate these two logical form into English statements without using any quantifier laws: (a) ∃x∀y ¬L(x,y) (b) ¬(∃x∀y L(x,y)) where ...
1
vote
1answer
31 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 ...
1
vote
1answer
24 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
1answer
34 views

Functions and Relations Predicate logic

If we are given a set universal set $U$ and another set $X$, how do we know if the given set $X$ is a relation on $U$ or a function on $U$ ?
1
vote
1answer
403 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
0
votes
0answers
90 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
22 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 ...
0
votes
0answers
32 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 ...
1
vote
2answers
69 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
4answers
102 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 ...
2
votes
1answer
60 views

Extension of theory

There are two languages $L_1=\{+\}$ with equation, where nonlogical symbol is binary function. There are formulas: $$φ≡∃n∀x(n+x=x)∧∃n∀x(x+n=x)$$ $$ψ≡∃n∀x(n+x=x∧x+n=x)$$ There are theories $T_1={φ}$, ...
3
votes
1answer
43 views

$A\cong B$ then $Th(A)=Th(B)$

question: $A\cong B$ then $Th(A)=Th(B)$ answer: $\phi \in Th(A)$ then $A\vDash \phi$ and $A\cong B$ so we have $B\vDash \phi$ then $\phi \in Th(B)$ and $Th(A)\subseteq Th(B)$ and we could prove ...
9
votes
2answers
533 views

Is there a mistake in the SEP article about Godel's Incompleteness theorems?

Update: The mistake referred to in this question has now been corrected. The below refers to a previous version of the article: The second supplement to the Stanford Encyclopaedia of Philosophy ...
0
votes
2answers
39 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
5answers
305 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 ...