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)

1
vote
1answer
19 views

Show For any language L two L-structures M and N are elementarily equivalent iff they are elementarily equivalent for every finite sublanguage.

Setting For any language $\mathcal L$, two $\mathcal L$-structures $\mathcal M$ and $\mathcal N$ are elementarily equivalent iff they are elementarily equivalent for every finite sublanguage. ...
1
vote
2answers
48 views

Write the negation of the following

$P(x,y)$ is the set $\{0,1,2,3,4,5\}$ $ \forall\ y\ \neg P(2,y)$ I solved this is it correct? $$\neg P(2,0) \wedge P(2,1) \wedge P(2,2) \wedge P(2,3) \wedge P(2,4) \wedge P(2,5)$$
3
votes
2answers
73 views

Determine whether or not $\neg q \to \neg (q \land (p \to \neg q))$ is a tautology

I have been trying to solve this but I got stuck at the end. $$\begin{align} \neg q \to \neg (q \land (p \to \neg q)) &\equiv \neg \neg q\lor \neg (q \land ( \neg p\lor \neg q)) \\& ...
1
vote
1answer
32 views

Am I right in this discrete mathematics question?

$A = \{0, 1, 2\}$ $B = \{x \in R\mid−1 \le x \lt 3\}$ $C = \{x \in R\mid−1 \lt x \lt 3\}$ $D = \{x \in Z\mid−1 \lt x \lt 3\}$ $E = \{x \in Z+ \mid−1 \lt x \lt 3\}$ I put that $A=D$, $A=C$, and ...
2
votes
3answers
35 views

Determining if a relation is reflexive, symmetric, or transitive [on hold]

Let $A = \{0,1,2,3\}$ Define a relation $T$ on $A$ as follows: $T = \{(0,1),(2,3)\}$ Is $T$ reflexive? symmetric? transitive?
0
votes
3answers
24 views

Finding the equivalence classes of a relation R

Let A = {0,1,2,3,4} and define a relation R on A as follows: R = {{0,0},{0,4},{1,1},{1,3},{2,2},{3,1},{3,3},{4,0},{4,4}}. Find the distinct equivalence classes of R. How do I solve this problem? ...
0
votes
1answer
27 views

Proving Equivalence Relations On A Set

Let X be the set of all nonempty subsets of {1,2,3}. Then X = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} Define a relation R on X as follows: for all S and T in X, SRT if, and only if, the least ...
1
vote
1answer
39 views

Are the implicitly definable sets of a second-order theory the sets the second-order quantifiers range over?

I know that in a second-order setting, due to the failure of the Beth definability theorem, implicit and explicit definition come apart (i.e., there are predicates which can be implicitly, but not ...
0
votes
2answers
22 views

when tossing a coin ten times, what is the probability of an outcome which has a string of 3 or more heads as well as a string of 3 or more tails?

here is an experiment from my Stat textbook "Try this experiment: Write down a sequence of heads and tails that you think imitates 10 tosses of a balanced coin. How long was the longest string ...
1
vote
2answers
47 views

Discrete Math: Implication

If $\neg(P) \to \neg(Q) = Q \to P$ works as a Rule, then why doesn't $\neg(P) \to \neg(Q) = P \to Q$ work as a rule.
3
votes
3answers
63 views

How various properties of numbers, operations are found?

I know that how the term "property" is defined. Definition: An attribute, quality, or characteristic of something. Like one of the property of addition is "commutativity" which behaves like, ...
-7
votes
0answers
35 views

Logic puzzle for mathematician [on hold]

Suppose in some dimension If -> 9999 -4 -> 8888-8 -> 1816-9 -> 1212-0 then what is 1919- ?
1
vote
2answers
55 views

a relation in logic

Suppose $\prec$ is a relation defined in the set of well defined formulas such that $\phi \prec \psi$ iff $\models \phi \rightarrow \psi$ and $ \nvDash \psi \rightarrow \phi$ I would like to prove ...
3
votes
0answers
36 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
-1
votes
0answers
61 views

Algebra and Logic [on hold]

A ⇔-wff is a well-formed formula that is built out of propositional variables and the double arrow ⇔ only. (a) Characterise precisely all positive integers that arise as the number of symbols used to ...
2
votes
1answer
27 views

Enderton's logic book about completeness theorem

In page 141 of A Mathematical Introduction to Logic, Enderton simply writes, STEP 6: Restrict the structure $\mathfrak{A}/E$ to the original language. This restriction of $\mathfrak{A}/E$ ...
1
vote
1answer
29 views

Reconstructing the conditional's truth table from natural deduction

Can the conditional's truth table be reconstructed using the rules from natural deduction?
1
vote
0answers
55 views

Deduction method with a quantified statement

In this expression I am trying to prove is a valid argument using the deduction method that is using equivalences and rules of inference in a proof sequence. ...
0
votes
0answers
21 views

L-structure, configuration, example

I have a question to the following task. Please excuse me, when I make mistakes. I am not a native speaker. :) Task: Give an example for a language L, a L-structure $\mathcal{M}$, a configuration ...
15
votes
0answers
125 views

