Questions about 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
7 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
0
votes
0answers
15 views

Trying to justify each step correctly in proof sequence

I am trying Justify each step in the proof sequence below for correctly with [A → (B ∨ C)] ∧ B' ∧ C' → A' So I justified my steps here but I am not sure at 1 to 3 if I did it correctly. A → (B ∨ ...
5
votes
0answers
91 views

A transfinite epistemic logic puzzle: what numbers did Cheryl give to Albert and Bernard?

I expect that nearly everyone here at stackexchange is by now familiar with Cheryl's birthday problem, which spawned many variant problems, including a transfinite version due to Timothy Gowers. In ...
3
votes
1answer
42 views

What are the L-sentences that are true in an empty structure?

I am looking for an algorithm or set of rules to figure out whether a sentence (in first order logic) is true when we are dealing with an empty set as domain. Clearly, it has to be a sentence (no free ...
0
votes
1answer
27 views

Negation of “Diane rode her bicycle 100 miles on Sunday”

Let P : Diane rode her bicycle 100 miles on Sunday. The negation of P will be: It is not the case that Diane rode her bicycle 100 miles on Sunday. Can the negation of P be expressed in a simpler ...
-2
votes
2answers
21 views

Prove tautology by using boolean laws $\neg q \to \neg(q\wedge(p\to\neg q))$

$$\neg q \to \neg(q\wedge(p\to\neg q))$$ Please help me to prove if it's tautology or not by using the logic law.
2
votes
0answers
51 views

Is $\forall n\exists m:\, m^2=n,\text{ where }m,n ∈ \mathbb N$ true or false?

$\forall n\exists m:\, m^2=n,\text{ where }m,n ∈ \mathbb N$. Prove whether this expression is true or false. My attempt: False, take $n=3,$ then there is no such integer $m$, such that $m^2=3$. Thus, ...
0
votes
0answers
44 views

If I have propositions $P,Q$ and I want to prove $P \longrightarrow Q$ [on hold]

If I have propositions $P,Q$ and I want to prove $P \longrightarrow Q$ and I do so with logical deductions, but every step uses an $\text{if and only if }(\iff)$. Does that mean I actually proved ...
3
votes
1answer
63 views

No Borel well-order of the reals?

I'm told there is no Borel well-order of the reals (in ZFC). I'm told, in fact, that this is because of Borel determinacy. However, this is usually a vague handwave of the form (a) take the usual ...
2
votes
1answer
38 views

Why do we need ultrafilters to make sense of the cartesian product of $\mathcal{L}$-structures

I'm trying understand why we need ultrafilters in model theory. Here is how I see things. Could someone tell me if this is correct ? Further explanations are always welcome. Let $\mathcal{L}$ be a ...
0
votes
0answers
22 views

What is Val m,s in Logic, and what does it really mean?

My Logic lecture notes are full of Theorems and Corollaries showing different calculations using Val m,s (....) but what exactly does it mean? I cant seem to find a clear, concise explanation ...
-4
votes
0answers
48 views

Will this happen, if this happens? [on hold]

If a monkey takes over the universe, will all monkeys on Earth die? Answer this question, yes, no, or unable to be determined. I believe that the answer to this question can NEVER be determined, ...
3
votes
2answers
109 views

Do we know if the consistency of $ \mathsf{ZFC} $ is sufficient to prove that $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) \to \mathsf{SM} $?

This is basically a sequel to this earlier post. There, I asked: If $ \mathsf{ZFC} $ is consistent, then is $ \mathsf{ZFC} \nvdash \neg \text{Con}(\mathsf{ZFC}) $, i.e., $ \neg ...
5
votes
9answers
197 views

If $4=5$, then $6=8\,$ (yes or no?)

I had an argument with a friend about the statement in the title. I asserted that if $4=5$, then $6=8$, as you can derive any conclusion from a false statement. However, he does not agree, and claims ...
0
votes
0answers
23 views

Adding Sentence Variables and Quantifiers to Formal Languages

