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)

2
votes
6answers
107 views

Showing that $\lnot Q \lor (\lnot Q \land R) = \lnot Q$ without a truth table

I've done a truth table after reducing it to this and it seems to be equal to $\neg Q$: $$\lnot Q \lor (\lnot Q \land R) = \lnot Q$$ But when I try to show it without a truth table (with just ...
0
votes
4answers
32 views

Can $(A \lor B) \land (\lnot A \land \lnot C)$ be more simplified?

Can $(A \lor B) \land (\lnot A \land \lnot C)$ be more simplified/expanded? With a kind of distributive property?
0
votes
0answers
14 views

If $P$ a probability of a sentence to be true, then $\{P(\phi | T_i)\}_{i \in \mathbb{N}}$ is a martingale over constructed theories $T_i$

I am reading Section 2.1 of Definability of Truth in Probabilistic Logic. For a language $L$, fix a probability distribution $P:L \to [0,1]$. Enumerate sentences $\phi_1, \phi_2, \ldots$ of a ...
13
votes
7answers
2k views

Why do statements which appear elementary have complicated proofs?

The motivation for this question is : Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $[a,b]$ and some other problems in Mathematics which looks as if they are elementary but their ...
0
votes
1answer
33 views

Use Resolution to proove a sentence in First Order Logic

I was just wondering if anyone could tell me if I've solved this problem right. If wrong, I would like to know what I did wrong. "Use resolution to prove Green(Linn) given the information below. You ...
2
votes
2answers
72 views

A question on empty set and Russell's paradox

Suppose $S$ is a well-defined set and $A$ is meant to be a subset of $S$ that is defined as follows: $A = \{x|(x\in S)\wedge(x\not\in S)\}$. Is $A$ the empty set $\varnothing$, since it is based on ...
0
votes
1answer
46 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= $p(n)$ for $n=1$ or any ...
0
votes
1answer
35 views

Did I do this big-Omega proof correctly?

Prove or disprove: 6n^3 – 4n^2 + 3n +2 is in Ω (5n^3 – n^2 + n +1). So I'm not sure if I did this right or not, any pointers or the correct steps would be helpful Ǝc ∈ ℝ+, ƎB ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ ...
0
votes
1answer
27 views

Big-Omega proof using L'Hopital's Rule?

Prove or disprove: $15n^2$ is in $\Omega(3 \times 2^n)$ So we'd have to prove or disprove this statement: $$ \exists c \in\mathbb{R}^+,\,\exists B\in\mathbb{N}, \forall n \in\mathbb{N}, n ≥ B ...
0
votes
0answers
55 views

Symbol for “Take Highest Number”

As the title states, is there a symbol for taking the highest value? Let's say we have two variables $a=2$ and $b=3$ now I want $aXb$ (where $X$ is the symbol I am looking for) and I want that answer ...
0
votes
4answers
41 views

proof for a problem in propositional logic

I cant find a proof for given problem: $$p \to ( q \to p) ≡ \lnot p \to ( p \to q ) $$ Please give proof to prove above statement.
1
vote
4answers
141 views

Could the Riemann hypothesis be provably unprovable?

I don't know much about foundations and logic, so I ask forgiveness if my question is just plain stupid. Assume we have a statement of the form: There exist no $x\in X$ such that $P(x)$. where ...
3
votes
3answers
102 views

Disproving $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$

Let $A,B,C$ be any sets. Tell if $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$ is true or false. I tried to prove by absurd. Suppose $A \subset B \wedge B ...
4
votes
1answer
80 views

Are there non-equivalent cardinal arithmetics?

‎Generalizing a concept in mathematics is always a problematic situation. In most cases there are several ways to generalize a notion and it is not easy to decide if a particular generalization is ...
0
votes
0answers
30 views

Predicate logic ∀x.∃y.≥(x,y) [on hold]

∀x.∃y.≥(x,y) (1) ∃y.∀x.≥(x,y) (2) a) translate this in a sentence b) is (1) true, is (2) true c) is (1) ⊨ (2) true, is (2) ⊨ (1) true d) prove (1) ⊨ (2) thanks
-2
votes
2answers
58 views

Combinatorics homework problem [on hold]

