Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [elementary-set-theory]

This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, differences and complements, De Morgan's laws, Venn diagrams, relations, etc. More advanced topics should use (set-theory) instead.

0
votes
0answers
32 views

Cardinality of uncomputable functions

Let's denote the set of all computable functions from $\mathbb{N} \to \mathbb{N}$ as $F$. Now, by any Gödel numbering, $F \simeq \mathbb{N}$. However, $\mathbb{N}^\mathbb{N} \simeq \mathbb{R}$. It'...
0
votes
1answer
18 views

Directed set and partially/totally ordered sets.

I am barely new to order theory and this motivates if the question is trivial. I understood the definitions of preorder, partially and totally ordered sets and well ordered sets. In particular there ...
2
votes
2answers
28 views

Prove that if $n \in \omega$ then $n \notin n$

Prove that if $n \in \omega$ then $n \notin n$. I'm trying to do it by induction. Consider $S=\{n \in \omega : n \notin n\}$ $0 \in S$: $\emptyset \notin\emptyset $ $i\in S \Rightarrow s(i) \in S$: ...
0
votes
1answer
37 views

Counterexample: linearly ordered sets for which there exists more than one isomorphism

In my axiomatic set theory notes, there appears that, if $A$ and $B$ are well-ordered isomorphic sets, then there exists one isomorphism between them. However, as a side note, it is stated that this ...
-2
votes
0answers
21 views

Set theory finding bijection [on hold]

Associate with each subset X of a set S, another subset f(X) of S in such a way that if X contains Y then f(X) contains f(Y) define C={X subset of S :X subset of f(X)} Let A be the union of all member ...
4
votes
3answers
85 views

Function $F$ is surjective if and only if $F$ is $1-1$ [duplicate]

While I was working on proofs of functions, the following claim occurred to me that I think it is correct but I could not prove it. Please note that the claim may not be correct since it is just my ...
0
votes
3answers
33 views

Types of relations , besides equivalence relation and ordering relation?

In order to define types of relations, mathematicians combine abstract properties such as reflexivity, transitivity, etc. For example ( after Partee, Mathematical methods in linguistics) : ...
0
votes
1answer
36 views

What is the meaning of the character “$\,\mathscr{C}\,$”? [on hold]

The character in the circle with question mark. Is it mean Lebesgue? Thx for reply! :)
2
votes
2answers
73 views

Power sets : Do the relations between P(A) and P(B) always mirror the relations between the sets A and B?

If I am correct it is true that: (1) "P(A) is included in P(B)" implies "A is included in B". (2) "P(A) = P(B)" implies "A=B". Might I conclude from this that the power sets of two sets always ...
1
vote
2answers
30 views

Countability of a denumerable union of countable sets

I am trying to prove the following denumerable$$\bigcup_ {n \in \Bbb N} \left\{\frac{n}{2^k} : k \in \Bbb N\right\}$$ I am supposed to use theorems from my book to prove this denumerable. There is a ...
0
votes
0answers
24 views

Basic Proposition of Cardinals

Definition. A cardinal is an ordinal which it is not in bijection with any smaller ordinal. Notation. $|X|$ means that cardinal of $X$. Proposition 1. Let $w$ be an ordinal. Then $|w+1|=w.$ ...
0
votes
1answer
58 views

What kind of numbers are inside a generating open interval of the Borel $\sigma$-algebra? [on hold]

If it is enough to have all open intervals (a,b) with end points $a$ and $b$ belonging to the rational numbers, a < b, in order to generate a Borel $\sigma$-algebra on $\mathbb{R}$. Asked here: ...
-1
votes
2answers
30 views

Set theory and Venn diagram

In a group of 70 cars tested by a garage in Delhi, 15 had faulty tyres, 20 had faulty brakes and 18 exceed the allowable emission limits. Also, 5 cars had faulty tyres and breaks, 6 failed on tyres ...
0
votes
1answer
30 views

Algebra of Sets: Proof of absorption laws without using DeMorgan's laws?

I'm trying to prove set algebras's absoption laws without using DeMorgan's laws. Absoption laws : $A \cup (A \cap B) = A$ $A \cap (A \cup B) = A$ Is this possible? I would like to prove these ...
1
vote
1answer
45 views

Demonstration by induction without using the induction hypothesis

my definition of sum: $\sigma_n(0)=n$ $ \sigma_n(s(m)) = s(\sigma_n(m))$ in which $\sigma_n$ is obtained from the recursion theorem. I want to show directly from the axioms of peano that if $n,m \...
1
vote
1answer
9 views

Question on Partially ordered sets and images of sets

