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)

-3
votes
0answers
32 views

Neither symmetric nor asymmetric [closed]

I have a set X={s,t,u,v}. I have shown an example where X is symmetric, antisymmetric but not asymmetric, asymmetric but how would I get an example of a binary relation that is neither symmetric nor ...
2
votes
0answers
25 views

How - in a Kripke model - to define a world by modal formulas true only at them?

I'm currently using van Benthem's "Modal logic for open minds", ed. 2010. In page 16 (and later in exercises), he considers a model whose relations are shown by directed graphs (the so called process ...
2
votes
0answers
30 views

What the definition of validity of a formule in a possible Kripke-world in Modal Logic?

Basic question here but I cannot find the definition: Given a modal logic and a set of propositions $P$, a model $M=(W,R,V)$ where $W$ are possible worlds, $R$ an accesibility relation and $V$ a ...
4
votes
1answer
67 views

extending automorphisms in complete boolean algebras

Suppose $A$ is a complete subalgebra of a complete boolean algebra $B$. Suppose $f : A \to A$ is an automorphism. Then $f$ can be extended to an automorphism of $B$. I can see this using the fact ...
3
votes
1answer
18 views

Let $\Gamma$ be a $\kappa$-based monotone operator where $\kappa$ is regular. Then the closure ordinal of $\Gamma$ is $\kappa$.

A monotone operator $\Gamma: \mathcal{P}(A) \to \mathcal{P}(A)$ is an operator such that, if $X \subseteq Y \subseteq A$, then $\Gamma(X) \subseteq \Gamma(Y)$. A monotone operator is $\kappa$-based ...
0
votes
1answer
88 views

A few questions about a true but unprovable statement

Can someone explain to me what this comment means: If ZFC is not a sound theory, a true but unprovable statement may be refutable and therefore decidable. What is a sound theory? What is ...
1
vote
2answers
38 views

Is the replacement theorem true for conditionals?

I read about the replacement theorem in Kleene's intro to logic which is as follows: If $\vDash(A\sim B)$ then $\vDash(C_A\sim C_B)$ where $C_A$ is a formula containing formula $A$ and $C_B$ is ...
2
votes
1answer
30 views

Finding a unique relation $T$

This is one question I have been solving from Velleman's How to prove book: Suppose $R$ and $S$ are relations on a set $A$, and $S$ is an equivalence relation. We will say that $R$ is compatible ...
0
votes
0answers
15 views

How to get accuracy of prediction?

I am working on a project where there is a part, which is based on the confidence level (between 0 and 1). The confidence level here is for various situations finally going Yes or No. So, 0.9 ...
-1
votes
0answers
20 views

Introductory books on Mathematical logic? [duplicate]

I am a graduate student.Any recommendation for an introductory book on Mathematical Logic?
0
votes
1answer
41 views

propositional logic entailment proof

I have a question, I am doing this exercise but I am a bit lost, it is the following: Let $\Sigma = \{\phi_1,...,\phi_n\}$ and $\varphi$ a proposition. Show that $\Sigma \vDash\varphi \iff ...
1
vote
2answers
51 views

Is the converse of a false conditional always true as in the Truth Table?

Accroding to the Truth Table, If $p$ is TRUE, and $q$ is FALSE, then $p\implies q$ is FALSE. And the converse, $q \implies p$, is TRUE. If the conditional statement is "If two angles are ...
1
vote
1answer
38 views

Proof strategy/writing for change of variables

Claim: If $f(x)=g(x)$ for all $x$, then $f(x+c)=g(x+c)$ for all x. Proof (attempt): Set $u=x-c$, and substitute $x=u+c$. $f(x)=g(x)$ implies $f(u+c)=g(u+c)$ for all $u$. Because $u$ is a dummy ...
2
votes
2answers
61 views

Questions about definability of truth

Suppose i work in ZFC. Using the recursion theorem, i can define the the truth value of formuals in the language $\mathcal{L}$ of set theory (one predicate symbol $\in$), $Val_\mathcal{M}(\varphi)$, ...
0
votes
0answers
60 views

How to convert formulas to rectified prenex form?

I'm preparing to an exam and I haven't understood this question: Convert the following formulas into rectified prenex form: a) $F = (\forall x \exists y\, P(x, g(y, f(x))) \lor \neg Q(z)) ...
0
votes
0answers
67 views

Proof for this equivalent statement to $2^{\aleph_0}=2^{\aleph_1}$ ??

This statement is some kind o a weak form of diamond and I am looking for a proof for its equivalence to $2^{\aleph_0}=2^{\aleph_1}$. $2^{\aleph_0}=2^{\aleph_1}$ is equivalent to the following ...
0
votes
1answer
24 views