When are two proofs “the same”?

Often, we find different proofs for certain theorems that, on the surface, seem to be very different but actually use the same fundamental ideas. For example, the topological proof of the infinitude ...
2
votes
3answers
41 views

Can a sequence whose final term is an axiom, be considered a formal proof?

Wikipedia gives the following definition of a formal proof: A formal proof or derivation is a finite sequence of sentences (called well-formed formulas in the case of a formal language) each of ...
0
votes
1answer
31 views

Given L = {<,c0,c1,…} and T3 the theory of DLO with sentence asserting co < c1 < …, Show T4 is complete with four countable models.

Let $\mathcal L_3 = \{<,c_o,c_1,\ldots\}$, and $T_3$ be the theory of DLO with sentences added stating $c_o < c_1 < \ldots$. Now let $\mathcal L_4 = \mathcal L_3 \cup \{P\}$, where $P$ is a ...
1
vote
3answers
44 views

Help With Notation In Fermat's Last Theorem

The following is the notation for Fermat's Last Theorem $\neg\exists_{\{a,b,c,n\},(a,b,c,n)\in(\mathbb{Z}^+)\color{blue}{^4}\land n>2\land abc\neq 0}a^n+b^n=c^n$ I understand everything in ...
1
vote
1answer
33 views

How to evaluate the single turnstile symbol ($\vdash$) in propositional logic?

Wikipedia says, that: $x \vdash y$ means y is provable from x (in some specified formal system). But what do you actually check or calculate, when you have $(a \land \lnot b) \vdash a$? Has $(a ...
0
votes
1answer
35 views

Bound Variable and Free Variable, A Questions and one Example?

I see a Local Contest Question as : for statement $ \forall x [ \exists y ( x<y+z) \to \exists z (x < y+z)] $ two following axiom is True: I) $ y, z$ is free and $x$ is bounded. II) ...
-2
votes
0answers
41 views

Question 4.5.1 from Marker [on hold]

This is question 4.5.1 from Marker. Lifted verbatium but with a correction: Let $\mathcal M = (X,<)$ be a dense linear order, let $A \subset M$ and $\bar b, \bar c \in M^n$ with $b_1 < \ldots ...
0
votes
1answer
36 views

Rewrite predicate formulas in propositional calculus

Suppose that the universe of discourse of the atomic formula P(x,y) is the set {0,1,2,3,4,5}. Write each of the following propositions using dis-junctions, conjunctions and only one negation: 1) ∃x ...
0
votes
0answers
19 views

Are the rows of a hypothetical truth table with infite propositional variables non countable;

If i want to write every propositional formula as disjunction(V) of conjunctions(^) and i have an infinite set of propositional variables then would the rows of my hypothetical truth table be non ...
1
vote
1answer
38 views

Link between definitional expansions and definitional extensions.

I need to prove this, Let $T$ be a theory in language $L$, let $T'$ be a definitional extension of $T$ to language $L\subseteq L'$. If $\mathcal {M} \models T'$, then $\mathcal M$ is a ...
0
votes
1answer
39 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
42 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 ∨ ...
21
votes
2answers
1k 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
51 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 ...
1
vote
1answer
29 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
22 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
53 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
45 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 ...
4
votes
1answer
80 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
42 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
27 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
51 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
125 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 ...
6
votes
9answers
257 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
28 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
48 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
34 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
20 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
1answer
47 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}$$ ...