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)

2
votes
1answer
15 views

how to prove that a relation is antisymmetric?

I have this question that I didn't know how to prove it and need your help. $R$ is a transitive and not reflexive relation on $A$. Prove that $R$ is antisymmetric. I tried to apply the definition of ...
0
votes
2answers
21 views

What sequent does this derivation prove?

Trying to learn sequent calculus and so I am trying to work thru some examples to get a better grip/understanding but the following question is not answered at the back of the book. I wrote my guess ...
0
votes
1answer
48 views

Isn't the axiom of determinacy inconsistent with ZF? What am I overlooking?

I'm sure there's something I'm missing here; probably a naive confusion of mathematics with metamathematics. Regardless, I've come up with what looks to me like a proof that (first-order) ZF+AD is ...
1
vote
0answers
49 views

How can nontrivial elementary embeddings of the universe to some inner model be surjective?

Consider $\kappa$ to the least measurable cardinal, or equivalently $\kappa$ is the critical point for an elementary embedding $j:V \rightarrow M$ from the universe $V$ to an inner model $M$ (critical ...
1
vote
1answer
53 views

What does “Fixed-Point Lemma” says intuitively?

The lemma as stated in Enderton's logic says: Fixed-Point Lemma.   Given any formula $\beta$ in which only $v_1$ occurs free, we can find a sentence $\sigma$ such that $$ A_E \vdash ...
0
votes
1answer
36 views

Assumptions, Axioms and Premises

The following attempt of mine at defining these terms, reflects my current understanding of them: Assumption: $\quad$ A statement accepted as true without proof being required. ...
3
votes
2answers
54 views

Help in proving a tautology

I am having real trouble deriving this tautology: $\forall(x) ((x=a) \lor (x\neq a))$ It is easy to solve this by assuming the negation, unpack the negation with DeMorgan's Law, and derive from ...
6
votes
1answer
67 views

Propositional Logic: Proof involving only the symbols $\{\rightarrow,F \}$

I feel like I literally tried everything. I'm exhausted, and could really use some help. I was instructed to prove some logic proposition using only the symbols $\{\rightarrow,F \}$. Let me first ...
-4
votes
1answer
39 views

What does a separation in lines mean?

does putting a problem on two different lines make it two seperate problems? 1+1 1+1 Is this the same as 1+11+1 Or does the line break indicate a seperation of problems? Is there a specific ...
4
votes
2answers
67 views

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined?

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined, when $A$ is a set of reals ($A \subset \omega^\omega$)? I assume that there is a standard definition, but I can't seem to find ...
1
vote
1answer
32 views

Positive and negative logical connectives

By inspecting the rules of inference for (intuitionistic) predicate calculus (or, alternatively, thinking about double negation translation), one sees that there is a certain dichotomy between two ...
0
votes
0answers
26 views

Conservative extensions and elementary equivalence- anything in common?

What is the difference between a Conservative extension, T', of a theory T, and a theory that is elementarily equivalent to T (but non-isomorphic, having, say, more elements). As far as I gathered, T' ...
0
votes
3answers
49 views

proving logic equation in logic algebra

Im trying to prove the following logic equations are equal and am having trouble. $ab'e'f + a'b'ef + acd'e' + a'cd'e + b'c'f + b'df = acd'e' + a'cd'e + b'c'f + b'df$ $a' = \neg a$ I am pretty new ...
5
votes
1answer
63 views

Is there any formula of monadic second-order logic that is only satisfied by an infinite set?

Is there any formula, of monadic second-order logic, that is only satisfied by an infinite set?
-2
votes
0answers
32 views

Textbook with full solutions: To self-learn logic for the first time [on hold]

I never studied logic before; so I'm seeking an intelligible textbook (written in simple English) with practice problems that MUST be accompanied with full detailed solutions. I read ...
2
votes
1answer
64 views

Hilbert–Bernays provability conditions

Let "provability formula" ${\rm Prf}(x, y)$ written in the manner that provability operator $\square A$ defined as $\exists x\ {\rm Prf}(x, \overline A)$ satisfying Hilbert–Bernays axioms: If ZF ...
4
votes
2answers
83 views

How to intuit 'only if'?

I already know, and so ask NOT about, the proof of:   $A$ only if $B$   =   $A \Longrightarrow B$. Because I ask only for intuition, please do NOT prove this or use truth tables. My problem: I try ...
2
votes
1answer
42 views

Satisfiability proof of formulas with pure literals

Let $\varphi$ be any propositional formula in negation normal form (NNF). A literal $\ell$ is pure in a formula $\varphi$, if the complement of $\ell$, $\ell^c$, does not occur in $\varphi$, where ...
0
votes
1answer
37 views

Which mistake(s) in my argument re: representability, definability and the halting problem?

I'd like to ask for your help in showing me the (quite likely: several) flaws in my argument below, relating weak and strong representability in a formal system and the halting problem. At least ...
0
votes
0answers
38 views

Validity of a first-order formula

How can I see (and prove) whether the given first-order formula $\varphi$ is valid or not? $\varphi = \forall x \forall y [ (r(x,y) \rightarrow (p(x) \rightarrow p(y))) \land (r(x,y) \rightarrow ...
2
votes
1answer
46 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
61 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
85 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
34 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
43 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
25 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
29 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
40 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
27 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
48 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
65 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
39 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
60 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
39 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
65 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
29 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
30 views

Reconstructing the conditional's truth table from natural deduction

Can the conditional's truth table be reconstructed using the rules from natural deduction?
0
votes
0answers
24 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 ...
21
votes
0answers
230 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
42 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
41 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
45 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
34 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
37 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
43 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
44 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
46 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 ∨ ...