Equivalence and implication for two identical statements

I saw in a maths book the following statement: $x>y ⇒ 2x>2y$ I think it should be written like this: $x>y ⇔ 2x>2y$ Which of the two above statements is correct?
3
votes
1answer
46 views

Counting quantification and the cardinality of a set

A counting quantifier is a quantifier that denotes how many elements satisfy a predicate. I will use the notation $C_n x P[x]$ to denote that there are $n$ elements that satisfy $P$. I was thinking ...
1
vote
1answer
44 views

Playing with propositional truth-tables

The following is the truth-table describing the definitions which allow us to establish truth values to composite formulae or molecules, which is nothing new: I had an idea about playing with the ...
4
votes
2answers
398 views

Is this axiom self-contradicting?

I was on physics stackexchange and came across an unusual answer where it was stated that the axiom, $$\forall x ((x \in x) \land (x \notin x))$$ Creates an axiom system where "nothing" exists in ...
0
votes
2answers
68 views

Decidability of certain first-order statements

Is it possible to construct an algorithm that can formally prove any statement in some countable first-order theory except for exactly those which aren't provable in the theory? Why or why not? Edit: ...
1
vote
0answers
33 views

How can a structure for a formal language be defined? [duplicate]

I'm learning some stuff about formal languages and structures for them. However there's this thing I don't understand. How can we ever define/specify a structure for a language, if we do not yet have ...
1
vote
1answer
33 views

Genus and faces of a graph

I am trying to determine the genus of a simple, undirected, connected graph using Euler's formula. However, I'm having trouble computing the number of faces of this graph: I seem to be confused ...
1
vote
3answers
54 views

Counterexample to “$A \to B, A \to C$, therefore $B \to C$”

We have $A\to B$ and $A\to C$. I need counter-examples to: '$\therefore B\to C$'. More formally, disprove: $$ (A\to B)\land(A\to C)\to (B\to C)$$ I have $A$ is a blackbird, $B$ is 'is black', $C$ ...
2
votes
2answers
36 views

The equivalence between the statements

Statement 1: Suppose for sake of contradiction that there is no non-negative rational number $x$ for which $x^2 < 2 < (x+ \epsilon)^2 $ . Statement 2: This means that whenever $x$ is ...
2
votes
0answers
29 views

Multiple order axioms independence [duplicate]

Let $T$ be a theory, let $L$ be its language, let $A$ be its set of axioms and let $P_0 \in L$ be a property. $P_0$ could be : Consequence of $A$ The negation of a consequence of $A$ Independent of ...
0
votes
0answers
57 views

“there are infinitely many” with finitely many variables

I vaguely recall reading somewhere that one cannot say "there are infinitely may" using a formula with only finitely many variables. A bit more precisely, let $\mathcal L$ be the result of extending ...
5
votes
3answers
252 views

Plantinga's logical argument for mind-body dualism [closed]

Some may feel this is not appropriate for the mathematics stack exchange, but it is a question in logic, and I feel it is entirely a good fit. The following argument has been put forth by the ...
1
vote
1answer
102 views

Computer program to tell you

Are there any computer programs, where if you input the premises and the conclusion, it tells you whether the conclusion is true or false?
1
vote
2answers
35 views

difference between some terminologies in logics

$$1) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, \alpha_k\vdash\alpha $$ Is a valid sequesnt. $$2) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, ...
0
votes
0answers
23 views

Meaning of valid sequent in logics

If $$\alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, \alpha_k\vdash\alpha$$ Here $\alpha_i$ are premises and $\alpha$ is conclusion .If I prove that sequent is valid using given rules in ...
-1
votes
0answers
48 views

Confusion with laws of logic?

