Questions about logic and 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)

30
votes
2answers
745 views

When should I be doing cohomology?

Background: I'm a logic student with very little background in cohomology etc., so this question is fairly naive. Although mathematical logic is generally perceived as sitting off on its own, there ...
1
vote
1answer
31 views

If $\Sigma$ satisfies $\alpha$ and also not-$\alpha$ then $\Sigma$ is not satisfiable?

Why is it true that if $\Sigma$ satisfies $\alpha$ and also not-$\alpha$ then $\Sigma$ is not satisfiable? Is it true at all? it doesn't make any sense to me and I would like to know more about that ...
2
votes
1answer
105 views

How much set theory and logic should typical algebraists/analysts/geometers know? (soft-question)

I know enough amount of set theory and logic to study grad-level math. However, I don't know more advanced set theory and logic, such as the ones on Kunen's or Shoenfield's texts. Although it's good ...
1
vote
2answers
43 views

Value of an expression with an impossible predicate

let $a = (a_1, a_2, a_3, \ldots , a_n)^T$ for some arbitrary large (irrelevant to the question) value of $n$. and let $i,k \in \mathbb{Z}$ What would the value of the following expression be when $i ...
4
votes
1answer
59 views

sheaves of rings and maps to classifying topos

Let $R$ be the category of finitely presented commutative rings (but I don't know how necessary the hypothesis of finite presentation is for my question). Let $Set^R=Fun(R, Set)$ be the category of ...
2
votes
1answer
68 views

On the definition of a Type

I am working through Spivak's text on category theory and he gives the definition of a type as :"A type is an abstract concept, a distinction the author has made". This seems very informal and after ...
0
votes
0answers
34 views

Show that if $f$ is a give p.c. function there exist infinitely many indices i for $f$.

Show that if $f$ is a give p.c. function there exist infinitely many indices i for $f$, that is $f=\phi _{i}$. answer: by Definition $ P _{x}$ is the set of instructions associated with the integer ...
2
votes
2answers
52 views

What to conclude from $ x \in (A \setminus B \cap B \setminus C)$

I have been working on one of the proof of logical statement and one part of it is like this: $ x \in (A \triangle B) \cap (B \triangle C)$ $ x \in (A \setminus B\cup B \setminus A) \cap (B ...
3
votes
0answers
53 views

Need to check if these logic answers are correct =)

Are my answers true or wrong or not even wrong? Exercises says translate the following english sentences into symbolic sentences with quantifiers quantifiers the universe for each is given in ...
11
votes
3answers
391 views

Axiom of Choice: What exactly is a choice, and when and why is it needed?

I'm having trouble understanding the necessity of the Axiom of Choice. Given a set of non-empty subsets, what is the necessity of a function that picks out one element from each of those subsets? For ...
4
votes
0answers
101 views

A question regarding a paper of M. Magidor [closed]

I am interested in the following paper of M. Magidor: "On the role of supercompact and extendible cardinals in logic", Israel Journal of Mathematics, 05/1971; 10(2): 147-157. The abstract (which I ...
3
votes
1answer
67 views

Would this be an acceptable translation of the English statement as well?

This is an except from my textbook (Discrete Mathematics and Its Applications 7th Edition) This was my initial stab at the problem (with domain of both variables being all real numbers) Would it ...
1
vote
1answer
26 views

Would these two statements be logically equivalent?

This is an excerpt from my textbook(Discrete Mathematics and Its Applications 7th edition) When I tried doing this example on my own, my answer was "There is a student x in this class and that ...
3
votes
0answers
60 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
5
votes
3answers
242 views

What is the first order axiom characterizing a field having characteristic zero?

In this thread on the axioms of $\mathbb Q$ it's stated that a field having characteristic zero can be written down in first-order logic. The definition in the logic lecture notes I work with (by ...
2
votes
1answer
104 views

Is this a correct solution to determine as to whom I should invite for the party?

I was working my way through some Propositional Logic Questions in Discrete Maths by Rosen, when I came across the following question: When planning a party you want to know whom to invite. Among ...
0
votes
1answer
55 views

A Model of Dense Linear Orders without Endpoints

Hopefully this question is well defined. Consider the following linear order in the language $\{<\}$: Step 0: Begin with $\mathbb{Q}$. Step 1: Create a new model $Q_1$ by realizing all the ...
5
votes
1answer
118 views

How to formally prove the negation of a statement “A if and only if B”?

Motivated by this question, I'm trying to establish a logical proof to the fact that the following statement is false: $2x+1$ is prime if and only if $x$ is prime. There are several ways to ...
0
votes
0answers
60 views

Diagonalization

So off and on I've been studying basic recursion theory and I've realized that, at least when restricted to the basic stuff I've been learning, recursion theory is essentially the study of uses of ...
1
vote
0answers
35 views

Confusion between categoricity and indiscernability

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. Is this because ...
0
votes
1answer
53 views

Indiscernibility of indiscernibles in second order logic

It is not clear to me if the statements in $0^\#$ remain indiscernible when we move to second order logic. Or are there second logic formulas that can discriminate between first order indiscernibles?
34
votes
11answers
3k views

Why not both true and false?

Why can't some mathematical statement (or whatever is the correct term) be both true and false? For example we can prove (e.g. by induction) that $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ for all positive ...
4
votes
1answer
103 views

Is there any identity which cannot be proved

For example, if we want to prove that $a^2+b^2\ge 2ab$ for all $a,b\in\mathbb{R}$, we will start from something which is true (axiom or something that is already proved). In this case we will use fact ...
1
vote
3answers
116 views

Elementary embeddings vs isomorphisms

I'm trying to get a better handle on the concepts of literal embeddings, elementary embeddings and isomorphisms, as the show up in logic. This is the problem: It seems to me, (and is, according to my ...
0
votes
1answer
31 views

Which of the following conditions must necessarily be true?

Suppose that $\{A, B\}$ is a set of mutually exhaustive conditions, and that $\{C, D\}$ is another set of mutually exhaustive conditions. If the following implications are true: $$A \Longrightarrow ...
8
votes
1answer
107 views

Examples of Forcing in Model Theory

My question is exactly my title: What are some examples of (set theoretic) forcing in model theory? I have been studying (combinatorial) set theory and model theory (independently of one another) for ...
18
votes
3answers
1k views

What do bitwise operators look like in 3d?

The hypothetical relation is $z = \mathrm{xor}\left(x,y\right)$ where xor is any bitwise operator such as AND, OR, NAND, etc. I see that these operations may be defined for integers trivially using ...
4
votes
1answer
56 views

Rewriting $X\leftrightarrow Y$ using only $\neg$ and $\lor$

Note: The book I'm using doesn't have any solutions/answers so I will be posting some of the questions I'm unsure about in the hope that someone will check it for me. Question: Re-write ...
2
votes
1answer
42 views

Statement calculus

Turn the statement 'either $X$ or $Y$' into an iterated composition. I'm not sure if my answer is correct, can someone please check for me? : $$\text{either }X\text{ or }Y \equiv (X\vee Y)\wedge ...
1
vote
1answer
53 views

o-minimal structures and definable functions

Consider the following definition of an o-minimal structure: An o-minimal structure $O=\{O_n\}$ is a sequence of Boolean algebras $O_n$ of subsets of $\mathbb{R}$ which satisfies the following ...
3
votes
2answers
129 views

A ⊆ B ∪ C -> x ∈ B or x ∈ C.

This is one of the problem I have been working from Velleman's How to Prove it book: Theorem: Suppose A, B, and C are sets and A ⊆ B ∪ C. Then either A ⊆ B or ...
1
vote
1answer
58 views

Proof in sequent calculus without cut

I met an exercise in Gaisi Takeuti, Proof Theory [Exercise 2.7, page 14]. How to construct a cut-free proof of$\ \forall xA(x)\rightarrow B\vdash \exists x(A(x)\rightarrow B)$, where A(a) and B are ...
3
votes
1answer
28 views

How to prove that predicate is expressible?

I have to prove, that predicate "x is transposition" in $S_5$ group. I can use such symbols, as *, 1, -1, =. However, I don't know any algorithm or way, which can ...
3
votes
2answers
42 views

Translate sentences in first-order logic

I need to translate the following sentence: "All mothers love their daughters". I thought: $\forall X \forall Y (mother(X) \wedge daughter(Y, X)) \Rightarrow love(X, Y)$ but on my book I found this ...
1
vote
1answer
92 views

Is this a correct solution to determining which of two people is the liar using one question?

I am a newbie to Stack-Exchange and if there is any problem in my question -- I apologize beforehand . I was working my way through some Propositional Logic Questions in Discrete Maths by Rosen , ...
4
votes
2answers
74 views

Logic - Prove the following

Here's the Problem: Which one of these is true? A) All of the below B) None of the below C) Some of the above D )None of the above E )None of the above My attempt: Suppose ...
1
vote
1answer
98 views

2 Questions regarding Relative Consistency Proofs

First Question: Let IC be the statement "There is an inaccessible cardinal." I have read that one cannot prove (in ZFC) the relative consistency of ZFC + IC w.r.t. ZFC. i.e. $ Con(ZFC) \rightarrow ...
3
votes
2answers
51 views

Establishing the validity of an argument.

I've been trying to determine the validity of a particular argument for some time now and I've had no luck in figuring it out. The argument in question goes as follows: \begin{align} & p \wedge q ...
4
votes
2answers
47 views

Proving or disproving $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$

Prove/disprove: $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$ I know the LHS isn't like in the definition of ordered sets so it's probably false but I can't find any numbers as counter example, nor ...
1
vote
2answers
33 views

proof for propositional logic

I am unable to prove the following proposition logic. $(p \lor \neg r) \land (r \lor \neg p) \leftrightarrow (p \leftrightarrow q) \land (q \leftrightarrow r)$ My solution is given in the image. ...
1
vote
1answer
86 views

Existence of nonstandard elementary extensions of $PA$?

My question follows from the 1958 result of MacDowell–Specker (located originally in Modelle der Arithmetik, J. Symbolic Logic Volume 38, Issue 4 (1973), 651-652) of the proof of the following ...
1
vote
2answers
37 views

Can we ignore predicates in a statement if they aren't used?

Prove/disprove: $$\forall a>0:a\in\mathbb R: \exists N\in\mathbb R:\forall x\in \mathbb R:\exists z\in\mathbb R:\forall n\in \mathbb N:|n-99|<N\Rightarrow n>10 \vee \frac {n^2} 4 \le 25$$ ...
3
votes
0answers
77 views

Is this a valid proof for $1+1=2$? [duplicate]

I am extremely new to proofs, and quite bad at them. In studying and practicing the different types of proofs, I developed this very rough proof that $1+1=2$, one of the simplest mathematical truths I ...
1
vote
2answers
84 views

Clarification regarding Drinker's paradox [duplicate]

This is the informal proof of Drinker's paradox The proof begins by recognising it is true that either everyone in the pub is drinking (in this particular round of drinks), or at least one ...
2
votes
2answers
77 views

Infinite sets having no RE subsets

I'm back trying to learn recursion theory on my own. I'd like to prove the following result: There exists an infinite set having no infinite R.E. subset. Constructive comments are appreciated. Proof: ...
1
vote
1answer
36 views

How to simplify Boolean expression: $(C'B')+(CB)$

I'm very weak in math and logic, and currently tried doing K-map, and got this as result: $$(C'B')+(CB)$$ My question is, can this be further simplified? I tried it myself, but I got $0$ (False). ...
4
votes
0answers
88 views

Is there a logic to formalize the concept of “understanding”

The question may seem little bit weird given that philosophers have been struggling to have a full grasp on the concept of "understanding". But I'm wondering if there are any logics (modal-based or ...
2
votes
2answers
56 views

All Vatican anarchists are honest and dishonest at the same time if there is no anarchists in Vatican! How to resolve this contradiction? [duplicate]

Lets suppose we want to investigate proposition "All Vatican anarchists are honest". We can transform this proposition into implication "If a citizen of Vatican is an anarchist then he/she is honest". ...
1
vote
2answers
44 views

when does $a\in\mathbb{R}$ does $\neg(a\leq 15\implies a>1)$ hold? [duplicate]

How can I formally write down for which $a\in\mathbb{R}$ the statement $\neg(a\leq 15\implies a>1)$ holds?
1
vote
4answers
88 views

Help with proposition whether it's true or false [closed]

Is this proposition true or false? $$\exists y \in \mathbb R \;\forall x \in \mathbb R\,(xy\neq x \rightarrow x=0) $$ And why? I'm confused as to what exactly is being claimed.