Stack Exchange Network

Stack Exchange network consists of 174 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, ...

2
votes
0answers
6 views

Proving Equivalence Relations, Constructing and Defining Operations on Equivalence Classes

I think I have an intuitive sense of how ordered pairs can function to specify equivalence classes when used in the construction of integers and rationals, for example. I put the cart before the horse,...
0
votes
0answers
6 views

Show or disprove $f[\cap\chi]=\cap\{f[X]:X\in\chi\}\forall\chi\subseteq\mathcal{P}(A)$ with $\chi\neq\emptyset$

I don't know how to start because I don't know what the cornered brackets mean ín settheory. Would be nice if somebody could give me a hint how to approach this excercise.
0
votes
1answer
23 views

Distinct Uncountable Dense Subsets of R

I'm working on Question #5.v in chapter 3.1 of Sidney Morris's Toplogy without Tears. I'm supposed to prove that $\mathbb{R}$ has $2^{\mathfrak{c}}$ distinct uncountable dense subsets. I think my ...
0
votes
1answer
14 views

Set notation for a solution to a simple equation

Solve this equation below and express answer using set notation. $$|x+3|=9$$ My question really isn't about solving this inequality, it is more about the second part of the question, using set ...
0
votes
1answer
15 views

Reformulation of intersection of two unions

I want to prove a relation: $\left(\cup_{i \in I}A_i\right) \cap \left(\cup_{j \in J}B_j \right)= \cup_{i \in I, j\in J}\left(A_i \cap B_j\right)$. Would someone check if the following my attempt is ...
0
votes
1answer
35 views

Is this function $f$ defined uniquely?

Consider function $f: \mathbb{N}\times\mathbb{N} \to \mathbb{N}\times\mathbb{N}$. ($0 \in \mathbb{N}$.) We know that: $f$ is bijective $f((0,1)) = (1,0)$ $\forall x \forall y: x \leq y \implies f(x) \...
1
vote
2answers
26 views

Size of largest subset $F$ of $\mathcal{p}(X)$ such that any two subsets in $F$ intersect no trivially. [on hold]

Help with the following Putnam problem: let $S$ be a finite set, and suppose that a collection $\mathcal{F}$ of subsets of $S$ has the property that any two members of $\mathcal{F}$ have at least one ...
0
votes
1answer
22 views

How to prove by induction that n = m, |X| = n, |Y| = m [on hold]

We have two finite sets X and Y, where |X| = n, |Y| = m, n,m ∈ ℕ. I should show that n = m by induction. For that I should assume that f: X->Y is bijective. In this case it is clear that the ...
0
votes
1answer
32 views

A is a subset of B if and only if (C - B) is a subset of (C - A) (condition: for non-empty set C) [on hold]

How can I prove this phrase by starting from the left side? (start from A is a subset of B)
0
votes
1answer
33 views

Largest separated subset of a finite set

I can see the idea behind the following proof but I cannot express it in a mathematically elegant way...any help? Thanks in advance! Let X = {1, 2, 3, . . . , 2k}. Prove that the largest separated ...
0
votes
1answer
38 views

Proving - set theory

Is x∈ ((A\C) ∩ B) ∪ ((A\B) ∩ C) same as x∈ (AΔC)\B ? I need to prove that $(A\backslash (B \cup C))\cup (C\backslash (A\cup B))$ $=$ $(A\Delta C)\backslash B $ and using 'Let x∈... ...' method I get ...
-3
votes
0answers
39 views

Are all the constant sequences countable. [on hold]

Also another query is if all the real sequences are countable?
0
votes
0answers
30 views

Existence of empty set

Empty set does not follow the definition of set, then why it is called a set,it does not contain well-defined collection of objects.
1
vote
2answers
42 views

Proof and problem solving - set theory

Prove that $(A\Delta C)\backslash B = (A\backslash (B \cup C))\cup (C\backslash (A\cup B))$. I tried with an $x$ that can be in $(A\Delta C)\backslash B$, so $x$ is in $A \Delta C$ but not in $B$. If ...
1
vote
1answer
29 views

Notation for countable union

I sometimes see the following notation for a countable union of sets: $\bigcup_{n\in\omega}E_n$ Is this notation strictly synonymous with the more standard $\bigcup_{n\in\mathbb{N}}E_n$?
-1
votes
3answers
21 views

Prove $A\ \triangle\ B = A^\prime\ \triangle\ B^\prime$, where $\triangle$ is the symmetric difference, and $X^\prime$ is the complement of $X$

Help prove that the symmetric difference of the sets is equal to the symmetric difference of the complements of these sets. That is, that $$A\ \triangle\ B = A^\prime\ \triangle\ B^\prime$$ Thank you ...
2
votes
1answer
32 views

Disjoint Events iff $P(A \cap B) = 0$

I found for example here that: $A$ and $B$ are disjoint iff $P(A\cap B) == 0$. I don't understand why. Take for example: $A = \{$"rolling a six-sided dice a 7 shows up"$\}$ $B = \{"$rolling a six-...
4
votes
4answers
60 views

