Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

0
votes
1answer
34 views

Logical formula with natural numbers

How to write a formula using only quantifiers, variables, brackets, logical operators and $\in$, $\mathbb{N}$, $+$, $\cdot$, $=$, $\leq$ : Among any three natural numbers exist pair of them such ...
1
vote
1answer
35 views

(∀x ∈ X, P(x)) or (∀x ∈ X, Q(x)) ⇒ ∀x ∈ X,(P(x) or Q(x)) where X is nonempty and P(x) and Q(x) are statements.

I know this is an obvious statement but how would one go about in showing that this is true ? My answer is : Consider the 2 cases; Case 1) ∀x ∈ X, P(x) holds. Then clearly ∀x ∈ X, P(x) or Q(x) ...
1
vote
1answer
87 views

Propositional calculus logic question

In my assignment I have the following question: For every proposition $\theta$ let $E(\theta)$ be the set of basic propositions. Prove the following: For every two propositions, $\alpha$ and ...
5
votes
1answer
129 views

Compactness Theorem / Set made of formulas of infinite size

Could someone give me an example of an infinite countable set, where formulas contained in it are under the form of a conjunction or disjunction of infinite size, for which the compactness theorem ...
0
votes
1answer
53 views

What we can infer from there exists x satisfying P

If it is known that there exists x satisfying P, can we infer that there also exists x not satisfying P? I ask this question since I have a problem as follows. Given three premises: (1)if a student ...
0
votes
1answer
80 views

How much conservative ZF+AC and ZF+DC are over ZF?

A logical theory $T_2$ is a (proof theoretic) conservative extension of a theory $T_1$ if the language of $T_2$ extends the language of $T_1$; every theorem of $T_1$ is a theorem of $T_2$; and any ...
1
vote
0answers
41 views

Some doubts regarding decidable sets

I've been working at one of the problems, related to the decidability. Let's denote $ f: \mathbb{N} \rightarrow \mathbb{N}$ as a computable increasing function, $A \subset \mathbb{N}$ is a ...
1
vote
2answers
42 views

Inequality with respect to transitivity