I have been thinking about the following construction, and was contemplating investigating it for my undergraduate thesis: Let $L$ be a formal language, e.g. the set $\{x_1, x_2, \dots, \forall, ...
0
votes
1answer
26 views

Union of a chain of consistent subsets is consistent.

In a proof of Gödel's completeness theorem via Lindenbaum's Lemma I have seen it is necesssary to prove that if we have a chain of consistent sets, ordered by the $\subseteq$ relation, the union over ...
2
votes
1answer
46 views

Proving $(p\to q)\land(p\to r) \equiv p\to(q\land r)$ using logic laws — short cut or incorrect?

Working through this problem: Using logic laws, show that the following are logically equivalent: $$(p\to q)\land(p\to r)\qquad\text{and}\qquad p\to(q\land r).$$ The way I did the problem is ...
4
votes
1answer
33 views

Algorithm for traversing a conditional maze

Imagine a maze where there are rooms and doors. You can only go one way through a door. Some doors are locked. Certain rooms contain keys to certain doors. In effect, each time you find a key, the ...
0
votes
1answer
19 views

Logic Variable Assignments

I am having trouble calculating some variable assignments. Let $s$ be a variable assignment over $M=(D,J) $ We define: $$\begin{align} s(d/x)(y) & = d & \mbox{ if $y$ is identical to $x$} ...
0
votes
0answers
38 views

How to prove that a set containing G$\phi$ and G$\neg \phi$is inconsistent without completeness but with soundness.

I'm stuck with this problem... The logic is a adaptation to temporal logic from $K_4$ of modal logic. The interpretation of G$\phi$ is always true in the future (now is not included). The axioms for ...
0
votes
1answer
17 views

Question regarding condition of perpendicularity

Let $ax^2+2hxy+by^2=0$ be the equation of two straight lines passing through the origin. We know that the angle between these two straight lines is given by, $$\arctan \dfrac{2\sqrt{h^2-ab}}{a+b}$$ ...
1
vote
0answers
25 views

Show that $\Phi$ is negation complete.

Im working on a FOL exercise but i'm a little stuck here. Let $S$ be a symbol set and $\mathcal{J} = (\mathcal{U}, \beta)$ an $S$-interpretation. Further let $\Phi:=\{\varphi\in ...
1
vote
2answers
51 views

((a ⇔ b) ⇒ c) ⇔ (a ⇔ (b ⇒ c)) tautology, contradiction, or neither?

((a ⇔ b) ⇒ c) ⇔ (a ⇔ (b ⇒ c)). Prove whether its a tautology, a contradiction, or neither. My attempt: ((a ⇔ b) ⇒ c) ⇔ (a ⇔ (b ⇒ c)) if I take all F: ((F ⇔ F) ⇒ F) ⇔ (F ⇔ (F ⇒ F)) [(F ⇒ F ∧ F ⇒ ...
0
votes
1answer
32 views

Exam preparation: logic - problems on (maximally) consistent sets

I am preparing for an exam on aspects of Logic related to propositional and first order logic. One of my revision exam questions is . I have attempted this question but I am really struggling with ...
0
votes
0answers
16 views

Setting up a matrix using logical constraints?

Hello all at Stack Exchange! This is my first post! It took me a while to learn MathJax, but a buddy who referred me said people heavily prefer this format, so I thought I'd just follow the rules of ...
2
votes
0answers
46 views

Dependence of axioms of Zermelo set theory

I'm reading a book about Zermelo–Fraenkel set theory, and I was told that there are a lot of dependence relation among the commonly used axiom system (in the question What axioms does ZF have, ...
1
vote
1answer
91 views

Reference request for the independence of $ \text{Con}(\mathsf{ZFC}) $.

Gödel’s Second Incompleteness Theorem says that if $ \mathsf{ZFC} $ is consistent, then $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) $, i.e., $ \text{Con}(\mathsf{ZFC}) $ is not provable in $ ...
-1
votes
2answers
50 views

How do I simplify just using 2 logic operations?

I need simplify the following proposition to 2 logic operations using the laws of the algebra of propositions. Write each step on a separate line with the algebra law you used as a justification. ...
0
votes
2answers
22 views

Negate a proposition with quantifier?

I'm going over the proof of the theorem stating that "In a metric space, compactness impliess sequential compactness". I'm very likely confusing myself. I have the following proposition: $\forall ...
0
votes
0answers
54 views

A provability puzzle

This is a problem I came up with on my own, and it has me stumped, so I am going to pose it as a kind of puzzle. Let $F$ be a formal proof system, recursively axiomatizable, with an acceptable ...
3
votes
1answer
68 views

Multiple solutions to this Singapore Contest Logic question?

This problem has been making the round on the internet. The solution provided gives one answer, and I don't disagree with the logic to arrive at that answer. However, it seems to me that there is at ...
0
votes
1answer
56 views

How do I simplify these logic questions using laws of logic? [on hold]

1. $(p \vee q) \Rightarrow [q \Rightarrow (p \wedge q)] \equiv q \Rightarrow p$ 2. $(q\Rightarrow p) \wedge (p \vee \neg q) \equiv q \Rightarrow p$ 3. $[(p \vee q) \wedge \neg r]⇒ (p ...
0
votes
1answer
63 views

Consider the following expression about natural number: $\forall n\exists m: m^{2}=n$

I understood the first part and made an attempt. Then the question asked me to demonstrate an expression about natural numbers of my own which has an opposite truth value to the one above and explain ...
0
votes
1answer
60 views

Which one of the following logical propositions is to be preferred?

I'm trying to update the symbolism of Giuseppe Peano's "Arithmetices Principia", to make the translation freely available. Might I ask you, which of the following might be a correct mathematical ...
-4
votes
0answers
25 views

logic question dealing with blood type [on hold]

Human blood is classified O, A, B, or AB, depending on whether the blood contains no antigen, an A antigen, a B antigen, or both the A and B antigens. A third antigen, called the Rh antigen, is ...
-2
votes
0answers
15 views

figure out the venn diagram of 100 people [on hold]

100 people were asked if they knew who any of the following are: Thor, Zeus, and Osiris. 25 people did not know any of these. 3 people knew all three. 48 people knew who Zeus or Osiris were but did ...
1
vote
2answers
51 views

If $x,y \in \mathbb{R}$ where $x\leq y$ and $y\leq x$. Does $x=y$?

I'm trying to complete this problem: Let $A$ be a nonempty set and suppose $\alpha$ and $\beta$ are both suprema of $A$. Prove that $\alpha = \beta$. The first thing i did was try to find an ...
1
vote
2answers
18 views

Prove that the greatest lower bound of $F$ (in the subset partial order) is $\cap F$.

This is one of the question I'm working on: Suppose $A$ is a set, $F \subseteq \mathbb{P(A)}$, and $F \neq \emptyset$. Then prove that the greatest lower bound of $F$ (in the subset partial ...
1
vote
1answer
32 views

Sum of two dedekind cut is a cut

Given $A_1,A_2\in\mathbb R$, define the following: $$ A_1+A_2= \{x + y: x \in A_1, y \in A_2\} $$ I was able to prove that it is not equal to $\mathbb Q$ and isn't the empty set and but I can't prove ...
1
vote
1answer
34 views

Complete $n$-types for the theories of $( \mathbb Z , s )$ and $( \mathbb Z , s , < )$

This is exercise 4.5.2 from Marker's Model Theory: An Introduction (p.163), quoted verbatim: Let $T$ be the theory of $(\mathbb Z,s)$ where $s(x) = x+1$. Determine the types in $S_n(T)$ for each ...
0
votes
0answers
30 views

equisatisfiable symbol in logic

I'm learning about the Skolem algorithm, equisatisfiability in First Order Logic and see that the book Mathematical Logic for Computer Science uses the symbol $ \approx $ to indicate ...
-1
votes
1answer
30 views

Soundness and completeness

the question : Instead of the standard rule for disjunction (where we process a disjunction A∨B with two branches—one with A and one with B) we use a rule where the result is two branches, one with A ...
1
vote
1answer
52 views

Can't get Logical Error

Firstly I 'll mention Absorption laws : $((\sim p) \vee q) \wedge (\sim q)=(\sim p)$ $((\sim p) \vee q) \wedge p=q$ Also, $p \Longrightarrow q = (\sim p) \vee q$ And, $p \Longleftrightarrow q = ...
0
votes
1answer
19 views

single value computation

I was solving a coding problem where given a bunch of numbers, i need to compute step difference till i'm left with only one number. For example numbers are 3, 5, 2, 6, 7 such that my result is ...
2
votes
1answer
69 views

How show $ S \models \forall x ( \alpha \Leftrightarrow \beta)$?

I read some notes on Logic Course. I read that we can conclude: $$ S \models \forall x ( \alpha \Leftrightarrow \beta)$$ if and only if $ S \models \forall\, x\, \alpha$ has conclusion $ S ...
0
votes
1answer
54 views

Show This theory is complete with four countable models

Let $\mathcal L_3 = \{<,c_o,c_1,\ldots\}$, where $c_o, c_1,\ldots$ are constant symbols. Let $T_3$ be the theory of DLO with sentences added asserting $c_o < c_1 < \ldots$. I would like to ...
-1
votes
0answers
20 views

Analytical challenge - solve how 100 people can all meet among each other! [on hold]

100 people in an audience are to divide into two groups, green and red. The red group are to be seated as follows - 5 people on each 10 round tables. The green people are to rotate as follows - 5 ...
0
votes
0answers
26 views

Show DLO + $\{ \phi : \phi = c_o < c_1 < \ldots \}$ has three models up to isomorphism

Let $\mathcal L_3 = \{<,c_o,c_1,\ldots\}$, where $c_o, c_1,\ldots$ are constant symbols. Let $T_3$ be the theory of DLO with sentences added asserting $c_o < c_1 < \ldots$. I would like to ...
5
votes
4answers
723 views

Albert, Bernard and Cheryl popular question (Please comment on my theory)

Here is the problem, I think that there is one point that makes the question ambiguous, I think they should explicitly say the reason why Albert knows that Bernard does not know the date. Case 1: ...
0
votes
0answers
30 views

Do indiscernibles imply additional non-stardard models?

From Wikipedia Indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula. Usually only first-order formulas are considered. Question: does the ...