Question: Use the laws of logic to show the following: $$q \iff (\lnot p \lor q) \equiv p \lor q$$ Could somebody proof read my attempt? $$ q \iff (\lnot p \lor q)\\ (q \lor q) \iff (\lnot p \lor ...
0
votes
1answer
48 views

Confused on 'using the laws of logic'

Use the laws of logic to show the following: $$(a) \quad(p\rightarrow r)\vee (q\rightarrow r) \equiv (p\wedge q)\rightarrow r$$ $$(b) \quad [\neg q\wedge (p\rightarrow q)]\rightarrow \neg ...
1
vote
1answer
31 views

Proof involving recursive enumerability

Consider the set $S = \{x : \phi^1_x(x) \ \ \text{is undefined/does not converge\} }$ This is supposed to be a set that is not recursively enumerable. How do we prove this? My thoughts so far: ...
2
votes
2answers
79 views

Can we treat logic mathematically without using logic?

I'm reading Kleene's introduction to logic and in the beginning he mentions something that I have thought about for a while. The question is how can we treat logic mathematically without using logic ...
2
votes
1answer
85 views

Why isn't this a valid formalization of , “Every farmer who owns a donkey beats it?”

Why isn't $\forall(f,d)[\mathrm{farmer?}(f) \land \mathrm{donkey?}(d) \land \mathrm{owns?}(f, d) \implies \mathrm{beats?}(f,d)]$ a valid formalization of, "Every farmer who owns a donkey beats it?" ...
-1
votes
1answer
42 views

Proving unsatisfiability with propositional resolution

I'm having trouble understanding how to use the resolution rule to prove if a statement is satisfiable or unsatisfiable. I watched this course lecture on propositional resolution and unsatisfiability ...
3
votes
1answer
33 views

Total Turing reducibility

For $x, y\in 2^\omega$, say $x$ is totally reducible to $y$ - and write "$x\le_{Tot}y$" - if there is some Turing machine $\Phi_e$ which is total on every oracle (that is, $\Phi_e^z$ is total for all ...
-1
votes
1answer
47 views

How to reason with Equisatisfiability

I am having trouble reasoning about the equisatisfiability of statements. (In the following I'll use the notation where addition is OR, multiplication is AND, and overbar is NOT.) By exhaustive ...
1
vote
1answer
39 views

Let $\alpha\in \text{FORM}$. If $\beta \in Sub( \alpha) \implies \beta $ shows up in every formation chain of $\alpha$.

Warning: I'm translating from spanish so probably many terms may sound unfamiliar. Warning 2: I'm probably going to link this question from many others I ask so I don't copy and paste these ...
0
votes
1answer
19 views

Translation of definition into logical proposition.

I want to translate the following definition into logical proposition. There is a function $f:X \rightarrow Y$,$g:X \rightarrow Y$. $f=g$ is for all $x$, $f(x)=g(x)$. What I've done is this. $$f=g ...
1
vote
1answer
35 views

Computably enumerable closed under inverse image

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a computable function and let $A \subseteq \mathbb{N}$ be computably enumerable. I'm trying to find a reason why the inverse image $f^{-1}(A)$ is also ...
1
vote
1answer
32 views

Finite set of formulas from $L(A)$ is realized iff it is consistent with $Th(\mathfrak{A})$

Let $\mathfrak{A}$ be an $L$-structure with domain $A$. If $\Sigma$ is a finite set of formulas in $L(A)$, how can I prove that $\Sigma$ is realized in $\mathfrak{A}$ iff it is consistent with ...
0
votes
5answers
53 views

Formal proof of a simple fact, namely that $S$ has even cardinality if certain pairs could idenitifed

Let $S$ be a finite set such that to each $s \in S$ there corresponds exactly one $t \ne s$ such that $t$ uniquely corresponds to $s$. Then $S$ has even order. This is quite obvious, an argument ...
2
votes
0answers
76 views

On the paper “Forcing and the CH” by Aspero/Larson/Moore

Forcing Axioms and the CH by Aspero/Larson/Moore On page 11 of this paper I struggle with the beginning of the proof of Lemma 3.5. Coding: For $r \in 2^\omega$ and $A \in H(\aleph_1)$ let us say ...
0
votes
1answer
35 views

Please help me solve this tautological proof

I'm studying for an upcoming exam and have run across this tautological proof: $(R\to Q)\to ((J\land\neg K)\to [(J\equiv Q)\lor(K\equiv R)])$ To start this one off, I decided to create two ...
1
vote
0answers
62 views

Why is $\mathsf{Type} : \mathsf{Type}$ a contradiction?

In reading this cstheory.se question and this stackoverflow question, they mention that $\mathsf{Type}: \mathsf{Type}$ is inconsistent. I also understand that Coq has an infinite hierarchy of Types. ...
-2
votes
1answer
39 views

Logic: Conditional Proof

$(G\land H)\to (J\equiv L)$ $(G\equiv H)$ $(H\land\neg L)\lor(H\land K)$ | $J\to K$ I am trying to use a conditional proof to solve this one. So I'm assuming J is true and using that to prove ...
0
votes
0answers
21 views

Finding average as well as impact of quantity

I am new to this site, I am basically a developer and stuck at a logical mathematics portion. I have polarity of people sending email, so suppose p1 sent mail and mathematical polarity came out to be ...
0
votes
1answer
53 views

Boolean formulas over omega automata

I've been reading on omega automata(automata on infinite words) and stumbled upon a definition involving logic which caught me off guard. For example, on Buchi automata the definition I originally ...