Given a relation R, R is said to be transitive if aRb ∧ bRc, then aRc. The unequal relation (≠) is not transitive, for instance a≠b ∧ b≠c, then a≠c is an invalid consequent of the antecedent (a≠b ∧ ...
2
votes
2answers
45 views

Have I properly used $\,\exists !\,$ in this statement?

I want to express the following in logical notation. For every natural number, there is a unique natural number that succeeds it. Does the following statement express that proposition? ...
0
votes
2answers
55 views

How to find the contrapositive of this statement?

$if \ \ \ \forall a \forall b \in Q, \ \ \ xy \notin Q \ then \ (a \lor b) \notin Q$ I hope I wrote that correctly. In English terms, it would be: " If a and b are real numbers and ab is irrational, ...
0
votes
1answer
54 views

Prove by contrapositive: Φ∪{β} ⊨ α & Φ∪{¬β} ⊨ α iff Φ ⊨ α

We are to prove this by contrapositive (by the way: Φ is a set of formulas of predicate logic and α a formula of predicate logic) I've managed the Right to Left proof, but I struggle with the Left to ...
2
votes
1answer
117 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...
0
votes
1answer
31 views

Logic proof using contrapositive

If n=ab is the product of two integers $a$ and $b$, then either $a\leq n^{(1/2)}$ or $b\leq n^{(1/2)}$. Use the proof by contrapositive method. The new statement is: if $a>n^{(1/2)}$ or ...
1
vote
3answers
66 views

Prove the two logic expressions are equal

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$ It makes sense when I think about it, but how does one prove it? Also is there a relationship with the above and saying: $(a \implies ...
1
vote
4answers
214 views

Two plus two equals four when earth has one moon?

As is well known, we have the least intuitive of basic operations, the 'implication' or '=>'. Consider 'A => B'. Most beginners get stumped on the vacuous truth, that implication could be true even ...
0
votes
1answer
68 views

Logic behind continuity definition.

I have a question regarding the definition of continuous functions : from wikipedia and my book : $f$ is said to be continuous at the point $c$ if the following holds: For any number ...
52
votes
1answer
2k views

What does it take to divide by $2$?

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 ...
0
votes
1answer
104 views

What does First Godel's Incompleteness theorem mean?

I am terribly confused what really "Incomplete" mean in terms of the Godel's theorem. Does it mean there are some theorems that are definable in First order theory of natural numbers and true but ...
0
votes
1answer
42 views

Example of language implementation

I'm trying to find example of implementation $M$ of language $L$ such that $M \models \varphi_1 \land \varphi_2 \land \varphi_3 \land \varphi_4$ Where $L = \{•, \blacksquare, n\}$ is language with ...
0
votes
2answers
82 views

Help with semi-formal logic

How do I write semi-formally 'there are only 2 objects in the universe'? My hypothesis is: ∃x∃y(x≠y) Any ideas?
2
votes
2answers
261 views

Every element of the empty set has three toes true or false? [duplicate]

This is a bonus question that we have and I cannot figure it out. Any help would be great! Is the proposition Every element of the empty set has three toes true or false? Explain your answer
1
vote
1answer
100 views

Uncountable reals in the theory

The Question I'm looking for a possibility to somehow proof the "essence" of Cantor's diagonal argument within a recursive first-order theory which is satisfied by the reals (better: within a theory ...
3
votes
2answers
139 views

Recursion on a class instead of a set

According to Wikipedia, the recursion theorem states the following: Let $X$ be a set, and $f:X\to X$ a function. For any $x\in X$, there exists a unique function $g:\omega\to X$ such that $g(0)=x$ ...
3
votes
2answers
81 views

Does ultralimit of sequence change after shift?

Let $(a_n)$ be a bounded sequence of numbers, $\omega$ be an non-principal ultrafilter on $\mathbb N$, then one can assign a limit along ultrafilter $(\omega-)\lim a_n$ to it as is said here. This ...
1
vote
0answers
31 views

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ [duplicate]

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ Or how do one go about showing that the former is not a proposition. I've just started reading Dalen's Logic and ...
2
votes
0answers
87 views

Is there any inconsistent large cardinal axiom which its inconsistency proof is essentially different from proof of Kunen inconsisteny theorem?

There is a long list of large cardinal axioms. Most of them deemed to be consistent with ZFC but there are also some axioms like existence of Reinhardt or $\omega$-huge cardinals which are natural ...
1
vote
1answer
378 views

Which of the following figures represents the relationship between english teachers, popular english teachers and unpopular teachers?

I am not sure if this is the right platform for this question but In India, we have a PSA test which is based on logic and I have a question which I cannot understand, so the question is:- Which of ...
14
votes
2answers
469 views

What is the most influential work of Grothendieck in mathematics?

Recently Alexander Grothendieck has passed away but his mathematical wave is still alive and passes its growth ages. It is hard to describe the influence of such a great man in mathematics just in few ...
1
vote
1answer
56 views

Prove a predicate formula in the constructive logic

Using the constructive logic (the axiom $A\lor\lnot A$ cannot be used), using quantifier axioms and Modus Ponens, and Generalization, prove the following: $\exists x(B(x) \to C(x)) \to (\forall xB(x) ...
1
vote
1answer
121 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 ...
2
votes
1answer
137 views

How large is an uncountable regular cardinal which is closed under arbitrary fast operators?

Let $Card$ be the proper class of all cardinals, define an infinite set of operators like $\otimes_{n}:(Card\setminus \omega)\times (Card\setminus\{0\})\longrightarrow Card$ which are defined for each ...
2
votes
0answers
108 views

A Proof by Induction about terms and variable assignments

I am (sort of) familiar with inductive proofs about wffs, but proofs by induction about terms took me by surprise. Prove by Induction that: if variable assignments q, q' agree on all variables ...
4
votes
1answer
61 views

Constructing a function whose domain is $\omega$ using successor operation recursively

Let $x$ be a set. Does there exist a functional relation $f:\omega\to \bf{V}$ which has the following property? \begin{eqnarray*} f(0)&=&x\\ f(1)&=&S(x)=x\cup\{x\},\\ ...
-4
votes
4answers
107 views

Demostration of ∀x ∈ ∅ p(x) is always true [duplicate]

It seem that the following statement is always true for any "p": ∀x ∈ ∅ p(x) What is the demonstration or where can I find a demonstration about it? Otherwise, what is the counter-demonstration?
1
vote
3answers
170 views

Is $(P\implies Q)\implies (\lnot Q\implies \lnot P)$ always true?

I've discovered that many theorems in mathematics are often in forms: $$P\implies Q$$ I've also discovered that usually $\lnot Q\implies \lnot P$, if $P \implies Q$ is a theorem and I'm interested if ...
2
votes
3answers
45 views

Does every element of the empty list posses every property?

Suppose we have a list of elements $v_1, v_2, \ldots, v_n$. Then, as I've understood, setting $n=0$ above results in the empty list $v_1, v_2, \ldots, v_0$ of no elements (please correct me if I'm ...
1
vote
4answers
113 views

How many valuations of these literals satisfy this expression?

considering all the possible valuations of literals A, B, C, D, E, F, G and H (256 valuations in total), how would you go about finding how many of these valuations satisfy this expression: $$ ...
7
votes
1answer
467 views

Understanding the proof of “$\sqrt{2}$ is irrational” by contradiction.

I have some difficulties in understanding the proof of "$\sqrt{2}$is irrational" by contradiction. I am reading it in 10th class(in India) Mathematics book( available online, here ) This is the ...
0
votes
1answer
31 views

Are these structures in the same language?

I have these teo structures, $(N, <)$ and $(Q, <)$. And I want to know if they can come from the same language? I'm confused about the definition I have for an La-structure. Specefically about ...
1
vote
1answer
34 views

Help understanding the equivalence of these two statements

Help understanding the equivalence of these two statements Let $\Omega $ and $S $ be sets and $Y : \Omega \mapsto S $ $\Sigma $ is a $\sigma $-algebra on $S $ $X: \Omega \mapsto \mathbb R $ Now I ...
2
votes
2answers
97 views

Different definitions for consistent set of sentences

In my logic class, we were given the following definition for a set of sentences being consistent in first order logic: Let $\Gamma$ be a set of sentences in some underlying language $L$. The set ...
0
votes
1answer
59 views

Least and greatest element of the $(\mathbb{N}, |)$

Consider the relation | on $\mathbb{N}$, where $\mathbb{N} = \{0,1,2,... \}$ and $n|m$ means $n$ divides $m$. I know that the pair $(\mathbb{N}, |)$ is a partial order, : (1) Find the least and ...
1
vote
1answer
46 views

proving unsatisfiability in a union of closed WFF

If I am given a closed set of wff $X$ and it is unsatisfiable, then how do I show that the set $X \cup \{A\}$, where $A$ is any closed wff, is unsatisfiable?
0
votes
3answers
42 views

Question about negating implied propositions

I'm negating this proposition: "If you study you will not fail." I'm using proposition P: "You study" and proposition Q: "You will fail." The original statement can be written as "$P → ¬Q.$" My ...
2
votes
1answer
99 views

provide an interpretation for a given WFF

Provide a satisfying and falsifying interpretation for the following WFF: ∀x∀y(P(x,y) ↔ P(y,x)) my attempt: x,y are numbers P(x,y): x > y falsifying ...
2
votes
0answers
129 views

A universal formula is not equivalent to an existential formula

Suppose a formula is looks like the following: $\forall x_1 ... \forall x_n \alpha$ Where $\alpha$ is a formula free of quantifiers. And if $P$ is a 1-ary relation letter, then the formula ...
3
votes
2answers
101 views

If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$

If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$ Here, a set of formulas is inconsistent means they syntactically imply some formula as well as its negation. ...
2
votes
1answer
117 views

Proof in First-Order Logic using Compactness Theorem

If we have $\Sigma$ and $T$ as two first-order theories such they do not have any common models. How can I prove that there is a sentence φ such that Σ ⊨ φ and Τ ⊨ ¬ φ? Does Compactness Theorem help? ...
1
vote
4answers
85 views

Basic logic question: Can $\neg p \implies p$ be true?

Can $\neg p \implies p$ be true? How about $p \implies \neg p$? I was told yes, but it doesn't make sense to me. Any help would be appreciated!
0
votes
1answer
38 views

Given $p \rightarrow q$ and p are true, show $q ∨ r$ is true using rules of inference

I have a question from computing mathematics which I am not really able to prove. Given that $p \rightarrow q$ and $p$ are true, show that $q \lor r$ is true using rules of inference. Any ...