Why is $\{-1,1\}^{\mathbb{Z}^2}$ not countable?

People at my class acted like it was obvious, but I am not that sure: Why is this set not countable? $$\{-1,1\}^{\mathbb{Z}^2}$$ So, this set contains all the functions from $$\mathbb{Z}^2\to\{-1,...
5
votes
1answer
56 views

How many $S\subseteq\mathcal{P}(A)$ contain each element of $A$ an even number of times?

Let $A=\{1,2,...,n\}$. Let the powerset of $A$ be $\mathcal{P}(A)$. We call $S\subseteq \mathcal{P}(A)$ a paired family of subsets if $\forall a\in A$, the number of elements of $S$ that contain $a$ ...
0
votes
1answer
12 views

Set Inverse Based on Mapping [on hold]

If I have a set R where R: A <-> B (i.e R is a set that relates the type A to the type B) and I have a set ...
-2
votes
0answers
57 views

I have question on my math homework for set [on hold]

How many pairs of subsets $A, B \subseteq [n]$ are there such that $A \cap B \not=\emptyset$.
0
votes
1answer
42 views

Intersection of infinite number of sets

Assume I have infinite number of sets such as $\left[1,\infty\right),\left[2,\infty\right),\left[3,\infty\right),...$.Any number in such set is natural. What is intersection of them: $S = \left[1,\...
2
votes
2answers
55 views

Why is $\bigcap_{x\in\mathbb{R}}\mathbb{N}=\mathbb{N}$?

$\bigcap_{x\in\mathbb{R}}\mathbb{N}=\mathbb{N}$ The generaldefinition of Intersection/Union is, that you have a indexset and an Array of sets $(A_i)$ that can be directly assigned to the index: Let $...
2
votes
1answer
68 views

Comparing enumerations on the same infinite set

Given two enumerations $A:S \to \mathbb{N}$, $B:S \to \mathbb{N}$ on the same countably infinite set $S$, are there infinitely many elements $s \in S$ with $A(s) \geq B(s)$? My feeling is that there ...
0
votes
0answers
28 views

C.Pinter A book of set theory, EX 3.3.11

Let G and H be equivalence relations in A. Prove that each equivalence class modulo G ∩ H is the intersection of an equivalence class modulo G with an equivalence class modulo H. More exactly, $$(G\...
0
votes
3answers
45 views

Proving Set Equality $A=B$

I have the following question: $$\text{Suppose $A,B,C$ are sets so that $A \cap C = B \cap C $ and $A \cup C=B \cup C$. Prove that $A=B$.}$$ My question is that the way I am doing it seems rather ...
0
votes
1answer
72 views

What is the point of defining relations in terms of other relations in mathematics?

I was reading the following set of notes on logic (page 84 of paper pdf) and came a across a rather simple definition but was unsure what it meant conceptually: I think I understand the proof (it ...
0
votes
2answers
32 views

Bijection between two infinite sets [duplicate]

I am trying to get right answer to question: Can you make bijection between set ℝ\{-3} and set ℝ? I know those two sets are not same size but I think I can still make bijection, but I need ...
1
vote
0answers
24 views

Showing that the class of finite subsets of a well-ordered class can be well-ordered

We know that if $(X, <)$ is a well-ordered class, then $\mathcal{P}(X)$ can be totally ordered by the following: $$A<^*B\ \text{iff min}(A\Delta B) \in A $$ where $\Delta$ is the symmetric ...
1
vote
1answer
41 views

Without the Axiom of Choice, is there a bijection between $\mathcal{P}(\aleph_\alpha)$ and $\mathcal{P}(\aleph_\alpha \times \aleph_\alpha)$?

My question is about finding a bijection between $\mathcal{P}(\aleph_\alpha)$ and $\mathcal{P}(\aleph_\alpha \times \aleph_\alpha)$ without the axiom of choice. This is an unproved statement in an ...
-3
votes
2answers
39 views

Define the relation $\sim$ on $A \times A$ by $(a, b) \sim (c, d) \iff abcd ≥ 0$. Show that $\sim$ is an equivalence relation.

Let $A = \mathbb Z \setminus \{0\}$ be the set of nonzero integers. Define the relation $\sim$ on $A \times A$ by $$(a, b) \sim (c, d) \iff abcd ≥ 0.$$ Show that $\sim$ is an equivalence relation. I ...
1
vote
1answer
23 views

Strange Notation for Collection of Sets

My professor used this notation for a collection of sets: $\{A_{\lambda} \}_{\lambda}$. What's the purpose of this extra subscript on the right curly bracket? I usually just go with $\{A_\lambda\}$ ...
1
vote
2answers
76 views

How shall I understand what the GNU utilities “comm” and “diff” do in terms of ordered sets?

I am looking for some help to understand two GNU utility programs in terms of ordered sets. If you happen to know their usages, you might be able to understand what I am asking here. In mathematics, ...
-2
votes
0answers
31 views

Brute Force AES and/ RSA with mathematical explanation, input from math guru?

Does a cryptography expert knowledgable with math have a explanation on: The amount of time it takes to brute force AES-$N$ bit with a password with combinations $A^N$, where $A$ is the number of ...
-2
votes
1answer
24 views

Proof that $((A\setminus B)\setminus (B\setminus C))^{c} = A^{c} \cup B$ [on hold]

I'm lost in this question, how can I deal with multiple complements and differences?
0
votes
4answers
51 views

Bijective map between two finite sets is equivalent to the same cardinality

Let $X$ and $Y$ be two finite sets with cardinalities $|X| = n, |Y | = m$ respectively, where$ n,m \in \mathbb{N}$. Further assume $f : X \to Y$ to be bijective. Show that $n = m$. Hint: ...
1
vote
0answers
27 views

Applying Dilworth's theorem to 50 intervals in R

Problem : Prove that among any 50 intervals R, one can either find 8 disjoint intervals or 8 intervals having a common point. I think it is quite obvious I need to apply Dilworth's theorem to my ...
1
vote
0answers
56 views

$\text {dom}(R)$ and $\text {ran}(R)$ exists for any definition of order pair.

Suppose that we define, for any sets $x,y$, a set $(x,y)$ with the propertie that $$(x,y)=(x',y')\rightarrow x=x'\wedge y=y'(*)$$ Let $R$ be a set. I want to show that the classes $\{x:\exists y((x,y)...
0
votes
0answers
32 views

Can I bound universal set [closed]

Let Universe U={ A1,A2,A3, ... An} be a set of Facebook groups(i.e. A1, A2.... are representing a group), and E={e1,e2,e3} be a set of information. according to a "soft set theory," I am going to make ...
0
votes
1answer
48 views

Sheave of sets, what does $\{f_i \} \mapsto \{f_i \mid_{U_i \cap U_j}\}$ mean?

... for an open covering $U = \bigcup U_i$, an $I$-indexed family of functions $f_i : U_i \to \Bbb{R}, \ i \in I$, is an element of the product set $\prod_i CU_i$, while the assignments $\{f_i\} \...
-3
votes
1answer
33 views

When any function is applied to the output of any even function, is it odd or even? Explain [duplicate]

I only need a couple of sentences to explain, but I don't know how to word it, please help! I do not need an algebraic proof, just a sentence or two to explain why the output is always even.
2
votes
2answers
52 views

How do we formally define “j-th smallest element”?

Let $A$ be a nonempty finite subset of $\mathbb{R}$. Firstly, let me write down how to define the term "the smallest element of $A$" formally. Suppose 'for every $x\in A$, there exists $y \in A$ ...
-1
votes
0answers
39 views

A coherent general definition of an $n$-ary relation?

I know most people define a finitary relation as a subset of a Cartesian product of a finite number of sets: $$R\subseteq S_1\times S_2\times\cdots\times S_n$$ I used to do this too but I have ...
-1
votes
5answers
41 views

What does this set mean: $ \{ g \mid g : \{0,1\} \rightarrow \mathbb{N} \} $

I have an excercise and there is the set $ \{ g\mid g : \{0,1\} \rightarrow \mathbb{N} \} $. Now I wanted to know, that this set mean? What's the content of it? I know normal sets very well but in my ...
3
votes
2answers
239 views

If the objects of a category form a proper class, do the arrows necessarily form a proper class too?

In some categories, like $\text{Set}$ or $\text{Group}$, the objects are "constructed" out of sets (or are sets, possibly with additional structure). In order to avoid paradoxes, the collection of ...
0
votes
1answer
34 views

Draw a venn diagram showing an event along with its sufficient and necessary conditions

Consider some event $S$ along with: $S_n$ (Necessary events for $S$) $S_s$ (Sufficient events for $S$) $S_{ns}$ (Necessary and sufficient events for $S$) Draw a Venn diagram indicating the above. ...
1
vote
1answer
38 views

Is this proof of the Cantor–Bernstein theorem I wrote valid? Or did I make a mistake somewhere?

Given any two disjoint sets $A$ and $B$ note if there exists two injections $f:A\to B$ and $g:B\to A$ then we can construct another injection $h:A\cup B\to A\cup B$ as follows: $$h(x)=\begin{cases}f(...
-2
votes
0answers
26 views

Can binary relation on a set of 6 elements which contains 33 pairs be transitive? [closed]

There is a binary relation on a set of 6 elements which contains 33 pairs. Which properties does it have? Symmetric. But can it be transitive?
0
votes
1answer
27 views

Given any two sets $A$ and $B$ is it true that $A\cap B\times \{A\}=\emptyset$?

Given any two sets $A$ and $B$ is it true that $A\cap B\times \{A\}=\emptyset$? I feel like it should be.
4
votes
2answers
47 views

Why the function $f: \emptyset \rightarrow \emptyset$ exist? $0^0 = 1$

If $f: \emptyset \rightarrow \emptyset$, that is: $\forall a \in \emptyset \Rightarrow \exists b\in \emptyset, (a,b)\in \emptyset \times \emptyset$. But how we can say, that for non-existing element ...