Could someone look through my attempt at proving the following problem please? Let $(A,\preceq)$ and $(B,\preceq')$ be POSETS and $C \subseteq A$. Suppose that $h:A \rightarrow B$ satisifies $x \...
0
votes
2answers
40 views

What are mathematically definable/ useful properties of ternary relations? ( How to define for example symmetry or transitivity?)

My question may seem gratuitous. Here are my presuppositions. What makes a relation mathematically interesting is that one can define abstract properties of this relation , such as reflexivity, ...
0
votes
1answer
16 views

Test if a function given as a non-integrable ode set is Bijective

Given that state space trajectories of an autonomous system do not cross, can I deduce that a mapping function f:(x,y)→(x',y') given by a solution of an ODE of an autonomous system is bijective? ...
2
votes
2answers
30 views

Question regarding partially ordered sets and the subset relation

Could someone look through my attempt at proving the following problem please? Let $(A, \preceq)$ be a POSET.For each $x,y \in A$,let $P_x=\{a \in A: a \preceq x\}$. Let $F$ be the family of sets ...
0
votes
1answer
32 views

Power Set of an Interval

I am working through a set of problems, and I have found one that has me stumped. The question is asking for the power set of {x: x ∈ N, -10 < x < 10}. What has me confused is what I should ...
0
votes
1answer
17 views

Question about Partially Ordered Sets and functions

Could someone verify my attempt at the following problem? Let $(A,\preceq)$ and $(B, \preceq ')$ be Partially ordered sets and suppose that $h:A \rightarrow B$ satisfies $x \preceq y \iff h(x) \...
0
votes
2answers
44 views

Prove that $f$ is a surjection

Let $f$:$\Bbb R^+ \times \Bbb R^+ \rightarrow \Bbb R^+ \times \Bbb R^+$ be defined by $f(x,y) = (\frac yx, xy)$. Prove that $f$ is a surjection.
1
vote
2answers
46 views

Correspondence between a countably infinite set A and the set of positive integers

I'm currently taking a course on logic & computability and they're using as a manual the famous "Logic and computability" by Boolos, Burgess and Jeffrey. The last week I've been trying to solve ...
0
votes
1answer
30 views

The cardinality of some sets [duplicate]

I want to prove that $P((0,1)-\mathbb{ Q}) = 2^{\mathbb{R}}$, i have a proof which is roughly that $((0,1)-\mathbb{Q}) \cup \mathbb{Q} = (0,1)$ and there intersection is empty so assuming the AC we ...
1
vote
2answers
28 views

Trying to prove one set in terms of another using identity laws

Prove: $A\ - (A\cap \ B ) = A - B$ My work thus far $$ \begin{aligned} &\quad A\ - (A\cap \ B) \\ &= (A-A)\ \cap\ (A-B) \text{(using the distributive law)} \\ &= A-B\ \text{(since A-A is ...
0
votes
1answer
48 views

Does $x \notin A \backslash B $ mean $x \notin A \wedge x \in B$?

Does $x \notin A \backslash B $ mean $x \notin A \wedge x \in B$? I am trying to prove a statement where I need to use $x \notin A \backslash B$. But it does not help me, so I am assuming I am using ...
-3
votes
1answer
17 views

Direct and contrapositive proofs on set theory [on hold]

How do I prove the following: Let $A,B$ and $C$ be sets. If $A \cap (B \backslash C) = \emptyset$, and $A \ne \emptyset$, then $B \subset C$.
1
vote
2answers
45 views

Are the definitions of addition of natural numbers as cardinals ($|A| + |B| =|A \cup B|$) and by recursion ($a+S(b) = S(a+b)$) related?

In Peterson, Theory of Arithmetic ( available at Archive.org) addition of whole numbers is defined in the following way. If $A$ and $B$ are disjoint sets, and if $a$ is the cardinal number of $A$ ...
0
votes
1answer
55 views

Can we represent $\mathbb{R}$ to $\mathbb{C}$, such that: $\forall c \in \mathbb{C}: \exists x \in \mathbb{R}: f(x)=c$? [duplicate]

I am wondering why the complex plane is not defined to be of higher cardinality than the reals. Since there should not be a function: $$f: \mathbb{R} \rightarrow \mathbb{C}$$ such that, $$\forall c \...
0
votes
1answer
40 views

Identification of a Subset to a Point

If $A$ is a subspace of a topological space $S$, we can define a relation $∼$ on S by declaring $$x ∼ x\quad\text{for all}\quad x\in S$$ (so the relation is reflexive) and $$x ∼ y\quad\text{for all}\...
0
votes
3answers
57 views

Is every element in a power set a sub set?

I have understood so far that an element cannot be a sub set of itself. If A = {1,2,{3}} and {3} is not a sub set of A. But in my textbook it has been given that every element in a power set is a ...
-1
votes
1answer
38 views

Set Theory, Infinite chain of subsets [on hold]

Given an infinite chain of subsets $S_1\subseteq S_2 \subseteq S_3...$. Consider a subset $N\subset\bigcup\limits_{i=1}^{\infty} S_{i}$, can we say that $N\subseteq S_i$ for some $i$. If so, how do we ...
2
votes
4answers
467 views

Determine whether f is a function, an injection, a surjection

Let $P=\{p(x)$ | $p(x)$ is a polynomial of degree $n$, $n \in \Bbb Z^+\cup\{0\} $ with coefficients in $\Bbb R \}$. Define $f : P\rightarrow P$ where $f(p(x)) =p'(x)$, the derivative of $p(x)$. ...
2
votes
1answer
31 views

Exercise 4.8 from Hrbacek's “Introduction to set theory”

4.8 Let $(A,<)$ be linearly ordered. Define $\prec$ on $\text{Seq}(A)$ by: $\big\langle a_0,...,a_{m-1}\big\rangle \prec \big\langle b_0,...,b_{n-1} \big\rangle$ if and only if there is $k<n$ ...
0
votes
6answers
45 views

How restrictive is the “for all” quantifier in the definition of reflexivity, symmetry, and transitivity?

Only recently, my math teacher introduced me to the topic reflexivity, symmetry, and transitivity of binary relations, but there are some holes in my understanding that I am desperate to clarify. Each ...
1
vote
1answer
61 views

Surjection from a powerset onto $\Bbb{N}$ is always possible

I found this answer that I can't quite understand: https://math.stackexchange.com/a/1296795/431135 It says that, for any infinite set $A$, there is always a surjection from $\cal{P}$$(A)$ onto $\Bbb{...
0
votes
1answer
31 views

Is a set of values of an exponential function uncountable?

E.G. $f(x) = 2^x$ If yes, is there an easy, informal proof that a layman could understand?
1
vote
0answers
24 views

Is there any uncountable subset of Real numbers whose intersection with its limit points is empty set. [duplicate]

Is there any uncountable subset of Real numbers whose intersection with its limit points is empty set.
0
votes
2answers
51 views

Why $\mathbb Q$ has not the supremum property?

Why $\mathbb Q$ has not the supremum property ? i.e. why an upper bounded doesn't necessarily have a supremum ? As a hint, I have to consider $A=\{x\in\mathbb Q\mid x^2\leq 2\}$. I tried by ...
1
vote
4answers
100 views

Uniqueness proof : $a = a'$ so $a$ is unique. Is the proof absolutely rigorous?

My question deals with uniqueness proofs. For example the proof of the uniqueness of the empty set, or the proof of the uniqueness of the identity element in a group. These proofs are convincing of ...
0
votes
2answers
32 views

How to prove “ If (A is included in B) then (A Intersection Complement of B is equal to the null set) ” using only set algebra laws?

This statement is quite easy to prove using logic ( and the constant F = " Falsum" = the proposition equivalent to any logical falsehood). But I cannot manage to prove it simply with the laws of the ...
0
votes
1answer
32 views

Proof of function property in group theory

The question states: Consider a function $f: S\rightarrow S$. Let $f(A) = \{f(x)|x \in A\}$ and $f(B) = \{f(x)|x \in B\}$. Prove that if $A \subseteq B \subseteq S$ then $f(A) \subseteq f(B)$. The ...
1
vote
1answer
41 views

Discrete mathematics: chances of getting specific card on card-game

The game is played with a deck of $40$ cards. Three of them are dealt to each of two players, so my hand, the cards that were given to me, is formed by three cards of the deck. At the same time, ...
7
votes
4answers
706 views

If the empty set is a subset of every set, why write … $\cup \{∅\}$?

I met the notation $ S=\{(a,b] ; a,b\in \mathbb R,a<b\}\cup\{\emptyset\} $ I know $S$ is a family of subsets ,a set of intervals, and from set theory $\emptyset$ is a subsets of every set then why ...
0
votes
1answer
24 views

Another way of show number of exclusive elements in a set

Sorry for any confusing. This is the first time I asked on this site, if there is any term that's wrongly used, please let me know So given a diagram of A and B, to show exclusively A and exlusively ...
1
vote
2answers
61 views

is a null set the same as {}

Ø vs set {}: Ø has no elements whereas {} has the null set as an element; that is, say you are making power set of {}: Ø would be an element of the power set or in symbols, P({}): {Ø} right? I feel ...
0
votes
1answer
24 views

What is the relationship between a requirement for consistency of a theory and what it can prove?

This is a question that I always had in mind. When it is said that the consistency of a theory $T$ requires the assumption of existence of some specified cardinal $\kappa$. Is that taken to mean ...
0
votes
0answers
18 views

Argmax as a list

I have a dataset X containing a column which I already computed using f(X). Now, I would like to get the maximum 30% of dataset X depending on the f(X) using argmax. Any help please? Regards, Soft.
0
votes
1answer
43 views

A simple question on surjective map

Let $f\colon X\to Y$ a surjective map, where $X$ and $Y$ are two no empty set. Let $A\subseteq X$ be a subset no empty. Know that $g:=f_{|A}\colon A\to Y$ is also surjective. Since $f$ is surjective ...
-1
votes
3answers
41 views

How to show that the relation $xRy$ if $\sin(x-y)=0$ is transitive? [on hold]

"Logically" it seems transitive as if $x-y=k(𝜋)$ and $y-z=k(\pi)$ then $x-z=k'(\pi)$ but how to put it into a good proof? also what would we be its equivalence classes since if it is transitive then ...