In how many ways can $23$ different books be given to $5$ students so that $2$ of the students will have $4$ books each and the other $3$ will have $5$ books each?
0
votes
2answers
385 views

Writing a boolean formula and logic circuit that computes mux

Let $mux(p_{11}, p_{10}, p_{01}, p_{00}, x_1, x_0) = P_{x1x0}$ (with all variables bits). Write a boolean formula, and then draw a circuit, that computes mux. For ...
4
votes
5answers
72 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...
2
votes
2answers
36 views

How would you prove in FOL that x is a member of {x} for all x?

How can I formulate and prove the following in first-order logic? $$\forall x (x\in \{x\})$$ I have the following two statements: member(x,$\alpha$) $\neg \exists y(\text{member}(y,\alpha )\land ...
4
votes
2answers
44 views

Formula for perfect squares spectrum.

I have been working on exercises from "A first Course in Logic" by S. Hedman. Exercise 2.3 (d) asks to find a first-order sentence $\varphi$ having the set of perfect squares as a finite spectrum. But ...
3
votes
2answers
39 views

origin of syntax for mathematical equations

Bear with me, I don't have any formal training in mathematics. I wonder if there is something that accounts for the syntax of mathematical equations, some deeper logic or reasons why I know that ...
10
votes
0answers
123 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 ...
5
votes
1answer
54 views

Proper use of implication and equivalence

I think I have a pretty good understanding of implication and equivalence (I also found this question), but there are some things I am unsure about. First of all, in maths class in high school, when ...
1
vote
1answer
36 views

Proof of $p\rightarrow (\Box (\Box p \wedge p) \rightarrow (\Box p \wedge p))$

I need to prove: $$p\rightarrow (\Box (\Box p \wedge p) \rightarrow (\Box p \wedge p))$$ The system contains all propostional tautologies and the axiom scheme $\mathbf K$:$ \Box(p \rightarrow q) ...
0
votes
1answer
36 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem: Each of the K knights from the round table needs to choose a card which is marked with a number from 1 to N, N >= K. The cards all have different number. ...
2
votes
2answers
135 views

How to derive $\exists$ Elimination rule in Enderton's system

I'm trying to derive the following rule : from $α→β$, infer $(∃x)α→β$, provided that $x$ is not free in $β$ in the system of Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001). ...
5
votes
1answer
224 views

Difference between elementary submodel and elementary substructure

This is a really "elementary" question, forgive the pun. What is the difference between an elementary submodel and an elementary substructure (in first-order Logic)? Sincere thanks for help.
1
vote
1answer
60 views

Intuitive diagrams for models of non-well founded set theory

Based on our intuition about von-Neuman's rank, there is a standard view to describe a model of ZFC as a large V-shape world. When we remove the Axiom of Foundation (AF) from ZFC and replace it with ...
1
vote
0answers
27 views

Given an open statement determine if their quantification is true

The Question My Work/Question My book says for part a, iv is true. I disagree. To show an existential statement is false we have to show that for all x that statement is untrue. There are no ...
0
votes
0answers
33 views

Calculation: Emotional Contagion [on hold]

Can someone help me with this calculation? If 1 person impacts the emotions of 100 others, and each of those other 100 also impacts the emotions of 100 others, and so on, how many people are impacted ...
1
vote
2answers
54 views

Consider $(\mathbb N, +)$ as a model for the language with one binary function $+$ . Are the following statements true?

Consider $(\mathbb N, +)$ as a model for the language with one symbol $+$ for a binary function. Are the following statements true? $(\mathbb N, +) \vDash \forall x \exists y \forall z\ x + y\neq z$ ...
2
votes
1answer
33 views

How to deal with long and tedious logic problem? [on hold]

I am always pretty bad at logic problems. Because most of the logics used aren't really logical (to me)So, as you might think, a long logic problem only adds to it already boring nature. The ...
1
vote
0answers
33 views

Show that all recursively enumerable sets are definable in arithmetic [on hold]

This is taken to be a given in most proofs and textbooks - can somebody prove this. Thanks
0
votes
1answer
17 views

A predicate logic question about write down a sentence

Let $\mathcal{L}=\{f\}$ be a first-order language containing a unary function symbol f, and no other non-logical symbols. Write down sentences $φ$ and $ψ$ of $\mathcal{L}$ such that for any ...
0
votes
2answers
53 views

Let $\Gamma = \{\exists x \forall y (x\mathrel R y),\exists x \forall y(y\mathrel R x),\forall x\exists y(x\mathrel R y)\}$. Is $\Gamma$ consistent?

Consider the language consisting of one symbol $R$ for a binary relation. Let $\Gamma = \{\exists x \forall y (x\mathrel R y),\exists x \forall y(y\mathrel R x),\forall x\exists y(x\mathrel R y)\}$. ...
-3
votes
1answer
117 views

SEVEN - NINE= EIGHT [on hold]

Things are not always what they seem. What is true from one point of view may be false from another and vice-versa, and here is a puzzle to prove it. Despite the fact that every arithmetic teacher in ...
3
votes
1answer
30 views

How to negate $\forall A. \exists a,b. a \neq b \land a,b \in P(A)$?

$$ \forall A. \exists a,b. a \neq b \land a,b \in P(A) $$ My intuition tells me it is false, because given $A=\emptyset$, then $P(\emptyset) = \{\emptyset\}$, so $a=b=\emptyset$. I proceeded to ...
0
votes
1answer
41 views

If $a+b \geq x$ is known to be true does that mean $a+b\geq x-1$ contradicts it?

So I was proving something and I'm wondering if this line of argument is correct. Suppose that it is true that given conditions $M,N,O$; $a+b\geq x$. That is given those conditions the minimum value ...
0
votes
0answers
20 views

How to recognize if a there is a logical entailment?

I have evaluated each of the formulas in gamma and they are not tautologies. Then, I have no idea... Can someone help?
-1
votes
0answers
22 views

Equivalent sentences using logical connectives

Using only logical connectives implication ($\to $) and negation ($\lnot $), write a sentence equivalent to the sentence: $$ (p \land q ) \lor r $$ Using logical connectives disjunction ($\lor$) ...
0
votes
0answers
33 views

show that if A is creative then A is not computable

show that if $A$ is creative then $A$ is not computable? proof:If A is computable the $A$ andn the complement$A$ are computable enumerable. and $A$ is creative so there was a recsive function ...
0
votes
0answers
64 views

Let Γ = {p∧q,(¬p)∨q,p∨r}. Is it true that Γ ⊢ r?

I"m not sure how to solve this type of question. Here is the problem in more detail, and a similar problem: I know that given this set of formulas I'm supposed to show if its possible to deduce r ...
-8
votes
0answers
67 views

P=NP and human thought [on hold]

I've been thinking about P=NP a lot, and wonder if there could be a new type of math created - like 23 would equal two plus three, two minus three, two times three, and two divided by three, etc. So ...
0
votes
1answer
28 views

what is the meaning of this predicate statement

This question appeared in the GATE exam 2011 Q.32 Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate P(x) = ...
0
votes
2answers
59 views

Finding a formal deduction from an empty set of premises

I can't seem to make sense of any of this. I'm given a set of axioms schemes, modus ponens as the inference rule and I'm supposed to find a formal deduction. The question (question 1) is here. It ...
0
votes
2answers
45 views

what happens in a universal implication when the premise is false

I have just started learning Mathematical logic and couldn't figure out the answer to the above question . my question is what happens to the truth value if the premise in a universal implication is ...
5
votes
2answers
2k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
1
vote
2answers
27 views

How to specify each digit of a real number in decimal representation in set theory?

So real numbers have decimal representations. If you want to say the $n$th digit of some real number, how do you say this formally in set theory?
66
votes
4answers
7k views

How do I convince someone that $1+1=2$ may not necessarily be true?

Me and my friend were arguing over this "fact" that we all know and hold dear. However, I do know that $1+1=2$ is an axiom. That is why I beg to differ. Neither of us have the required mathematical ...
-2
votes
1answer
27 views

a formal logic proposition about real numbers

I have the following informal statement about real numbers: Every real number except zero has a multiplicative inverse. Can this be expressed as: $$ \forall x \exists y(x\neq 0 \implies xy=1) ...